12.4.2 Step 3: Rebalance

The rebalancing step's outline is much like that for deletion in a symmetrically threaded tree, except that we must check for a null child pointer on the left side of x versus a thread on the right side:

476. <Step 3: Rebalance after RTRB deletion 476> =
if (p->rtrb_color == RTRB_BLACK) 
  {
    for (; k > 1; k--) 
      {
        struct rtrb_node *x;
        if (da[k - 1] == 0 || pa[k - 1]->rtrb_rtag == RTRB_CHILD)
          x = pa[k - 1]->rtrb_link[da[k - 1]];
        else 
          x = NULL;
        if (x != NULL && x->rtrb_color == RTRB_RED) 
          {
            x->rtrb_color = RTRB_BLACK;
            break;
          }

        if (da[k - 1] == 0)
          { 
            <Left-side rebalancing after RTRB deletion 477> 
          }
        else 
          { 
            <Right-side rebalancing after RTRB deletion 478> 
          }
      }

    if (tree->rtrb_root != NULL) 
      tree->rtrb_root->rtrb_color = RTRB_BLACK;
  }

This code is included in 470.

As for RTRB insertion, rebalancing on either side of the root is not symmetric because the tree structure itself is not symmetric, but again the rebalancing steps are very similar. The outlines of the left-side and right-side rebalancing code are below. The code for ensuring that w is black and for case 1 on each side are the same as the corresponding unthreaded RB code, because none of that code needs to check for empty trees:

477. <Left-side rebalancing after RTRB deletion 477> =
struct rtrb_node *w = pa[k - 1]->rtrb_link[1];

if (w->rtrb_color == RTRB_RED) 
  { 
    <Ensure w is black in left-side RB deletion rebalancing; rb => rtrb 230> 
  }

if ((w->rtrb_link[0] == NULL 
     || w->rtrb_link[0]->rtrb_color == RTRB_BLACK)
    && (w->rtrb_rtag == RTRB_THREAD 
        || w->rtrb_link[1]->rtrb_color == RTRB_BLACK))
  { 
    <Case 1 in left-side RB deletion rebalancing; rb => rtrb 231> 
  }
else 
  {
    if (w->rtrb_rtag == RTRB_THREAD 
        || w->rtrb_link[1]->rtrb_color == RTRB_BLACK)
      { 
        <Transform left-side RTRB deletion rebalancing case 3 into case 2 481> 
      }

    <Case 2 in left-side RTRB deletion rebalancing 479>
    break;
  }

This code is included in 476.

478. <Right-side rebalancing after RTRB deletion 478> =
struct rtrb_node *w = pa[k - 1]->rtrb_link[0];

if (w->rtrb_color == RTRB_RED) 
  { 
    <Ensure w is black in right-side RB deletion rebalancing; rb => rtrb 236> 
  }

if ((w->rtrb_link[0] == NULL 
     || w->rtrb_link[0]->rtrb_color == RTRB_BLACK)
    && (w->rtrb_rtag == RTRB_THREAD 
        || w->rtrb_link[1]->rtrb_color == RTRB_BLACK))
  { 
    <Case 1 in right-side RB deletion rebalancing; rb => rtrb 237> 
  }
else 
  {
    if (w->rtrb_link[0] == NULL 
        || w->rtrb_link[0]->rtrb_color == RTRB_BLACK)
      { 
        <Transform right-side RTRB deletion rebalancing case 3 into case 2 482> 
      }

    <Case 2 in right-side RTRB deletion rebalancing 480>
    break;
  }

This code is included in 476.

Case 2: w's child opposite the deletion is red

If the deletion was on the left side of w and w's right child is red, we rotate left at pa[k - 1] and perform some recolorings, as we did for unthreaded RB trees (see rbdelcase2). There is a special case when w has no left child. This must be transformed into a thread from leading to w following the rotation:

479. <Case 2 in left-side RTRB deletion rebalancing 479> =
<Case 2 in left-side RB deletion rebalancing; rb => rtrb 232>

if (w->rtrb_link[0]->rtrb_link[1] == NULL) 
  {
    w->rtrb_link[0]->rtrb_rtag = RTRB_THREAD;
    w->rtrb_link[0]->rtrb_link[1] = w;
  }

This code is included in 477.

Alternately, if the deletion was on the right side of w and w's left child is right, we rotate right at pa[k - 1] and recolor. There is an analogous special case:

480. <Case 2 in right-side RTRB deletion rebalancing 480> =
<Case 2 in right-side RB deletion rebalancing; rb => rtrb 239>

if (w->rtrb_rtag == RTRB_THREAD) 
  {
    w->rtrb_rtag = RTRB_CHILD;
    pa[k - 1]->rtrb_link[0] = NULL;
  }

This code is included in 478.

Case 3: w's child on the side of the deletion is red

If the deletion was on the left side of w and w's left child is red, then we rotate right at w and recolor, as in case 3 for unthreaded RB trees (see rbdelcase3). There is a special case when w's left child has a right thread. This must be transformed into a null left child of w's right child following the rotation:

481. <Transform left-side RTRB deletion rebalancing case 3 into case 2 481> =
<Transform left-side RB deletion rebalancing case 3 into case 2; rb => rtrb 233>

if (w->rtrb_rtag == RTRB_THREAD) 
  {
    w->rtrb_rtag = RTRB_CHILD;
    w->rtrb_link[1]->rtrb_link[0] = NULL;
  }

This code is included in 477.

Alternately, if the deletion was on the right side of w and w's right child is red, we rotate left at w and recolor. There is an analogous special case:

482. <Transform right-side RTRB deletion rebalancing case 3 into case 2 482> =
<Transform right-side RB deletion rebalancing case 3 into case 2; rb => rtrb 238>

if (w->rtrb_link[0]->rtrb_link[1] == NULL) 
  {
    w->rtrb_link[0]->rtrb_rtag = RTRB_THREAD;
    w->rtrb_link[0]->rtrb_link[1] = w;
  }

This code is included in 478.