GNU libavl 2.0.1
Chapter 10
1.
If we already have right-threaded trees, then we can get the benefits of
a left-threaded tree just by reversing the sense of the comparison
function, so there is no additional benefit to left-threaded trees.
Section 10.5.1
1.
| | struct rtbst_node *s = r->rtbst_link[0];
while (s->rtbst_link[0] != NULL)
{
r = s;
s = r->rtbst_link[0];
}
p->rtbst_data = s->rtbst_data;
if (s->rtbst_rtag == RTBST_THREAD)
r->rtbst_link[0] = NULL;
else
r->rtbst_link[0] = s->rtbst_link[1];
p = s;
|
Section 10.5.2
1.
This alternate version is not really an improvement: it runs up against
the same problem as right-looking deletion, so it sometimes needs to
search for a predecessor.
| | struct rtbst_node *s = r->rtbst_link[1];
while (s->rtbst_rtag == RTBST_CHILD)
{
r = s;
s = r->rtbst_link[1];
}
p->rtbst_data = s->rtbst_data;
if (s->rtbst_link[0] != NULL)
{
struct rtbst_node *t = s->rtbst_link[0];
while (t->rtbst_rtag == RTBST_CHILD)
t = t->rtbst_link[1];
t->rtbst_link[1] = p;
r->rtbst_link[1] = s->rtbst_link[0];
}
else
{
r->rtbst_link[1] = p;
r->rtbst_rtag = RTBST_THREAD;
}
p = s;
|
