avl.cc 5.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245
  1. /* $Id$ */
  2. #include <alloc.h>
  3. /* Implementation of AVL-trees: trees in which the difference in depth
  4. of the left branch and the right branch is at most one.
  5. The difference in depth is indicated by a "balance" flag in each node:
  6. this flag has one of three values:
  7. . indicating that the left branch has the same depth as the right branch,
  8. + indicating that the right branch is deeper,
  9. - indicating that the left branch is deeper.
  10. So, a node has the following structure:
  11. */
  12. struct avl_node {
  13. struct avl_node
  14. *left,
  15. *right; /* the left and right branches */
  16. char *info; /* pointer to information in this node */
  17. char balance; /* balance information described above */
  18. };
  19. /* create definitions for new_avl_node() and free_avl_node() */
  20. /* STATICALLOCDEF "avl_node" 10 */
  21. /* There is also a tree header, which contains the root of the tree and
  22. the address of a user-supplied comparison routine:
  23. */
  24. struct avl_tree {
  25. struct avl_node
  26. *root; /* root of the avl tree */
  27. int (*cmp)(); /* address of comparison routine */
  28. };
  29. /* create definitions for new_avl_tree() and free_avl_tree() */
  30. /* STATICALLOCDEF "avl_tree" 2 */
  31. /* The next routine adds a node to an avl tree. It returns 1 if the
  32. tree got deeper.
  33. */
  34. static int
  35. balance_add(ppsc, n, cmp)
  36. struct avl_node **ppsc; /* address of root */
  37. register char *n; /* user-supplied information */
  38. int (*cmp)(); /* user-supplied comparison routine */
  39. {
  40. register struct avl_node *psc = *ppsc, *qsc, *ssc;
  41. if (! psc) {
  42. *ppsc = new_avl_node();
  43. (*ppsc)->balance = '.';
  44. (*ppsc)->info = n;
  45. return 1;
  46. }
  47. if ((*cmp)(n, psc->info) < 0) {
  48. if (balance_add(&(psc->left), n, cmp)) {
  49. /* left hand side got deeper */
  50. if (psc->balance == '+') {
  51. /* but the right hand side was deeper */
  52. psc->balance = '.';
  53. return 0;
  54. }
  55. if (psc->balance == '.') {
  56. /* but the right hand side was as deep */
  57. psc->balance = '-';
  58. return 1;
  59. }
  60. /* left hand side already was one deeper; re-organize */
  61. qsc = psc->left;
  62. if (qsc->balance == '-') {
  63. /* if left-hand side of left node was deeper,
  64. this node becomes the new root
  65. */
  66. psc->balance = '.';
  67. qsc->balance = '.';
  68. psc->left = qsc->right;
  69. qsc->right = psc;
  70. *ppsc = qsc;
  71. return 0;
  72. }
  73. /* else the right node of the left node becomes the new root */
  74. ssc = qsc->right;
  75. psc->left = ssc->right;
  76. qsc->right = ssc->left;
  77. ssc->left = qsc;
  78. ssc->right = psc;
  79. *ppsc = ssc;
  80. if (ssc->balance == '.') {
  81. psc->balance = '.';
  82. qsc->balance = '.';
  83. return 0;
  84. }
  85. if (ssc->balance == '-') {
  86. psc->balance = '+';
  87. qsc->balance = '.';
  88. ssc->balance = '.';
  89. return 0;
  90. }
  91. psc->balance = '.';
  92. qsc->balance = '-';
  93. }
  94. return 0;
  95. }
  96. if (balance_add(&(psc->right), n, cmp)) {
  97. /* right hand side got deeper */
  98. if (psc->balance == '-') {
  99. /* but the left hand side was deeper */
  100. psc->balance = '.';
  101. return 0;
  102. }
  103. if (psc->balance == '.') {
  104. /* but the left hand side as deep */
  105. psc->balance = '+';
  106. return 1;
  107. }
  108. /* right hand side already was one deeper; re-organize */
  109. qsc = psc->right;
  110. if (qsc->balance == '+') {
  111. /* if right-hand side of left node was deeper,
  112. this node becomes the new root
  113. */
  114. psc->balance = '.';
  115. qsc->balance = '.';
  116. psc->right = qsc->left;
  117. qsc->left = psc;
  118. *ppsc = qsc;
  119. return 0;
  120. }
  121. /* else the left node of the right node becomes the new root */
  122. ssc = qsc->left;
  123. psc->right = ssc->left;
  124. qsc->left = ssc->right;
  125. ssc->right = qsc;
  126. ssc->left = psc;
  127. *ppsc = ssc;
  128. if (ssc->balance == '.') {
  129. psc->balance = '.';
  130. qsc->balance = '.';
  131. return 0;
  132. }
  133. if (ssc->balance == '+') {
  134. psc->balance = '-';
  135. qsc->balance = '.';
  136. ssc->balance = '.';
  137. return 0;
  138. }
  139. psc->balance = '.';
  140. qsc->balance = '+';
  141. }
  142. return 0;
  143. }
  144. /* extern struct avl_tree *create_avl_tree(int (*cmp)());
  145. Returns a fresh avl_tree structure.
  146. */
  147. struct avl_tree *
  148. create_avl_tree(cmp)
  149. int (*cmp)(); /* comparison routine */
  150. {
  151. register struct avl_tree *p = new_avl_tree();
  152. p->cmp = cmp;
  153. return p;
  154. }
  155. /* extern add_to_avl_tree(struct avl_tree *tree, char *n);
  156. Adds the information indicated by 'n' to the avl_tree indicated by 'tree'
  157. */
  158. add_to_avl_tree(tree, n)
  159. struct avl_tree *tree; /* tree to be added to */
  160. char *n; /* information */
  161. {
  162. (void) balance_add(&(tree->root), n, tree->cmp);
  163. }
  164. /* extern char *find_ngt(struct avl_tree *tree, char *n);
  165. Returns the information in the largest node that still compares <= to 'n',
  166. or 0 if not present.
  167. */
  168. char *
  169. find_ngt(tree, n)
  170. struct avl_tree *tree; /* tree to be searched in */
  171. char *n; /* information to be compared with */
  172. {
  173. register struct avl_node *nd = tree->root, *lastnd = 0;
  174. for (;;) {
  175. while (nd && (*tree->cmp)(nd->info, n) > 0) {
  176. nd = nd->left;
  177. }
  178. while (nd && (*tree->cmp)(nd->info, n) <= 0) {
  179. lastnd = nd;
  180. nd = nd->right;
  181. }
  182. if (! nd) break;
  183. }
  184. return lastnd ? lastnd->info : (char *) 0;
  185. }
  186. /* extern char *find_nlt(struct avl_tree *tree, char *n);
  187. Returns the information in the largest node that still compares >= to 'n',
  188. or 0 if not present.
  189. */
  190. char *
  191. find_nlt(tree, n)
  192. struct avl_tree *tree; /* tree to be searched in */
  193. char *n; /* information to be compared with */
  194. {
  195. register struct avl_node *nd = tree->root, *lastnd = 0;
  196. for (;;) {
  197. while (nd && (*tree->cmp)(nd->info, n) < 0) {
  198. nd = nd->right;
  199. }
  200. while (nd && (*tree->cmp)(nd->info, n) >= 0) {
  201. lastnd = nd;
  202. nd = nd->left;
  203. }
  204. if (! nd) break;
  205. }
  206. return lastnd ? lastnd->info : (char *) 0;
  207. }
  208. /* extern char *find_eq(struct avl_tree *tree, char *n);
  209. Returns the information in the node that compares equal to 'n',
  210. or 0 if not present.
  211. */
  212. char *
  213. find_eq(tree, n)
  214. struct avl_tree *tree; /* tree to be searched in */
  215. char *n; /* information to be compared with */
  216. {
  217. register struct avl_node *nd = tree->root;
  218. for (;;) {
  219. while (nd && (*tree->cmp)(nd->info, n) < 0) {
  220. nd = nd->right;
  221. }
  222. while (nd && (*tree->cmp)(nd->info, n) > 0) {
  223. nd = nd->left;
  224. }
  225. if (! nd) break;
  226. }
  227. return nd ? nd->info : (char *) 0;
  228. }