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 withnnodes has height betweenlog2(n+ 1) and 1.44 *log2(n+ 2) - 0.328. An AVL tree with heighthhas between 1.17 *pow(1.618,h) - 2 andpow(2,h) - 1 nodes.For comparison, an optimally balanced BST with

nnodes has heightceil(log2(n+ 1)). An optimally balanced BST with heighthhas betweenpow(2,h- 1) andpow(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. */ #ifndefAVL_MAX_HEIGHT#defineAVL_MAX_HEIGHT92 #endif

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].