www.delorie.com/gnu/docs/avl/libavl_90.html

search

	Buy GNU books!

GNU libavl 2.0.1

6.1.1 Analysis

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.