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


GNU libavl 2.0.1

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

Chapter 8

Section 8.1

1. No: the compiler may insert padding between or after structure members. For example, today (2002) the most common desktop computers have 32-bit pointers and and 8-bit chars. On these systems, most compilers will pad out structures to a multiple of 32 bits. Under these circumstances, struct tavl_node is no larger than struct avl_node, because (32 + 32 + 8) and (32 + 32 + 8 + 8 + 8) both round up to the same multiple of 32 bits, or 96 bits.

Section 8.2

1. We just have to special-case the possibility that subtree b is a thread.

 
static void 
rotate_right (struct tavl_node **yp)
{ struct tavl_node *y = *yp; struct tavl_node *x = y-&#62;tavl_link[0]; if (x-&#62;tavl_tag[1] == TAVL_THREAD)
{ x-&#62;tavl_tag[1] = TAVL_CHILD; y-&#62;tavl_tag[0] = TAVL_THREAD; y-&#62;tavl_link[0] = x; } else
y-&#62;tavl_link[0] = x-&#62;tavl_link[1]; x-&#62;tavl_link[1] = y; *yp = x; }

 
static void 
rotate_left (struct tavl_node **xp)
{ struct tavl_node *x = *xp; struct tavl_node *y = x-&#62;tavl_link[1]; if (y-&#62;tavl_tag[0] == TAVL_THREAD)
{ y-&#62;tavl_tag[0] = TAVL_CHILD; x-&#62;tavl_tag[1] = TAVL_THREAD; x-&#62;tavl_link[1] = y; } else
x-&#62;tavl_link[1] = y-&#62;tavl_link[0]; y-&#62;tavl_link[0] = x; *xp = y; }

Section 8.4.2

1. Besides this change, the statement

 

must be removed from &#60;@xref{\NODE\, , Step 4: Rebalance after TAVL insertion.&#62;,304}, and copies added to the end of &#60;@xref{\NODE\, , \TITLE\}.&#62;{Rebalance TAVL tree after insertion in right subtree,308} and &#60;@ref{\NODE\, , Rebalance for -.&#62; balance factor in TAVL insertion in left subtree,306}.

 
w = x-&#62;tavl_link[1];
rotate_left (&y-&#62;tavl_link[0]);
rotate_right (&z-&#62;tavl_link[y != z-&#62;tavl_link[0]]);
if (w-&#62;tavl_balance == -1) 
x-&#62;tavl_balance = 0, y-&#62;tavl_balance = +1; else if (w-&#62;tavl_balance == 0)
x-&#62;tavl_balance = y-&#62;tavl_balance = 0; else /* w-&#62;tavl_balance == +1 */
x-&#62;tavl_balance = -1, y-&#62;tavl_balance = 0; w-&#62;tavl_balance = 0;

Section 8.5.2

1. We can just reuse the alternate implementation of case 4 for TBST deletion, following it by setting up q and dir as the rebalancing step expects them to be.

 
&#60;@ref{alternate version; tbst @result{, , Case 4 in TBST deletion.&#62; tavl},656}
q = r;
dir = 0;

Section 8.5.6

1. Our argument here is similar to that in Exercise 7.7-4. Consider the links that are traversed to successfully find the parent of each node, besides the root, in the tree shown below. Do not include links followed on the side that does not lead to the node's parent. Because there are never more of these than on the successful side, they add only a constant time to the algorithm and can be ignored.

tbstdel6

The table below lists the links followed. The important point is that no link is listed twice.

Node Links Followed to Node's Parent
0 0-&#62;2, 2-&#62;3
1 1-&#62;2
2 2-&#62;1, 1-&#62;0
3 3-&#62;5, 5-&#62;6
4 4-&#62;5
5 5-&#62;4, 4-&#62;3
6 (root)
7 7-&#62;6

This generalizes to all TBSTs. Because a TBST with n nodes contains only 2n links, this means we have an upper bound on finding the parent of every node in a TBST of at most 2n successful link traversals plus 2n unsuccessful link traversals. Averaging 4n over n nodes, we get an upper bound of 4n/n == 4 link traversals, on average, to find the parent of a given node.

This upper bound applies only to the average case, not to the case of any individual node. In particular, it does not say that the usage of the algorithm in tavl_delete() will exhibit average behavior. In practice, however, the performance of this algorithm in tavl_delete() seems quite acceptable. See Exercise 3 for an alternative with more certain behavior.

2. Instead of storing a null pointer in the left thread of the least node and the right thread of the greatest node, store a pointer to a node "above the root". To make this work properly, tavl_root will have to become an actual node, not just a node pointer, because otherwise trying to find its right child would invoke undefined behavior. Also, both of tavl_root's children would have to be the root node.

This is probably not worth it. On the surface it seems like a good idea but ugliness lurks beneath.

3. The necessary changes are pervasive, so the complete code for the modified function is presented below. The search step is borrowed from TRB deletion, presented in the next chapter.

 
void *
tavl_delete (struct tavl_table *tree, const void *item)
{ /* Stack of nodes. */ struct tavl_node *pa[TAVL_MAX_HEIGHT]; /* Nodes. */ unsigned char da[TAVL_MAX_HEIGHT]; /* tavl_link[] indexes. */ int k = 0; /* Stack pointer. */ struct tavl_node *p; /* Traverses tree to find node to delete. */ int cmp; /* Result of comparison between item and p. */ int dir; /* Child of p to visit next. */ assert (tree != NULL && item != NULL); &#60;@xref{\NODE\, , Step 1: Search TRB tree for item to delete; trb =>.&#62; tavl,350} &#60;@xref{with stack, , Step 2: Delete item from TAVL tree.&#62;,660} &#60;@xref{with stack, , Steps 3 and 4: Update balance factors and rebalance after TAVL deletion.&#62;,665} return (void *) item; }

 
if (p-&#62;tavl_tag[1] == TAVL_THREAD) 
{ if (p-&#62;tavl_tag[0] == TAVL_CHILD) {
&#60;@xref{with stack, , Case 1 in TAVL deletion.&#62;,661}
} else
{
&#60;@xref{with stack, , Case 2 in TAVL deletion.&#62;,662}
} }
else
{ struct tavl_node *r = p-&#62;tavl_link[1]; if (r-&#62;tavl_tag[0] == TAVL_THREAD) {
&#60;@xref{with stack, , Case 3 in TAVL deletion.&#62;,663}
} else
{
&#60;@xref{with stack, , Case 4 in TAVL deletion.&#62;,664}
} } tree-&#62;tavl_count--; tree-&#62;tavl_alloc-&#62;libavl_free (tree-&#62;tavl_alloc, p);
This code is included in @refalso{659

 
struct tavl_node *r = p-&#62;tavl_link[0];
while (r-&#62;tavl_tag[1] == TAVL_CHILD)
  r = r-&#62;tavl_link[1];
r-&#62;tavl_link[1] = p-&#62;tavl_link[1];
pa[k - 1]-&#62;tavl_link[da[k - 1]] = p-&#62;tavl_link[0];
This code is included in @refalso{660

 
pa[k - 1]-&#62;tavl_link[da[k - 1]] = p-&#62;tavl_link[da[k - 1]];
if (pa[k - 1] != (struct tavl_node *) &tree-&#62;tavl_root)
  pa[k - 1]-&#62;tavl_tag[da[k - 1]] = TAVL_THREAD;
This code is included in @refalso{660

 
r-&#62;tavl_link[0] = p-&#62;tavl_link[0];
r-&#62;tavl_tag[0] = p-&#62;tavl_tag[0];
r-&#62;tavl_balance = p-&#62;tavl_balance;
if (r-&#62;tavl_tag[0] == TAVL_CHILD) 
{ struct tavl_node *x = r-&#62;tavl_link[0]; while (x-&#62;tavl_tag[1] == TAVL_CHILD) x = x-&#62;tavl_link[1]; x-&#62;tavl_link[1] = r; } pa[k - 1]-&#62;tavl_link[da[k - 1]] = r; da[k] = 1; pa[k++] = r;
This code is included in @refalso{660

 
struct tavl_node *s;
int j = k++;
for (;;) 
{ da[k] = 0; pa[k++] = r; s = r-&#62;tavl_link[0]; if (s-&#62;tavl_tag[0] == TAVL_THREAD) break; r = s; } da[j] = 1; pa[j] = pa[j - 1]-&#62;tavl_link[da[j - 1]] = s; if (s-&#62;tavl_tag[1] == TAVL_CHILD) r-&#62;tavl_link[0] = s-&#62;tavl_link[1]; else
{ r-&#62;tavl_link[0] = s; r-&#62;tavl_tag[0] = TAVL_THREAD; } s-&#62;tavl_balance = p-&#62;tavl_balance; s-&#62;tavl_link[0] = p-&#62;tavl_link[0]; if (p-&#62;tavl_tag[0] == TAVL_CHILD)
{ struct tavl_node *x = p-&#62;tavl_link[0]; while (x-&#62;tavl_tag[1] == TAVL_CHILD) x = x-&#62;tavl_link[1]; x-&#62;tavl_link[1] = s; s-&#62;tavl_tag[0] = TAVL_CHILD; } s-&#62;tavl_link[1] = p-&#62;tavl_link[1]; s-&#62;tavl_tag[1] = TAVL_CHILD;
This code is included in @refalso{660

 
assert (k > 0);
while (--k > 0) 
{ struct tavl_node *y = pa[k]; if (da[k] == 0)
{ y-&#62;tavl_balance++; if (y-&#62;tavl_balance == +1)
break; else if (y-&#62;tavl_balance == +2)
{ &#60;@xref{with stack, , Step 4: Rebalance after TAVL deletion.&#62;,666} } }
else
{ &#60;@xref{with stack, , Steps 3 and 4: Symmetric case in TAVL deletion.&#62;,667} } }
This code is included in @refalso{659

 
struct tavl_node *x = y-&#62;tavl_link[1];
assert (x != NULL);
if (x-&#62;tavl_balance == -1) 
{ struct tavl_node *w; &#60;@xref{\NODE\, , Rebalance for -.&#62; balance factor in TAVL insertion in right subtree,310} pa[k - 1]-&#62;tavl_link[da[k - 1]] = w; } else if (x-&#62;tavl_balance == 0)
{ y-&#62;tavl_link[1] = x-&#62;tavl_link[0]; x-&#62;tavl_link[0] = y; x-&#62;tavl_balance = -1; y-&#62;tavl_balance = +1; pa[k - 1]-&#62;tavl_link[da[k - 1]] = x; break; } else /* x-&#62;tavl_balance == +1 */
{ if (x-&#62;tavl_tag[0] == TAVL_CHILD) y-&#62;tavl_link[1] = x-&#62;tavl_link[0]; else
{ y-&#62;tavl_tag[1] = TAVL_THREAD; x-&#62;tavl_tag[0] = TAVL_CHILD; } x-&#62;tavl_link[0] = y; x-&#62;tavl_balance = y-&#62;tavl_balance = 0; pa[k - 1]-&#62;tavl_link[da[k - 1]] = x; }
This code is included in @refalso{665

 
y-&#62;tavl_balance--;
if (y-&#62;tavl_balance == -1) 
break; else if (y-&#62;tavl_balance == -2)
{ struct tavl_node *x = y-&#62;tavl_link[0]; assert (x != NULL); if (x-&#62;tavl_balance == +1)
{ struct tavl_node *w; &#60;@xref{\NODE\, , Rebalance for +.&#62; balance factor in TAVL insertion in left subtree,307} pa[k - 1]-&#62;tavl_link[da[k - 1]] = w; } else if (x-&#62;tavl_balance == 0)
{ y-&#62;tavl_link[0] = x-&#62;tavl_link[1]; x-&#62;tavl_link[1] = y; x-&#62;tavl_balance = +1; y-&#62;tavl_balance = -1; pa[k - 1]-&#62;tavl_link[da[k - 1]] = x; break; } else /* x-&#62;tavl_balance == -1 */
{ if (x-&#62;tavl_tag[1] == TAVL_CHILD) y-&#62;tavl_link[0] = x-&#62;tavl_link[1]; else
{ y-&#62;tavl_tag[0] = TAVL_THREAD; x-&#62;tavl_tag[1] = TAVL_CHILD; } x-&#62;tavl_link[1] = y; x-&#62;tavl_balance = y-&#62;tavl_balance = 0; pa[k - 1]-&#62;tavl_link[da[k - 1]] = x; } }
This code is included in @refalso{665


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

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