1

I'm trying to learn the proof of the minimum number of nodes in an AVL tree of height h and I'm stumped on how $2N_{h-2}$ becomes $2^{h/2}$. I've read this [answer](How does $2N_{h-2}$ become $2^{h/2}$?$2n-h-2$-become-$2h-2)$ and I'm still confused as to why you keep doing this until $k = h/2$.

I understand how $N_h > 2^kN_{h-2k}$. I just am not grasping how that is simplified to $2^{h/2}$. I'm looking for a slightly more detailed answer than the one I linked to. Thanks a lot. Sorry if it's a really stupid question. I bet it's something simple, but it's just flying over my head.

Community
  • 1
David Velasquez
  • 251
  • The answer there says that the next step is to take $k=h/2$, so you get $N_h > 2^{h/2} N_0$. Does that step make sense? –  Jul 05 '15 at 16:10
  • @StevenTaschuk Not really :/ why is the next step to take k = h/2? Where is that coming from? – David Velasquez Jul 05 '15 at 16:13
  • The previous part of the proof establishes $N_h > 2N_{h-2}$. As you noted, by induction it follows that $N_h > 2^k N_{h-2k}$. We're using induction here as a formal version of saying "if you do this $k$ times, here's the result". We take $k=h/2$ because that corresponds to the end of that process. You extend $N_h > 2N_{h-2} > 2^2N_{h-4} > \dotsb$ until you can't extend it any further. –  Jul 05 '15 at 16:16
  • Bigger picture: We're trying to get closed-form information about $N_h$ from recursive information about $N_h$. In this case we can just unroll the recursion until we hit the base case, and then there's no recursion left. –  Jul 05 '15 at 16:28
  • @StevenTaschuk I get it now! I wasn't realizing that h/2 was substituted into k and that's how it simplifies to N_0. And N_0 = 1 which simplifies to 2^{h/2}. Thanks I understand it now :] – David Velasquez Jul 05 '15 at 16:35
  • I'm new to the math stack exchange and I can't figure out the formatting ha. So sorry for the bad style. – David Velasquez Jul 05 '15 at 16:37
  • Formatting tips: use dollar signs for TeX, and use asterisks for emphasis. Thus $2^{h/2}$ gives $2^{h/2}$; $$2^{h/2}$$ gives $$2^{h/2} \quad (\textrm{i.e., on a new line});$$ *2^{h/2}* gives 2^{h/2}; and **2^{h/2}** gives 2^{h/2}. See also this very helpful formatting reference page. – Théophile Jul 05 '15 at 16:47
  • @Ghost_Stark Yeah, that's what "take $k=h/2$" means. –  Jul 05 '15 at 16:52

1 Answers1

1

Given $N_h > 2^kN_{h-2k}$, we want to choose a value of $k$ such that the right-hand-side is constant. That is, we want to reach the initial value $N_0$, which happens when the index $h-2k = 0$, i.e., $k = \frac h2$.

Théophile
  • 24,627