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 /* Returns the balance factor of the specified AVL tree node --- that is, the
114 * height of its right subtree minus the height of its left subtree. */
115 static AVL_INLINE int
116 avl_get_balance_factor(const struct avl_tree_node *node)
118 return (int)(node->parent_balance & 3) - 1;
121 /* Sets the balance factor of the specified AVL tree node. The caller MUST
122 * ensure that this number is valid and maintains the AVL tree invariants. */
123 static AVL_INLINE void
124 avl_set_balance_factor(struct avl_tree_node *node, int balance_factor)
126 node->parent_balance =
127 (node->parent_balance & ~3) | (balance_factor + 1);
130 /* Increments the balance factor of the specified AVL tree @node by the
131 * specified @amount. The caller MUST ensure that this number is valid and
132 * maintains the AVL tree invariants. */
133 static AVL_INLINE void
134 avl_adjust_balance_factor(struct avl_tree_node *node, int amount)
136 node->parent_balance += amount;
140 * Template for performing a rotation ---
142 * Clockwise/Right (sign > 0):
152 * Counterclockwise/Left (sign < 0)- same, except left and right are reversed:
162 * This updates pointers but not balance factors!
164 static AVL_INLINE void
165 avl_rotate(struct avl_tree_node * const A, const int sign)
167 struct avl_tree_node * const B = avl_get_child(A, -sign);
168 struct avl_tree_node * const C = avl_get_child(A, +sign);
169 struct avl_tree_node * const E = avl_get_child(B, +sign);
170 struct avl_tree_node * const X = avl_get_parent(A);
172 avl_set_child(A, -sign, E);
173 avl_set_child(A, +sign, C);
174 avl_set_parent(A, B);
176 avl_set_child(B, +sign, A);
177 avl_set_parent(B, X);
180 avl_set_parent(E, A);
183 if (avl_get_child(X, +sign) == A)
184 avl_set_child(X, +sign, B);
186 avl_set_child(X, -sign, B);
190 /* See description in avl_handle_subtree_growth() */
191 static AVL_INLINE struct avl_tree_node *
192 avl_do_double_rotate(struct avl_tree_node * const B,
193 struct avl_tree_node * const A, const int sign)
196 struct avl_tree_node * const E = avl_get_child(B, -sign);
197 const int e = avl_get_balance_factor(E);
199 avl_rotate(B, +sign);
200 avl_rotate(A, -sign);
201 avl_set_balance_factor(A, ((sign * e <= 0) ? 0 : -e));
202 avl_set_balance_factor(B, ((sign * e >= 0) ? 0 : -e));
203 avl_set_balance_factor(E, 0);
208 static AVL_INLINE bool
209 avl_handle_subtree_growth(struct avl_tree_node * const node,
210 struct avl_tree_node * const parent,
213 /* Height of @node subtree of @parent has increased by 1.
214 * Adjust @parent's balance factor and check whether rotations need to
217 const int old_balance_factor = avl_get_balance_factor(parent);
218 const int new_balance_factor = old_balance_factor + sign;
220 if (old_balance_factor == 0) {
221 /* Parent has increased in height but is still sufficiently
222 * balanced. Continue up the tree. */
223 avl_adjust_balance_factor(parent, sign);
227 if (new_balance_factor == 0) {
228 /* Parent is balanced; nothing more to to. */
229 avl_adjust_balance_factor(parent, sign);
233 /* FROM THIS POINT ONWARDS THE COMMENTS ASSUME sign < 0.
234 * The other case is symmetric --- that is, the rotations done are the
235 * the mirror images, all the balance factors are inverted, and left and
236 * right pointers are otherwise reversed. */
238 /* Parent is left-heavy (balance_factor == -2). */
240 if (sign * avl_get_balance_factor(node) > 0) {
242 /* Child node (@node, also B below) is also left-heavy.
243 * It must have balance_factor == -1.
244 * Do a clockwise ("right") rotation rooted at
255 * Before the rotation:
258 * Let x = height(C). Then:
262 * max(height(F), height(G)) = x.
264 * After the rotation:
265 * height(D) = max(height(F), height(G)) + 1
267 * height(A) = max(height(E), height(C)) + 1
268 * = max(x, x) + 1 = x + 1
273 avl_rotate(parent, -sign);
275 avl_set_balance_factor(node, 0); /* B */
276 avl_set_balance_factor(parent, 0); /* A */
278 /* Child node (@node, also B below) is right-heavy.
279 * It must have balance_factor == +1.
280 * Do a counterclockwise ("left") rotation rooted at child node
281 * (B below), then a clockwise ("right") rotation rooted at
282 * parent node (A below).
292 * Before the rotation:
295 * Let x = height(C). Then:
300 * max(height(F), height(G)) = x
302 * After both rotations:
303 * height(A) = max(height(G), height(C)) + 1
305 * balance(A) = balance(E{orig}) >= 0 ? 0 : -balance(E{orig})
306 * height(B) = max(height(D), height(F)) + 1
308 * balance(B) = balance(E{orig} <= 0) ? 0 : -balance(E{orig})
313 avl_do_double_rotate(node, parent, sign);
318 /* Rebalance the tree after insertion of the specified node. */
320 avl_tree_rebalance_after_insert(struct avl_tree_node **root_ptr,
321 struct avl_tree_node *inserted)
323 struct avl_tree_node *node, *parent;
326 inserted->left = NULL;
327 inserted->right = NULL;
329 for (node = inserted, parent = avl_get_parent(node);
331 node = parent, parent = avl_get_parent(parent))
333 /* Height of @node subtree has increased by 1 */
335 if (node == parent->left)
336 done = avl_handle_subtree_growth(node, parent, -1);
338 done = avl_handle_subtree_growth(node, parent, +1);
340 /* Due to rotations, *root_ptr may no longer be the root of the tree */
341 while (avl_get_parent(*root_ptr))
342 *root_ptr = avl_get_parent(*root_ptr);
345 static AVL_INLINE struct avl_tree_node *
346 avl_handle_subtree_shrink(struct avl_tree_node *parent,
348 bool * const left_deleted_ret)
350 struct avl_tree_node *node;
352 const int old_balance_factor = avl_get_balance_factor(parent);
353 const int new_balance_factor = old_balance_factor + sign;
355 if (old_balance_factor == 0) {
356 /* Prior to the deletion, the subtree rooted at
357 * @parent was perfectly balanced. It's now
358 * unbalanced by 1, but that's okay and its height
359 * hasn't changed. Nothing more to do. */
360 avl_adjust_balance_factor(parent, sign);
362 } else if (new_balance_factor == 0) {
363 /* The subtree rooted at @parent is now perfectly
364 * balanced, whereas before the deletion it was
365 * unbalanced by 1. Its height must have decreased
366 * by 1. No rotation is needed at this location,
367 * but continue up the tree. */
368 avl_adjust_balance_factor(parent, sign);
371 /* The subtree rooted at @parent is now significantly
372 * unbalanced (by 2 in some direction). */
373 node = avl_get_child(parent, sign);
375 /* The rotations below are similar to those done during
376 * insertion. The only new case is the one where the
377 * child node has a balance factor of 0. */
379 if (sign * avl_get_balance_factor(node) >= 0) {
380 avl_rotate(parent, -sign);
382 if (avl_get_balance_factor(node) == 0) {
383 avl_set_balance_factor(node, -sign);
384 avl_set_balance_factor(parent, +sign);
385 /* Height is unchanged; nothing more to do. */
388 avl_set_balance_factor(node, 0);
389 avl_set_balance_factor(parent, 0);
392 node = avl_do_double_rotate(node, parent, sign);
395 parent = avl_get_parent(node);
397 *left_deleted_ret = (node == parent->left);
401 /* Swaps node X, which must have 2 children, with its in-order successor.
402 * This adjusts all the necessary pointers and balance factors. */
403 static AVL_INLINE void
404 avl_tree_swap_with_successor(struct avl_tree_node * const X)
406 struct avl_tree_node * const Y = avl_tree_next_in_order(X);
407 struct avl_tree_node * const Y_right = Y->right;
408 struct avl_tree_node * const Y_parent = avl_get_parent(Y);
409 struct avl_tree_node * const X_parent = avl_get_parent(X);
410 const int Y_balance_factor = avl_get_balance_factor(Y);
412 /* Set child pointer to Y when placed in X's position */
414 if (X == X_parent->left)
420 /* Set child pointer to X when placed in Y's position. Also set
421 * the right pointer of Y (it may point to X if the nodes are
424 if (Y == Y_parent->left)
433 /* Set parent pointer to X when placed in Y's position */
435 avl_set_parent(Y_right, X);
437 /* Note: Y has no left child since it is the in-order sucessor of X. */
439 /* Set parent pointers to Y when placed in X's position, as well as X's
440 * parent when placed in Y's position. */
441 avl_set_parent(X->left, Y);
443 avl_set_parent(X->right, Y);
444 avl_set_parent(X, Y_parent);
446 avl_set_parent(X, Y);
449 avl_set_parent(Y, X_parent);
451 avl_set_balance_factor(Y, avl_get_balance_factor(X));
455 avl_set_balance_factor(X, Y_balance_factor);
458 /* Removes the specified @node from the AVL tree whose root is pointed to by
461 * This *only* unlinks the node and rebalances the tree; it does not free any
462 * memory or anything. */
464 avl_tree_remove(struct avl_tree_node **root_ptr, struct avl_tree_node *node)
466 struct avl_tree_node *child, *parent;
469 if (node->left && node->right)
470 avl_tree_swap_with_successor(node);
473 child = node->left ? node->left : node->right;
474 parent = avl_get_parent(node);
476 if (node == parent->left) {
477 parent->left = child;
480 parent->right = child;
481 left_deleted = false;
487 avl_set_parent(child, parent);
489 /* Rebalance the tree */
492 parent = avl_handle_subtree_shrink(parent, +1, &left_deleted);
494 parent = avl_handle_subtree_shrink(parent, -1, &left_deleted);
497 /* Due to rotations, *root_ptr may no longer point to the root of the
500 while (avl_get_parent(*root_ptr))
501 *root_ptr = avl_get_parent(*root_ptr);