www.delorie.com/gnu/docs/avl/libavl_287.html

search

	Buy GNU books!

GNU libavl 2.0.1

Chapter 11

Section 11.3

1.

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

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.

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

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 @refalso{673

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 @refalso{673

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 @refalso{673

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 @refalso{673

3.

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;