9.4.5 Symmetric Case

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

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

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 right-side TRB deletion rebalancing 367> 
  }
else 
  {
    if (w->trb_tag[0] == TRB_THREAD 
        || w->trb_link[0]->trb_color == TRB_BLACK)
      { 
        <Transform right-side TRB deletion rebalancing case 3 into case 2 369> 
      }

    <Case 2 in right-side TRB deletion rebalancing 368>
    break;
  }

This code is included in 358.

366. <Ensure w is black in right-side TRB deletion rebalancing 366> =
<Ensure w is black in right-side RB deletion rebalancing; rb => trb 236>

This code is included in 365.

367. <Case 1 in right-side TRB deletion rebalancing 367> =
<Case 1 in right-side RB deletion rebalancing; rb => trb 237>

This code is included in 365.

368. <Case 2 in right-side TRB deletion rebalancing 368> =
<Case 2 in right-side RB deletion rebalancing; rb => trb 239>

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

This code is included in 365.

369. <Transform right-side TRB deletion rebalancing case 3 into case 2 369> =
<Transform right-side RB deletion rebalancing case 3 into case 2; rb => trb 238>

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

This code is included in 365.

Exercises:

1. Write another version of trb_delete() that does not use a stack. You can use <Find parent of a TBST node 329> to find the parent of a node. [answer]