2 AVL balanced tree library
4 > Created (Julienne Walker): June 17, 2003
5 > Modified (Julienne Walker): September 24, 2005
7 #include "jsw_avltree.h"
20 #define HEIGHT_LIMIT 64 /* Tallest allowable tree */
23 typedef struct jsw_avlnode {
24 int balance; /* Balance factor */
25 void *data; /* User-defined content */
26 struct jsw_avlnode *link[2]; /* Left (0) and right (1) links */
30 jsw_avlnode_t *root; /* Top of the tree */
31 cmp_f cmp; /* Compare two items */
32 dup_f dup; /* Clone an item (user-defined) */
33 rel_f rel; /* Destroy an item (user-defined) */
34 size_t size; /* Number of items (user-defined) */
38 jsw_avltree_t *tree; /* Paired tree */
39 jsw_avlnode_t *it; /* Current node */
40 jsw_avlnode_t *path[HEIGHT_LIMIT]; /* Traversal path */
41 size_t top; /* Top of stack */
44 /* Two way single rotation */
45 #define jsw_single(root,dir) do { \
46 jsw_avlnode_t *save = root->link[!dir]; \
47 root->link[!dir] = save->link[dir]; \
48 save->link[dir] = root; \
52 /* Two way double rotation */
53 #define jsw_double(root,dir) do { \
54 jsw_avlnode_t *save = root->link[!dir]->link[dir]; \
55 root->link[!dir]->link[dir] = save->link[!dir]; \
56 save->link[!dir] = root->link[!dir]; \
57 root->link[!dir] = save; \
58 save = root->link[!dir]; \
59 root->link[!dir] = save->link[dir]; \
60 save->link[dir] = root; \
64 /* Adjust balance before double rotation */
65 #define jsw_adjust_balance(root,dir,bal) do { \
66 jsw_avlnode_t *n = root->link[dir]; \
67 jsw_avlnode_t *nn = n->link[!dir]; \
68 if ( nn->balance == 0 ) \
69 root->balance = n->balance = 0; \
70 else if ( nn->balance == bal ) { \
71 root->balance = -bal; \
74 else { /* nn->balance == -bal */ \
81 /* Rebalance after insertion */
82 #define jsw_insert_balance(root,dir) do { \
83 jsw_avlnode_t *n = root->link[dir]; \
84 int bal = dir == 0 ? -1 : +1; \
85 if ( n->balance == bal ) { \
86 root->balance = n->balance = 0; \
87 jsw_single ( root, !dir ); \
89 else { /* n->balance == -bal */ \
90 jsw_adjust_balance ( root, dir, bal ); \
91 jsw_double ( root, !dir ); \
95 /* Rebalance after deletion */
96 #define jsw_remove_balance(root,dir,done) do { \
97 jsw_avlnode_t *n = root->link[!dir]; \
98 int bal = dir == 0 ? -1 : +1; \
99 if ( n->balance == -bal ) { \
100 root->balance = n->balance = 0; \
101 jsw_single ( root, dir ); \
103 else if ( n->balance == bal ) { \
104 jsw_adjust_balance ( root, !dir, -bal ); \
105 jsw_double ( root, dir ); \
107 else { /* n->balance == 0 */ \
108 root->balance = -bal; \
110 jsw_single ( root, dir ); \
115 static jsw_avlnode_t *new_node ( jsw_avltree_t *tree, void *data )
117 jsw_avlnode_t *rn = (jsw_avlnode_t *)malloc ( sizeof *rn );
123 rn->data = tree->dup ( data );
124 rn->link[0] = rn->link[1] = NULL;
129 jsw_avltree_t *jsw_avlnew ( cmp_f cmp, dup_f dup, rel_f rel )
131 jsw_avltree_t *rt = (jsw_avltree_t *)malloc ( sizeof *rt );
145 void jsw_avldelete ( jsw_avltree_t *tree )
147 jsw_avlnode_t *it = tree->root;
150 /* Destruction by rotation */
151 while ( it != NULL ) {
152 if ( it->link[0] == NULL ) {
155 tree->rel ( it->data );
161 it->link[0] = save->link[1];
171 void *jsw_avlfind ( jsw_avltree_t *tree, void *data )
173 jsw_avlnode_t *it = tree->root;
175 while ( it != NULL ) {
176 int cmp = tree->cmp ( it->data, data );
181 it = it->link[cmp < 0];
184 return it == NULL ? NULL : it->data;
187 int jsw_avlinsert ( jsw_avltree_t *tree, void *data )
189 /* Empty tree case */
190 if ( tree->root == NULL ) {
191 tree->root = new_node ( tree, data );
192 if ( tree->root == NULL )
196 jsw_avlnode_t head = {0}; /* Temporary tree root */
197 jsw_avlnode_t *s, *t; /* Place to rebalance and parent */
198 jsw_avlnode_t *p, *q; /* Iterator and save pointer */
201 /* Set up false root to ease maintenance */
203 t->link[1] = tree->root;
205 /* Search down the tree, saving rebalance points */
206 for ( s = p = t->link[1]; ; p = q ) {
207 dir = tree->cmp ( p->data, data ) < 0;
213 if ( q->balance != 0 ) {
219 p->link[dir] = q = new_node ( tree, data );
223 /* Update balance factors */
224 for ( p = s; p != q; p = p->link[dir] ) {
225 dir = tree->cmp ( p->data, data ) < 0;
226 p->balance += dir == 0 ? -1 : +1;
229 q = s; /* Save rebalance point for parent fix */
231 /* Rebalance if necessary */
232 if ( abs ( s->balance ) > 1 ) {
233 dir = tree->cmp ( s->data, data ) < 0;
234 jsw_insert_balance ( s, dir );
238 if ( q == head.link[1] )
241 t->link[q == t->link[1]] = s;
249 int jsw_avlerase ( jsw_avltree_t *tree, void *data )
251 if ( tree->root != NULL ) {
252 jsw_avlnode_t *it, *up[HEIGHT_LIMIT];
253 int upd[HEIGHT_LIMIT], top = 0;
258 /* Search down tree and save path */
262 else if ( tree->cmp ( it->data, data ) == 0 )
265 /* Push direction and node onto stack */
266 upd[top] = tree->cmp ( it->data, data ) < 0;
269 it = it->link[upd[top - 1]];
272 /* Remove the node */
273 if ( it->link[0] == NULL || it->link[1] == NULL ) {
274 /* Which child is not null? */
275 int dir = it->link[0] == NULL;
279 up[top - 1]->link[upd[top - 1]] = it->link[dir];
281 tree->root = it->link[dir];
283 tree->rel ( it->data );
287 /* Find the inorder successor */
288 jsw_avlnode_t *heir = it->link[1];
291 /* Save this path too */
295 while ( heir->link[0] != NULL ) {
298 heir = heir->link[0];
303 it->data = heir->data;
306 /* Unlink successor and fix parent */
307 up[top - 1]->link[up[top - 1] == it] = heir->link[1];
309 tree->rel ( heir->data );
313 /* Walk back up the search path */
314 while ( --top >= 0 && !done ) {
315 /* Update balance factors */
316 up[top]->balance += upd[top] != 0 ? -1 : +1;
318 /* Terminate or rebalance as necessary */
319 if ( abs ( up[top]->balance ) == 1 )
321 else if ( abs ( up[top]->balance ) > 1 ) {
322 jsw_remove_balance ( up[top], upd[top], done );
326 up[top - 1]->link[upd[top - 1]] = up[top];
338 size_t jsw_avlsize ( jsw_avltree_t *tree )
343 jsw_avltrav_t *jsw_avltnew ( void )
345 return malloc ( sizeof ( jsw_avltrav_t ) );
348 void jsw_avltdelete ( jsw_avltrav_t *trav )
354 First step in traversal,
357 static void *start ( jsw_avltrav_t *trav, jsw_avltree_t *tree, int dir )
360 trav->it = tree->root;
363 /* Build a path to work with */
364 if ( trav->it != NULL ) {
365 while ( trav->it->link[dir] != NULL ) {
366 trav->path[trav->top++] = trav->it;
367 trav->it = trav->it->link[dir];
371 return trav->it == NULL ? NULL : trav->it->data;
375 Subsequent traversal steps,
376 handles ascending and descending
378 static void *move ( jsw_avltrav_t *trav, int dir )
380 if ( trav->it->link[dir] != NULL ) {
381 /* Continue down this branch */
382 trav->path[trav->top++] = trav->it;
383 trav->it = trav->it->link[dir];
385 while ( trav->it->link[!dir] != NULL ) {
386 trav->path[trav->top++] = trav->it;
387 trav->it = trav->it->link[!dir];
391 /* Move to the next branch */
395 if ( trav->top == 0 ) {
401 trav->it = trav->path[--trav->top];
402 } while ( last == trav->it->link[dir] );
405 return trav->it == NULL ? NULL : trav->it->data;
408 void *jsw_avltfirst ( jsw_avltrav_t *trav, jsw_avltree_t *tree )
410 return start ( trav, tree, 0 ); /* Min value */
413 void *jsw_avltlast ( jsw_avltrav_t *trav, jsw_avltree_t *tree )
415 return start ( trav, tree, 1 ); /* Max value */
418 void *jsw_avltnext ( jsw_avltrav_t *trav )
420 return move ( trav, 1 ); /* Toward larger items */
423 void *jsw_avltprev ( jsw_avltrav_t *trav )
425 return move ( trav, 0 ); /* Toward smaller items */