9.3.2 Step 3: Rebalance

The basic rebalancing loop is unchanged from <Step 3: Rebalance after RB insertion 203>.

342. <Step 3: Rebalance after TRB insertion 342> =
while (k >= 3 && pa[k - 1]->trb_color == TRB_RED) 
  {
    if (da[k - 2] == 0)
      { 
        <Left-side rebalancing after TRB insertion 343> 
      }
    else 
      { 
        <Right-side rebalancing after TRB insertion 347> 
      }
  }
tree->trb_root->trb_color = TRB_BLACK;

This code is included in 339.

The cases for rebalancing are the same as in <Left-side rebalancing after RB insertion 204>, too. We do need to check for threads, instead of null pointers.

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

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

    <Case 2 in left-side TRB insertion rebalancing 345>
    break;
  }

This code is included in 342.

The rest of this section deals with the individual rebalancing cases, the same as in unthreaded RB insertion (see Inserting an RB Node Step 3 - Rebalance). Each iteration deals with a node whose color has just been changed to red, which is the newly inserted node n in the first trip through the loop. In the discussion, we'll call this node q.

Case 1: q's uncle is red

If node q has an red “uncle”, then only recoloring is required. Because no links are changed, no threads need to be updated, and we can reuse the code for RB insertion without change:

344. <Case 1 in left-side TRB insertion rebalancing 344> =
<Case 1 in left-side RB insertion rebalancing; rb => trb 205>

This code is included in 343.

Case 2: q is the left child of its parent

If q is the left child of its parent, we rotate right at q's grandparent, and recolor a few nodes. Here's the transformation:

This transformation can only cause thread problems with subtree c, since the other subtrees stay firmly in place. If c is a thread, then we need to make adjustments after the transformation to account for the difference between threaded and unthreaded rotation, so that the final operation looks like this:

345. <Case 2 in left-side TRB insertion rebalancing 345> =
<Case 2 in left-side RB insertion rebalancing; rb => trb 206>

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

Case 3: q is the right child of its parent

The modification to case 3 is the same as the modification to case 2, but it applies to a left rotation instead of a right rotation. The adjusted case looks like this:

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

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