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