9.4.5 Symmetric Case

363. <Right-side rebalancing after TRB deletion 363> =
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 364> 
  }

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 365> 
  }
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 367> 
      }

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

This code is included in 356.

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

This code is included in 363.

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

This code is included in 363.

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

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

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

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

Exercises:

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