www.delorie.com/gnu/docs/avl/libavl_285.html   search  
 
Buy GNU books!


GNU libavl 2.0.1

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

Chapter 9

Section 9.3.3

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

 
&#60;@xref{\NODE\, , Find parent of a TBST node; tbst =>.&#62; 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); &#60;@xref{\NODE\, , Step 1: Search TBST for insertion point; tbst =>.&#62; trb,255} &#60;@xref{\NODE\, , Step 2: Insert TRB node.&#62;,339} p = n; for (;;)
{ struct trb_node *f, *g; f = find_parent (tree, p); if (f == (struct trb_node *) &tree-&#62;trb_root
|| f-&#62;trb_color == TRB_BLACK) break; g = find_parent (tree, f); if (g == (struct trb_node *) &tree-&#62;trb_root) break; if (g-&#62;trb_link[0] == f)
{ struct trb_node *y = g-&#62;trb_link[1]; if (g-&#62;trb_tag[1] == TRB_CHILD && y-&#62;trb_color == TRB_RED)
{ f-&#62;trb_color = y-&#62;trb_color = TRB_BLACK; g-&#62;trb_color = TRB_RED; p = g; }
else
{ struct trb_node *c, *x; if (f-&#62;trb_link[0] == p) y = f; else
{ x = f; y = x-&#62;trb_link[1]; x-&#62;trb_link[1] = y-&#62;trb_link[0]; y-&#62;trb_link[0] = x; g-&#62;trb_link[0] = y; if (y-&#62;trb_tag[0] == TRB_THREAD)
{ y-&#62;trb_tag[0] = TRB_CHILD; x-&#62;trb_tag[1] = TRB_THREAD; x-&#62;trb_link[1] = y; } } c = find_parent (tree, g); c-&#62;trb_link[c-&#62;trb_link[0] != g] = y; x = g; x-&#62;trb_color = TRB_RED; y-&#62;trb_color = TRB_BLACK; x-&#62;trb_link[0] = y-&#62;trb_link[1]; y-&#62;trb_link[1] = x; if (y-&#62;trb_tag[1] == TRB_THREAD)
{ y-&#62;trb_tag[1] = TRB_CHILD; x-&#62;trb_tag[0] = TRB_THREAD; x-&#62;trb_link[0] = y; } break; } }
else
{ struct trb_node *y = g-&#62;trb_link[0]; if (g-&#62;trb_tag[0] == TRB_CHILD && y-&#62;trb_color == TRB_RED)
{ f-&#62;trb_color = y-&#62;trb_color = TRB_BLACK; g-&#62;trb_color = TRB_RED; p = g; }
else
{ struct trb_node *c, *x; if (f-&#62;trb_link[1] == p) y = f; else
{ x = f; y = x-&#62;trb_link[0]; x-&#62;trb_link[0] = y-&#62;trb_link[1]; y-&#62;trb_link[1] = x; g-&#62;trb_link[1] = y; if (y-&#62;trb_tag[1] == TRB_THREAD)
{ y-&#62;trb_tag[1] = TRB_CHILD; x-&#62;trb_tag[0] = TRB_THREAD; x-&#62;trb_link[0] = y; } } c = find_parent (tree, g); c-&#62;trb_link[c-&#62;trb_link[0] != g] = y; x = g; x-&#62;trb_color = TRB_RED; y-&#62;trb_color = TRB_BLACK; x-&#62;trb_link[1] = y-&#62;trb_link[0]; y-&#62;trb_link[0] = x; if (y-&#62;trb_tag[0] == TRB_THREAD)
{ y-&#62;trb_tag[0] = TRB_CHILD; x-&#62;trb_tag[1] = TRB_THREAD; x-&#62;trb_link[1] = y; } break; } } } tree-&#62;trb_root-&#62;trb_color = TRB_BLACK; return &n-&#62;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-&#62;trb_link[0]; if (s-&#62;trb_tag[0] == TRB_THREAD) break; r = s; } p-&#62;trb_data = s-&#62;trb_data; if (s-&#62;trb_tag[1] == TRB_THREAD)
{ r-&#62;trb_tag[0] = TRB_THREAD; r-&#62;trb_link[0] = p; }
else
{ struct trb_node *t = r-&#62;trb_link[0] = s-&#62;trb_link[1]; while (t-&#62;trb_tag[0] == TRB_CHILD) t = t-&#62;trb_link[0]; t-&#62;trb_link[0] = p; } p = s;

Section 9.4.5

1. The code used in the rebalancing loop is related to &#60;@xref{\NODE\, , \TITLE\}.&#62;{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.

 
&#60;@xref{\NODE\, , Find parent of a TBST node; tbst =>.&#62; 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); &#60;@xref{\NODE\, , Step 1: Search TAVL tree for item to delete; tavl =>.&#62; trb,312} if (p-&#62;trb_tag[1] == TRB_THREAD)
{ if (p-&#62;trb_tag[0] == TRB_CHILD)
{ struct trb_node *t = p-&#62;trb_link[0]; while (t-&#62;trb_tag[1] == TRB_CHILD) t = t-&#62;trb_link[1]; t-&#62;trb_link[1] = p-&#62;trb_link[1]; x = q-&#62;trb_link[dir] = p-&#62;trb_link[0]; }
else
{ q-&#62;trb_link[dir] = p-&#62;trb_link[dir]; if (q != (struct trb_node *) &tree-&#62;trb_root) q-&#62;trb_tag[dir] = TRB_THREAD; x = NULL; } f = q; }
else
{ enum trb_color t; struct trb_node *r = p-&#62;trb_link[1]; if (r-&#62;trb_tag[0] == TRB_THREAD)
{ r-&#62;trb_link[0] = p-&#62;trb_link[0]; r-&#62;trb_tag[0] = p-&#62;trb_tag[0]; if (r-&#62;trb_tag[0] == TRB_CHILD)
{ struct trb_node *t = r-&#62;trb_link[0]; while (t-&#62;trb_tag[1] == TRB_CHILD) t = t-&#62;trb_link[1]; t-&#62;trb_link[1] = r; } q-&#62;trb_link[dir] = r; x = r-&#62;trb_tag[1] == TRB_CHILD ? r-&#62;trb_link[1] : NULL; t = r-&#62;trb_color; r-&#62;trb_color = p-&#62;trb_color; p-&#62;trb_color = t; f = r; dir = 1; }
else
{ struct trb_node *s; for (;;)
{ s = r-&#62;trb_link[0]; if (s-&#62;trb_tag[0] == TRB_THREAD) break; r = s; } if (s-&#62;trb_tag[1] == TRB_CHILD) x = r-&#62;trb_link[0] = s-&#62;trb_link[1]; else
{ r-&#62;trb_link[0] = s; r-&#62;trb_tag[0] = TRB_THREAD; x = NULL; } s-&#62;trb_link[0] = p-&#62;trb_link[0]; if (p-&#62;trb_tag[0] == TRB_CHILD)
{ struct trb_node *t = p-&#62;trb_link[0]; while (t-&#62;trb_tag[1] == TRB_CHILD) t = t-&#62;trb_link[1]; t-&#62;trb_link[1] = s; s-&#62;trb_tag[0] = TRB_CHILD; } s-&#62;trb_link[1] = p-&#62;trb_link[1]; s-&#62;trb_tag[1] = TRB_CHILD; t = s-&#62;trb_color; s-&#62;trb_color = p-&#62;trb_color; p-&#62;trb_color = t; q-&#62;trb_link[dir] = s; f = r; dir = 0; } } if (p-&#62;trb_color == TRB_BLACK)
{ for (;;) { if (x != NULL && x-&#62;trb_color == TRB_RED)
{ x-&#62;trb_color = TRB_BLACK; break; } if (f == (struct trb_node *) &tree-&#62;trb_root) break; g = find_parent (tree, f); if (dir == 0)
{ struct trb_node *w = f-&#62;trb_link[1]; if (w-&#62;trb_color == TRB_RED)
{ w-&#62;trb_color = TRB_BLACK; f-&#62;trb_color = TRB_RED; f-&#62;trb_link[1] = w-&#62;trb_link[0]; w-&#62;trb_link[0] = f; g-&#62;trb_link[g-&#62;trb_link[0] != f] = w; g = w; w = f-&#62;trb_link[1]; } if ((w-&#62;trb_tag[0] == TRB_THREAD || w-&#62;trb_link[0]-&#62;trb_color == TRB_BLACK) && (w-&#62;trb_tag[1] == TRB_THREAD || w-&#62;trb_link[1]-&#62;trb_color == TRB_BLACK))
w-&#62;trb_color = TRB_RED; else
{ if (w-&#62;trb_tag[1] == TRB_THREAD || w-&#62;trb_link[1]-&#62;trb_color == TRB_BLACK)
{ struct trb_node *y = w-&#62;trb_link[0]; y-&#62;trb_color = TRB_BLACK; w-&#62;trb_color = TRB_RED; w-&#62;trb_link[0] = y-&#62;trb_link[1]; y-&#62;trb_link[1] = w; w = f-&#62;trb_link[1] = y; if (w-&#62;trb_tag[1] == TRB_THREAD)
{ w-&#62;trb_tag[1] = TRB_CHILD; w-&#62;trb_link[1]-&#62;trb_tag[0] = TRB_THREAD; w-&#62;trb_link[1]-&#62;trb_link[0] = w; } } w-&#62;trb_color = f-&#62;trb_color; f-&#62;trb_color = TRB_BLACK; w-&#62;trb_link[1]-&#62;trb_color = TRB_BLACK; f-&#62;trb_link[1] = w-&#62;trb_link[0]; w-&#62;trb_link[0] = f; g-&#62;trb_link[g-&#62;trb_link[0] != f] = w; if (w-&#62;trb_tag[0] == TRB_THREAD)
{ w-&#62;trb_tag[0] = TRB_CHILD; f-&#62;trb_tag[1] = TRB_THREAD; f-&#62;trb_link[1] = w; } break; } }
else
{ struct trb_node *w = f-&#62;trb_link[0]; if (w-&#62;trb_color == TRB_RED)
{ w-&#62;trb_color = TRB_BLACK; f-&#62;trb_color = TRB_RED; f-&#62;trb_link[0] = w-&#62;trb_link[1]; w-&#62;trb_link[1] = f; g-&#62;trb_link[g-&#62;trb_link[0] != f] = w; g = w; w = f-&#62;trb_link[0]; } if ((w-&#62;trb_tag[0] == TRB_THREAD || w-&#62;trb_link[0]-&#62;trb_color == TRB_BLACK) && (w-&#62;trb_tag[1] == TRB_THREAD || w-&#62;trb_link[1]-&#62;trb_color == TRB_BLACK))
w-&#62;trb_color = TRB_RED; else
{ if (w-&#62;trb_tag[0] == TRB_THREAD || w-&#62;trb_link[0]-&#62;trb_color == TRB_BLACK)
{ struct trb_node *y = w-&#62;trb_link[1]; y-&#62;trb_color = TRB_BLACK; w-&#62;trb_color = TRB_RED; w-&#62;trb_link[1] = y-&#62;trb_link[0]; y-&#62;trb_link[0] = w; w = f-&#62;trb_link[0] = y; if (w-&#62;trb_tag[0] == TRB_THREAD)
{ w-&#62;trb_tag[0] = TRB_CHILD; w-&#62;trb_link[0]-&#62;trb_tag[1] = TRB_THREAD; w-&#62;trb_link[0]-&#62;trb_link[1] = w; } } w-&#62;trb_color = f-&#62;trb_color; f-&#62;trb_color = TRB_BLACK; w-&#62;trb_link[0]-&#62;trb_color = TRB_BLACK; f-&#62;trb_link[0] = w-&#62;trb_link[1]; w-&#62;trb_link[1] = f; g-&#62;trb_link[g-&#62;trb_link[0] != f] = w; if (w-&#62;trb_tag[1] == TRB_THREAD)
{ w-&#62;trb_tag[1] = TRB_CHILD; f-&#62;trb_tag[0] = TRB_THREAD; f-&#62;trb_link[0] = w; } break; } } x = f; f = find_parent (tree, x); if (f == (struct trb_node *) &tree-&#62;trb_root) break; dir = f-&#62;trb_link[0] != x; } } tree-&#62;trb_alloc-&#62;libavl_free (tree-&#62;trb_alloc, p); tree-&#62;trb_count--; return (void *) item; }


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

  webmaster   donations   bookstore     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003