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

search

	Buy GNU books!

GNU libavl 2.0.1

Chapter 9

Section 9.3.3

1. For a brief explanation of an algorithm similar to the one here, see 16.3 Insertion.

<@xref{\NODE\, , Find parent of a TBST node; tbst =>.> trb,327} void ** trb_probe (struct trb_table *tree, void *item) { struct trb_node *p; /* Traverses tree looking for insertion point. */ struct trb_node *n; /* Newly inserted node. */ int dir; /* Side of p on which n is inserted. */ assert (tree != NULL && item != NULL); <@xref{\NODE\, , Step 1: Search TBST for insertion point; tbst =>.> trb,255} <@xref{\NODE\, , Step 2: Insert TRB node.>,339} p = n; for (;;) { struct trb_node *f, *g; f = find_parent (tree, p); if (f == (struct trb_node *) &tree->trb_root || f->trb_color == TRB_BLACK) break; g = find_parent (tree, f); if (g == (struct trb_node *) &tree->trb_root) break; if (g->trb_link[0] == f) { struct trb_node *y = g->trb_link[1]; if (g->trb_tag[1] == TRB_CHILD && y->trb_color == TRB_RED) { f->trb_color = y->trb_color = TRB_BLACK; g->trb_color = TRB_RED; p = g; } else { struct trb_node *c, *x; if (f->trb_link[0] == p) y = f; else { x = f; y = x->trb_link[1]; x->trb_link[1] = y->trb_link[0]; y->trb_link[0] = x; g->trb_link[0] = y; if (y->trb_tag[0] == TRB_THREAD) { y->trb_tag[0] = TRB_CHILD; x->trb_tag[1] = TRB_THREAD; x->trb_link[1] = y; } } c = find_parent (tree, g); c->trb_link[c->trb_link[0] != g] = y; x = g; x->trb_color = TRB_RED; y->trb_color = TRB_BLACK; x->trb_link[0] = y->trb_link[1]; y->trb_link[1] = x; if (y->trb_tag[1] == TRB_THREAD) { y->trb_tag[1] = TRB_CHILD; x->trb_tag[0] = TRB_THREAD; x->trb_link[0] = y; } break; } } else { struct trb_node *y = g->trb_link[0]; if (g->trb_tag[0] == TRB_CHILD && y->trb_color == TRB_RED) { f->trb_color = y->trb_color = TRB_BLACK; g->trb_color = TRB_RED; p = g; } else { struct trb_node *c, *x; if (f->trb_link[1] == p) y = f; else { x = f; y = x->trb_link[0]; x->trb_link[0] = y->trb_link[1]; y->trb_link[1] = x; g->trb_link[1] = y; if (y->trb_tag[1] == TRB_THREAD) { y->trb_tag[1] = TRB_CHILD; x->trb_tag[0] = TRB_THREAD; x->trb_link[0] = y; } } c = find_parent (tree, g); c->trb_link[c->trb_link[0] != g] = y; x = g; x->trb_color = TRB_RED; y->trb_color = TRB_BLACK; x->trb_link[1] = y->trb_link[0]; y->trb_link[0] = x; if (y->trb_tag[0] == TRB_THREAD) { y->trb_tag[0] = TRB_CHILD; x->trb_tag[1] = TRB_THREAD; x->trb_link[1] = y; } break; } } } tree->trb_root->trb_color = TRB_BLACK; return &n->trb_data; }

Section 9.4.2

1.

struct trb_node *s; da[k] = 1; pa[k++] = p; for (;;) { da[k] = 0; pa[k++] = r; s = r->trb_link[0]; if (s->trb_tag[0] == TRB_THREAD) break; r = s; } p->trb_data = s->trb_data; if (s->trb_tag[1] == TRB_THREAD) { r->trb_tag[0] = TRB_THREAD; r->trb_link[0] = p; } else { struct trb_node *t = r->trb_link[0] = s->trb_link[1]; while (t->trb_tag[0] == TRB_CHILD) t = t->trb_link[0]; t->trb_link[0] = p; } p = s;

Section 9.4.5

1. The code used in the rebalancing loop is related to <@xref{\NODE\, , \TITLE\}.>{Step 3: Rebalance tree after PRB deletion,571}. Variable x is initialized by step 2 here, though, because otherwise the pseudo-root node would be required to have a trb_tag[] member.

