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

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.

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

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

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

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

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

3.

680. <Case 4 in RTAVL deletion, alternate version 680> =
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;