Chapter 10 [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

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.

671. <Case 4 in right-looking RTBST deletion, alternate version 671> =
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.

672. <Case 4 in left-looking RTBST deletion, alternate version 672> =
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;