4 * Intrusive, nonrecursive AVL tree data structure (self-balancing binary search
5 * tree), implementation file.
10 * This file is placed into the public domain. You can do whatever you want
14 #include <wimlib/avl_tree.h>
16 /* Starts an in-order traversal of the tree: returns the least-valued node, or
17 * NULL if the tree is empty. */
18 struct avl_tree_node *
19 avl_tree_first_in_order(const struct avl_tree_node *root)
21 const struct avl_tree_node *first = root;
26 return (struct avl_tree_node *)first;
29 /* Continues an in-order traversal of the tree: returns the next-greatest-valued
30 * node, or NULL if there is none. */
31 struct avl_tree_node *
32 avl_tree_next_in_order(const struct avl_tree_node *prev)
34 const struct avl_tree_node *next;
37 for (next = prev->right;
42 for (next = avl_get_parent(prev);
43 next && prev == next->right;
44 prev = next, next = avl_get_parent(next))
46 return (struct avl_tree_node *)next;
49 /* Starts a postorder traversal of the tree. */
50 struct avl_tree_node *
51 avl_tree_first_in_postorder(const struct avl_tree_node *root)
53 const struct avl_tree_node *first = root;
56 while (first->left || first->right)
57 first = first->left ? first->left : first->right;
59 return (struct avl_tree_node *)first;
62 /* Continues a postorder traversal of the tree. @prev will not be deferenced as
63 * it's allowed that its memory has been freed; @prev_parent must be its saved
64 * parent node. Returns NULL if there are no more nodes (i.e. @prev was the
65 * root of the tree). */
66 struct avl_tree_node *
67 avl_tree_next_in_postorder(const struct avl_tree_node *prev,
68 const struct avl_tree_node *prev_parent)
70 const struct avl_tree_node *next = prev_parent;
72 if (next && prev == next->left && next->right)
73 for (next = next->right;
74 next->left || next->right;
75 next = next->left ? next->left : next->right)
77 return (struct avl_tree_node *)next;
80 /* Get the left child (sign < 0) or the right child (sign > 0)
81 * Note: for all calls of this, 'sign' is constant at compilation time and the
82 * compiler can remove the conditional. */
83 static AVL_INLINE struct avl_tree_node *
84 avl_get_child(const struct avl_tree_node *parent, int sign)
92 /* Set the left child (sign < 0) or the right child (sign > 0)
93 * Note: for all calls of this, 'sign' is constant at compilation time and the
94 * compiler can remove the conditional. */
95 static AVL_INLINE void
96 avl_set_child(struct avl_tree_node *parent, int sign,
97 struct avl_tree_node *child)
100 parent->left = child;
102 parent->right = child;
105 /* Sets the parent of the AVL tree @node to @parent. */
106 static AVL_INLINE void
107 avl_set_parent(struct avl_tree_node *node, struct avl_tree_node *parent)
109 node->parent_balance =
110 (node->parent_balance & 3) | (uintptr_t)parent;
113 /* Sets the parent and balance factor of the AVL tree @node. */
114 static AVL_INLINE void
115 avl_set_parent_balance(struct avl_tree_node *node, struct avl_tree_node *parent,
118 node->parent_balance = (uintptr_t)parent | (balance_factor + 1);
121 /* Returns the balance factor of the specified AVL tree node --- that is, the
122 * height of its right subtree minus the height of its left subtree. */
123 static AVL_INLINE int
124 avl_get_balance_factor(const struct avl_tree_node *node)
126 return (int)(node->parent_balance & 3) - 1;
129 /* Sets the balance factor of the specified AVL tree node. The caller MUST
130 * ensure that this number is valid and maintains the AVL tree invariants. */
131 static AVL_INLINE void
132 avl_set_balance_factor(struct avl_tree_node *node, int balance_factor)
134 node->parent_balance =
135 (node->parent_balance & ~3) | (balance_factor + 1);
138 /* Increments the balance factor of the specified AVL tree @node by the
139 * specified @amount. The caller MUST ensure that this number is valid and
140 * maintains the AVL tree invariants. */
141 static AVL_INLINE void
142 avl_adjust_balance_factor(struct avl_tree_node *node, int amount)
144 node->parent_balance += amount;
148 * Template for performing a rotation ---
150 * Clockwise/Right (sign > 0):
160 * Counterclockwise/Left (sign < 0)- same, except left and right are reversed:
170 * This updates pointers but not balance factors!
172 static AVL_INLINE void
173 avl_rotate(struct avl_tree_node ** const root_ptr,
174 struct avl_tree_node * const A, const int sign)
176 struct avl_tree_node * const B = avl_get_child(A, -sign);
177 struct avl_tree_node * const C = avl_get_child(A, +sign);
178 struct avl_tree_node * const E = avl_get_child(B, +sign);
179 struct avl_tree_node * const X = avl_get_parent(A);
181 avl_set_child(A, -sign, E);
182 avl_set_child(A, +sign, C);
183 avl_set_parent(A, B);
185 avl_set_child(B, +sign, A);
186 avl_set_parent(B, X);
189 avl_set_parent(E, A);
192 if (avl_get_child(X, +sign) == A)
193 avl_set_child(X, +sign, B);
195 avl_set_child(X, -sign, B);
202 * Template for performing a double rotation ---
204 * Rotate counterclockwise (left) rooted at B, then clockwise (right) rooted at
215 * Rotate clockwise (right) rooted at B, then counterclockwise (left) rooted at
226 * Returns a pointer to E, the new root, and updates balance factors. Except
227 * for that, this is equivalent to:
228 * avl_rotate(root_ptr, B, -sign);
229 * avl_rotate(root_ptr, A, +sign);
232 static AVL_INLINE struct avl_tree_node *
233 avl_do_double_rotate(struct avl_tree_node ** const root_ptr,
234 struct avl_tree_node * const B,
235 struct avl_tree_node * const A, const int sign)
237 struct avl_tree_node * const E = avl_get_child(B, +sign);
238 struct avl_tree_node * const F = avl_get_child(E, -sign);
239 struct avl_tree_node * const G = avl_get_child(E, +sign);
240 struct avl_tree_node * const X = avl_get_parent(A);
241 const int e = avl_get_balance_factor(E);
243 avl_set_child(A, -sign, G);
244 avl_set_parent_balance(A, E, ((sign * e >= 0) ? 0 : -e));
246 avl_set_child(B, +sign, F);
247 avl_set_parent_balance(B, E, ((sign * e <= 0) ? 0 : -e));
249 avl_set_child(E, +sign, A);
250 avl_set_child(E, -sign, B);
251 avl_set_parent_balance(E, X, 0);
254 avl_set_parent(G, A);
257 avl_set_parent(F, B);
260 if (avl_get_child(X, +sign) == A)
261 avl_set_child(X, +sign, E);
263 avl_set_child(X, -sign, E);
271 static AVL_INLINE bool
272 avl_handle_subtree_growth(struct avl_tree_node ** const root_ptr,
273 struct avl_tree_node * const node,
274 struct avl_tree_node * const parent,
277 /* Height of @node subtree of @parent has increased by 1.
278 * Adjust @parent's balance factor and check whether rotations need to
281 int old_balance_factor, new_balance_factor;
283 old_balance_factor = avl_get_balance_factor(parent);
285 if (old_balance_factor == 0) {
286 /* Parent has increased in height but is still sufficiently
287 * balanced. Continue up the tree. */
288 avl_adjust_balance_factor(parent, sign);
292 new_balance_factor = old_balance_factor + sign;
294 if (new_balance_factor == 0) {
295 /* Parent is balanced; nothing more to to. */
296 avl_adjust_balance_factor(parent, sign);
300 /* FROM THIS POINT ONWARDS THE COMMENTS ASSUME sign < 0.
301 * The other case is symmetric --- that is, the rotations done are the
302 * the mirror images, all the balance factors are inverted, and left and
303 * right pointers are otherwise reversed. */
305 /* Parent is left-heavy (balance_factor == -2). */
307 if (sign * avl_get_balance_factor(node) > 0) {
309 /* Child node (@node, also B below) is also left-heavy.
310 * It must have balance_factor == -1.
311 * Do a clockwise ("right") rotation rooted at
322 * Before the rotation:
325 * Let x = height(C). Then:
329 * max(height(F), height(G)) = x.
331 * After the rotation:
332 * height(D) = max(height(F), height(G)) + 1
334 * height(A) = max(height(E), height(C)) + 1
335 * = max(x, x) + 1 = x + 1
340 avl_rotate(root_ptr, parent, -sign);
341 avl_adjust_balance_factor(parent, -sign); /* A */
342 avl_adjust_balance_factor(node, -sign); /* B */
344 /* Child node (@node, also B below) is right-heavy.
345 * It must have balance_factor == +1.
346 * Do a counterclockwise ("left") rotation rooted at child node
347 * (B below), then a clockwise ("right") rotation rooted at
348 * parent node (A below).
358 * Before the rotation:
361 * Let x = height(C). Then:
365 * max(height(F), height(G)) = x
367 * After both rotations:
368 * height(A) = max(height(G), height(C)) + 1
370 * balance(A) = balance(E{orig}) >= 0 ? 0 : -balance(E{orig})
371 * height(B) = max(height(D), height(F)) + 1
373 * balance(B) = balance(E{orig} <= 0) ? 0 : -balance(E{orig})
378 avl_do_double_rotate(root_ptr, node, parent, -sign);
383 /* Rebalance the tree after insertion of the specified node. */
385 avl_tree_rebalance_after_insert(struct avl_tree_node **root_ptr,
386 struct avl_tree_node *inserted)
388 struct avl_tree_node *node, *parent;
391 inserted->left = NULL;
392 inserted->right = NULL;
394 for (node = inserted, parent = avl_get_parent(node);
396 node = parent, parent = avl_get_parent(parent))
398 /* Height of @node subtree has increased by 1 */
400 if (node == parent->left)
401 done = avl_handle_subtree_growth(root_ptr, node,
404 done = avl_handle_subtree_growth(root_ptr, node,
409 static AVL_INLINE struct avl_tree_node *
410 avl_handle_subtree_shrink(struct avl_tree_node ** const root_ptr,
411 struct avl_tree_node *parent,
413 bool * const left_deleted_ret)
415 struct avl_tree_node *node;
417 const int old_balance_factor = avl_get_balance_factor(parent);
418 const int new_balance_factor = old_balance_factor + sign;
420 if (old_balance_factor == 0) {
421 /* Prior to the deletion, the subtree rooted at
422 * @parent was perfectly balanced. It's now
423 * unbalanced by 1, but that's okay and its height
424 * hasn't changed. Nothing more to do. */
425 avl_adjust_balance_factor(parent, sign);
427 } else if (new_balance_factor == 0) {
428 /* The subtree rooted at @parent is now perfectly
429 * balanced, whereas before the deletion it was
430 * unbalanced by 1. Its height must have decreased
431 * by 1. No rotation is needed at this location,
432 * but continue up the tree. */
433 avl_adjust_balance_factor(parent, sign);
436 /* The subtree rooted at @parent is now significantly
437 * unbalanced (by 2 in some direction). */
438 node = avl_get_child(parent, sign);
440 /* The rotations below are similar to those done during
441 * insertion. The only new case is the one where the
442 * child node has a balance factor of 0. */
444 if (sign * avl_get_balance_factor(node) >= 0) {
445 avl_rotate(root_ptr, parent, -sign);
447 if (avl_get_balance_factor(node) == 0) {
448 /* Child node (@node, also B below) is balanced.
449 * Do a clockwise ("right") rotation rooted at
460 * Before the rotation:
463 * Let x = height(C). Then:
467 * max(height(F), height(G)) = x.
469 * After the rotation:
470 * height(D) = max(height(F), height(G)) + 1
472 * height(A) = max(height(E), height(C)) + 1
473 * = max(x + 1, x) + 1 = x + 2
478 /* A: -2 => -1 (sign < 0)
479 * or +2 => +1 (sign > 0)
480 * No change needed --- that's the same as
481 * old_balance_factor. */
483 /* B: 0 => +1 (sign < 0)
484 * or 0 => -1 (sign > 0) */
485 avl_adjust_balance_factor(node, -sign);
487 /* Height is unchanged; nothing more to do. */
490 avl_adjust_balance_factor(parent, -sign);
491 avl_adjust_balance_factor(node, -sign);
494 node = avl_do_double_rotate(root_ptr, node,
498 parent = avl_get_parent(node);
500 *left_deleted_ret = (node == parent->left);
504 /* Swaps node X, which must have 2 children, with its in-order successor, then
505 * unlinks node X. Returns the parent of X just before unlinking, without its
506 * balance factor having been updated to account for the unlink. */
507 static AVL_INLINE struct avl_tree_node *
508 avl_tree_swap_with_successor(struct avl_tree_node **root_ptr,
509 struct avl_tree_node *X,
510 bool *left_deleted_ret)
512 struct avl_tree_node *Y, *P, *ret;
525 * [ X removed, Y returned ]
528 *left_deleted_ret = false;
530 struct avl_tree_node *Q;
542 * A ... => A ... => A ...
551 * [ X removed, Q returned ]
556 avl_set_parent(Q->left, Q);
558 avl_set_parent(X->right, Y);
560 *left_deleted_ret = true;
564 avl_set_parent(X->left, Y);
566 Y->parent_balance = X->parent_balance;
567 P = avl_get_parent(X);
580 /* Removes the specified @node from the AVL tree. @root_ptr must point to the
581 * pointer to the root node of the tree; *root_ptr may change if the tree is
584 * This *only* removes the node and rebalances the tree; it does not free
585 * memory, nor does it do the equivalent of avl_tree_node_set_unlinked(). */
587 avl_tree_remove(struct avl_tree_node **root_ptr, struct avl_tree_node *node)
589 struct avl_tree_node *child, *parent;
592 if (node->left && node->right) {
593 parent = avl_tree_swap_with_successor(root_ptr, node,
597 child = node->left ? node->left : node->right;
598 parent = avl_get_parent(node);
600 if (node == parent->left) {
601 parent->left = child;
604 parent->right = child;
605 left_deleted = false;
611 avl_set_parent(child, parent);
616 /* Rebalance the tree */
619 parent = avl_handle_subtree_shrink(root_ptr, parent,
622 parent = avl_handle_subtree_shrink(root_ptr, parent,