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


GNU libavl 2.0.1

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

5.12 Balance

Sometimes binary trees can grow to become much taller than their optimum height. For example, the following binary tree was one of the tallest from a sample of 100 15-node trees built by inserting nodes in random order:

bal1

The average number of comparisons required to find a random node in this tree is \ASCII\{(1 + 2 + (3 \times 2) + (4 \times 4) + (5 \times 4) + 6 + 7 + 8) / 15 = 4.4, (1 + 2 + (3 * 2) + (4 * 4) + (5 * 4) + 6 + 7 + 8) / 15 = 4.4} comparisons. In contrast, the corresponding optimal binary tree, shown below, requires only \ASCII\{(1 + (2 \times 2) + (3 \times 4) + (4 \times 8))/15 = 3.3, (1 + (2 * 2) + (3 * 4) + (4 * 8))/15 = 3.3} comparisons, on average. Moreover, the optimal tree requires a maximum of 4, as opposed to 8, comparisons for any search:

bal2

Besides this inefficiency in time, trees that grow too tall can cause inefficiency in space, leading to an overflow of the stack in bst_t_next(), bst_copy(), or other functions. For both reasons, it is helpful to have a routine to rearrange a tree to its minimum possible height, that is, to balance (see balance) the tree.

The algorithm we will use for balancing proceeds in two stages. In the first stage, the binary tree is "flattened" into a pathological, linear binary tree, called a "vine." In the second stage, binary tree structure is restored by repeatedly "compressing" the vine into a minimal-height binary tree.

Here's a top-level view of the balancing function:

 
&#60;@xref{\NODE\, , BST to vine function.&#62;,89}
&#60;@xref{\NODE\, , Vine to balanced BST function.&#62;,90}
void 
bst_balance (struct bst_table *tree)
{ assert (tree != NULL); tree_to_vine (tree); vine_to_tree (tree); tree-&#62;bst_generation++; }
This code is included in @refalso{29

 
/* Special BST functions. */
void bst_balance (struct bst_table *tree);
This code is included in @refalso{24

See also: [ Stout 1986], rebalance procedure.

5.12.1 From Tree to Vine  
5.12.2 From Vine to Balanced Tree  


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

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