1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
|
.TH AVL 3
.SH NAME
mkavltree, insertavl, lookupavl, deleteavl, avlwalk, avlnext, avlprev, endwalk - AVL tree routines
.SH SYNOPSIS
.\" .ta 0.75i 1.5i 2.25i 3i 3.75i 4.5i
.ta 0.7i +0.7i +0.7i +0.7i +0.7i +0.7i +0.7i
.EX
#include <u.h>
#include <libc.h>
#include <avl.h>
.sp 0.3v
typedef struct Avl Avl;
struct Avl
{
Avl *p; /* parent */
Avl *n[2]; /* children */
int bal; /* balance bits */
};
.sp 0.3v
Avl *avlnext(Avlwalk *walk);
Avl *avlprev(Avlwalk *walk);
Avlwalk *avlwalk(Avltree *tree);
void deleteavl(Avltree *tree, Avl *key, Avl **oldp);
void endwalk(Avlwalk *walk);
void insertavl(Avltree *tree, Avl *new, Avl **oldp);
Avl *lookupavl(Avltree *tree, Avl *key);
Avl *searchavl(Avltree *tree, Avl *key, int neighbor);
Avltree *mkavltree(int(*cmp)(Avl*, Avl*));
.EE
.SH DESCRIPTION
An AVL tree is a self-balancing binary search tree.
These routines allow creation and maintenance of in-memory AVL trees.
.PP
An empty AVL tree is created by calling
.I mkavltree
with a comparison function as argument.
This function should take two pointers to
.B Avl
objects and return -1, 0 or 1 as the first is
respectively less than,
equal to, or greater than,
the second.
.I Insertavl
adds a
.I new
tree node into
.IR tree .
If
.I oldp
is non-nil upon return,
it points to storage for an old node
with the same key that may now be freed.
.I Lookupavl
returns the
.I tree
node that matches
.I key
by
.IR tree 's
comparison function,
or
.B nil
if none.
.PP
.I Searchavl
returns the
.I tree
node that matches
.I key
by
.IR tree 's
comparison function, if it exists.
If it does not, and
.I neighbor
is positive, it returns the nearest node whose
.I key
is greater or
.B nil
if there is none and, if
.I neighbor
is negative, it returns the nearest node whose
.I key
is less or
.B nil
if there is none.
It is an error to set
.I neighbor
to values other than \-1, 0, or +1.
.PP
.I Deleteavl
removes the node matching
.I key
from
.IR tree ;
.I oldp
is handled as per
.IR insertavl .
.PP
.I Avlwalk
returns a pointer to a newly-allocated
.B Avlwalk
object.
.I Endwalk
frees such an object.
.I Avlnext
and
.I avlprev
walk the tree associated with
.IR walk ,
returning the next
(respectively, previous)
tree node in the comparison order
defined by the comparison function
associated with the tree associated with
.IR walk .
.SH EXAMPLES
Intended usage seems to be to make an anonymous
.B Avl
the first member of the application's tree-node structure,
then pass these routines tree-node pointers instead of
.BR Avl* s.
.IP
.EX
typedef struct Node {
Avl;
uchar score[VtScoreSize];
int type;
} Node;
.sp 0.3v
Avltree *tree;
Avl *res;
Node *np;
\fI\&...\fP
res = lookupavl(tree, np);
.EE
.SH SOURCE
.B \*9/src/libavl
.SH SEE ALSO
G. M. Adelson-Velsky,
E. M. Landis,
``An algorithm for the organization of information'',
.IR "Soviet Mathematics" ,
Vol. 3, pp. 1256—1263.
.SH DIAGNOSTICS
Functions returning pointers return
.B nil
on error.
|