Chapter 9 [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

Section 9.3.3

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

670. <TRB item insertion function, without stack 670> =
<Find parent of a TBST node; tbst => trb 329>

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 257> <Step 2: Insert TRB node 341> 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.

671. <Case 4 in TRB deletion, alternate version 671> =
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 <Step 3: Rebalance tree after PRB deletion 573>. Variable x is initialized by step 2 here, though, because otherwise the pseudo-root node would be required to have a trb_tag[] member.

672. <TRB item deletion function, without stack 672> =
<Find parent of a TBST node; tbst => trb 329>

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