Chapter 9

#### Section 9.3.3

1. For a brief explanation of an algorithm similar to the one here, see Inserting into a PRB Tree.

668. <TRB item insertion function, without stack 668> =
<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); <Step 1: Search TBST for insertion point; tbst => trb 255> <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
{ 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
{ 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.

669. <Case 4 in TRB deletion, alternate version 669> =
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)
else

#### Section 9.4.5

1. The code used in the rebalancing loop is related to <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.

670. <TRB item deletion function, without stack 670> =
<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); <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)
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)
{ 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
{ 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)