[Solved]: Maximal difference of height between two leaves in an AVL tree

Problem Detail: 

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?

Asked By : user40545

Answered By : hengxin

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

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/52077

 Ask a Question

 Download Related Notes/Documents