GNU libavl 2.0.1
12.5.2 Step 2: Delete
As demonstrated in the previous chapter, left-looking deletion, where we
examine the left subtree of the node to be deleted, is more efficient
than right-looking deletion in an RTBST (see section 11.5.2 Left-Looking Deletion). This holds true in an RTAVL tree, too.
| | if (p->rtavl_link[0] == NULL)
{
if (p->rtavl_rtag == RTAVL_CHILD)
{
<@xref{\NODE\, , Case 1 in RTAVL deletion.>,432}
}
else
{
<@xref{\NODE\, , Case 2 in RTAVL deletion.>,433}
}
}
else
{
struct rtavl_node *r = p->rtavl_link[0];
if (r->rtavl_rtag == RTAVL_THREAD)
{
<@xref{\NODE\, , Case 3 in RTAVL deletion.>,434}
}
else
{
<@xref{\NODE\, , Case 4 in RTAVL deletion.>,435}
}
}
tree->rtavl_alloc->libavl_free (tree->rtavl_alloc, p);
|
This code is included in @refalso{429
Case 1: p has a right child but no left child
If the node to be deleted, p, has a right child but not a left child,
then we replace it by its right child.
| | pa[k - 1]->rtavl_link[da[k - 1]] = p->rtavl_link[1];
|
This code is included in @refalso{431
Case 2: p has a right thread and no left child
If we are deleting a leaf, then we replace it by a null pointer if it's
a left child, or by a pointer to its own former right thread if it's a
right child. Refer back to the commentary on <@xref{\NODE\, , \TITLE\}.>{Case 2 in right-looking
RTBST deletion,385} for further explanation.
| | pa[k - 1]->rtavl_link[da[k - 1]] = p->rtavl_link[da[k - 1]];
if (da[k - 1] == 1)
pa[k - 1]->rtavl_rtag = RTAVL_THREAD;
|
This code is included in @refalso{431
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->rtavl_link[1] = p->rtavl_link[1];
r->rtavl_rtag = p->rtavl_rtag;
r->rtavl_balance = p->rtavl_balance;
pa[k - 1]->rtavl_link[da[k - 1]] = r;
da[k] = 0;
pa[k++] = r;
|
This code is included in @refalso{431
Case 4: p's left child has a right child
The final case, where node p's left child r has a right child, is
also the most complicated. We find p's predecessor s first:
| | struct rtavl_node *s;
int j = k++;
for (;;)
{
da[k] = 1;
pa[k++] = r;
s = r->rtavl_link[1];
if (s->rtavl_rtag == RTAVL_THREAD)
break;
r = s;
}
|
See also @refalso{436
This code is included in @refalso{431
Then we move s into p's place, not forgetting to update links and
tags as necessary:
| | da[j] = 0;
pa[j] = pa[j - 1]->rtavl_link[da[j - 1]] = s;
if (s->rtavl_link[0] != NULL)
r->rtavl_link[1] = s->rtavl_link[0];
else
{
r->rtavl_rtag = RTAVL_THREAD;
r->rtavl_link[1] = s;
}
|
Finally, we copy p's old information into s, except for the actual
data:
| | s->rtavl_balance = p->rtavl_balance;
s->rtavl_link[0] = p->rtavl_link[0];
s->rtavl_link[1] = p->rtavl_link[1];
s->rtavl_rtag = p->rtavl_rtag;
|
