1 375b78fb 2009-08-23 rsc .TH AVL 3
  2 375b78fb 2009-08-23 rsc .SH NAME
  3 375b78fb 2009-08-23 rsc mkavltree, insertavl, lookupavl, deleteavl, avlwalk, avlnext, avlprev, endwalk - AVL tree routines
  4 375b78fb 2009-08-23 rsc .SH SYNOPSIS
  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
  7 375b78fb 2009-08-23 rsc .EX
  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>
 11 375b78fb 2009-08-23 rsc .sp 0.3v
 12 375b78fb 2009-08-23 rsc typedef struct Avl Avl;
 13 375b78fb 2009-08-23 rsc struct Avl
 14 375b78fb 2009-08-23 rsc {
 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 */
 18 375b78fb 2009-08-23 rsc };
 19 375b78fb 2009-08-23 rsc .sp 0.3v
 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*));
 29 375b78fb 2009-08-23 rsc .EE
 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.
 33 375b78fb 2009-08-23 rsc .PP
 34 375b78fb 2009-08-23 rsc An empty AVL tree is created by calling
 35 375b78fb 2009-08-23 rsc .I mkavltree
 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
 38 375b78fb 2009-08-23 rsc .B Avl
 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,
 42 375b78fb 2009-08-23 rsc the second.
 43 375b78fb 2009-08-23 rsc .I Insertavl
 44 375b78fb 2009-08-23 rsc adds a
 45 375b78fb 2009-08-23 rsc .I new
 46 375b78fb 2009-08-23 rsc tree node into
 47 375b78fb 2009-08-23 rsc .IR tree .
 48 375b78fb 2009-08-23 rsc If
 49 375b78fb 2009-08-23 rsc .I oldp
 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.
 53 375b78fb 2009-08-23 rsc .I Lookupavl
 54 375b78fb 2009-08-23 rsc returns the
 55 375b78fb 2009-08-23 rsc .I tree
 56 375b78fb 2009-08-23 rsc node that matches
 57 375b78fb 2009-08-23 rsc .I key
 58 375b78fb 2009-08-23 rsc by
 59 375b78fb 2009-08-23 rsc .IR tree 's
 60 375b78fb 2009-08-23 rsc comparison function,
 61 375b78fb 2009-08-23 rsc or
 62 375b78fb 2009-08-23 rsc .B nil
 63 375b78fb 2009-08-23 rsc if none.
 64 e63f0507 2011-06-02 rsc .PP
 65 e63f0507 2011-06-02 rsc .I Searchavl
 66 e63f0507 2011-06-02 rsc returns the
 67 e63f0507 2011-06-02 rsc .I tree
 68 e63f0507 2011-06-02 rsc node that matches
 69 e63f0507 2011-06-02 rsc .I key
 70 e63f0507 2011-06-02 rsc by
 71 e63f0507 2011-06-02 rsc .IR tree 's
 72 e63f0507 2011-06-02 rsc comparison function, if it exists.
 73 e63f0507 2011-06-02 rsc If it does not, and
 74 e63f0507 2011-06-02 rsc .I neighbor
 75 e63f0507 2011-06-02 rsc is positive, it returns the nearest node whose
 76 e63f0507 2011-06-02 rsc .I key
 77 e63f0507 2011-06-02 rsc is greater or
 78 e63f0507 2011-06-02 rsc .B nil
 79 e63f0507 2011-06-02 rsc if there is none and, if
 80 e63f0507 2011-06-02 rsc .I neighbor
 81 e63f0507 2011-06-02 rsc is negative, it returns the nearest node whose
 82 e63f0507 2011-06-02 rsc .I key
 83 e63f0507 2011-06-02 rsc is less or
 84 e63f0507 2011-06-02 rsc .B nil
 85 e63f0507 2011-06-02 rsc if there is none.
 86 e63f0507 2011-06-02 rsc It is an error to set
 87 e63f0507 2011-06-02 rsc .I neighbor
 88 e63f0507 2011-06-02 rsc to values other than \-1, 0, or +1.
 89 e63f0507 2011-06-02 rsc .PP
 90 375b78fb 2009-08-23 rsc .I Deleteavl
 91 375b78fb 2009-08-23 rsc removes the node matching
 92 375b78fb 2009-08-23 rsc .I key
 93 375b78fb 2009-08-23 rsc from
 94 375b78fb 2009-08-23 rsc .IR tree ;
 95 375b78fb 2009-08-23 rsc .I oldp
 96 375b78fb 2009-08-23 rsc is handled as per
 97 375b78fb 2009-08-23 rsc .IR insertavl .
 98 375b78fb 2009-08-23 rsc .PP
 99 375b78fb 2009-08-23 rsc .I Avlwalk
100 375b78fb 2009-08-23 rsc returns a pointer to a newly-allocated
101 375b78fb 2009-08-23 rsc .B Avlwalk
102 375b78fb 2009-08-23 rsc object.
103 375b78fb 2009-08-23 rsc .I Endwalk
104 375b78fb 2009-08-23 rsc frees such an object.
105 375b78fb 2009-08-23 rsc .I Avlnext
106 375b78fb 2009-08-23 rsc and
107 375b78fb 2009-08-23 rsc .I avlprev
108 375b78fb 2009-08-23 rsc walk the tree associated with
109 375b78fb 2009-08-23 rsc .IR walk ,
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
115 375b78fb 2009-08-23 rsc .IR walk .
116 375b78fb 2009-08-23 rsc .SH EXAMPLES
117 375b78fb 2009-08-23 rsc Intended usage seems to be to make an anonymous
118 375b78fb 2009-08-23 rsc .B Avl
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
121 375b78fb 2009-08-23 rsc .BR Avl* s.
122 375b78fb 2009-08-23 rsc .IP
123 375b78fb 2009-08-23 rsc .EX
124 375b78fb 2009-08-23 rsc typedef struct Node {
125 375b78fb 2009-08-23 rsc 	Avl;
126 375b78fb 2009-08-23 rsc 	uchar	score[VtScoreSize];
127 375b78fb 2009-08-23 rsc 	int	type;
128 375b78fb 2009-08-23 rsc } Node;
129 375b78fb 2009-08-23 rsc .sp 0.3v
130 375b78fb 2009-08-23 rsc Avltree *tree;
131 375b78fb 2009-08-23 rsc Avl *res;
132 375b78fb 2009-08-23 rsc Node *np;
133 375b78fb 2009-08-23 rsc \fI\&...\fP
134 375b78fb 2009-08-23 rsc 	res = lookupavl(tree, np);
135 375b78fb 2009-08-23 rsc .EE
136 375b78fb 2009-08-23 rsc .SH SOURCE
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
146 375b78fb 2009-08-23 rsc .B nil
147 375b78fb 2009-08-23 rsc on error.