www.delorie.com/gnu/docs/avl/libavl_90.html | search |
Buy GNU books! | |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
How good is the AVL balancing rule? That is, before we consider how much complication it adds to BST operations, what does this balancing rule guarantee about performance? This is a simple question only if you're familiar with the mathematics behind computer science. For our purposes, it suffices to state the results:
An AVL tree with n nodes has height between log2 (n + 1) and 1.44 * log2 (n + 2) - 0.328. An AVL tree with height h has between \ASCII\{2^{h + .328} / 1.44, pow (2, (h + .328) / 1.44) - 2} and \ASCII\{2^h - 1, pow (2, h) - 1} nodes.For comparison, an optimally balanced BST with n nodes has height \ASCII\\rceil, ceil (log2 (n + 1))}. An optimally balanced BST with height h has between \ASCII\, pow (2, h - 1)} and pow (2, h) - 1 nodes.(10)
The average speed of a search in a binary tree depends on the tree's height, so the results above are quite encouraging: an AVL tree will never be more than about 50% taller than the corresponding optimally balanced tree. Thus, we have a guarantee of good performance even in the worst case, and optimal performance in the best case.
See also: [ Knuth 1998b], theorem 6.2.3A.
webmaster | delorie software privacy |
Copyright © 2003 by The Free Software Foundation | Updated Jun 2003 |