6.5.2 Step 3: Rebalance

At this point, node p has been removed from tree and p->rb_color indicates the color of the node that was removed from the tree. Our first step is to handle one common special case: if we deleted a red node, no rebalancing is necessary, because deletion of a red node cannot violate either rule. Here is the code to avoid rebalancing in this special case:

227. <Step 3: Rebalance tree after RB deletion 227> =
if (p->rb_color == RB_BLACK)
  { 
    <Rebalance after RB deletion 228> 
  }

This code is included in 222.

On the other hand, if a black node was deleted, then we have more work to do. At the least, we have a violation of rule 2. If the deletion brought together two red nodes, as happened in the example in the previous section, there is also a violation of rule 1.

We must now fix both of these problems by rebalancing. This time, the rebalancing loop invariant is that the black-height of pa[k - 1]'s subtree on side da[k - 1] is 1 less than the black-height of its other subtree, a rule 2 violation.

There may also be a rule 2 violation, such pa[k - 1] and its child on side da[k - 1], which we will call x, are both red. (In the first iteration of the rebalancing loop, node x is the node labeled as such in the diagrams in the previous section.) If this is the case, then the fix for rule 2 is simple: just recolor x black. This increases the black-height and fixes any rule 1 violation as well. If we can do this, we're all done. Otherwise, we have more work to do.

Here's the rebalancing loop:

228. <Rebalance after RB deletion 228> =
for (;;) 
  {
    struct rb_node *x = pa[k - 1]->rb_link[da[k - 1]];
    if (x != NULL && x->rb_color == RB_RED) 
      {
        x->rb_color = RB_BLACK;
        break;
      }
    if (k < 2)
      break;

    if (da[k - 1] == 0)
      { 
        <Left-side rebalancing after RB deletion 229> 
      }
    else 
      { 
        <Right-side rebalancing after RB deletion 235> 
      }

    k--;
  }

This code is included in 227.

Now we'll take a detailed look at the rebalancing algorithm. As before, we'll only examine the case where the deleted node was in its parent's left subtree, that is, where da[k - 1] is 0. The other case is similar.

Recall that x is pa[k - 1]->rb_link[da[k - 1]] and that it may be a null pointer. In the left-side deletion case, x is pa[k - 1]'s left child. We now designate x's “sibling”, the right child of pa[k - 1], as w. Jumping right in, here's an outline of the rebalancing code:

229. <Left-side rebalancing after RB deletion 229> =
struct rb_node *w = pa[k - 1]->rb_link[1];

if (w->rb_color == RB_RED)
  { 
    <Ensure w is black in left-side RB deletion rebalancing 230> 
  }

if ((w->rb_link[0] == NULL 
     || w->rb_link[0]->rb_color == RB_BLACK)
    && (w->rb_link[1] == NULL 
        || w->rb_link[1]->rb_color == RB_BLACK))
  { <Case 1 in left-side RB deletion rebalancing 231> }
else 
  {
    if (w->rb_link[1] == NULL 
        || w->rb_link[1]->rb_color == RB_BLACK)
      { 
        <Transform left-side RB deletion rebalancing case 3 into case 2 233> 
      }

    <Case 2 in left-side RB deletion rebalancing 232>
    break;
  }

This code is included in 228.

Case Reduction: Ensure w is black

We know, at this point, that x is a black node or an empty tree. Node w may be red or black. If w is red, we perform a left rotation at the common parent of x and w, labeled A in the diagram below, and recolor A and its own newly acquired parent C. Then we reassign w as the new sibling of x. The effect is to ensure that w is also black, in order to reduce the number of cases:

Node w must have children because x is black, in order to satisfy rule 2, and w's children must be black because of rule 1.

Here is the code corresponding to this transformation. Because the ancestors of node x change, pa[] and da[] are updated as well as w.

230. <Ensure w is black in left-side RB deletion rebalancing 230> =
w->rb_color = RB_BLACK;
pa[k - 1]->rb_color = RB_RED;

pa[k - 1]->rb_link[1] = w->rb_link[0];
w->rb_link[0] = pa[k - 1];
pa[k - 2]->rb_link[da[k - 2]] = w;

pa[k] = pa[k - 1];
da[k] = 0;
pa[k - 1] = w;
k++;

w = pa[k - 1]->rb_link[1];

This code is included in 229, 360, and 477.

Now we can take care of the three rebalancing cases one by one. Remember that the situation is a deleted black node in the subtree designated x and the goal is to correct a rule 2 violation. Although subtree x may be an empty tree, the diagrams below show it as a black node. That's okay because the code itself never refers to x. The label is supplied for the reader's benefit only.

Case 1: w has no red children

If w doesn't have any red children, then it can be recolored red. When we do that, the black-height of the subtree rooted at w has decreased, so we must move up the tree, with pa[k - 1] becoming the new x, to rebalance at w and x's parent.

The parent, labeled B in the diagram below, may be red or black. Its color is not changed within the code for this case. If it is red, then the next iteration of the rebalancing loop will recolor it as red immediately and exit. In particular, B will be red if the transformation to make x black was performed earlier. If, on the other hand, B is black, the loop will continue as usual.

231. <Case 1 in left-side RB deletion rebalancing 231> =
w->rb_color = RB_RED;

This code is included in 229, 361, 477, and 576.

Case 2: w's right child is red

If w's right child is red, we can perform a left rotation at pa[k - 1] and recolor some nodes, and thereby satisfy both of the red-black rules. The loop is then complete. The transformation looks like this:

The corresponding code is below. The break is supplied by the enclosing code segment <Left-side rebalancing after RB deletion 229>:

232. <Case 2 in left-side RB deletion rebalancing 232> =
w->rb_color = pa[k - 1]->rb_color;
pa[k - 1]->rb_color = RB_BLACK;
w->rb_link[1]->rb_color = RB_BLACK;

pa[k - 1]->rb_link[1] = w->rb_link[0];
w->rb_link[0] = pa[k - 1];
pa[k - 2]->rb_link[da[k - 2]] = w;

This code is included in 229, 362, and 479.

Case 3: w's left child is red

Because the conditions for neither case 1 nor case 2 apply, the only remaining possibility is that w has a red left child. When this is the case, we can transform it into case 2 by rotating right at w. This causes w to move to the node that was previously w's left child, in this way:

233. <Transform left-side RB deletion rebalancing case 3 into case 2 233> =
struct rb_node *y = w->rb_link[0];
y->rb_color = RB_BLACK;
w->rb_color = RB_RED;
w->rb_link[0] = y->rb_link[1];
y->rb_link[1] = w;
w = pa[k - 1]->rb_link[1] = y;

This code is included in 229, 363, and 481.