1
0

avl 2.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147
  1. .TH AVL 2
  2. .SH NAME
  3. mkavltree, insertavl, lookupavl, deleteavl, avlwalk, avlnext, avlprev, endwalk - AVL tree routines
  4. .SH SYNOPSIS
  5. .\" .ta 0.75i 1.5i 2.25i 3i 3.75i 4.5i
  6. .ta 0.7i +0.7i +0.7i +0.7i +0.7i +0.7i +0.7i
  7. .EX
  8. #include <u.h>
  9. #include <libc.h>
  10. #include <avl.h>
  11. .sp 0.3v
  12. typedef struct Avl Avl;
  13. struct Avl
  14. {
  15. Avl *p; /* parent */
  16. Avl *n[2]; /* children */
  17. int bal; /* balance bits */
  18. };
  19. .sp 0.3v
  20. Avl *avlnext(Avlwalk *walk);
  21. Avl *avlprev(Avlwalk *walk);
  22. Avlwalk *avlwalk(Avltree *tree);
  23. void deleteavl(Avltree *tree, Avl *key, Avl **oldp);
  24. void endwalk(Avlwalk *walk);
  25. void insertavl(Avltree *tree, Avl *new, Avl **oldp);
  26. Avl *lookupavl(Avltree *tree, Avl *key);
  27. Avl *searchavl(Avltree *tree, Avl *key, int neighbor);
  28. Avltree *mkavltree(int(*cmp)(Avl*, Avl*));
  29. .EE
  30. .SH DESCRIPTION
  31. An AVL tree is a self-balancing binary search tree.
  32. These routines allow creation and maintenance of in-memory AVL trees.
  33. .PP
  34. An empty AVL tree is created by calling
  35. .I mkavltree
  36. with a comparison function as argument.
  37. This function should take two pointers to
  38. .B Avl
  39. objects and return -1, 0 or 1 as the first is
  40. respectively less than,
  41. equal to, or greater than,
  42. the second.
  43. .I Insertavl
  44. adds a
  45. .I new
  46. tree node into
  47. .IR tree .
  48. If
  49. .I oldp
  50. is non-nil upon return,
  51. it points to storage for an old node
  52. with the same key that may now be freed.
  53. .I Lookupavl
  54. returns the
  55. .I tree
  56. node that matches
  57. .I key
  58. by
  59. .IR tree 's
  60. comparison function,
  61. or
  62. .B nil
  63. if none.
  64. .PP
  65. .I Searchavl
  66. returns the
  67. .I tree
  68. node that matches
  69. .I key
  70. by
  71. .IR tree 's
  72. comparison function, if it exists.
  73. If it does not, and
  74. .I neighbor
  75. is positive, it returns the nearest node whose
  76. .I key
  77. is greater or
  78. .B nil
  79. if there is none and, if
  80. .I neighbor
  81. is negative, it returns the nearest node whose
  82. .I key
  83. is less or
  84. .B nil
  85. if there is none.
  86. It is an error to set
  87. .I neighbor
  88. to values other than \-1, 0, or +1.
  89. .PP
  90. .I Deleteavl
  91. removes the node matching
  92. .I key
  93. from
  94. .IR tree ;
  95. .I oldp
  96. is handled as per
  97. .IR insertavl .
  98. .PP
  99. .I Avlwalk
  100. returns a pointer to a newly-allocated
  101. .B Avlwalk
  102. object.
  103. .I Endwalk
  104. frees such an object.
  105. .I Avlnext
  106. and
  107. .I avlprev
  108. walk the tree associated with
  109. .IR walk ,
  110. returning the next
  111. (respectively, previous)
  112. tree node in the comparison order
  113. defined by the comparison function
  114. associated with the tree associated with
  115. .IR walk .
  116. .SH EXAMPLES
  117. Intended usage seems to be to make an anonymous
  118. .B Avl
  119. the first member of the application's tree-node structure,
  120. then pass these routines tree-node pointers instead of
  121. .BR Avl* s.
  122. .IP
  123. .EX
  124. typedef struct Node {
  125. Avl;
  126. uchar score[VtScoreSize];
  127. int type;
  128. } Node;
  129. .sp 0.3v
  130. Avltree *tree;
  131. Avl *res;
  132. Node *np;
  133. \fI\&...\fP
  134. res = lookupavl(tree, np);
  135. .EE
  136. .SH SOURCE
  137. .B /sys/src/libavl
  138. .SH SEE ALSO
  139. G. M. Adelson-Velsky,
  140. E. M. Landis,
  141. ``An algorithm for the organization of information'',
  142. .IR "Soviet Mathematics" ,
  143. Vol. 3, pp. 1256—1263.
  144. .SH DIAGNOSTICS
  145. Functions returning pointers return
  146. .B nil
  147. on error.