patternMinor
Maximal difference of height between two leaves in an AVL tree
Viewed 0 times
heightleavesdifferencetwobetweenavlmaximaltree
Problem
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?
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?
Solution
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):
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$.
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$.
Context
StackExchange Computer Science Q#52077, answer score: 6
Revisions (0)
No revisions yet.