12.3.2 Step 3: Rebalance

The rebalancing outline follows <Step 3: Rebalance after RB insertion 203>.

461. <Step 3: Rebalance after RTRB insertion 461> =
while (k >= 3 && pa[k - 1]->rtrb_color == RTRB_RED) 
  {
    if (da[k - 2] == 0)
      { 
        <Left-side rebalancing after RTRB insertion 462> 
      }
    else 
      { 
        <Right-side rebalancing after RTRB insertion 463> 
      }
  }
tree->rtrb_root->rtrb_color = RTRB_BLACK;

This code is included in 458.

The choice of case for insertion on the left side is made in the same way as in <Left-side rebalancing after RB insertion 204>, except that of course right-side tests for non-empty subtrees are made using rtrb_rtag instead of rtrb_link[1], and similarly for insertion on the right side. In short, we take q (which is not a real variable) as the new node n if this is the first time through the loop, or a node whose color has just been changed to red otherwise. We know that both q and its parent pa[k - 1] are red, violating rule 1 for red-black trees, and that q's grandparent pa[k - 2] is black. Here is the code to distinguish cases:

462. <Left-side rebalancing after RTRB insertion 462> =
struct rtrb_node *y = pa[k - 2]->rtrb_link[1];
if (pa[k - 2]->rtrb_rtag == RTRB_CHILD && y->rtrb_color == RTRB_RED)
  { 
    <Case 1 in left-side RTRB insertion rebalancing 464> 
  }
else 
  {
    struct rtrb_node *x;

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

    <Case 2 in left-side RTRB insertion rebalancing 466>
    break;
  }

This code is included in 461.

463. <Right-side rebalancing after RTRB insertion 463> =
struct rtrb_node *y = pa[k - 2]->rtrb_link[0];
if (pa[k - 2]->rtrb_link[0] != NULL && y->rtrb_color == RTRB_RED)
  { 
    <Case 1 in right-side RTRB insertion rebalancing 465> 
  }
else 
  {
    struct rtrb_node *x;

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

    <Case 2 in right-side RTRB insertion rebalancing 467>
    break;
  }

This code is included in 461.

Case 1: q's uncle is red

If node q's uncle is red, then no links need be changed. Instead, we will just recolor nodes. We reuse the code for RB insertion (see rbinscase1):

464. <Case 1 in left-side RTRB insertion rebalancing 464> =
<Case 1 in left-side RB insertion rebalancing; rb => rtrb 205>

This code is included in 462.

465. <Case 1 in right-side RTRB insertion rebalancing 465> =
<Case 1 in right-side RB insertion rebalancing; rb => rtrb 209>

This code is included in 463.

Case 2: q is on same side of parent as parent is of grandparent

If q is a left child of its parent y and y is a left child of its own parent x, or if both q and y are right children, then we rotate at x away from y. This is the same that we would do in an unthreaded RB tree (see rbinscase2).

However, as usual, we must make sure that threads are fixed up properly in the rotation. In particular, for case 2 in left-side rebalancing, we must convert a right thread of y, after rotation, into a null left child pointer of x, like this:

466. <Case 2 in left-side RTRB insertion rebalancing 466> =
<Case 2 in left-side RB insertion rebalancing; rb => rtrb 206>

if (y->rtrb_rtag == RTRB_THREAD) 
  {
    y->rtrb_rtag = RTRB_CHILD;
    x->rtrb_link[0] = NULL;
  }

This code is included in 462.

For the right-side rebalancing case, we must convert a null left child of y, after rotation, into a right thread of x:

467. <Case 2 in right-side RTRB insertion rebalancing 467> =
<Case 2 in right-side RB insertion rebalancing; rb => rtrb 210>

if (x->rtrb_link[1] == NULL) 
  {
    x->rtrb_rtag = RTRB_THREAD;
    x->rtrb_link[1] = y;
  }

This code is included in 463.

Case 3: q is on opposite side of parent as parent is of grandparent

If q is a left child and its parent is a right child, or vice versa, then we have an instance of case 3, and we rotate at q's parent in the direction from q to its parent. We handle this case as seen before for unthreaded RB trees (see rbinscase3), with the addition of fix-ups for threads during rotation.

The left-side fix-up and the code to do it look like this:

468. <Case 3 in left-side RTRB insertion rebalancing 468> =
<Case 3 in left-side RB insertion rebalancing; rb => rtrb 207>

if (x->rtrb_link[1] == NULL) 
  {
    x->rtrb_rtag = RTRB_THREAD;
    x->rtrb_link[1] = y;
  }

This code is included in 462.

Here's the right-side fix-up and code:

469. <Case 3 in right-side RTRB insertion rebalancing 469> =
<Case 3 in right-side RB insertion rebalancing; rb => rtrb 211>

if (y->rtrb_rtag == RTRB_THREAD) 
  {
    y->rtrb_rtag = RTRB_CHILD;
    x->rtrb_link[0] = NULL;
  }

This code is included in 463.