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:

474. <Step 3: Rebalance after RTRB deletion 474> =
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 475> 
          }
        else 
          { 
            <Right-side rebalancing after RTRB deletion 476> 
          }
      }

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

This code is included in 468.

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:

475. <Left-side rebalancing after RTRB deletion 475> =
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 228> 
  }

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 229> 
  }
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 479> 
      }

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

This code is included in 474.

476. <Right-side rebalancing after RTRB deletion 476> =
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 234> 
  }

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 235> 
  }
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 480> 
      }

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

This code is included in 474.

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:

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

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 475.

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:

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

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

This code is included in 476.

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:

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

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

This code is included in 475.

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:

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

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 476.