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


GNU libavl 2.0.1

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

5.12.2.2 Implementation

Implementing this algorithm is more or less straightforward. Let's start from an outline:

 
&#60;@xref{\NODE\, , BST compression function.&#62;,95}
/* Converts tree, which must be in the shape of a vine, into a balanced 
tree. */ static void
vine_to_tree (struct bst_table *tree)
{ unsigned long vine; /* Number of nodes in main vine. */ unsigned long leaves; /* Nodes in incomplete bottom level, if any. */ int height; /* Height of produced balanced tree. */ &#60;@xref{\NODE\, , Calculate leaves.&#62;,91} &#60;@xref{\NODE\, , Reduce vine general case to special case.&#62;,92} &#60;@xref{\NODE\, , Make special case vine into balanced tree and count height.&#62;,93} &#60;@xref{\NODE\, , Check for tree height in range.&#62;,94} }
This code is included in @refalso{87

The first step is to calculate the number of compression transformations necessary to reduce the general case of a tree with m nodes to the special case of exactly 2**n - 1 nodes, i.e., calculate m - (2**n - 1), and store it in variable leaves. We are given only the value of m, as tree-&#62;bst_count. Rewriting the calculation as the equivalent m + 1 - 2**n, one way to calculate it is evident from looking at the pattern in binary:

m n m + 1 2**n m + 1 - 2**n
1 1 2 = 00010 2 = 00010 0 = 00000
2 1 3 = 00011 2 = 00010 1 = 00001
3 2 4 = 00100 4 = 00100 0 = 00000
4 2 5 = 00101 4 = 00100 1 = 00001
5 2 6 = 00110 4 = 00100 2 = 00010
6 2 7 = 00111 4 = 00100 3 = 00011
7 3 8 = 01000 8 = 01000 0 = 00000
8 3 9 = 01001 8 = 01000 1 = 00000
9 3 10 = 01001 8 = 01000 2 = 00000

See the pattern? It's simply that m + 1 - 2**n is m with the leftmost 1-bit turned off. So, if we can find the leftmost 1-bit in \ASCII\, we can figure out the number of leaves.

In turn, there are numerous ways to find the leftmost 1-bit in a number. The one used here is based on the principle that, if x is a positive integer, then x & (x - 1) is x with its rightmost 1-bit turned off.

Here's the code that calculates the number of leaves and stores it in leaves:

 
leaves = tree-&#62;bst_count + 1;
for (;;) 
{ unsigned long next = leaves & (leaves - 1); if (next == 0) break; leaves = next; } leaves = tree-&#62;bst_count + 1 - leaves;
This code is included in @refalso{90

Once we have the number of leaves, we perform a compression composed of leaves compression transformations. That's all it takes to reduce the general case to the 2**n - 1 special case. We'll write the compress() function itself later:

 
compress ((struct bst_node *) &tree-&#62;bst_root, leaves);
This code is included in @refalso{90

The heart of the function is the compression of the vine into the tree. Before each compression, vine contains the number of nodes in the main vine of the tree. The number of compression transformations necessary for the compression is vine / 2; e.g., when the main vine contains 7 nodes, 7 / 2 = 3 transformations are necessary. The number of nodes in the vine afterward is the same number (@pageref{Transforming a Vine into a Balanced BST}).

At the same time, we keep track of the height of the balanced tree. The final tree always has height at least 1. Each compression step means that it is one level taller than that. If the tree needed general-to-special-case transformations, that is, leaves > 0, then it's one more than that.

 
vine = tree-&#62;bst_count - leaves;
height = 1 + (leaves > 0);
while (vine > 1) 
{ compress ((struct bst_node *) &tree-&#62;bst_root, vine / 2); vine /= 2; height++; }
This code is included in @refalso{90

Finally, we make sure that the height of the tree is within range for what the functions that use stacks can handle. Otherwise, we could end up with an infinite loop, with bst_t_next() (for example) calling bst_balance() repeatedly to balance the tree in order to reduce its height to the acceptable range.

 
if (height > BST_MAX_HEIGHT) 
{ fprintf (stderr, "libavl:Treetoobig(%lunodes)tohandle.", (unsigned long) tree-&#62;bst_count); exit (EXIT_FAILURE); }
This code is included in @refalso{90


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

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