5.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 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.¹

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. */
#ifndef AVL_MAX_HEIGHT
#define AVL_MAX_HEIGHT 92
#endif

This code is included in 143.

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