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;
}
*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)     {
}
*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)
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> =
if (r->rtavl_link[0] != NULL)   {
struct rtavl_node *t = r->rtavl_link[0];
while (t->rtavl_rtag == RTAVL_CHILD)
}
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;
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)
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)
}

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;
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)