src/rbt.c

   1 #include "a/rbt.h"
   2
   3 /*
   4 red-black trees properties: https://en.wikipedia.org/wiki/Rbtree
   5
   6  1) A node is either red or black
   7  2) The root is black
   8  3) All leaves (null) are black
   9  4) Both children of every red node are black
  10  5) Every simple path from root to leaves contains the same number of black nodes.
  11
  12  4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two
  13  consecutive red nodes in a path and every red node is therefore followed by
  14  a black. So if B is the number of black nodes on every simple path (as per
  15  5), then the longest possible path due to 4 is 2B.
  16
  17  We shall indicate color with case, where black nodes are uppercase and red
  18  nodes will be lowercase. Unknown color nodes shall be drawn as red within
  19  parentheses and have some accompanying text comment.
  20 */
  21
  22 /* Replaces the child of the specified red–black tree node. */
  23 static A_INLINE void a_rbt_new_child(a_rbt *root, a_rbt_node *parent, a_rbt_node *node, a_rbt_node *newnode)
  24 {
  25     if (parent)
  26     {
  27         if (parent->left == node)
  28         {
  29             parent->left = newnode;
  30         }
  31         else
  32         {
  33             parent->right = newnode;
  34         }
  35     }
  36     else
  37     {
  38         root->node = newnode;
  39     }
  40 }
  41
  42 /* Sets the parent and color of the specified red–black tree node. */
  43 static A_INLINE void a_rbt_set_parent_color(a_rbt_node *node, a_rbt_node *parent, unsigned int color)
  44 {
  45 #if defined(A_SIZE_POINTER) && (A_SIZE_POINTER + 0 > 1)
  46     node->_parent = (a_uptr)parent | color;
  47 #else /* !A_SIZE_POINTER */
  48     node->parent = parent;
  49     node->color = color;
  50 #endif /* A_SIZE_POINTER */
  51 }
  52
  53 /* Sets the parent of the specified red–black tree node. */
  54 static A_INLINE void a_rbt_set_parent(a_rbt_node *node, a_rbt_node *parent)
  55 {
  56 #if defined(A_SIZE_POINTER) && (A_SIZE_POINTER + 0 > 1)
  57     node->_parent = (a_uptr)parent | (node->_parent & 1);
  58 #else /* !A_SIZE_POINTER */
  59     node->parent = parent;
  60 #endif /* A_SIZE_POINTER */
  61 }
  62
  63 /* Returns the color of the specified red–black tree node. */
  64 static A_INLINE unsigned int a_rbt_color(a_rbt_node const *node)
  65 {
  66 #if defined(A_SIZE_POINTER) && (A_SIZE_POINTER + 0 > 1)
  67     return (unsigned int)(node->_parent & 1);
  68 #else /* !A_SIZE_POINTER */
  69     return node->color;
  70 #endif /* A_SIZE_POINTER */
  71 }
  72
  73 /* Sets the black color of the specified red–black tree node. */
  74 static A_INLINE void a_rbt_set_black(a_rbt_node *node)
  75 {
  76 #if defined(A_SIZE_POINTER) && (A_SIZE_POINTER + 0 > 1)
  77     node->_parent |= A_RBT_B;
  78 #else /* !A_SIZE_POINTER */
  79     node->color = A_RBT_B;
  80 #endif /* A_SIZE_POINTER */
  81 }
  82
  83 /*
  84 Helper function for rotations:
  85  - node's parent and color get assigned to new
  86  - node gets assigned new as a parent and 'color' as a color.
  87 */
  88 static A_INLINE void a_rbt_set_parents(a_rbt *root, a_rbt_node *node, a_rbt_node *newnode, unsigned int color)
  89 {
  90     a_rbt_node *const parent = a_rbt_parent(node);
  91 #if defined(A_SIZE_POINTER) && (A_SIZE_POINTER + 0 > 1)
  92     newnode->_parent = node->_parent;
  93 #else /* !A_SIZE_POINTER */
  94     newnode->parent = node->parent;
  95     newnode->color = node->color;
  96 #endif /* A_SIZE_POINTER */
  97     a_rbt_set_parent_color(node, newnode, color);
  98     a_rbt_new_child(root, parent, node, newnode);
  99 }
 100
 101 void a_rbt_insert_adjust(a_rbt *root, a_rbt_node *node)
 102 {
 103     for (a_rbt_node *parent = a_rbt_parent(node), *gparent, *tmp;;)
 104     {
 105         /* Loop invariant: node is red. */
 106         if (a_unlikely(!parent))
 107         {
 108             /*
 109             The inserted node is root. Either this is the first node,
 110             or we recursed at Case 1 below and are no longer violating 4).
 111             */
 112             a_rbt_set_parent_color(node, A_NULL, A_RBT_B);
 113             break;
 114         }
 115         /*
 116         If there is a black parent, we are done. Otherwise, take some corrective action as, per 4),
 117         we don't want a red root or two consecutive red nodes.
 118         */
 119         if (a_rbt_color(parent) == A_RBT_B) { break; }
 120         gparent = a_rbt_parent(parent);
 121         tmp = gparent->right;
 122         if (parent != tmp) /* parent == gparent->left */
 123         {
 124             if (tmp && a_rbt_color(tmp) == A_RBT_R)
 125             {
 126                 /*
 127                 Case 1 - node's uncle is red (color flips).
 128
 129                         G            g
 130                        / \          / \
 131                       p   u  -->   P   U
 132                      /            /
 133                     n            n
 134
 135                 However, since g's parent might be red, and 4) does not allow this, we need to recurse at g.
 136                 */
 137                 a_rbt_set_parent_color(tmp, gparent, A_RBT_B);
 138                 a_rbt_set_parent_color(parent, gparent, A_RBT_B);
 139                 node = gparent;
 140                 parent = a_rbt_parent(node);
 141                 a_rbt_set_parent_color(node, parent, A_RBT_R);
 142                 continue;
 143             }
 144             tmp = parent->right;
 145             if (node == tmp)
 146             {
 147                 /*
 148                 Case 2 - node's uncle is black and node is the parent's right child (left rotate at parent).
 149
 150                       G             G
 151                      / \           / \
 152                     p   U  -->    n   U
 153                      \           /
 154                       n         p
 155
 156                 This still leaves us in violation of 4), the continuation into Case 3 will fix that.
 157                 */
 158                 tmp = node->left;
 159                 parent->right = tmp;
 160                 node->left = parent;
 161                 if (tmp) { a_rbt_set_parent_color(tmp, parent, A_RBT_B); }
 162                 a_rbt_set_parent_color(parent, node, A_RBT_R);
 163                 parent = node;
 164                 tmp = node->right;
 165             }
 166             /*
 167             Case 3 - node's uncle is black and node is
 168             the parent's left child (right rotate at gparent).
 169
 170                     G           P
 171                    / \         / \
 172                   p   U  -->  n   g
 173                  /                 \
 174                 n                   U
 175             */
 176             gparent->left = tmp; /* == parent->right */
 177             parent->right = gparent;
 178             if (tmp) { a_rbt_set_parent_color(tmp, gparent, A_RBT_B); }
 179             a_rbt_set_parents(root, gparent, parent, A_RBT_R);
 180             break;
 181         }
 182         else
 183         {
 184             tmp = gparent->left;
 185             if (tmp && a_rbt_color(tmp) == A_RBT_R)
 186             {
 187                 /* Case 1 - color flips */
 188                 a_rbt_set_parent_color(tmp, gparent, A_RBT_B);
 189                 a_rbt_set_parent_color(parent, gparent, A_RBT_B);
 190                 node = gparent;
 191                 parent = a_rbt_parent(node);
 192                 a_rbt_set_parent_color(node, parent, A_RBT_R);
 193                 continue;
 194             }
 195             tmp = parent->left;
 196             if (node == tmp)
 197             {
 198                 /* Case 2 - right rotate at parent */
 199                 tmp = node->right;
 200                 parent->left = tmp;
 201                 node->right = parent;
 202                 if (tmp) { a_rbt_set_parent_color(tmp, parent, A_RBT_B); }
 203                 a_rbt_set_parent_color(parent, node, A_RBT_R);
 204                 parent = node;
 205                 tmp = node->left;
 206             }
 207             /* Case 3 - left rotate at gparent */
 208             gparent->right = tmp; /* == parent->left */
 209             parent->left = gparent;
 210             if (tmp) { a_rbt_set_parent_color(tmp, gparent, A_RBT_B); }
 211             a_rbt_set_parents(root, gparent, parent, A_RBT_R);
 212             break;
 213         }
 214     }
 215 }
 216
 217 static A_INLINE void a_rbt_remove_adjust(a_rbt *root, a_rbt_node *parent)
 218 {
 219     for (a_rbt_node *node = A_NULL, *sibling, *tmp1, *tmp2;;)
 220     {
 221         /*
 222         Loop invariants:
 223          - node is black (or null on first iteration)
 224          - node is not the root (parent is not null)
 225          - All leaf paths going through parent and node have a
 226            black node count that is 1 lower than other leaf paths.
 227         */
 228         if (node != parent->right) /* node == parent->left */
 229         {
 230             sibling = parent->right;
 231             if (a_rbt_color(sibling) == A_RBT_R)
 232             {
 233                 /*
 234                 Case 1 - left rotate at parent
 235
 236                       P               S
 237                      / \             / \
 238                     N   s    -->    p   Sr
 239                        / \         / \
 240                       Sl  Sr      N   Sl
 241                 */
 242                 tmp1 = sibling->left;
 243                 parent->right = tmp1;
 244                 sibling->left = parent;
 245                 a_rbt_set_parent_color(tmp1, parent, A_RBT_B);
 246                 a_rbt_set_parents(root, parent, sibling, A_RBT_R);
 247                 sibling = tmp1;
 248             }
 249             tmp1 = sibling->right;
 250             if (!tmp1 || a_rbt_color(tmp1) == A_RBT_B)
 251             {
 252                 tmp2 = sibling->left;
 253                 if (!tmp2 || a_rbt_color(tmp2) == A_RBT_B)
 254                 {
 255                     /*
 256                     Case 2 - sibling color flip (p could be either color here)
 257
 258                          (p)           (p)
 259                          / \           / \
 260                         N   S    -->  N   s
 261                            / \           / \
 262                           Sl  Sr        Sl  Sr
 263
 264                     This leaves us violating 5) which can be fixed by flipping p to black if it was red,
 265                     or by recursing at p. p is red when coming from Case 1.
 266                     */
 267                     a_rbt_set_parent_color(sibling, parent, A_RBT_R);
 268                     if (a_rbt_color(parent) == A_RBT_R)
 269                     {
 270                         a_rbt_set_black(parent);
 271                     }
 272                     else
 273                     {
 274                         node = parent;
 275                         parent = a_rbt_parent(node);
 276                         if (parent) { continue; }
 277                     }
 278                     break;
 279                 }
 280                 /*
 281                 Case 3 - right rotate at sibling (p could be either color here)
 282
 283                      (p)           (p)
 284                      / \           / \
 285                     N   S    -->  N   sl
 286                        / \             \
 287                       sl  Sr            S
 288                                          \
 289                                           Sr
 290
 291                 Note: p might be red, and then both p and sl are red after rotation(which breaks property 4).
 292                 This is fixed in Case 4 (in a_rbt_set_parents() which set sl the color of p and set A_RBT_B)
 293
 294                      (p)            (sl)
 295                      / \            /  \
 296                     N   sl   -->   P    S
 297                          \        /      \
 298                           S      N        Sr
 299                            \
 300                             Sr
 301                 */
 302                 tmp1 = tmp2->right;
 303                 sibling->left = tmp1;
 304                 tmp2->right = sibling;
 305                 parent->right = tmp2;
 306                 if (tmp1) { a_rbt_set_parent_color(tmp1, sibling, A_RBT_B); }
 307                 tmp1 = sibling;
 308                 sibling = tmp2;
 309             }
 310             /*
 311             Case 4 - left rotate at parent + color flips (p and sl could be either color here.
 312             After rotation, p becomes black, s acquires p's color, and sl keeps its color)
 313
 314                  (p)             (s)
 315                  / \             / \
 316                 N   S     -->   P   Sr
 317                    / \         / \
 318                  (sl) sr      N  (sl)
 319             */
 320             tmp2 = sibling->left;
 321             parent->right = tmp2;
 322             sibling->left = parent;
 323             a_rbt_set_parent_color(tmp1, sibling, A_RBT_B);
 324             if (tmp2) { a_rbt_set_parent(tmp2, parent); }
 325             a_rbt_set_parents(root, parent, sibling, A_RBT_B);
 326             break;
 327         }
 328         else if (parent->left)
 329         {
 330             sibling = parent->left;
 331             if (a_rbt_color(sibling) == A_RBT_R)
 332             {
 333                 /* Case 1 - right rotate at parent */
 334                 tmp1 = sibling->right;
 335                 parent->left = tmp1;
 336                 sibling->right = parent;
 337                 a_rbt_set_parent_color(tmp1, parent, A_RBT_B);
 338                 a_rbt_set_parents(root, parent, sibling, A_RBT_R);
 339                 sibling = tmp1;
 340             }
 341             tmp1 = sibling->left;
 342             if (!tmp1 || a_rbt_color(tmp1) == A_RBT_B)
 343             {
 344                 tmp2 = sibling->right;
 345                 if (!tmp2 || a_rbt_color(tmp2) == A_RBT_B)
 346                 {
 347                     /* Case 2 - sibling color flip */
 348                     a_rbt_set_parent_color(sibling, parent, A_RBT_R);
 349                     if (a_rbt_color(parent) == A_RBT_R)
 350                     {
 351                         a_rbt_set_black(parent);
 352                     }
 353                     else
 354                     {
 355                         node = parent;
 356                         parent = a_rbt_parent(node);
 357                         if (parent) { continue; }
 358                     }
 359                     break;
 360                 }
 361                 /* Case 3 - left rotate at sibling */
 362                 tmp1 = tmp2->left;
 363                 sibling->right = tmp1;
 364                 tmp2->left = sibling;
 365                 parent->left = tmp2;
 366                 if (tmp1) { a_rbt_set_parent_color(tmp1, sibling, A_RBT_B); }
 367                 tmp1 = sibling;
 368                 sibling = tmp2;
 369             }
 370             /* Case 4 - right rotate at parent + color flips */
 371             tmp2 = sibling->right;
 372             parent->left = tmp2;
 373             sibling->right = parent;
 374             a_rbt_set_parent_color(tmp1, sibling, A_RBT_B);
 375             if (tmp2) { a_rbt_set_parent(tmp2, parent); }
 376             a_rbt_set_parents(root, parent, sibling, A_RBT_B);
 377             break;
 378         }
 379         else { break; }
 380     }
 381 }
 382
 383 void a_rbt_remove(a_rbt *root, a_rbt_node *node)
 384 {
 385     a_rbt_node *child = node->right;
 386     a_rbt_node *tmp = node->left;
 387     a_rbt_node *parent, *adjust;
 388 #if defined(A_SIZE_POINTER) && (A_SIZE_POINTER + 0 > 1)
 389     a_uptr pc;
 390 #else /* !A_SIZE_POINTER */
 391     unsigned int color;
 392 #endif /* A_SIZE_POINTER */
 393
 394     if (!tmp)
 395     {
 396         /*
 397         Case 1: node to erase has no more than 1 child (easy!)
 398         Note that if there is one child it must be red due to 5) and node must be black due to 4).
 399         We adjust colors locally so as to bypass a_rbt_remove_adjust() later on.
 400         */
 401 #if defined(A_SIZE_POINTER) && (A_SIZE_POINTER + 0 > 1)
 402         pc = node->_parent;
 403 #else /* !A_SIZE_POINTER */
 404         color = node->color;
 405 #endif /* A_SIZE_POINTER */
 406         parent = a_rbt_parent(node);
 407         a_rbt_new_child(root, parent, node, child);
 408         if (child)
 409         {
 410 #if defined(A_SIZE_POINTER) && (A_SIZE_POINTER + 0 > 1)
 411             child->_parent = pc;
 412 #else /* !A_SIZE_POINTER */
 413             child->parent = parent;
 414             child->color = color;
 415 #endif /* A_SIZE_POINTER */
 416             adjust = A_NULL;
 417         }
 418         else
 419         {
 420 #if defined(A_SIZE_POINTER) && (A_SIZE_POINTER + 0 > 1)
 421             adjust = (pc & 1) == A_RBT_B ? parent : A_NULL;
 422 #else /* !A_SIZE_POINTER */
 423             adjust = color == A_RBT_B ? parent : A_NULL;
 424 #endif /* A_SIZE_POINTER */
 425         }
 426     }
 427     else if (!child)
 428     {
 429         /* Still case 1, but this time the child is node->left */
 430 #if defined(A_SIZE_POINTER) && (A_SIZE_POINTER + 0 > 1)
 431         tmp->_parent = node->_parent;
 432 #else /* !A_SIZE_POINTER */
 433         tmp->parent = node->parent;
 434         tmp->color = node->color;
 435 #endif /* A_SIZE_POINTER */
 436         parent = a_rbt_parent(node);
 437         a_rbt_new_child(root, parent, node, tmp);
 438         adjust = A_NULL;
 439     }
 440     else
 441     {
 442         a_rbt_node *successor = child, *child2;
 443
 444         tmp = child->left;
 445         if (!tmp)
 446         {
 447             /*
 448             Case 2: node's successor is its right child
 449
 450                   (n)          (s)
 451                   / \          / \
 452                 (x) (s)  ->  (x) (c)
 453                       \
 454                      (c)
 455             */
 456             parent = successor;
 457             child2 = successor->right;
 458         }
 459         else
 460         {
 461             /*
 462             Case 3: node's successor is leftmost under node's right child subtree
 463
 464                   (n)          (s)
 465                   / \          / \
 466                 (x) (y)  ->  (x) (y)
 467                     /            /
 468                   (p)          (p)
 469                   /            /
 470                 (s)          (c)
 471                   \
 472                   (c)
 473             */
 474             do {
 475                 parent = successor;
 476                 successor = tmp;
 477                 tmp = tmp->left;
 478             } while (tmp);
 479             child2 = successor->right;
 480             parent->left = child2;
 481             successor->right = child;
 482             a_rbt_set_parent(child, successor);
 483         }
 484
 485         tmp = node->left;
 486         successor->left = tmp;
 487         a_rbt_set_parent(tmp, successor);
 488
 489 #if defined(A_SIZE_POINTER) && (A_SIZE_POINTER + 0 > 1)
 490         pc = node->_parent;
 491 #else /* !A_SIZE_POINTER */
 492         color = node->color;
 493 #endif /* A_SIZE_POINTER */
 494         tmp = a_rbt_parent(node);
 495         a_rbt_new_child(root, node, successor, tmp);
 496
 497         if (child2)
 498         {
 499             a_rbt_set_parent_color(child2, parent, A_RBT_B);
 500             adjust = A_NULL;
 501         }
 502         else
 503         {
 504             adjust = a_rbt_color(successor) == A_RBT_B ? parent : A_NULL;
 505         }
 506 #if defined(A_SIZE_POINTER) && (A_SIZE_POINTER + 0 > 1)
 507         successor->_parent = pc;
 508 #else /* !A_SIZE_POINTER */
 509         successor->parent = tmp;
 510         successor->color = color;
 511 #endif /* A_SIZE_POINTER */
 512     }
 513
 514     if (adjust) { a_rbt_remove_adjust(root, adjust); }
 515 }
 516
 517 a_rbt_node *a_rbt_insert(a_rbt *root, a_rbt_node *node, int (*cmp)(void const *, void const *))
 518 {
 519     a_rbt_node *parent = root->node;
 520     a_rbt_node **link = &root->node;
 521     while (*link)
 522     {
 523         parent = *link;
 524         int const res = cmp(node, parent);
 525         if (res < 0)
 526         {
 527             link = &parent->left;
 528         }
 529         else if (res > 0)
 530         {
 531             link = &parent->right;
 532         }
 533         else { return parent; }
 534     }
 535     *link = a_rbt_init(node, parent);
 536     a_rbt_insert_adjust(root, node);
 537     return A_NULL;
 538 }
 539
 540 a_rbt_node *a_rbt_search(a_rbt const *root, void const *ctx, int (*cmp)(void const *, void const *))
 541 {
 542     for (a_rbt_node *cur = root->node; cur;)
 543     {
 544         int const res = cmp(ctx, cur);
 545         if (res < 0)
 546         {
 547             cur = cur->left;
 548         }
 549         else if (res > 0)
 550         {
 551             cur = cur->right;
 552         }
 553         else { return cur; }
 554     }
 555     return A_NULL;
 556 }
 557
 558 a_rbt_node *a_rbt_head(a_rbt const *root)
 559 {
 560     a_rbt_node *node = root->node;
 561     if (node)
 562     {
 563         while (node->left) { node = node->left; }
 564     }
 565     return node;
 566 }
 567
 568 a_rbt_node *a_rbt_tail(a_rbt const *root)
 569 {
 570     a_rbt_node *node = root->node;
 571     if (node)
 572     {
 573         while (node->right) { node = node->right; }
 574     }
 575     return node;
 576 }
 577
 578 a_rbt_node *a_rbt_next(a_rbt_node *node)
 579 {
 580     /*
 581          D
 582        /   \
 583       B     F
 584      / \   / \
 585     A   C E   G
 586     */
 587     if (!node) { return node; }
 588     if (node->right) /* D -> F -> E */
 589     {
 590         for (node = node->right; node->left; node = node->left)
 591         {
 592         }
 593     }
 594     else /* C -> B -> D */
 595     {
 596         a_rbt_node *last = node;
 597         for (node = a_rbt_parent(node); node && node->left != last;)
 598         {
 599             last = node;
 600             node = a_rbt_parent(node);
 601         }
 602     }
 603     return node;
 604 }
 605
 606 a_rbt_node *a_rbt_prev(a_rbt_node *node)
 607 {
 608     if (!node) { return node; }
 609     if (node->left)
 610     {
 611         for (node = node->left; node->right; node = node->right) {}
 612     }
 613     else
 614     {
 615         a_rbt_node *last = node;
 616         for (node = a_rbt_parent(node); node && node->right != last;)
 617         {
 618             last = node;
 619             node = a_rbt_parent(node);
 620         }
 621     }
 622     return node;
 623 }
 624
 625 a_rbt_node *a_rbt_pre_next(a_rbt_node *node)
 626 {
 627     /*
 628          D
 629        /   \
 630       B     F
 631      / \   / \
 632     A   C E   G
 633     */
 634     a_rbt_node *last = node;
 635     if (!node) { return node; }
 636     if (node->left) { return node->left; }
 637     if (node->right) { return node->right; }
 638     for (node = a_rbt_parent(node); node; node = a_rbt_parent(node))
 639     {
 640         if (node->right && node->right != last)
 641         {
 642             node = node->right; /* A -> B -> C */
 643             break;
 644         }
 645         last = node; /* C -> B -> D -> F */
 646     }
 647     return node;
 648 }
 649
 650 a_rbt_node *a_rbt_pre_prev(a_rbt_node *node)
 651 {
 652     a_rbt_node *last = node;
 653     if (!node) { return node; }
 654     if (node->right) { return node->right; }
 655     if (node->left) { return node->left; }
 656     for (node = a_rbt_parent(node); node; node = a_rbt_parent(node))
 657     {
 658         if (node->left && node->left != last)
 659         {
 660             node = node->left;
 661             break;
 662         }
 663         last = node;
 664     }
 665     return node;
 666 }
 667
 668 #define A_RBT_POST(head, tail) \
 669     for (;;)                   \
 670     {                          \
 671         if (node->head)        \
 672         {                      \
 673             node = node->head; \
 674         }                      \
 675         else if (node->tail)   \
 676         {                      \
 677             node = node->tail; \
 678         }                      \
 679         else { break; }        \
 680     }                          \
 681     (void)0
 682
 683 a_rbt_node *a_rbt_post_head(a_rbt const *root)
 684 {
 685     a_rbt_node *node = root->node;
 686     if (node) { A_RBT_POST(left, right); }
 687     return node;
 688 }
 689
 690 a_rbt_node *a_rbt_post_tail(a_rbt const *root)
 691 {
 692     a_rbt_node *node = root->node;
 693     if (node) { A_RBT_POST(right, left); }
 694     return node;
 695 }
 696
 697 a_rbt_node *a_rbt_post_next(a_rbt_node *node)
 698 {
 699     /*
 700          D
 701        /   \
 702       B     F
 703      / \   / \
 704     A   C E   G
 705     */
 706     a_rbt_node *last = node;
 707     if (!node) { return node; }
 708     node = a_rbt_parent(node);
 709     if (node && node->right && node->right != last)
 710     {
 711         node = node->right; /* B -> D -> F -> E */
 712         A_RBT_POST(left, right); /* A -> B -> C */
 713     } /* C -> B */
 714     return node;
 715 }
 716
 717 a_rbt_node *a_rbt_post_prev(a_rbt_node *node)
 718 {
 719     a_rbt_node *last = node;
 720     if (!node) { return node; }
 721     node = a_rbt_parent(node);
 722     if (node && node->left && node->left != last)
 723     {
 724         node = node->left;
 725         A_RBT_POST(right, left);
 726     }
 727     return node;
 728 }
 729
 730 a_rbt_node *a_rbt_tear(a_rbt *root, a_rbt_node **next)
 731 {
 732     a_rbt_node *node = *next;
 733     if (!node)
 734     {
 735         node = root->node;
 736         if (!node) { return node; }
 737     }
 738     A_RBT_POST(left, right);
 739     *next = a_rbt_parent(node);
 740     a_rbt_new_child(root, *next, node, A_NULL);
 741     return node;
 742 }