GNU libavl 2.0.1
13.4.1 Step 2: Delete
We use left-looking deletion. At this point, p is the node to delete.
After the deletion, x is the node that replaced p, or a null pointer
if the node was deleted without replacement. The cases are
distinguished in the usual way:
| | if (p->rtrb_link[0] == NULL)
{
if (p->rtrb_rtag == RTRB_CHILD)
{
<@xref{\NODE\, , Case 1 in RTRB deletion.>,470}
}
else
{
<@xref{\NODE\, , Case 2 in RTRB deletion.>,471}
}
}
else
{
enum rtrb_color t;
struct rtrb_node *r = p->rtrb_link[0];
if (r->rtrb_rtag == RTRB_THREAD)
{
<@xref{\NODE\, , Case 3 in RTRB deletion.>,472}
}
else
{
<@xref{\NODE\, , Case 4 in RTRB deletion.>,473}
}
}
|
This code is included in @refalso{468
Case 1: p has a right child but no left child
If p, the node to be deleted, has a right child but no left child,
then we replace it by its right child. This is the same as <@xref{\NODE\, , \TITLE\}.>{Case 1 in
RTAVL deletion,432}.
| | <@xref{\NODE\, , Case 1 in RTAVL deletion; rtavl =>.> rtrb,432}
|
This code is included in @refalso{469
Case 2: p has a right thread and no left child
Similarly, case 2 is the same as <@xref{\NODE\, , Case 2 in RTAVL deletion.>,433}, with the
addition of an assignment to x.
| | <@xref{\NODE\, , Case 2 in RTAVL deletion; rtavl =>.> rtrb,433}
|
This code is included in @refalso{469
Case 3: p's left child has a right thread
If p has a left child r, and r has a right thread, then we replace
p by r and transfer p's former right link to r. Node r also
receives p's balance factor.
| | r->rtrb_link[1] = p->rtrb_link[1];
r->rtrb_rtag = p->rtrb_rtag;
t = r->rtrb_color;
r->rtrb_color = p->rtrb_color;
p->rtrb_color = t;
pa[k - 1]->rtrb_link[da[k - 1]] = r;
da[k] = 0;
pa[k++] = r;
|
This code is included in @refalso{469
Case 4: p's left child has a right child
The fourth case, where p has a left child that itself has a right
child, uses the same algorithm as <@xref{\NODE\, , Case 4 in RTAVL deletion.>,435}, except
that instead of setting the balance factor of s, we swap the colors
of t and s as in <@xref{\NODE\, , Case 3 in RB deletion.>,224}.
| | struct rtrb_node *s;
int j = k++;
for (;;)
{
da[k] = 1;
pa[k++] = r;
s = r->rtrb_link[1];
if (s->rtrb_rtag == RTRB_THREAD)
break;
r = s;
}
da[j] = 0;
pa[j] = pa[j - 1]->rtrb_link[da[j - 1]] = s;
if (s->rtrb_link[0] != NULL)
r->rtrb_link[1] = s->rtrb_link[0];
else
{
r->rtrb_rtag = RTRB_THREAD;
r->rtrb_link[1] = s;
}
s->rtrb_link[0] = p->rtrb_link[0];
s->rtrb_link[1] = p->rtrb_link[1];
s->rtrb_rtag = p->rtrb_rtag;
t = s->rtrb_color;
s->rtrb_color = p->rtrb_color;
p->rtrb_color = t;
|
This code is included in @refalso{469
