Chapter 11

Section 11.3

1.

/* Rotates right at *yp. */
static void 
rotate_right (struct rtbst_node **yp) 
{
  struct rtbst_node *y = *yp;
  struct rtbst_node *x = y->rtbst_link[0];
  if (x->rtbst_rtag[1] == RTBST_THREAD) 
    {
      x->rtbst_rtag = RTBST_CHILD;
      y->rtbst_link[0] = NULL;
    }
  else 
    y->rtbst_link[0] = x->rtbst_link[1];
  x->rtbst_link[1] = y;
  *yp = x;
}

/* Rotates left at *xp. */
static void 
rotate_left (struct rtbst_node **xp) 
{
  struct rtbst_node *x = *xp;
  struct rtbst_node *y = x->rtbst_link[1];
  if (y->rtbst_link[0] == NULL) 
    {
      x->rtbst_rtag = RTBST_THREAD;
      x->rtbst_link[1] = y;
    }
  else 
    x->rtbst_link[1] = y->rtbst_link[0];
  y->rtbst_link[0] = x;
  *xp = y;
}

Section 11.5.4

1. There is no general efficient algorithm to find the parent of a node in an RTAVL tree. The lack of left threads means that half the time we must do a full search from the top of the tree. This would increase the execution time for deletion unacceptably.

2.

673. <Step 2: Delete RTAVL node, right-looking 673> =
if (p->rtavl_rtag == RTAVL_THREAD) 
  {
    if (p->rtavl_link[0] != NULL)
      { 
        <Case 1 in RTAVL deletion, right-looking 674> 
      }
    else 
      { 
        <Case 2 in RTAVL deletion, right-looking 675> 
      }
  } 
else 
  {
    struct rtavl_node *r = p->rtavl_link[1];
    if (r->rtavl_link[0] == NULL)
      { 
        <Case 3 in RTAVL deletion, right-looking 676> 
      }
    else 
      { 
        <Case 4 in RTAVL deletion, right-looking 677> 
      }
  }

tree->rtavl_alloc->libavl_free (tree->rtavl_alloc, p);

674. <Case 1 in RTAVL deletion, right-looking 674> =
struct rtavl_node *t = p->rtavl_link[0];
while (t->rtavl_rtag == RTAVL_CHILD)
  t = t->rtavl_link[1];
t->rtavl_link[1] = p->rtavl_link[1];
pa[k - 1]->rtavl_link[da[k - 1]] = p->rtavl_link[0];

This code is included in 673.

675. <Case 2 in RTAVL deletion, right-looking 675> =
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 673.

676. <Case 3 in RTAVL deletion, right-looking 676> =
r->rtavl_link[0] = p->rtavl_link[0];
if (r->rtavl_link[0] != NULL) 
  {
    struct rtavl_node *t = r->rtavl_link[0];
    while (t->rtavl_rtag == RTAVL_CHILD)
      t = t->rtavl_link[1];
    t->rtavl_link[1] = r;
  }
pa[k - 1]->rtavl_link[da[k - 1]] = r;
r->rtavl_balance = p->rtavl_balance;
da[k] = 1;
pa[k++] = r;

This code is included in 673.

677. <Case 4 in RTAVL deletion, right-looking 677> =
struct rtavl_node *s;
int j = k++;

for (;;) 
  {
    da[k] = 0;
    pa[k++] = r;
    s = r->rtavl_link[0];
    if (s->rtavl_link[0] == NULL)
      break;

    r = s;
  }

da[j] = 1;
pa[j] = pa[j - 1]->rtavl_link[da[j - 1]] = s;

if (s->rtavl_rtag == RTAVL_CHILD)
  r->rtavl_link[0] = s->rtavl_link[1];
else 
  r->rtavl_link[0] = NULL;

if (p->rtavl_link[0] != NULL) 
  {
    struct rtavl_node *t = p->rtavl_link[0];
    while (t->rtavl_rtag == RTAVL_CHILD)
      t = t->rtavl_link[1];
    t->rtavl_link[1] = s;
  }

s->rtavl_link[0] = p->rtavl_link[0];
s->rtavl_link[1] = p->rtavl_link[1];
s->rtavl_rtag = RTAVL_CHILD;
s->rtavl_balance = p->rtavl_balance;

This code is included in 673.

3.

678. <Case 4 in RTAVL deletion, alternate version 678> =
struct rtavl_node *s;

da[k] = 0;
pa[k++] = p;
for (;;) 
  {
    da[k] = 1;
    pa[k++] = r;
    s = r->rtavl_link[1];
    if (s->rtavl_rtag == RTAVL_THREAD)
      break;
    r = s;
  }

if (s->rtavl_link[0] != NULL) 
  {
    struct rtavl_node *t = s->rtavl_link[0];
    while (t->rtavl_rtag == RTAVL_CHILD)
      t = t->rtavl_link[1];
    t->rtavl_link[1] = p;
  }

p->rtavl_data = s->rtavl_data;
if (s->rtavl_link[0] != NULL)
  r->rtavl_link[1] = s->rtavl_link[0];
else 
  {
    r->rtavl_rtag = RTAVL_THREAD;
    r->rtavl_link[1] = p;
  }

p = s;