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.

569. <Step 2: Delete item from PRB tree 569> =
if (p->prb_link[1] == NULL)
  { 
    <Case 1 in PRB deletion 570> 
  }
else 
  {
    enum prb_color t;
    struct prb_node *r = p->prb_link[1];

    if (r->prb_link[0] == NULL)
      { 
        <Case 2 in PRB deletion 571> 
      }
    else 
      { 
        <Case 3 in PRB deletion 572> 
      }
  }

This code is included in 568.

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

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

f = q;

This code is included in 569.

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 225> set up the top of stack. The rest is the same as PBST deletion (see pbstdel2).

571. <Case 2 in PRB deletion 571> =
<Case 2 in PBST deletion; pbst => prb 500>

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

f = r;
dir = 1;

This code is included in 569.

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 226> set up the stack. The rest is borrowed from PBST deletion (see pbstdel3).

572. <Case 3 in PRB deletion 572> =
<Case 3 in PBST deletion; pbst => prb 501>

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

f = r;
dir = 0;

This code is included in 569.