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(;;)

{structrb_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> =structrb_node*w=pa[k- 1]->rb_link[1];if(w->rb_color==RB_RED) {

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

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

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.

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.

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> =structrb_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;