3 375b78fb 2009-08-23 rsc mkavltree, insertavl, lookupavl, deleteavl, avlwalk, avlnext, avlprev, endwalk - AVL tree routines
5 375b78fb 2009-08-23 rsc .\" .ta 0.75i 1.5i 2.25i 3i 3.75i 4.5i
6 375b78fb 2009-08-23 rsc .ta 0.7i +0.7i +0.7i +0.7i +0.7i +0.7i +0.7i
8 375b78fb 2009-08-23 rsc #include <u.h>
9 375b78fb 2009-08-23 rsc #include <libc.h>
10 375b78fb 2009-08-23 rsc #include <avl.h>
12 375b78fb 2009-08-23 rsc typedef struct Avl Avl;
15 375b78fb 2009-08-23 rsc Avl *p; /* parent */
16 375b78fb 2009-08-23 rsc Avl *n[2]; /* children */
17 375b78fb 2009-08-23 rsc int bal; /* balance bits */
20 375b78fb 2009-08-23 rsc Avl *avlnext(Avlwalk *walk);
21 375b78fb 2009-08-23 rsc Avl *avlprev(Avlwalk *walk);
22 375b78fb 2009-08-23 rsc Avlwalk *avlwalk(Avltree *tree);
23 375b78fb 2009-08-23 rsc void deleteavl(Avltree *tree, Avl *key, Avl **oldp);
24 375b78fb 2009-08-23 rsc void endwalk(Avlwalk *walk);
25 375b78fb 2009-08-23 rsc void insertavl(Avltree *tree, Avl *new, Avl **oldp);
26 375b78fb 2009-08-23 rsc Avl *lookupavl(Avltree *tree, Avl *key);
27 e63f0507 2011-06-02 rsc Avl *searchavl(Avltree *tree, Avl *key, int neighbor);
28 375b78fb 2009-08-23 rsc Avltree *mkavltree(int(*cmp)(Avl*, Avl*));
30 375b78fb 2009-08-23 rsc .SH DESCRIPTION
31 375b78fb 2009-08-23 rsc An AVL tree is a self-balancing binary search tree.
32 375b78fb 2009-08-23 rsc These routines allow creation and maintenance of in-memory AVL trees.
34 375b78fb 2009-08-23 rsc An empty AVL tree is created by calling
36 375b78fb 2009-08-23 rsc with a comparison function as argument.
37 375b78fb 2009-08-23 rsc This function should take two pointers to
39 375b78fb 2009-08-23 rsc objects and return -1, 0 or 1 as the first is
40 375b78fb 2009-08-23 rsc respectively less than,
41 375b78fb 2009-08-23 rsc equal to, or greater than,
46 375b78fb 2009-08-23 rsc tree node into
50 375b78fb 2009-08-23 rsc is non-nil upon return,
51 375b78fb 2009-08-23 rsc it points to storage for an old node
52 375b78fb 2009-08-23 rsc with the same key that may now be freed.
56 375b78fb 2009-08-23 rsc node that matches
60 375b78fb 2009-08-23 rsc comparison function,
68 e63f0507 2011-06-02 rsc node that matches
72 e63f0507 2011-06-02 rsc comparison function, if it exists.
73 e63f0507 2011-06-02 rsc If it does not, and
75 e63f0507 2011-06-02 rsc is positive, it returns the nearest node whose
77 e63f0507 2011-06-02 rsc is greater or
79 e63f0507 2011-06-02 rsc if there is none and, if
81 e63f0507 2011-06-02 rsc is negative, it returns the nearest node whose
85 e63f0507 2011-06-02 rsc if there is none.
86 e63f0507 2011-06-02 rsc It is an error to set
88 e63f0507 2011-06-02 rsc to values other than \-1, 0, or +1.
91 375b78fb 2009-08-23 rsc removes the node matching
96 375b78fb 2009-08-23 rsc is handled as per
97 375b78fb 2009-08-23 rsc .IR insertavl .
100 375b78fb 2009-08-23 rsc returns a pointer to a newly-allocated
104 375b78fb 2009-08-23 rsc frees such an object.
108 375b78fb 2009-08-23 rsc walk the tree associated with
110 375b78fb 2009-08-23 rsc returning the next
111 375b78fb 2009-08-23 rsc (respectively, previous)
112 375b78fb 2009-08-23 rsc tree node in the comparison order
113 375b78fb 2009-08-23 rsc defined by the comparison function
114 375b78fb 2009-08-23 rsc associated with the tree associated with
116 375b78fb 2009-08-23 rsc .SH EXAMPLES
117 375b78fb 2009-08-23 rsc Intended usage seems to be to make an anonymous
119 375b78fb 2009-08-23 rsc the first member of the application's tree-node structure,
120 375b78fb 2009-08-23 rsc then pass these routines tree-node pointers instead of
124 375b78fb 2009-08-23 rsc typedef struct Node {
126 375b78fb 2009-08-23 rsc uchar score[VtScoreSize];
130 375b78fb 2009-08-23 rsc Avltree *tree;
134 375b78fb 2009-08-23 rsc res = lookupavl(tree, np);
137 375b78fb 2009-08-23 rsc .B \*9/src/libavl
138 375b78fb 2009-08-23 rsc .SH SEE ALSO
139 375b78fb 2009-08-23 rsc G. M. Adelson-Velsky,
140 375b78fb 2009-08-23 rsc E. M. Landis,
141 375b78fb 2009-08-23 rsc ``An algorithm for the organization of information'',
142 375b78fb 2009-08-23 rsc .IR "Soviet Mathematics" ,
143 375b78fb 2009-08-23 rsc Vol. 3, pp. 1256—1263.
144 375b78fb 2009-08-23 rsc .SH DIAGNOSTICS
145 375b78fb 2009-08-23 rsc Functions returning pointers return