1 .TH AVL 3
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 \*9/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.