9.4.3 Step 3: Rebalance [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

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:

[Click here for plain-text rendering]

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:

[Click here for plain-text rendering]

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.