<@xref{\NODE\, , Find parent of a TBST node; tbst =>.> trb,327} void * trb_delete (struct trb_table *tree, const void *item) { struct trb_node *p; /* Node to delete. */ struct trb_node *q; /* Parent of p. */ struct trb_node *x; /* Node we might want to recolor red (maybe NULL). */ struct trb_node *f; /* Parent of x. */ struct trb_node *g; /* Parent of f. */ int dir, cmp; assert (tree != NULL && item != NULL); <@xref{\NODE\, , Step 1: Search TAVL tree for item to delete; tavl =>.> trb,312} if (p->trb_tag[1] == TRB_THREAD) { if (p->trb_tag[0] == TRB_CHILD) { struct trb_node *t = p->trb_link[0]; while (t->trb_tag[1] == TRB_CHILD) t = t->trb_link[1]; t->trb_link[1] = p->trb_link[1]; x = q->trb_link[dir] = p->trb_link[0]; } else { q->trb_link[dir] = p->trb_link[dir]; if (q != (struct trb_node *) &tree->trb_root) q->trb_tag[dir] = TRB_THREAD; x = NULL; } f = q; } else { enum trb_color t; struct trb_node *r = p->trb_link[1]; if (r->trb_tag[0] == TRB_THREAD) { r->trb_link[0] = p->trb_link[0]; r->trb_tag[0] = p->trb_tag[0]; if (r->trb_tag[0] == TRB_CHILD) { struct trb_node *t = r->trb_link[0]; while (t->trb_tag[1] == TRB_CHILD) t = t->trb_link[1]; t->trb_link[1] = r; } q->trb_link[dir] = r; x = r->trb_tag[1] == TRB_CHILD ? r->trb_link[1] : NULL; t = r->trb_color; r->trb_color = p->trb_color; p->trb_color = t; f = r; dir = 1; } else { struct trb_node *s; for (;;) { s = r->trb_link[0]; if (s->trb_tag[0] == TRB_THREAD) break; r = s; } if (s->trb_tag[1] == TRB_CHILD) x = r->trb_link[0] = s->trb_link[1]; else { r->trb_link[0] = s; r->trb_tag[0] = TRB_THREAD; x = NULL; } s->trb_link[0] = p->trb_link[0]; if (p->trb_tag[0] == TRB_CHILD) { struct trb_node *t = p->trb_link[0]; while (t->trb_tag[1] == TRB_CHILD) t = t->trb_link[1]; t->trb_link[1] = s; s->trb_tag[0] = TRB_CHILD; } s->trb_link[1] = p->trb_link[1]; s->trb_tag[1] = TRB_CHILD; t = s->trb_color; s->trb_color = p->trb_color; p->trb_color = t; q->trb_link[dir] = s; f = r; dir = 0; } } if (p->trb_color == TRB_BLACK) { for (;;) { if (x != NULL && x->trb_color == TRB_RED) { x->trb_color = TRB_BLACK; break; } if (f == (struct trb_node *) &tree->trb_root) break; g = find_parent (tree, f); if (dir == 0) { struct trb_node *w = f->trb_link[1]; if (w->trb_color == TRB_RED) { w->trb_color = TRB_BLACK; f->trb_color = TRB_RED; f->trb_link[1] = w->trb_link[0]; w->trb_link[0] = f; g->trb_link[g->trb_link[0] != f] = w; g = w; w = f->trb_link[1]; } if ((w->trb_tag[0] == TRB_THREAD || w->trb_link[0]->trb_color == TRB_BLACK) && (w->trb_tag[1] == TRB_THREAD || w->trb_link[1]->trb_color == TRB_BLACK)) w->trb_color = TRB_RED; else { if (w->trb_tag[1] == TRB_THREAD || w->trb_link[1]->trb_color == TRB_BLACK) { struct trb_node *y = w->trb_link[0]; y->trb_color = TRB_BLACK; w->trb_color = TRB_RED; w->trb_link[0] = y->trb_link[1]; y->trb_link[1] = w; w = f->trb_link[1] = y; if (w->trb_tag[1] == TRB_THREAD) { w->trb_tag[1] = TRB_CHILD; w->trb_link[1]->trb_tag[0] = TRB_THREAD; w->trb_link[1]->trb_link[0] = w; } } w->trb_color = f->trb_color; f->trb_color = TRB_BLACK; w->trb_link[1]->trb_color = TRB_BLACK; f->trb_link[1] = w->trb_link[0]; w->trb_link[0] = f; g->trb_link[g->trb_link[0] != f] = w; if (w->trb_tag[0] == TRB_THREAD) { w->trb_tag[0] = TRB_CHILD; f->trb_tag[1] = TRB_THREAD; f->trb_link[1] = w; } break; } } else { struct trb_node *w = f->trb_link[0]; if (w->trb_color == TRB_RED) { w->trb_color = TRB_BLACK; f->trb_color = TRB_RED; f->trb_link[0] = w->trb_link[1]; w->trb_link[1] = f; g->trb_link[g->trb_link[0] != f] = w; g = w; w = f->trb_link[0]; } if ((w->trb_tag[0] == TRB_THREAD || w->trb_link[0]->trb_color == TRB_BLACK) && (w->trb_tag[1] == TRB_THREAD || w->trb_link[1]->trb_color == TRB_BLACK)) w->trb_color = TRB_RED; else { if (w->trb_tag[0] == TRB_THREAD || w->trb_link[0]->trb_color == TRB_BLACK) { struct trb_node *y = w->trb_link[1]; y->trb_color = TRB_BLACK; w->trb_color = TRB_RED; w->trb_link[1] = y->trb_link[0]; y->trb_link[0] = w; w = f->trb_link[0] = y; if (w->trb_tag[0] == TRB_THREAD) { w->trb_tag[0] = TRB_CHILD; w->trb_link[0]->trb_tag[1] = TRB_THREAD; w->trb_link[0]->trb_link[1] = w; } } w->trb_color = f->trb_color; f->trb_color = TRB_BLACK; w->trb_link[0]->trb_color = TRB_BLACK; f->trb_link[0] = w->trb_link[1]; w->trb_link[1] = f; g->trb_link[g->trb_link[0] != f] = w; if (w->trb_tag[1] == TRB_THREAD) { w->trb_tag[1] = TRB_CHILD; f->trb_tag[0] = TRB_THREAD; f->trb_link[0] = w; } break; } } x = f; f = find_parent (tree, x); if (f == (struct trb_node *) &tree->trb_root) break; dir = f->trb_link[0] != x; } } tree->trb_alloc->libavl_free (tree->trb_alloc, p); tree->trb_count--; return (void *) item; }