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 Avltree	*mkavltree(int(*cmp)(Avl*, Avl*));
28 .EE
29 .SH DESCRIPTION
30 An AVL tree is a self-balancing binary search tree.
31 These routines allow creation and maintenance of in-memory AVL trees.
32 .PP
33 An empty AVL tree is created by calling
34 .I mkavltree
35 with a comparison function as argument.
36 This function should take two pointers to
37 .B Avl
38 objects and return -1, 0 or 1 as the first is
39 respectively less than,
40 equal to, or greater than,
41 the second.
42 .I Insertavl
43 adds a
44 .I new
45 tree node into
46 .IR tree .
47 If
48 .I oldp
49 is non-nil upon return,
50 it points to storage for an old node
51 with the same key that may now be freed.
52 .I Lookupavl
53 returns the
54 .I tree
55 node that matches
56 .I key
57 by
58 .IR tree 's
59 comparison function,
60 or
61 .B nil
62 if none.
63 .I Deleteavl
64 removes the node matching
65 .I key
66 from
67 .IR tree ;
68 .I oldp
69 is handled as per
70 .IR insertavl .
71 .PP
72 .I Avlwalk
73 returns a pointer to a newly-allocated
74 .B Avlwalk
75 object.
76 .I Endwalk
77 frees such an object.
78 .I Avlnext
79 and
80 .I avlprev
81 walk the tree associated with
82 .IR walk ,
83 returning the next
84 (respectively, previous)
85 tree node in the comparison order
86 defined by the comparison function
87 associated with the tree associated with
88 .IR walk .
89 .SH EXAMPLES
90 Intended usage seems to be to make an anonymous
91 .B Avl
92 the first member of the application's tree-node structure,
93 then pass these routines tree-node pointers instead of
94 .BR Avl* s.
95 .IP
96 .EX
97 typedef struct Node {
98 	Avl;
99 	uchar	score[VtScoreSize];
100 	int	type;
101 } Node;
102 .sp 0.3v
103 Avltree *tree;
104 Avl *res;
105 Node *np;
106 \fI\&...\fP
107 	res = lookupavl(tree, np);
108 .EE
109 .SH SOURCE
110 .B \*9/src/libavl
111 .SH SEE ALSO
112 G. M. Adelson-Velsky,
113 E. M. Landis,
114 ``An algorithm for the organization of information'',
115 .IR "Soviet Mathematics" ,
116 Vol. 3, pp. 1256—1263.
117 .SH DIAGNOSTICS
118 Functions returning pointers return
119 .B nil
120 on error.