12.3.2 Step 3: Rebalance

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

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

This code is included in 456.

The choice of case for insertion on the left side is made in the same way as in <Left-side rebalancing after RB insertion 202>, 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:

460. <Left-side rebalancing after RTRB insertion 460> =
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 462> 
  }
else 
  {
    struct rtrb_node *x;

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

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

This code is included in 459.

461. <Right-side rebalancing after RTRB insertion 461> =
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 463> 
  }
else 
  {
    struct rtrb_node *x;

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

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

This code is included in 459.

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):

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

This code is included in 460.

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

This code is included in 461.

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:

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

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

This code is included in 460.

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

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

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

This code is included in 461.

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:

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

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

This code is included in 460.

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

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

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

This code is included in 461.