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):

358. <Step 3: Rebalance tree after TRB deletion 358> =
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 359> 
          }
        else 
          { 
            <Right-side rebalancing after TRB deletion 365> 
          }
      }

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

This code is included in 351.

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

359. <Left-side rebalancing after TRB deletion 359> =
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 360> 
  }

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 361> 
  }
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 363> 
      }

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

This code is included in 358.

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.

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

This code is included in 359.

Case 1: w has no red children

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

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

This code is included in 359.

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:

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

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

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:

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

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