5 avl tree implementation using recursive functions
6 the height of an n node tree is less than 1.44*log2(n+2)-1
7 (so the max recursion depth in case of a tree with 2^32 nodes is 45)
17 static int delta(struct node *n) {
18 return (n->left ? n->left->height:0) - (n->right ? n->right->height:0);
21 static void updateheight(struct node *n) {
23 if (n->left && n->left->height > n->height)
24 n->height = n->left->height;
25 if (n->right && n->right->height > n->height)
26 n->height = n->right->height;
30 static struct node *rotl(struct node *n) {
31 struct node *r = n->right;
39 static struct node *rotr(struct node *n) {
40 struct node *l = n->left;
48 static struct node *balance(struct node *n) {
52 if (delta(n->right) > 0)
53 n->right = rotr(n->right);
56 if (delta(n->left) < 0)
57 n->left = rotl(n->left);
64 static struct node *find(struct node *n, const void *k,
65 int (*cmp)(const void *, const void *))
75 return find(n->left, k, cmp);
77 return find(n->right, k, cmp);
80 static struct node *insert(struct node **n, const void *k,
81 int (*cmp)(const void *, const void *), int *new)
87 *n = r = malloc(sizeof **n);
90 r->left = r->right = 0;
100 r = insert(&r->left, k, cmp, new);
102 r = insert(&r->right, k, cmp, new);
108 static struct node *remove_rightmost(struct node *n, struct node **rightmost)
114 n->right = remove_rightmost(n->right, rightmost);
118 static struct node *remove(struct node **n, const void *k,
119 int (*cmp)(const void *, const void *), struct node *parent)
125 c = cmp(k, (*n)->key);
129 r->left = remove_rightmost(r->left, n);
130 (*n)->left = r->left;
131 (*n)->right = r->right;
139 parent = remove(&(*n)->left, k, cmp, *n);
141 parent = remove(&(*n)->right, k, cmp, *n);
147 void *tdelete(const void *restrict key, void **restrict rootp,
148 int(*compar)(const void *, const void *))
150 struct node *n = *rootp;
152 /* last argument is arbitrary non-null pointer
153 which is returned when the root node is deleted */
154 ret = remove(&n, key, compar, n);
159 void *tfind(const void *key, void *const *rootp,
160 int(*compar)(const void *, const void *))
162 return find(*rootp, key, compar);
165 void *tsearch(const void *key, void **rootp,
166 int (*compar)(const void *, const void *))
169 struct node *n = *rootp;
171 ret = insert(&n, key, compar, &new);
176 static void walk(const struct node *r, void (*action)(const void *, VISIT, int), int d)
180 if (r->left == 0 && r->right == 0)
183 action(r, preorder, d);
184 walk(r->left, action, d+1);
185 action(r, postorder, d);
186 walk(r->right, action, d+1);
187 action(r, endorder, d);
191 void twalk(const void *root, void (*action)(const void *, VISIT, int))
193 walk(root, action, 0);