9.3.2 Step 3: Rebalance

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

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

This code is included in 337.

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

341. <Left-side rebalancing after TRB insertion 341> =
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 342> 
  }
else 
  {
    struct trb_node *x;

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

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

This code is included in 340.

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:

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

This code is included in 341.

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:

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

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

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:

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

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