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