15.4.2 Step 3: Rebalance

The rebalancing code is easily related to the analogous code for ordinary RB trees in <Rebalance after RB deletion 226>. As we carefully set up in step 2, we use f as the top of stack node and dir as the side of f from which a node was deleted. These variables f and dir were formerly represented by pa[k - 1] and da[k - 1], respectively. Additionally, variable g is used to represent the parent of f. Formerly the same node was referred to as pa[k - 2].

The code at the end of the loop simply moves f and dir up one level in the tree. It has the same effect as did popping the stack with k–.

```571. <Step 3: Rebalance tree after PRB deletion 571> =
if (p->prb_color == PRB_BLACK)   {
for (;;)       {
struct prb_node *x; /* Node we want to recolor black if possible. */
struct prb_node *g; /* Parent of f. */
struct prb_node *t; /* Temporary for use in finding parent. */

if (x != NULL && x->prb_color == PRB_RED)
{
x->prb_color = PRB_BLACK;
break;
}

if (f == (struct prb_node *) &tree->prb_root)
break;

g = f->prb_parent;
if (g == NULL)
g = (struct prb_node *) &tree->prb_root;

if (dir == 0)
{             <Left-side rebalancing after PRB deletion 572>           }
else           {             <Right-side rebalancing after PRB deletion 578>           }

t = f;
f = f->prb_parent;
if (f == NULL)
f = (struct prb_node *) &tree->prb_root;
}
}
```

This code is included in 566.

The code to distinguish rebalancing cases in PRB trees is almost identical to <Left-side rebalancing after RB deletion 227>.

```572. <Left-side rebalancing after PRB deletion 572> =

if (w->prb_color == PRB_RED)
{     <Ensure w is black in left-side PRB deletion rebalancing 573>   }

{     <Case 1 in left-side PRB deletion rebalancing 574>   }
else   {
{         <Transform left-side PRB deletion rebalancing case 3 into case 2 576>       }

<Case 2 in left-side PRB deletion rebalancing 575>
break;
}
```

This code is included in 571.

##### Case Reduction: Ensure w is black

The case reduction code is much like that for plain RB trees (see rbdcr), with pa[k - 1] replaced by f and pa[k - 2] replaced by g. Instead of updating the stack, we change g. Node f need not change because it's already what we want it to be. We also need to update parent pointers for the rotation.

```573. <Ensure w is black in left-side PRB deletion rebalancing 573> =
w->prb_color = PRB_BLACK;
f->prb_color = PRB_RED;

w->prb_parent = f->prb_parent;
f->prb_parent = w;

g = w;

w->prb_parent = f;
```

This code is included in 572.

##### Case 1: w has no red children

Case 1 is trivial. No changes from ordinary RB trees are necessary (see rbdelcase1).

```574. <Case 1 in left-side PRB deletion rebalancing 574> =
<Case 1 in left-side RB deletion rebalancing; rb => prb 229>
```

This code is included in 572.

##### Case 2: w's right child is red

The changes from ordinary RB trees (see rbdelcase2) for case 2 follow the same pattern.

```575. <Case 2 in left-side PRB deletion rebalancing 575> =
w->prb_color = f->prb_color;
f->prb_color = PRB_BLACK;

w->prb_parent = f->prb_parent;
f->prb_parent = w;
```

This code is included in 572.

##### Case 3: w's left child is red

The code for case 3 in ordinary RB trees (see rbdelcase3) needs slightly more intricate changes than case 1 or case 2, so the diagram below may help to clarify:

```576. <Transform left-side PRB deletion rebalancing case 3 into case 2 576> =