www.delorie.com/gnu/docs/avl/libavl_70.html | search |
Buy GNU books! | |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
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:
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:
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:
/* Special BST functions. */ void bst_balance (struct bst_table *tree); |
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 | delorie software privacy |
Copyright © 2003 by The Free Software Foundation | Updated Jun 2003 |