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