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

y = f;
else                 {
x = f;

y->trb_tag[0] = TRB_CHILD;
}
}

c = find_parent (tree, g);

x = g;
x->trb_color = TRB_RED;
y->trb_color = TRB_BLACK;

y->trb_tag[1] = TRB_CHILD;
}
break;
}
}       else         {
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;

y = f;
else                 {
x = f;

y->trb_tag[1] = TRB_CHILD;
}
}

c = find_parent (tree, g);

x = g;
x->trb_color = TRB_RED;
y->trb_color = TRB_BLACK;

y->trb_tag[0] = TRB_CHILD;
}
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;
break;

r = s;
}

p->trb_data = s->trb_data;

} else   {
while (t->trb_tag[0] == TRB_CHILD)
}

p = s;
```

#### 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[0] == TRB_CHILD)         {
while (t->trb_tag[1] == TRB_CHILD)
}       else         {
if (q != (struct trb_node *) &tree->trb_root)
x = NULL;
}
f = q;
}   else     {
enum trb_color t;

r->trb_tag[0] = p->trb_tag[0];
if (r->trb_tag[0] == TRB_CHILD)             {
while (t->trb_tag[1] == TRB_CHILD)
}
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 (;;)             {
break;

r = s;
}

if (s->trb_tag[1] == TRB_CHILD)
else             {
x = NULL;
}

if (p->trb_tag[0] == TRB_CHILD)             {
while (t->trb_tag[1] == TRB_CHILD)

s->trb_tag[0] = TRB_CHILD;
}

s->trb_tag[1] = TRB_CHILD;

t = s->trb_color;
s->trb_color = p->trb_color;
p->trb_color = t;

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

if (w->trb_color == TRB_RED)                 {
w->trb_color = TRB_BLACK;
f->trb_color = TRB_RED;

g = w;
}

|| w->trb_link[1]->trb_color == TRB_BLACK))                 w->trb_color = TRB_RED;
else                 {
y->trb_color = TRB_BLACK;
w->trb_color = TRB_RED;

w->trb_tag[1] = TRB_CHILD;
}
}

w->trb_color = f->trb_color;
f->trb_color = TRB_BLACK;

w->trb_tag[0] = TRB_CHILD;
}
break;
}
}           else             {

if (w->trb_color == TRB_RED)                 {
w->trb_color = TRB_BLACK;
f->trb_color = TRB_RED;

g = w;
}

|| w->trb_link[1]->trb_color == TRB_BLACK))                 w->trb_color = TRB_RED;
else                 {
y->trb_color = TRB_BLACK;
w->trb_color = TRB_RED;

w->trb_tag[0] = TRB_CHILD;
}
}

w->trb_color = f->trb_color;
f->trb_color = TRB_BLACK;

w->trb_tag[1] = TRB_CHILD;
}
break;
}
}

x = f;
f = find_parent (tree, x);
if (f == (struct trb_node *) &tree->trb_root)
break;