4.12.2.2 Implementation

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

90. <Vine to balanced BST function 90> =
<BST compression function 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. */

  <Calculate leaves 91>
  <Reduce vine general case to special case 92>
  <Make special case vine into balanced tree and count height 93>
  <Check for tree height in range 94>
}

This code is included in 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->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 , 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:

91. <Calculate leaves 91> =
leaves = tree->bst_count + 1;
for (;;) 
  {
    unsigned long next = leaves & (leaves - 1);
    if (next == 0)
      break;
    leaves = next;
  }
leaves = tree->bst_count + 1 - leaves;

This code is included in 90, 285, 512, and 680.

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:

92. <Reduce vine general case to special case 92> =
compress ((struct bst_node *) &tree->bst_root, leaves);

This code is included in 90, 512, and 680.

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 (see 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.

93. <Make special case vine into balanced tree and count height 93> =
vine = tree->bst_count - leaves;
height = 1 + (leaves > 0);
while (vine > 1) 
  {
    compress ((struct bst_node *) &tree->bst_root, vine / 2);
    vine /= 2;
    height++;
  }

This code is included in 90, 512, and 680.

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.

94. <Check for tree height in range 94> =
if (height > BST_MAX_HEIGHT) 
  {
    fprintf (stderr, "libavl: Tree too big (%lu nodes) to handle.",
             (unsigned long) tree->bst_count);
    exit (EXIT_FAILURE);
  }

This code is included in 90.