X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=src%2Favl_tree.c;h=d3afae4e2114e7de667113b433d905af98dc6c24;hp=eafbb80fcebb29e5078076a790d834cd4d566ecd;hb=eb3e3b72db23ecaa7789a807afeb9577962653fe;hpb=b85695a5f5f50bb0e06f945a2e83cf9dfed08ca7 diff --git a/src/avl_tree.c b/src/avl_tree.c index eafbb80f..d3afae4e 100644 --- a/src/avl_tree.c +++ b/src/avl_tree.c @@ -1,17 +1,29 @@ /* - * avl_tree.c + * avl_tree.c - intrusive, nonrecursive AVL tree data structure (self-balancing + * binary search tree), implementation file * - * Intrusive, nonrecursive AVL tree data structure (self-balancing binary search - * tree), implementation file. + * The following copying information applies to this specific source code file: * - * Author: Eric Biggers - * Year: 2014 + * Written in 2014 by Eric Biggers * - * This file is placed into the public domain. You can do whatever you want - * with it. + * To the extent possible under law, the author(s) have dedicated all copyright + * and related and neighboring rights to this software to the public domain + * worldwide via the Creative Commons Zero 1.0 Universal Public Domain + * Dedication (the "CC0"). + * + * This software is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS + * FOR A PARTICULAR PURPOSE. See the CC0 for more details. + * + * You should have received a copy of the CC0 along with this software; if not + * see . */ -#include +#ifdef HAVE_CONFIG_H +# include "config.h" +#endif + +#include "wimlib/avl_tree.h" /* Starts an in-order traversal of the tree: returns the least-valued node, or * NULL if the tree is empty. */ @@ -77,9 +89,10 @@ avl_tree_next_in_postorder(const struct avl_tree_node *prev, return (struct avl_tree_node *)next; } -/* Get the left child (sign < 0) or the right child (sign > 0) - * Note: for all calls of this, 'sign' is constant at compilation time and the - * compiler can remove the conditional. */ +/* Returns the left child (sign < 0) or the right child (sign > 0) of the + * specified AVL tree node. + * Note: for all calls of this, 'sign' is constant at compilation time, + * so the compiler can remove the conditional. */ static AVL_INLINE struct avl_tree_node * avl_get_child(const struct avl_tree_node *parent, int sign) { @@ -89,9 +102,10 @@ avl_get_child(const struct avl_tree_node *parent, int sign) return parent->right; } -/* Set the left child (sign < 0) or the right child (sign > 0) - * Note: for all calls of this, 'sign' is constant at compilation time and the - * compiler can remove the conditional. */ +/* Sets the left child (sign < 0) or the right child (sign > 0) of the + * specified AVL tree node. + * Note: for all calls of this, 'sign' is constant at compilation time, + * so the compiler can remove the conditional. */ static AVL_INLINE void avl_set_child(struct avl_tree_node *parent, int sign, struct avl_tree_node *child) @@ -102,12 +116,19 @@ avl_set_child(struct avl_tree_node *parent, int sign, parent->right = child; } -/* Sets the parent of the AVL tree @node to @parent. */ +/* Sets the parent and balance factor of the specified AVL tree node. */ +static AVL_INLINE void +avl_set_parent_balance(struct avl_tree_node *node, struct avl_tree_node *parent, + int balance_factor) +{ + node->parent_balance = (uintptr_t)parent | (balance_factor + 1); +} + +/* Sets the parent of the specified AVL tree node. */ static AVL_INLINE void avl_set_parent(struct avl_tree_node *node, struct avl_tree_node *parent) { - node->parent_balance = - (node->parent_balance & 3) | (uintptr_t)parent; + node->parent_balance = (uintptr_t)parent | (node->parent_balance & 3); } /* Returns the balance factor of the specified AVL tree node --- that is, the @@ -118,139 +139,230 @@ avl_get_balance_factor(const struct avl_tree_node *node) return (int)(node->parent_balance & 3) - 1; } -/* Sets the balance factor of the specified AVL tree node. The caller MUST - * ensure that this number is valid and maintains the AVL tree invariants. */ +/* Adds @amount to the balance factor of the specified AVL tree node. + * The caller must ensure this still results in a valid balance factor + * (-1, 0, or 1). */ static AVL_INLINE void -avl_set_balance_factor(struct avl_tree_node *node, int balance_factor) +avl_adjust_balance_factor(struct avl_tree_node *node, int amount) { - node->parent_balance = - (node->parent_balance & ~3) | (balance_factor + 1); + node->parent_balance += amount; } -/* Increments the balance factor of the specified AVL tree @node by the - * specified @amount. The caller MUST ensure that this number is valid and - * maintains the AVL tree invariants. */ static AVL_INLINE void -avl_adjust_balance_factor(struct avl_tree_node *node, int amount) +avl_replace_child(struct avl_tree_node **root_ptr, + struct avl_tree_node *parent, + struct avl_tree_node *old_child, + struct avl_tree_node *new_child) { - node->parent_balance += amount; + if (parent) { + if (old_child == parent->left) + parent->left = new_child; + else + parent->right = new_child; + } else { + *root_ptr = new_child; + } } /* - * Template for performing a rotation --- + * Template for performing a single rotation --- * - * Clockwise/Right (sign > 0): + * sign > 0: Rotate clockwise (right) rooted at A: * - * X X + * P? P? * | | * A B * / \ / \ - * B C => D A + * B C? => D? A * / \ / \ - * D E E C + * D? E? E? C? + * + * (nodes marked with ? may not exist) * - * Counterclockwise/Left (sign < 0)- same, except left and right are reversed: + * sign < 0: Rotate counterclockwise (left) rooted at A: * - * X X + * P? P? * | | * A B * / \ / \ - * C B => A D + * C? B => A D? * / \ / \ - * E D C E + * E? D? C? E? * * This updates pointers but not balance factors! */ static AVL_INLINE void -avl_rotate(struct avl_tree_node * const A, const int sign) +avl_rotate(struct avl_tree_node ** const root_ptr, + struct avl_tree_node * const A, const int sign) { struct avl_tree_node * const B = avl_get_child(A, -sign); - struct avl_tree_node * const C = avl_get_child(A, +sign); struct avl_tree_node * const E = avl_get_child(B, +sign); - struct avl_tree_node * const X = avl_get_parent(A); + struct avl_tree_node * const P = avl_get_parent(A); avl_set_child(A, -sign, E); - avl_set_child(A, +sign, C); avl_set_parent(A, B); avl_set_child(B, +sign, A); - avl_set_parent(B, X); + avl_set_parent(B, P); if (E) avl_set_parent(E, A); - if (X) { - if (avl_get_child(X, +sign) == A) - avl_set_child(X, +sign, B); - else - avl_set_child(X, -sign, B); - } + avl_replace_child(root_ptr, P, A, B); } -/* See description in avl_handle_subtree_growth() */ +/* + * Template for performing a double rotation --- + * + * sign > 0: Rotate counterclockwise (left) rooted at B, then + * clockwise (right) rooted at A: + * + * P? P? P? + * | | | + * A A E + * / \ / \ / \ + * B C? => E C? => B A + * / \ / \ / \ / \ + * D? E B G? D? F?G? C? + * / \ / \ + * F? G? D? F? + * + * (nodes marked with ? may not exist) + * + * sign < 0: Rotate clockwise (right) rooted at B, then + * counterclockwise (left) rooted at A: + * + * P? P? P? + * | | | + * A A E + * / \ / \ / \ + * C? B => C? E => A B + * / \ / \ / \ / \ + * E D? G? B C? G?F? D? + * / \ / \ + * G? F? F? D? + * + * Returns a pointer to E and updates balance factors. Except for those + * two things, this function is equivalent to: + * avl_rotate(root_ptr, B, -sign); + * avl_rotate(root_ptr, A, +sign); + * + * See comment in avl_handle_subtree_growth() for explanation of balance + * factor updates. + */ static AVL_INLINE struct avl_tree_node * -avl_do_double_rotate(struct avl_tree_node * const B, +avl_do_double_rotate(struct avl_tree_node ** const root_ptr, + struct avl_tree_node * const B, struct avl_tree_node * const A, const int sign) { - - struct avl_tree_node * const E = avl_get_child(B, -sign); + struct avl_tree_node * const E = avl_get_child(B, +sign); + struct avl_tree_node * const F = avl_get_child(E, -sign); + struct avl_tree_node * const G = avl_get_child(E, +sign); + struct avl_tree_node * const P = avl_get_parent(A); const int e = avl_get_balance_factor(E); - avl_rotate(B, +sign); - avl_rotate(A, -sign); - avl_set_balance_factor(A, ((sign * e <= 0) ? 0 : -e)); - avl_set_balance_factor(B, ((sign * e >= 0) ? 0 : -e)); - avl_set_balance_factor(E, 0); + avl_set_child(A, -sign, G); + avl_set_parent_balance(A, E, ((sign * e >= 0) ? 0 : -e)); + + avl_set_child(B, +sign, F); + avl_set_parent_balance(B, E, ((sign * e <= 0) ? 0 : -e)); + + avl_set_child(E, +sign, A); + avl_set_child(E, -sign, B); + avl_set_parent_balance(E, P, 0); + + if (G) + avl_set_parent(G, A); + + if (F) + avl_set_parent(F, B); + + avl_replace_child(root_ptr, P, A, E); return E; } +/* + * This function handles the growth of a subtree due to an insertion. + * + * @root_ptr + * Location of the tree's root pointer. + * + * @node + * A subtree that has increased in height by 1 due to an insertion. + * + * @parent + * Parent of @node; must not be NULL. + * + * @sign + * -1 if @node is the left child of @parent; + * +1 if @node is the right child of @parent. + * + * This function will adjust @parent's balance factor, then do a (single + * or double) rotation if necessary. The return value will be %true if + * the full AVL tree is now adequately balanced, or %false if the subtree + * rooted at @parent is now adequately balanced but has increased in + * height by 1, so the caller should continue up the tree. + * + * Note that if %false is returned, no rotation will have been done. + * Indeed, a single node insertion cannot require that more than one + * (single or double) rotation be done. + */ static AVL_INLINE bool -avl_handle_subtree_growth(struct avl_tree_node * const node, +avl_handle_subtree_growth(struct avl_tree_node ** const root_ptr, + struct avl_tree_node * const node, struct avl_tree_node * const parent, const int sign) { - /* Height of @node subtree of @parent has increased by 1. - * Adjust @parent's balance factor and check whether rotations need to - * be done. */ + int old_balance_factor, new_balance_factor; - const int old_balance_factor = avl_get_balance_factor(parent); - const int new_balance_factor = old_balance_factor + sign; + old_balance_factor = avl_get_balance_factor(parent); if (old_balance_factor == 0) { - /* Parent has increased in height but is still sufficiently - * balanced. Continue up the tree. */ avl_adjust_balance_factor(parent, sign); + /* @parent is still sufficiently balanced (-1 or +1 + * balance factor), but must have increased in height. + * Continue up the tree. */ return false; } + new_balance_factor = old_balance_factor + sign; + if (new_balance_factor == 0) { - /* Parent is balanced; nothing more to to. */ avl_adjust_balance_factor(parent, sign); + /* @parent is now perfectly balanced (0 balance factor). + * It cannot have increased in height, so there is + * nothing more to do. */ return true; } - /* FROM THIS POINT ONWARDS THE COMMENTS ASSUME sign < 0. - * The other case is symmetric --- that is, the rotations done are the - * the mirror images, all the balance factors are inverted, and left and - * right pointers are otherwise reversed. */ - - /* Parent is left-heavy (balance_factor == -2). */ + /* @parent is too left-heavy (new_balance_factor == -2) or + * too right-heavy (new_balance_factor == +2). */ + /* Test whether @node is left-heavy (-1 balance factor) or + * right-heavy (+1 balance factor). + * Note that it cannot be perfectly balanced (0 balance factor) + * because here we are under the invariant that @node has + * increased in height due to the insertion. */ if (sign * avl_get_balance_factor(node) > 0) { - /* Child node (@node, also B below) is also left-heavy. - * It must have balance_factor == -1. - * Do a clockwise ("right") rotation rooted at - * @parent (A below): + /* @node (B below) is heavy in the same direction @parent + * (A below) is heavy. + * + * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ + * The comment, diagram, and equations below assume sign < 0. + * The other case is symmetric! + * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ + * + * Do a clockwise rotation rooted at @parent (A below): * * A B * / \ / \ - * B C => D A + * B C? => D A * / \ / \ / \ - * D E F G E C + * D E? F? G?E? C? * / \ - * F G + * F? G? * * Before the rotation: * balance(A) = -2 @@ -269,25 +381,32 @@ avl_handle_subtree_growth(struct avl_tree_node * const node, * balance(B) = 0 * balance(A) = 0 */ + avl_rotate(root_ptr, parent, -sign); - avl_rotate(parent, -sign); + /* Equivalent to setting @parent's balance factor to 0. */ + avl_adjust_balance_factor(parent, -sign); /* A */ - avl_set_balance_factor(node, 0); /* B */ - avl_set_balance_factor(parent, 0); /* A */ + /* Equivalent to setting @node's balance factor to 0. */ + avl_adjust_balance_factor(node, -sign); /* B */ } else { - /* Child node (@node, also B below) is right-heavy. - * It must have balance_factor == +1. - * Do a counterclockwise ("left") rotation rooted at child node - * (B below), then a clockwise ("right") rotation rooted at - * parent node (A below). + /* @node (B below) is heavy in the direction opposite + * from the direction @parent (A below) is heavy. + * + * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ + * The comment, diagram, and equations below assume sign < 0. + * The other case is symmetric! + * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ + * + * Do a counterblockwise rotation rooted at @node (B below), + * then a clockwise rotation rooted at @parent (A below): * * A A E * / \ / \ / \ - * B C => E C => B A + * B C? => E C? => B A * / \ / \ / \ / \ - * D E B G D F G C + * D? E B G? D? F?G? C? * / \ / \ - * F G D F + * F? G? D? F? * * Before the rotation: * balance(A) = -2 @@ -309,8 +428,10 @@ avl_handle_subtree_growth(struct avl_tree_node * const node, * height(E) = x + 2 * balance(E) = 0 */ - avl_do_double_rotate(node, parent, sign); + avl_do_double_rotate(root_ptr, node, parent, -sign); } + + /* Height after rotation is unchanged; nothing more to do. */ return true; } @@ -320,36 +441,88 @@ avl_tree_rebalance_after_insert(struct avl_tree_node **root_ptr, struct avl_tree_node *inserted) { struct avl_tree_node *node, *parent; - bool done = false; + bool done; inserted->left = NULL; inserted->right = NULL; - for (node = inserted, parent = avl_get_parent(node); - parent && !done; - node = parent, parent = avl_get_parent(parent)) - { - /* Height of @node subtree has increased by 1 */ + node = inserted; + + /* Adjust balance factor of new node's parent. + * No rotation will need to be done at this level. */ + + parent = avl_get_parent(node); + if (!parent) + return; + + if (node == parent->left) + avl_adjust_balance_factor(parent, -1); + else + avl_adjust_balance_factor(parent, +1); + + if (avl_get_balance_factor(parent) == 0) + /* @parent did not change in height. Nothing more to do. */ + return; + + /* The subtree rooted at @parent increased in height by 1. */ + do { + /* Adjust balance factor of next ancestor. */ + + node = parent; + parent = avl_get_parent(node); + if (!parent) + return; + + /* The subtree rooted at @node has increased in height by 1. */ if (node == parent->left) - done = avl_handle_subtree_growth(node, parent, -1); + done = avl_handle_subtree_growth(root_ptr, node, + parent, -1); else - done = avl_handle_subtree_growth(node, parent, +1); - } - /* Due to rotations, *root_ptr may no longer be the root of the tree */ - while (avl_get_parent(*root_ptr)) - *root_ptr = avl_get_parent(*root_ptr); + done = avl_handle_subtree_growth(root_ptr, node, + parent, +1); + } while (!done); } +/* + * This function handles the shrinkage of a subtree due to a deletion. + * + * @root_ptr + * Location of the tree's root pointer. + * + * @parent + * A node in the tree, exactly one of whose subtrees has decreased + * in height by 1 due to a deletion. (This includes the case where + * one of the child pointers has become NULL, since we can consider + * the "NULL" subtree to have a height of 0.) + * + * @sign + * +1 if the left subtree of @parent has decreased in height by 1; + * -1 if the right subtree of @parent has decreased in height by 1. + * + * @left_deleted_ret + * If the return value is not NULL, this will be set to %true if the + * left subtree of the returned node has decreased in height by 1, + * or %false if the right subtree of the returned node has decreased + * in height by 1. + * + * This function will adjust @parent's balance factor, then do a (single + * or double) rotation if necessary. The return value will be NULL if + * the full AVL tree is now adequately balanced, or a pointer to the + * parent of @parent if @parent is now adequately balanced but has + * decreased in height by 1. Also in the latter case, *left_deleted_ret + * will be set. + */ static AVL_INLINE struct avl_tree_node * -avl_handle_subtree_shrink(struct avl_tree_node *parent, +avl_handle_subtree_shrink(struct avl_tree_node ** const root_ptr, + struct avl_tree_node *parent, const int sign, bool * const left_deleted_ret) { struct avl_tree_node *node; + int old_balance_factor, new_balance_factor; - const int old_balance_factor = avl_get_balance_factor(parent); - const int new_balance_factor = old_balance_factor + sign; + old_balance_factor = avl_get_balance_factor(parent); if (old_balance_factor == 0) { /* Prior to the deletion, the subtree rooted at @@ -358,7 +531,11 @@ avl_handle_subtree_shrink(struct avl_tree_node *parent, * hasn't changed. Nothing more to do. */ avl_adjust_balance_factor(parent, sign); return NULL; - } else if (new_balance_factor == 0) { + } + + new_balance_factor = old_balance_factor + sign; + + if (new_balance_factor == 0) { /* The subtree rooted at @parent is now perfectly * balanced, whereas before the deletion it was * unbalanced by 1. Its height must have decreased @@ -367,28 +544,78 @@ avl_handle_subtree_shrink(struct avl_tree_node *parent, avl_adjust_balance_factor(parent, sign); node = parent; } else { - /* The subtree rooted at @parent is now significantly - * unbalanced (by 2 in some direction). */ + /* @parent is too left-heavy (new_balance_factor == -2) or + * too right-heavy (new_balance_factor == +2). */ + node = avl_get_child(parent, sign); /* The rotations below are similar to those done during - * insertion. The only new case is the one where the - * child node has a balance factor of 0. */ + * insertion (see avl_handle_subtree_growth()), so full + * comments are not provided. The only new case is the + * one where @node has a balance factor of 0, and that is + * commented. */ if (sign * avl_get_balance_factor(node) >= 0) { - avl_rotate(parent, -sign); + + avl_rotate(root_ptr, parent, -sign); if (avl_get_balance_factor(node) == 0) { - avl_set_balance_factor(node, -sign); - avl_set_balance_factor(parent, +sign); + /* + * @node (B below) is perfectly balanced. + * + * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ + * The comment, diagram, and equations + * below assume sign < 0. The other case + * is symmetric! + * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ + * + * Do a clockwise rotation rooted at + * @parent (A below): + * + * A B + * / \ / \ + * B C? => D A + * / \ / \ / \ + * D E F? G?E C? + * / \ + * F? G? + * + * Before the rotation: + * balance(A) = -2 + * balance(B) = 0 + * Let x = height(C). Then: + * height(B) = x + 2 + * height(D) = x + 1 + * height(E) = x + 1 + * max(height(F), height(G)) = x. + * + * After the rotation: + * height(D) = max(height(F), height(G)) + 1 + * = x + 1 + * height(A) = max(height(E), height(C)) + 1 + * = max(x + 1, x) + 1 = x + 2 + * balance(A) = -1 + * balance(B) = +1 + */ + + /* A: -2 => -1 (sign < 0) + * or +2 => +1 (sign > 0) + * No change needed --- that's the same as + * old_balance_factor. */ + + /* B: 0 => +1 (sign < 0) + * or 0 => -1 (sign > 0) */ + avl_adjust_balance_factor(node, -sign); + /* Height is unchanged; nothing more to do. */ return NULL; } else { - avl_set_balance_factor(node, 0); - avl_set_balance_factor(parent, 0); + avl_adjust_balance_factor(parent, -sign); + avl_adjust_balance_factor(node, -sign); } } else { - node = avl_do_double_rotate(node, parent, sign); + node = avl_do_double_rotate(root_ptr, node, + parent, -sign); } } parent = avl_get_parent(node); @@ -397,106 +624,144 @@ avl_handle_subtree_shrink(struct avl_tree_node *parent, return parent; } -/* Swaps node X, which must have 2 children, with its in-order successor. - * This adjusts all the necessary pointers and balance factors. */ -static AVL_INLINE void -avl_tree_swap_with_successor(struct avl_tree_node * const X) +/* Swaps node X, which must have 2 children, with its in-order successor, then + * unlinks node X. Returns the parent of X just before unlinking, without its + * balance factor having been updated to account for the unlink. */ +static AVL_INLINE struct avl_tree_node * +avl_tree_swap_with_successor(struct avl_tree_node **root_ptr, + struct avl_tree_node *X, + bool *left_deleted_ret) { - struct avl_tree_node * const Y = avl_tree_next_in_order(X); - struct avl_tree_node * const Y_right = Y->right; - struct avl_tree_node * const Y_parent = avl_get_parent(Y); - struct avl_tree_node * const X_parent = avl_get_parent(X); - const int Y_balance_factor = avl_get_balance_factor(Y); - - /* Set child pointer to Y when placed in X's position */ - if (X_parent) { - if (X == X_parent->left) - X_parent->left = Y; - else - X_parent->right = Y; - } - - /* Set child pointer to X when placed in Y's position. Also set - * the right pointer of Y (it may point to X if the nodes are - * adjacent) */ - if (Y_parent != X) { - if (Y == Y_parent->left) - Y_parent->left = X; - else - Y_parent->right = X; - Y->right = X->right; + struct avl_tree_node *Y, *ret; + + Y = X->right; + if (!Y->left) { + /* + * P? P? P? + * | | | + * X Y Y + * / \ / \ / \ + * A Y => A X => A B? + * / \ / \ + * (0) B? (0) B? + * + * [ X unlinked, Y returned ] + */ + ret = Y; + *left_deleted_ret = false; } else { - Y->right = X; - } - - /* Set parent pointer to X when placed in Y's position */ - if (Y_right) - avl_set_parent(Y_right, X); - - /* Note: Y has no left child since it is the in-order sucessor of X. */ + struct avl_tree_node *Q; + + do { + Q = Y; + Y = Y->left; + } while (Y->left); + + /* + * P? P? P? + * | | | + * X Y Y + * / \ / \ / \ + * A ... => A ... => A ... + * | | | + * Q Q Q + * / / / + * Y X B? + * / \ / \ + * (0) B? (0) B? + * + * + * [ X unlinked, Q returned ] + */ - /* Set parent pointers to Y when placed in X's position, as well as X's - * parent when placed in Y's position. */ - avl_set_parent(X->left, Y); - if (X->right != Y) { + Q->left = Y->right; + if (Q->left) + avl_set_parent(Q->left, Q); + Y->right = X->right; avl_set_parent(X->right, Y); - avl_set_parent(X, Y_parent); - } else { - avl_set_parent(X, Y); + ret = Q; + *left_deleted_ret = true; } - avl_set_parent(Y, X_parent); Y->left = X->left; - avl_set_balance_factor(Y, avl_get_balance_factor(X)); + avl_set_parent(X->left, Y); + + Y->parent_balance = X->parent_balance; + avl_replace_child(root_ptr, avl_get_parent(X), X, Y); - X->left = NULL; - X->right = Y_right; - avl_set_balance_factor(X, Y_balance_factor); + return ret; } -/* Removes the specified @node from the AVL tree. @root_ptr must point to the - * pointer to the root node of the tree; *root_ptr may change if the tree is - * rebalanced. +/* + * Removes an item from the specified AVL tree. * - * This *only* removes the node and rebalances the tree; it does not free - * memory, nor does it do the equivalent of avl_tree_node_set_unlinked(). */ + * @root_ptr + * Location of the AVL tree's root pointer. Indirection is needed + * because the root node may change if the tree needed to be rebalanced + * because of the deletion or if @node was the root node. + * + * @node + * Pointer to the `struct avl_tree_node' embedded in the item to + * remove from the tree. + * + * Note: This function *only* removes the node and rebalances the tree. + * It does not free any memory, nor does it do the equivalent of + * avl_tree_node_set_unlinked(). + */ void avl_tree_remove(struct avl_tree_node **root_ptr, struct avl_tree_node *node) { - struct avl_tree_node *child, *parent; - bool left_deleted; - - if (node->left && node->right) - avl_tree_swap_with_successor(node); - - /* Unlink @node */ - child = node->left ? node->left : node->right; - parent = avl_get_parent(node); - if (parent) { - if (node == parent->left) { - parent->left = child; - left_deleted = true; + struct avl_tree_node *parent; + bool left_deleted = false; + + if (node->left && node->right) { + /* @node is fully internal, with two children. Swap it + * with its in-order successor (which must exist in the + * right subtree of @node and can have, at most, a right + * child), then unlink @node. */ + parent = avl_tree_swap_with_successor(root_ptr, node, + &left_deleted); + /* @parent is now the parent of what was @node's in-order + * successor. It cannot be NULL, since @node itself was + * an ancestor of its in-order successor. + * @left_deleted has been set to %true if @node's + * in-order successor was the left child of @parent, + * otherwise %false. */ + } else { + struct avl_tree_node *child; + + /* @node is missing at least one child. Unlink it. Set + * @parent to @node's parent, and set @left_deleted to + * reflect which child of @parent @node was. Or, if + * @node was the root node, simply update the root node + * and return. */ + child = node->left ? node->left : node->right; + parent = avl_get_parent(node); + if (parent) { + if (node == parent->left) { + parent->left = child; + left_deleted = true; + } else { + parent->right = child; + left_deleted = false; + } + if (child) + avl_set_parent(child, parent); } else { - parent->right = child; - left_deleted = false; + if (child) + avl_set_parent(child, parent); + *root_ptr = child; + return; } - } else { - *root_ptr = child; } - if (child) - avl_set_parent(child, parent); - /* Rebalance the tree */ - while (parent) { + /* Rebalance the tree. */ + do { if (left_deleted) - parent = avl_handle_subtree_shrink(parent, +1, &left_deleted); + parent = avl_handle_subtree_shrink(root_ptr, parent, + +1, &left_deleted); else - parent = avl_handle_subtree_shrink(parent, -1, &left_deleted); - } - - /* Due to rotations, *root_ptr may no longer point to the root of the - * tree. Fix it. */ - if (*root_ptr) - while (avl_get_parent(*root_ptr)) - *root_ptr = avl_get_parent(*root_ptr); + parent = avl_handle_subtree_shrink(root_ptr, parent, + -1, &left_deleted); + } while (parent); }