3 mkavltree, insertavl, lookupavl, deleteavl, avlwalk, avlnext, avlprev, endwalk - AVL tree routines
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
12 typedef struct Avl Avl;
16 Avl *n[2]; /* children */
17 int bal; /* balance bits */
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*));
31 An AVL tree is a self-balancing binary search tree.
32 These routines allow creation and maintenance of in-memory AVL trees.
34 An empty AVL tree is created by calling
36 with a comparison function as argument.
37 This function should take two pointers to
39 objects and return -1, 0 or 1 as the first is
40 respectively less than,
41 equal to, or greater than,
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.
72 comparison function, if it exists.
75 is positive, it returns the nearest node whose
79 if there is none and, if
81 is negative, it returns the nearest node whose
88 to values other than \-1, 0, or +1.
91 removes the node matching
100 returns a pointer to a newly-allocated
104 frees such an object.
108 walk the tree associated with
111 (respectively, previous)
112 tree node in the comparison order
113 defined by the comparison function
114 associated with the tree associated with
117 Intended usage seems to be to make an anonymous
119 the first member of the application's tree-node structure,
120 then pass these routines tree-node pointers instead of
124 typedef struct Node {
126 uchar score[VtScoreSize];
134 res = lookupavl(tree, np);
139 G. M. Adelson-Velsky,
141 ``An algorithm for the organization of information'',
142 .IR "Soviet Mathematics" ,
143 Vol. 3, pp. 1256—1263.
145 Functions returning pointers return