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 betweenpow(2, (h+ .328) / 1.44) - 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.

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