2
$\begingroup$

What is the maximal difference between heights of leaves in an AVL tree? I am interested only in the asymptotic difference.

I am not sure about my answer - I think that it is $O(\log n)$, given the fact that at every level we may have difference equal one.

Am I right?

$\endgroup$
4
$\begingroup$

We consider Fibonacci tree ([TAOCP3, Knuth98, Sect. 6.2.1]) and compute the maximal height difference in it.

A Fibonacci tree of order $k$ which is constructed recursively (see an Fibonacci tree of order 6 in the figure below; also from TAOCP):

  • If $k = 0$ or $k = 1$, the tree is simply a single node.
  • If $k \ge 2$, the tree has a left subtree of order $k-1$ and a right subtree of order $k-2$.

fibonacci-tree-order-6

It is easy to verify that a Fibonacci tree is also an AVL tree.


From the figure above, we observe that the two leaves at the leftmost $l$ and at the rightmost $r$ differ most by heights ($H_l, H_r$ among all pairs of leaves. We can compute the height difference as follows.

A Fibonacci tree of order $k$ has $n = F(k+2)-1 \sim \Phi^{k+2}$ nodes in total, where $\Phi$ is the golden ratio.

$$H_l - H_r = k \text{ (leftmost path; decrease by 1}) - k/2 \text{ (rightmost path; decrease by 2}) = k/2 \text{ (maybe floor or ceiling functions here; I omit the details)}.$$

Because $n = \Phi^{k+2}$, we have $k/2 = \log_{\Phi} \sqrt{n} - 1$.

$\endgroup$
1
$\begingroup$

Here is an almost perfect visualization of an AVL tree.

An ugly AVL tree

As you can see, you can increase the the maximal difference between leaves only once per level.

In other words, to have your AVL balanced you've got to keep the balance factor between $-1$ and $1$. So, if you want to maximise the highest difference between two leaves, then you don't want the balance factor to be equal $0$ in any node.

Basically, the maximal difference is $O(logn)$.

Here are some more AVL trees I've drawn to test my reasoning.

AVL 1

AVL 2

I guess that the maximal level is $\lfloor log(n) \rfloor - 1$ however I am not sure.

Resources:

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.