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