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.

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;