avl_tree: Cleanup and improve comments
[wimlib] / 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 }