GNU libavl 2.0.1
16.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.
| | if (p->prb_link[1] == NULL)
{
<@xref{\NODE\, , 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)
{
<@xref{\NODE\, , Case 2 in PRB deletion.>,569}
}
else
{
<@xref{\NODE\, , Case 3 in PRB deletion.>,570}
}
}
|
This code is included in @refalso{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 (@pageref{pbstdel1}).
| | <@xref{\NODE\, , Case 1 in PBST deletion; pbst =>.> prb,497}
f = q;
|
This code is included in @refalso{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 (@pageref{rbcolorswap}). We set up f and dir in the same
way that <@xref{\NODE\, , Case 2 in RB deletion.>,223} set up the top of stack. The rest
is the same as PBST deletion (@pageref{pbstdel2}).
| | <@xref{\NODE\, , 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 @refalso{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 (@pageref{rbcolorswap}), and sets up f and dir in the
same way that <@xref{\NODE\, , Case 3 in RB deletion.>,224} set up the stack. The rest is
borrowed from PBST deletion (@pageref{pbstdel3}).
| | <@xref{\NODE\, , 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 @refalso{567
