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> =
if (p->prb_link[1] == NULL)
  { 
    <Case 1 in PRB deletion 568> 
  }
else 
  {
    enum prb_color t;
    struct prb_node *r = p->prb_link[1];

    if (r->prb_link[0] == NULL)
      { 
        <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.