DS AVL Tree Performance

Section 8.16 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. The worse case performance for binary search trees is

O (n)

because the worst case "tree" equivalent to a singly linked list (see Section 8.14).

🔗

What is the worst case tree which also preserves a balance factor of -1, 0 or 1? Another way of asking that question is: how tall of a tree can we create for a given number of nodes that also preserves the balanace factor requirements? To answer this, we depict the minimum number of nodes to construct trees of height 0, 1, 2, and 3 in Figure 8.16.1. In the diagram, the most left-heavy tree possible is constructed for each height. We could have chosen to create the most right-heavy tree without loss of generalization.

🔗

described in detail following the image — Figure 8.16.1. Worst-Case Left-Heavy AVL Trees.
🔗

Going from left to right in Figure 8.16.1, the tree is constructed by adding a new root node (depicted in green). Then the previous tree (show in red) is added as its left subtree. Finally, tree before that (depicted in blue) is added as the root’s right subtree.

🔗

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

🔗

We can express the value of the number of nodes in a tree of height

h

in terms of its position in the Fibonacci sequence:

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

🔗

An important mathematical result is that the

i^{t h}

Fibonacci number can be found using Binet’s formula:

F_{i} = \frac{Φ^{i} - (1 - Φ)^{i}}{\sqrt{5}} .

🔗

You can consult a math text if you want to see a derivation of the previous formula.

Φ

is the golden ratio and as is defined as:

Φ = \frac{1 + \sqrt{5}}{2} \approx 1.618 .

🔗

In Binet’s formula, as

i

grows large, the term

(1 - Φ)^{i}

approaches zero, so we can use the following approximation to obtain a value close to the

i^{t h}

Fibonacci number:

F_{i} \approx \frac{Φ^{i}}{\sqrt{5}} .

🔗

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

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

🔗

If we rearrange the terms, and take the base 2 log of both sides and then solve for

h

we get the following derivation:

\begin{aligned} \log_{2} (N_{h} + 1) & = (h + 3) \log_{2} Φ - \frac{1}{2} \log_{2} 5 \\ h & = \frac{\log_{2} (N_{h} + 1) - 3 \log_{2} Φ + \frac{1}{2} \log_{2} 5}{\log_{2} Φ} \\ h & \approx 1.44 \log_{2} (N_{h} + 1) - 2.57 \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) .

🔗

You have attempted 1 of 1 activities on this page.

🔗

Prev Top Next