wimlib.net Git - wimlib/blob - src/avl_tree.c

   1 /*
   2  * avl_tree.c
   3  *
   4  * Intrusive, nonrecursive AVL tree data structure (self-balancing binary search
   5  * tree), implementation file.
   6  *
   7  * Author:  Eric Biggers
   8  * Year:    2014
   9  *
  10  * This file is placed into the public domain.  You can do whatever you want
  11  * with it.
  12  */
  13
  14 #include <wimlib/avl_tree.h>
  15
  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)
  20 {
  21         const struct avl_tree_node *first = root;
  22
  23         if (first)
  24                 while (first->left)
  25                         first = first->left;
  26         return (struct avl_tree_node *)first;
  27 }
  28
  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)
  33 {
  34         const struct avl_tree_node *next;
  35
  36         if (prev->right)
  37                 for (next = prev->right;
  38                      next->left;
  39                      next = next->left)
  40                         ;
  41         else
  42                 for (next = avl_get_parent(prev);
  43                      next && prev == next->right;
  44                      prev = next, next = avl_get_parent(next))
  45                         ;
  46         return (struct avl_tree_node *)next;
  47 }
  48
  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)
  52 {
  53         const struct avl_tree_node *first = root;
  54
  55         if (first)
  56                 while (first->left || first->right)
  57                         first = first->left ? first->left : first->right;
  58
  59         return (struct avl_tree_node *)first;
  60 }
  61
  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)
  69 {
  70         const struct avl_tree_node *next = prev_parent;
  71
  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)
  76                         ;
  77         return (struct avl_tree_node *)next;
  78 }
  79
  80 /* Returns the left child (sign < 0) or the right child (sign > 0) of the
  81  * specified AVL tree node.
  82  * Note: for all calls of this, 'sign' is constant at compilation time,
  83  * so the compiler can remove the conditional.  */
  84 static AVL_INLINE struct avl_tree_node *
  85 avl_get_child(const struct avl_tree_node *parent, int sign)
  86 {
  87         if (sign < 0)
  88                 return parent->left;
  89         else
  90                 return parent->right;
  91 }
  92
  93 /* Sets the left child (sign < 0) or the right child (sign > 0) of the
  94  * specified AVL tree node.
  95  * Note: for all calls of this, 'sign' is constant at compilation time,
  96  * so the compiler can remove the conditional.  */
  97 static AVL_INLINE void
  98 avl_set_child(struct avl_tree_node *parent, int sign,
  99               struct avl_tree_node *child)
 100 {
 101         if (sign < 0)
 102                 parent->left = child;
 103         else
 104                 parent->right = child;
 105 }
 106
 107 /* Sets the parent and balance factor of the specified AVL tree node.  */
 108 static AVL_INLINE void
 109 avl_set_parent_balance(struct avl_tree_node *node, struct avl_tree_node *parent,
 110                        int balance_factor)
 111 {
 112         node->parent_balance = (uintptr_t)parent | (balance_factor + 1);
 113 }
 114
 115 /* Sets the parent of the specified AVL tree node.  */
 116 static AVL_INLINE void
 117 avl_set_parent(struct avl_tree_node *node, struct avl_tree_node *parent)
 118 {
 119         node->parent_balance = (uintptr_t)parent | (node->parent_balance & 3);
 120 }
 121
 122 /* Returns the balance factor of the specified AVL tree node --- that is, the
 123  * height of its right subtree minus the height of its left subtree.  */
 124 static AVL_INLINE int
 125 avl_get_balance_factor(const struct avl_tree_node *node)
 126 {
 127         return (int)(node->parent_balance & 3) - 1;
 128 }
 129
 130 /* Sets the balance factor of the specified AVL tree node.  This must be
 131  * -1, 0, or 1.  */
 132 static AVL_INLINE void
 133 avl_set_balance_factor(struct avl_tree_node *node, int balance_factor)
 134 {
 135         node->parent_balance =
 136                 (node->parent_balance & ~3) | (balance_factor + 1);
 137 }
 138
 139 /* Adds @amount to the balance factor of the specified AVL tree node.
 140  * The caller must ensure this still results in a valid balance factor
 141  * (-1, 0, or 1).  */
 142 static AVL_INLINE void
 143 avl_adjust_balance_factor(struct avl_tree_node *node, int amount)
 144 {
 145         node->parent_balance += amount;
 146 }
 147
 148 static AVL_INLINE void
 149 avl_replace_child(struct avl_tree_node **root_ptr,
 150                   struct avl_tree_node *parent,
 151                   struct avl_tree_node *old_child,
 152                   struct avl_tree_node *new_child)
 153 {
 154         if (parent) {
 155                 if (old_child == parent->left)
 156                         parent->left = new_child;
 157                 else
 158                         parent->right = new_child;
 159         } else {
 160                 *root_ptr = new_child;
 161         }
 162 }
 163
 164 /*
 165  * Template for performing a single rotation ---
 166  *
 167  * sign > 0:  Rotate clockwise (right) rooted at A:
 168  *
 169  *           P?            P?
 170  *           |             |
 171  *           A             B
 172  *          / \           / \
 173  *         B   C?  =>    D?  A
 174  *        / \               / \
 175  *       D?  E?            E?  C?
 176  *
 177  * (nodes marked with ? may not exist)
 178  *
 179  * sign < 0:  Rotate counterclockwise (left) rooted at A:
 180  *
 181  *           P?            P?
 182  *           |             |
 183  *           A             B
 184  *          / \           / \
 185  *         C?  B   =>    A   D?
 186  *            / \       / \
 187  *           E?  D?    C?  E?
 188  *
 189  * This updates pointers but not balance factors!
 190  */
 191 static AVL_INLINE void
 192 avl_rotate(struct avl_tree_node ** const root_ptr,
 193            struct avl_tree_node * const A, const int sign)
 194 {
 195         struct avl_tree_node * const B = avl_get_child(A, -sign);
 196         struct avl_tree_node * const E = avl_get_child(B, +sign);
 197         struct avl_tree_node * const P = avl_get_parent(A);
 198
 199         avl_set_child(A, -sign, E);
 200         avl_set_parent(A, B);
 201
 202         avl_set_child(B, +sign, A);
 203         avl_set_parent(B, P);
 204
 205         if (E)
 206                 avl_set_parent(E, A);
 207
 208         avl_replace_child(root_ptr, P, A, B);
 209 }
 210
 211 /*
 212  * Template for performing a double rotation ---
 213  *
 214  * sign > 0:  Rotate counterclockwise (left) rooted at B, then
 215  *                   clockwise (right) rooted at A:
 216  *
 217  *           P?            P?          P?
 218  *           |             |           |
 219  *           A             A           E
 220  *          / \           / \        /   \
 221  *         B   C?  =>    E   C? =>  B     A
 222  *        / \           / \        / \   / \
 223  *       D?  E         B   G?     D?  F?G?  C?
 224  *          / \       / \
 225  *         F?  G?    D?  F?
 226  *
 227  * (nodes marked with ? may not exist)
 228  *
 229  * sign < 0:  Rotate clockwise (right) rooted at B, then
 230  *                   counterclockwise (left) rooted at A:
 231  *
 232  *         P?          P?              P?
 233  *         |           |               |
 234  *         A           A               E
 235  *        / \         / \            /   \
 236  *       C?  B   =>  C?  E    =>    A     B
 237  *          / \         / \        / \   / \
 238  *         E   D?      G?  B      C?  G?F?  D?
 239  *        / \             / \
 240  *       G?  F?          F?  D?
 241  *
 242  * Returns a pointer to E and updates balance factors.  Except for those
 243  * two things, this function is equivalent to:
 244  *      avl_rotate(root_ptr, B, -sign);
 245  *      avl_rotate(root_ptr, A, +sign);
 246  *
 247  * See comment in avl_handle_subtree_growth() for explanation of balance
 248  * factor updates.
 249  */
 250 static AVL_INLINE struct avl_tree_node *
 251 avl_do_double_rotate(struct avl_tree_node ** const root_ptr,
 252                      struct avl_tree_node * const B,
 253                      struct avl_tree_node * const A, const int sign)
 254 {
 255         struct avl_tree_node * const E = avl_get_child(B, +sign);
 256         struct avl_tree_node * const F = avl_get_child(E, -sign);
 257         struct avl_tree_node * const G = avl_get_child(E, +sign);
 258         struct avl_tree_node * const P = avl_get_parent(A);
 259         const int e = avl_get_balance_factor(E);
 260
 261         avl_set_child(A, -sign, G);
 262         avl_set_parent_balance(A, E, ((sign * e >= 0) ? 0 : -e));
 263
 264         avl_set_child(B, +sign, F);
 265         avl_set_parent_balance(B, E, ((sign * e <= 0) ? 0 : -e));
 266
 267         avl_set_child(E, +sign, A);
 268         avl_set_child(E, -sign, B);
 269         avl_set_parent_balance(E, P, 0);
 270
 271         if (G)
 272                 avl_set_parent(G, A);
 273
 274         if (F)
 275                 avl_set_parent(F, B);
 276
 277         avl_replace_child(root_ptr, P, A, E);
 278
 279         return E;
 280 }
 281
 282 /*
 283  * This function handles the growth of a subtree due to an insertion.
 284  *
 285  * @root_ptr
 286  *      Location of the tree's root pointer.
 287  *
 288  * @node
 289  *      A subtree that has increased in height by 1 due to an insertion.
 290  *
 291  * @parent
 292  *      Parent of @node; must not be NULL.
 293  *
 294  * @sign
 295  *      -1 if @node is the left child of @parent;
 296  *      +1 if @node is the right child of @parent.
 297  *
 298  * This function will adjust @parent's balance factor, then do a (single
 299  * or double) rotation if necessary.  The return value will be %true if
 300  * the full AVL tree is now adequately balanced, or %false if the subtree
 301  * rooted at @parent is now adequately balanced but has increased in
 302  * height by 1, so the caller should continue up the tree.
 303  *
 304  * Note that if %false is returned, no rotation will have been done.
 305  * Indeed, a single node insertion cannot require that more than one
 306  * (single or double) rotation be done.
 307  */
 308 static AVL_INLINE bool
 309 avl_handle_subtree_growth(struct avl_tree_node ** const root_ptr,
 310                           struct avl_tree_node * const node,
 311                           struct avl_tree_node * const parent,
 312                           const int sign)
 313 {
 314         int old_balance_factor, new_balance_factor;
 315
 316         old_balance_factor = avl_get_balance_factor(parent);
 317
 318         if (old_balance_factor == 0) {
 319                 avl_adjust_balance_factor(parent, sign);
 320                 /* @parent is still sufficiently balanced (-1 or +1
 321                  * balance factor), but must have increased in height.
 322                  * Continue up the tree.  */
 323                 return false;
 324         }
 325
 326         new_balance_factor = old_balance_factor + sign;
 327
 328         if (new_balance_factor == 0) {
 329                 avl_adjust_balance_factor(parent, sign);
 330                 /* @parent is now perfectly balanced (0 balance factor).
 331                  * It cannot have increased in height, so there is
 332                  * nothing more to do.  */
 333                 return true;
 334         }
 335
 336         /* @parent is too left-heavy (new_balance_factor == -2) or
 337          * too right-heavy (new_balance_factor == +2).  */
 338
 339         /* Test whether @node is left-heavy (-1 balance factor) or
 340          * right-heavy (+1 balance factor).
 341          * Note that it cannot be perfectly balanced (0 balance factor)
 342          * because here we are under the invariant that @node has
 343          * increased in height due to the insertion.  */
 344         if (sign * avl_get_balance_factor(node) > 0) {
 345
 346                 /* @node (B below) is heavy in the same direction @parent
 347                  * (A below) is heavy.
 348                  *
 349                  * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 350                  * The comment, diagram, and equations below assume sign < 0.
 351                  * The other case is symmetric!
 352                  * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 353                  *
 354                  * Do a clockwise rotation rooted at @parent (A below):
 355                  *
 356                  *           A              B
 357                  *          / \           /   \
 358                  *         B   C?  =>    D     A
 359                  *        / \           / \   / \
 360                  *       D   E?        F?  G?E?  C?
 361                  *      / \
 362                  *     F?  G?
 363                  *
 364                  * Before the rotation:
 365                  *      balance(A) = -2
 366                  *      balance(B) = -1
 367                  * Let x = height(C).  Then:
 368                  *      height(B) = x + 2
 369                  *      height(D) = x + 1
 370                  *      height(E) = x
 371                  *      max(height(F), height(G)) = x.
 372                  *
 373                  * After the rotation:
 374                  *      height(D) = max(height(F), height(G)) + 1
 375                  *                = x + 1
 376                  *      height(A) = max(height(E), height(C)) + 1
 377                  *                = max(x, x) + 1 = x + 1
 378                  *      balance(B) = 0
 379                  *      balance(A) = 0
 380                  */
 381                 avl_rotate(root_ptr, parent, -sign);
 382
 383                 /* Equivalent to:
 384                  *    avl_set_balance_factor(parent, 0);  */
 385                 avl_adjust_balance_factor(parent, -sign); /* A */
 386
 387                 /* Equivalent to:
 388                  *    avl_set_balance_factor(node, 0);  */
 389                 avl_adjust_balance_factor(node, -sign);   /* B */
 390         } else {
 391                 /* @node (B below) is heavy in the direction opposite
 392                  * from the direction @parent (A below) is heavy.
 393                  *
 394                  * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 395                  * The comment, diagram, and equations below assume sign < 0.
 396                  * The other case is symmetric!
 397                  * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 398                  *
 399                  * Do a counterblockwise rotation rooted at @node (B below),
 400                  * then a clockwise rotation rooted at @parent (A below):
 401                  *
 402                  *           A             A           E
 403                  *          / \           / \        /   \
 404                  *         B   C?  =>    E   C? =>  B     A
 405                  *        / \           / \        / \   / \
 406                  *       D?  E         B   G?     D?  F?G?  C?
 407                  *          / \       / \
 408                  *         F?  G?    D?  F?
 409                  *
 410                  * Before the rotation:
 411                  *      balance(A) = -2
 412                  *      balance(B) = +1
 413                  * Let x = height(C).  Then:
 414                  *      height(B) = x + 2
 415                  *      height(E) = x + 1
 416                  *      height(D) = x
 417                  *      max(height(F), height(G)) = x
 418                  *
 419                  * After both rotations:
 420                  *      height(A) = max(height(G), height(C)) + 1
 421                  *                = x + 1
 422                  *      balance(A) = balance(E{orig}) >= 0 ? 0 : -balance(E{orig})
 423                  *      height(B) = max(height(D), height(F)) + 1
 424                  *                = x + 1
 425                  *      balance(B) = balance(E{orig} <= 0) ? 0 : -balance(E{orig})
 426                  *
 427                  *      height(E) = x + 2
 428                  *      balance(E) = 0
 429                  */
 430                 avl_do_double_rotate(root_ptr, node, parent, -sign);
 431         }
 432
 433         /* Height after rotation is unchanged; nothing more to do.  */
 434         return true;
 435 }
 436
 437 /* Rebalance the tree after insertion of the specified node.  */
 438 void
 439 avl_tree_rebalance_after_insert(struct avl_tree_node **root_ptr,
 440                                 struct avl_tree_node *inserted)
 441 {
 442         struct avl_tree_node *node, *parent;
 443         bool done;
 444
 445         inserted->left = NULL;
 446         inserted->right = NULL;
 447
 448         node = inserted;
 449
 450         /* Adjust balance factor of new node's parent.
 451          * No rotation will need to be done at this level.  */
 452
 453         parent = avl_get_parent(node);
 454         if (!parent)
 455                 return;
 456
 457         if (node == parent->left)
 458                 avl_adjust_balance_factor(parent, -1);
 459         else
 460                 avl_adjust_balance_factor(parent, +1);
 461
 462         if (avl_get_balance_factor(parent) == 0)
 463                 /* @parent did not change in height.  Nothing more to do.  */
 464                 return;
 465
 466         /* The subtree rooted at @parent increased in height by 1.  */
 467
 468         do {
 469                 /* Adjust balance factor of next ancestor.  */
 470
 471                 node = parent;
 472                 parent = avl_get_parent(node);
 473                 if (!parent)
 474                         return;
 475
 476                 /* The subtree rooted at @node has increased in height by 1.  */
 477                 if (node == parent->left)
 478                         done = avl_handle_subtree_growth(root_ptr, node,
 479                                                          parent, -1);
 480                 else
 481                         done = avl_handle_subtree_growth(root_ptr, node,
 482                                                          parent, +1);
 483         } while (!done);
 484 }
 485
 486 /*
 487  * This function handles the shrinkage of a subtree due to a deletion.
 488  *
 489  * @root_ptr
 490  *      Location of the tree's root pointer.
 491  *
 492  * @parent
 493  *      A node in the tree, exactly one of whose subtrees has decreased
 494  *      in height by 1 due to a deletion.  (This includes the case where
 495  *      one of the child pointers has become NULL, since we can consider
 496  *      the "NULL" subtree to have a height of 0.)
 497  *
 498  * @sign
 499  *      +1 if the left subtree of @parent has decreased in height by 1;
 500  *      -1 if the right subtree of @parent has decreased in height by 1.
 501  *
 502  * @left_deleted_ret
 503  *      If the return value is not NULL, this will be set to %true if the
 504  *      left subtree of the returned node has decreased in height by 1,
 505  *      or %false if the right subtree of the returned node has decreased
 506  *      in height by 1.
 507  *
 508  * This function will adjust @parent's balance factor, then do a (single
 509  * or double) rotation if necessary.  The return value will be NULL if
 510  * the full AVL tree is now adequately balanced, or a pointer to the
 511  * parent of @parent if @parent is now adequately balanced but has
 512  * decreased in height by 1.  Also in the latter case, *left_deleted_ret
 513  * will be set.
 514  */
 515 static AVL_INLINE struct avl_tree_node *
 516 avl_handle_subtree_shrink(struct avl_tree_node ** const root_ptr,
 517                           struct avl_tree_node *parent,
 518                           const int sign,
 519                           bool * const left_deleted_ret)
 520 {
 521         struct avl_tree_node *node;
 522         int old_balance_factor, new_balance_factor;
 523
 524         old_balance_factor = avl_get_balance_factor(parent);
 525
 526         if (old_balance_factor == 0) {
 527                 /* Prior to the deletion, the subtree rooted at
 528                  * @parent was perfectly balanced.  It's now
 529                  * unbalanced by 1, but that's okay and its height
 530                  * hasn't changed.  Nothing more to do.  */
 531                 avl_adjust_balance_factor(parent, sign);
 532                 return NULL;
 533         }
 534
 535         new_balance_factor = old_balance_factor + sign;
 536
 537         if (new_balance_factor == 0) {
 538                 /* The subtree rooted at @parent is now perfectly
 539                  * balanced, whereas before the deletion it was
 540                  * unbalanced by 1.  Its height must have decreased
 541                  * by 1.  No rotation is needed at this location,
 542                  * but continue up the tree.  */
 543                 avl_adjust_balance_factor(parent, sign);
 544                 node = parent;
 545         } else {
 546                 /* @parent is too left-heavy (new_balance_factor == -2) or
 547                  * too right-heavy (new_balance_factor == +2).  */
 548
 549                 node = avl_get_child(parent, sign);
 550
 551                 /* The rotations below are similar to those done during
 552                  * insertion (see avl_handle_subtree_growth()), so full
 553                  * comments are not provided.  The only new case is the
 554                  * one where @node has a balance factor of 0, and that is
 555                  * commented.  */
 556
 557                 if (sign * avl_get_balance_factor(node) >= 0) {
 558
 559                         avl_rotate(root_ptr, parent, -sign);
 560
 561                         if (avl_get_balance_factor(node) == 0) {
 562                                 /*
 563                                  * @node (B below) is perfectly balanced.
 564                                  *
 565                                  * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 566                                  * The comment, diagram, and equations
 567                                  * below assume sign < 0.  The other case
 568                                  * is symmetric!
 569                                  * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 570                                  *
 571                                  * Do a clockwise rotation rooted at
 572                                  * @parent (A below):
 573                                  *
 574                                  *           A              B
 575                                  *          / \           /   \
 576                                  *         B   C?  =>    D     A
 577                                  *        / \           / \   / \
 578                                  *       D   E         F?  G?E   C?
 579                                  *      / \
 580                                  *     F?  G?
 581                                  *
 582                                  * Before the rotation:
 583                                  *      balance(A) = -2
 584                                  *      balance(B) =  0
 585                                  * Let x = height(C).  Then:
 586                                  *      height(B) = x + 2
 587                                  *      height(D) = x + 1
 588                                  *      height(E) = x + 1
 589                                  *      max(height(F), height(G)) = x.
 590                                  *
 591                                  * After the rotation:
 592                                  *      height(D) = max(height(F), height(G)) + 1
 593                                  *                = x + 1
 594                                  *      height(A) = max(height(E), height(C)) + 1
 595                                  *                = max(x + 1, x) + 1 = x + 2
 596                                  *      balance(A) = -1
 597                                  *      balance(B) = +1
 598                                  */
 599
 600                                 /* A: -2 => -1 (sign < 0)
 601                                  * or +2 => +1 (sign > 0)
 602                                  * No change needed --- that's the same as
 603                                  * old_balance_factor.  */
 604
 605                                 /* B: 0 => +1 (sign < 0)
 606                                  * or 0 => -1 (sign > 0)  */
 607                                 avl_adjust_balance_factor(node, -sign);
 608
 609                                 /* Height is unchanged; nothing more to do.  */
 610                                 return NULL;
 611                         } else {
 612                                 avl_adjust_balance_factor(parent, -sign);
 613                                 avl_adjust_balance_factor(node, -sign);
 614                         }
 615                 } else {
 616                         node = avl_do_double_rotate(root_ptr, node,
 617                                                     parent, -sign);
 618                 }
 619         }
 620         parent = avl_get_parent(node);
 621         if (parent)
 622                 *left_deleted_ret = (node == parent->left);
 623         return parent;
 624 }
 625
 626 /* Swaps node X, which must have 2 children, with its in-order successor, then
 627  * unlinks node X.  Returns the parent of X just before unlinking, without its
 628  * balance factor having been updated to account for the unlink.  */
 629 static AVL_INLINE struct avl_tree_node *
 630 avl_tree_swap_with_successor(struct avl_tree_node **root_ptr,
 631                              struct avl_tree_node *X,
 632                              bool *left_deleted_ret)
 633 {
 634         struct avl_tree_node *Y, *ret;
 635
 636         Y = X->right;
 637         if (!Y->left) {
 638                 /*
 639                  *     P?           P?           P?
 640                  *     |            |            |
 641                  *     X            Y            Y
 642                  *    / \          / \          / \
 643                  *   A   Y    =>  A   X    =>  A   B?
 644                  *      / \          / \
 645                  *    (0)  B?      (0)  B?
 646                  *
 647                  * [ X unlinked, Y returned ]
 648                  */
 649                 ret = Y;
 650                 *left_deleted_ret = false;
 651         } else {
 652                 struct avl_tree_node *Q;
 653
 654                 do {
 655                         Q = Y;
 656                         Y = Y->left;
 657                 } while (Y->left);
 658
 659                 /*
 660                  *     P?           P?           P?
 661                  *     |            |            |
 662                  *     X            Y            Y
 663                  *    / \          / \          / \
 664                  *   A   ...  =>  A  ...   =>  A  ...
 665                  *       |            |            |
 666                  *       Q            Q            Q
 667                  *      /            /            /
 668                  *     Y            X            B?
 669                  *    / \          / \
 670                  *  (0)  B?      (0)  B?
 671                  *
 672                  *
 673                  * [ X unlinked, Q returned ]
 674                  */
 675
 676                 Q->left = Y->right;
 677                 if (Q->left)
 678                         avl_set_parent(Q->left, Q);
 679                 Y->right = X->right;
 680                 avl_set_parent(X->right, Y);
 681                 ret = Q;
 682                 *left_deleted_ret = true;
 683         }
 684
 685         Y->left = X->left;
 686         avl_set_parent(X->left, Y);
 687
 688         Y->parent_balance = X->parent_balance;
 689         avl_replace_child(root_ptr, avl_get_parent(X), X, Y);
 690
 691         return ret;
 692 }
 693
 694 /*
 695  * Removes an item from the specified AVL tree.
 696  *
 697  * @root_ptr
 698  *      Location of the AVL tree's root pointer.  Indirection is needed
 699  *      because the root node may change if the tree needed to be rebalanced
 700  *      because of the deletion or if @node was the root node.
 701  *
 702  * @node
 703  *      Pointer to the `struct avl_tree_node' embedded in the item to
 704  *      remove from the tree.
 705  *
 706  * Note: This function *only* removes the node and rebalances the tree.
 707  * It does not free any memory, nor does it do the equivalent of
 708  * avl_tree_node_set_unlinked().
 709  */
 710 void
 711 avl_tree_remove(struct avl_tree_node **root_ptr, struct avl_tree_node *node)
 712 {
 713         struct avl_tree_node *parent;
 714         bool left_deleted = false;
 715
 716         if (node->left && node->right) {
 717                 /* @node is fully internal, with two children.  Swap it
 718                  * with its in-order successor (which must exist in the
 719                  * right subtree of @node and can have, at most, a right
 720                  * child), then unlink @node.  */
 721                 parent = avl_tree_swap_with_successor(root_ptr, node,
 722                                                       &left_deleted);
 723                 /* @parent is now the parent of what was @node's in-order
 724                  * successor.  It cannot be NULL, since @node itself was
 725                  * an ancestor of its in-order successor.
 726                  * @left_deleted has been set to %true if @node's
 727                  * in-order successor was the left child of @parent,
 728                  * otherwise %false.  */
 729         } else {
 730                 struct avl_tree_node *child;
 731
 732                 /* @node is missing at least one child.  Unlink it.  Set
 733                  * @parent to @node's parent, and set @left_deleted to
 734                  * reflect which child of @parent @node was.  Or, if
 735                  * @node was the root node, simply update the root node
 736                  * and return.  */
 737                 child = node->left ? node->left : node->right;
 738                 parent = avl_get_parent(node);
 739                 if (parent) {
 740                         if (node == parent->left) {
 741                                 parent->left = child;
 742                                 left_deleted = true;
 743                         } else {
 744                                 parent->right = child;
 745                                 left_deleted = false;
 746                         }
 747                         if (child)
 748                                 avl_set_parent(child, parent);
 749                 } else {
 750                         if (child)
 751                                 avl_set_parent(child, parent);
 752                         *root_ptr = child;
 753                         return;
 754                 }
 755         }
 756
 757         /* Rebalance the tree.  */
 758         do {
 759                 if (left_deleted)
 760                         parent = avl_handle_subtree_shrink(root_ptr, parent,
 761                                                            +1, &left_deleted);
 762                 else
 763                         parent = avl_handle_subtree_shrink(root_ptr, parent,
 764                                                            -1, &left_deleted);
 765         } while (parent);
 766 }