5.1.1 Analysis [ToC] [Index]         [Prev] [Up] [Next]

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 1.17 * pow (1.618, h) - 2 and pow (2, h) - 1 nodes.

For comparison, an optimally balanced BST with n nodes has height ceil (log2 (n + 1)). An optimally balanced BST with height h has between pow (2, h - 1) and pow (2, h) - 1 nodes.1

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.

To support at least 2**64 - 1 nodes in an AVL tree, as we do for unbalanced binary search trees, we must define the maximum AVL tree height to be 1.44 * log2 ((2**64 - 1) + 2) - 0.328, which is 92:

145. <AVL maximum height 145> =
/* Maximum AVL tree height. */
#define AVL_MAX_HEIGHT 92

This code is included in 143.

See also:  [Knuth 1998b], theorem 6.2.3A.


[1] Here log2 is the standard C base-2 logarithm function, pow is the exponentiation function, and ceil is the “ceiling” or “round up” function. For more information, consult a C reference guide, such as [Kernighan 1988].