9.4.3 Step 3: Rebalance

The outline for rebalancing after threaded RB deletion is the same as for the unthreaded case (see Deleting an RB Node Step 3 - Rebalance):

356. <Step 3: Rebalance tree after TRB deletion 356> =
if (p->trb_color == TRB_BLACK) 
  {
    for (; k > 1; k–) 
      {
        if (pa[k - 1]->trb_tag[da[k - 1]] == TRB_CHILD) 
          {
            struct trb_node *x = pa[k - 1]->trb_link[da[k - 1]];
            if (x->trb_color == TRB_RED) 
              {
                x->trb_color = TRB_BLACK;
                break;
              }
          }

        if (da[k - 1] == 0)
          { 
            <Left-side rebalancing after TRB deletion 357> 
          }
        else 
          { 
            <Right-side rebalancing after TRB deletion 363> 
          }
      }

    if (tree->trb_root != NULL)
      tree->trb_root->trb_color = TRB_BLACK;
  }

This code is included in 349.

The rebalancing cases are the same, too. We need to check for thread tags, not for null pointers, though, in some places:

357. <Left-side rebalancing after TRB deletion 357> =
struct trb_node *w = pa[k - 1]->trb_link[1];

if (w->trb_color == TRB_RED) 
  { 
    <Ensure w is black in left-side TRB deletion rebalancing 358> 
  }

if ((w->trb_tag[0] == TRB_THREAD 
     || w->trb_link[0]->trb_color == TRB_BLACK)
    && (w->trb_tag[1] == TRB_THREAD 
        || w->trb_link[1]->trb_color == TRB_BLACK))
  { 
    <Case 1 in left-side TRB deletion rebalancing 359> 
  }
else 
  {
    if (w->trb_tag[1] == TRB_THREAD 
        || w->trb_link[1]->trb_color == TRB_BLACK)
      { 
        <Transform left-side TRB deletion rebalancing case 3 into case 2 361> 
      }

    <Case 2 in left-side TRB deletion rebalancing 360>
    break;
  }

This code is included in 356.

Case Reduction: Ensure w is black

This transformation does not move around any subtrees that might be threads, so there is no need for it to change.

358. <Ensure w is black in left-side TRB deletion rebalancing 358> =
<Ensure w is black in left-side RB deletion rebalancing; rb => trb 228>

This code is included in 357.

Case 1: w has no red children

This transformation just recolors nodes, so it also does not need any changes.

359. <Case 1 in left-side TRB deletion rebalancing 359> =
<Case 1 in left-side RB deletion rebalancing; rb => trb 229>

This code is included in 357.

Case 2: w's right child is red

If w has a red right child and a left thread, then it is necessary to adjust tags and links after the left rotation at w and recoloring, as shown in this diagram:

360. <Case 2 in left-side TRB deletion rebalancing 360> =
<Case 2 in left-side RB deletion rebalancing; rb => trb 230>

if (w->trb_tag[0] == TRB_THREAD) 
  {
    w->trb_tag[0] = TRB_CHILD;
    pa[k - 1]->trb_tag[1] = TRB_THREAD;
    pa[k - 1]->trb_link[1] = w;
  }

This code is included in 357.

Case 3: w's left child is red

If w has a red left child, which has a right thread, then we again need to adjust tags and links after right rotation at w and recoloring, as shown here:

361. <Transform left-side TRB deletion rebalancing case 3 into case 2 361> =
<Transform left-side RB deletion rebalancing case 3 into case 2; rb => trb 231>

if (w->trb_tag[1] == TRB_THREAD) 
  {
    w->trb_tag[1] = TRB_CHILD;
    w->trb_link[1]->trb_tag[0] = TRB_THREAD;
    w->trb_link[1]->trb_link[0] = w;
  }

This code is included in 357.