9.3.3 Symmetric Case

345. <Right-side rebalancing after TRB insertion 345> =
struct trb_node *y = pa[k - 2]->trb_link[0];
if (pa[k - 2]->trb_tag[0] == TRB_CHILD && y->trb_color == TRB_RED)
  { 
    <Case 1 in right-side TRB insertion rebalancing 346> 
  }
else 
  {
    struct trb_node *x;

    if (da[k - 1] == 1)
      y = pa[k - 1];
    else 
      { 
        <Case 3 in right-side TRB insertion rebalancing 348> 
      }

    <Case 2 in right-side TRB insertion rebalancing 347>
    break;
  }

This code is included in 340.

346. <Case 1 in right-side TRB insertion rebalancing 346> =
<Case 1 in right-side RB insertion rebalancing; rb => trb 207>

This code is included in 345.

347. <Case 2 in right-side TRB insertion rebalancing 347> =
<Case 2 in right-side RB insertion rebalancing; rb => trb 208>

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

This code is included in 345.

348. <Case 3 in right-side TRB insertion rebalancing 348> =
<Case 3 in right-side RB insertion rebalancing; rb => trb 209>

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

This code is included in 345.

Exercises:

1. It could be argued that the algorithm here is “impure” because it uses a stack, when elimination of the need for a stack is one of the reasons originally given for using threaded trees. Write a version of trb_probe() that avoids the use of a stack. You can use find_parent() from <Find parent of a TBST node 327> as a substitute. [answer]