More detailed explanation of how $2N_{h-2}$ becomes $2^{h/2}$?

42 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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