I have an AVL tree with height h. I understand how to get h $\thickapprox$ 1.440 log N. However, I can't figure out how to calculate the minimum depth of a leaf node from root. I tried constructing a recursive formula where d = 1 + min(dL, dR) where dL and dR are the depths of the left and right subtree of the root. But can't get a solution of this. Can anyone help me out here?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Have you tried to use the AVL invariant, namely $|d_L - d_R| \leq 1$? $\endgroup$– Yuval FilmusSep 9, 2019 at 9:14
-
2$\begingroup$ Try a proof by induction. $\endgroup$– Yuval FilmusSep 9, 2019 at 9:15
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
Denote by $d(h)$ the minimum height of a leaf in an AVL tree of height $h$. One subtree of the root necessarily has height $h-1$, and the other one has height either $h-2$ or $h-1$ by the defining property of AVL trees. Therefore $$ d(h) = \min(d(h-1),d(h-2)) + 1. $$ Also, one checks that $d(0) = d(1) = 0$ (if one measures height as the maximum number of edges in a root-to-leaf path). The recurrence makes it clear that $d$ is monotone, and so $d(h) = d(h-2) + 1$. From here it's easy to calculate $d(h) = \lfloor h/2 \rfloor$.
answered Sep 9, 2019 at 11:13
-
$\begingroup$ Yes, I did just like this after you commented "Try a proof by induction". Thanks a lot. Hope this question comes in exam on Friday! $\endgroup$ Sep 9, 2019 at 11:15
-
$\begingroup$ Actually I was also thinking of another approach where I take as induction hypothesis P(h) => An AVL tree with height h has depth of leaf node at least ceil(h/2) and then remove the root of the AVL tree. Thus we get two trees T1 and T2 with height (h-1) and (h-2) or (h-1) respectively. By induction hypothesis, d(T2) is atleast ceil((h-2)/2). Thus, depth of leaf node in T = depth of leaf node in T2 + 1 = ceil((h-2)/2) + 1 = ceil(h/2), which was our induction hypothesis in the first place. Is this a valid proof?? $\endgroup$ Sep 9, 2019 at 11:22
-
$\begingroup$ It's essentially the same argument, only expressed a bit differently. $\endgroup$ Sep 9, 2019 at 11:25
-
$\begingroup$ So, this is a valid proof, right? Actually I don't understand the meaning of "The recurrence makes it clear that d is monotone." Can you explain it briefly? $\endgroup$ Sep 9, 2019 at 11:28
-
$\begingroup$ This is something you need to prove by induction, but the proof is pretty simple. $\endgroup$ Sep 9, 2019 at 11:29