6.17. AVL Tree Performance¶

Before we proceed any further let’s look at the result of enforcing this new balance factor requirement. Our claim is that by ensuring that a tree always has a balance factor of -1, 0, or 1 we can get better Big-O performance of key operations. Let us start by thinking about how this balance condition changes the worst-case tree. There are two possibilities to consider, a left-heavy tree and a right-heavy tree. If we consider trees of heights 0, 1, 2, and 3, Figure 2 illustrates the most unbalanced left-heavy tree possible under the new rules.

../_images/worstAVL.png — Figure 2: Worst-Case Left-Heavy AVL Trees¶

Looking at the total number of nodes in the tree we see that for a tree of height 0 there is 1 node, for a tree of height 1 there is $1 + 1 = 2$ nodes, for a tree of height 2 there are $1 + 1 + 2 = 4$ , and for a tree of height 3 there are $1 + 2 + 4 = 7$ . More generally the pattern we see for the number of nodes in a tree of height $h$ ( $N_{h}$ ) is:

N_{h} = 1 + N_{h - 1} + N_{h - 2}

This recurrence may look familiar to you because it is very similar to the Fibonacci sequence. We can use this fact to derive a formula for the height of an AVL tree given the number of nodes in the tree. Recall that for the Fibonacci sequence the $i^{t h}$ Fibonacci number is given by:

\begin{aligned} F_{0} & = 0 \\ F_{1} & = 1 \\ F_{i} & = F_{i - 1} + F_{i - 2} for all i \geq 2 \end{aligned}

An important mathematical result is that as the numbers of the Fibonacci sequence get larger and larger the ratio of $F_{i} / F_{i - 1}$ becomes closer and closer to approximating the golden ratio $Φ$ which is defined as $Φ = \frac{1 + \sqrt{5}}{2}$ . You can consult a math text if you want to see a derivation of the previous equation. We will simply use this equation to approximate $F_{i}$ as $F_{i} = Φ^{i} / \sqrt{5}$ . If we make use of this approximation we can rewrite the equation for $N_{h}$ as:

N_{h} = F_{h + 3} - 1, h \geq 1

By replacing the Fibonacci reference with its golden ratio approximation we get:

N_{h} = \frac{Φ^{h + 2}}{\sqrt{5}} - 1

If we rearrange the terms, take the base 2 log of both sides, and then solve for $h$ , we get the following derivation:

\begin{aligned} \log N_{h} + 1 & = (h + 2) \log Φ - \frac{1}{2} \log 5 \\ h & = \frac{\log (N_{h} + 1) - 2 \log Φ + \frac{1}{2} \log 5}{\log Φ} \\ h & = 1.44 \log N_{h} \end{aligned}

This derivation shows us that at any time the height of our AVL tree is equal to a constant (1.44) times the log of the number of nodes in the tree. This is great news for searching our AVL tree because it limits the search to $O (\log n)$ .