15.4.1 Step 2: Delete

The goal of this step is to remove p from the tree and set up f as the node where rebalancing should start. Secondarily, we set dir as the side of f from which the node was deleted. Together, f and dir fill the role that the top-of-stack entries in pa[] and da[] took in ordinary RB deletion.

```567. <Step 2: Delete item from PRB tree 567> =
{     <Case 1 in PRB deletion 568>   }
else   {
enum prb_color t;

{         <Case 2 in PRB deletion 569>       }
else       {         <Case 3 in PRB deletion 570>       }
}
```

This code is included in 566.

##### Case 1: p has no right child

If p has no right child, then rebalancing should start at its parent, q, and dir is already the side that p is on. The rest is the same as PBST deletion (see pbstdel1).

```568. <Case 1 in PRB deletion 568> =
<Case 1 in PBST deletion; pbst => prb 497>

f = q;
```

This code is included in 567.

##### Case 2: p's right child has no left child

In case 2, we swap the colors of p and r as for ordinary RB deletion (see rbcolorswap). We set up f and dir in the same way that <Case 2 in RB deletion 223> set up the top of stack. The rest is the same as PBST deletion (see pbstdel2).

```569. <Case 2 in PRB deletion 569> =
<Case 2 in PBST deletion; pbst => prb 498>

t = p->prb_color;
p->prb_color = r->prb_color;
r->prb_color = t;

f = r;
dir = 1;
```

This code is included in 567.

##### Case 3: p's right child has a left child

Case 2 swaps the colors of p and s the same way as in ordinary RB deletion (see rbcolorswap), and sets up f and dir in the same way that <Case 3 in RB deletion 224> set up the stack. The rest is borrowed from PBST deletion (see pbstdel3).

```570. <Case 3 in PRB deletion 570> =
<Case 3 in PBST deletion; pbst => prb 499>

t = p->prb_color;
p->prb_color = s->prb_color;
s->prb_color = t;

f = r;
dir = 0;
```

This code is included in 567.