src/avl.c

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