www.delorie.com/gnu/docs/avl/libavl_74.html | search |
Buy GNU books! | |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
Implementing this algorithm is more or less straightforward. Let's start from an outline:
<@xref{\NODE\, , BST compression function.>,95} /* Converts tree, which must be in the shape of a vine, into a balanced |
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->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->bst_count + 1; for (;;) |
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->bst_root, leaves); |
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->bst_count - leaves; height = 1 + (leaves > 0); while (vine > 1) |
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) |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
webmaster | delorie software privacy |
Copyright © 2003 by The Free Software Foundation | Updated Jun 2003 |