I was watching video 7. Binary Trees, Part 2: AVL, where professor Erik Demaine stated that $$2N_{h-2} = 2^{h/2\text{ (or maybe with floor or something... maybe it's ceiling)}}$$ where $N$ stands for the number of nodes in a subtree of height $h-2$. Can someone explain me in more detail why this recursion can be solved like this?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Does this answer your question? Don't understand one step for AVL tree height log n proof $\endgroup$– John L.May 23, 2022 at 16:48
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Let $N_h$ denote the minimum number of nodes in a height-balanced tree of height $h$. Given a height-balanced tree of height $h$, without loss of generality assume the left child of the root has height $h-1$. The right child must have height $h-1$ or $h-2$, and to get the smallest possible values (the worst-case), assume it has height $h-2$. Then, the number of nodes in the given tree is at least $N_{h-1} + N_{h-2} + 1$, because there are at least $N_{h-1}$ nodes in the left subtree of the root, at least $N_{h-2}$ nodes (in the worst case) in the right subtree of the root, and the root itself contributes 1 to the count of number of nodes.
Thus, we get that $N_h \ge N_{h-1} + N_{h-2} + 1$. One can pay attention to constants and show the terms $N_1, N_2, \ldots$ grow at least as fast as the Fibonacci sequence. The $h$th term of the Fibonacci sequence is at least $c \psi^h$ for some constant $c$ and the golden ratio $\psi$. Hence, the terms of the sequence grow exponentially fast. This can be shown to imply that $h$ is at most $1.44 \log n$, and so we get that $h=O(\log n)$ for a height-balanced tree with height $h$ and $n$ nodes.
But, in asymptotic analysis, you can be "sloppy" and ignore constants, and it suffices to use the fact that $N_{h-1}+1 > N_{h-2}$ to get that $N_h \ge N_{h-1}+N_{h-2}+1 > N_{h-2}+N_{h-2}$. Thus, we have $N_h > 2N_{h-2}$. This means the terms of the sequence $N_1, N_2,\ldots$ grow fast enough that they at least double every two terms: $N_3 > 2N_1$, $N_5 > 2N_3 > 4N_1$, and in general, $N_h > N_1 2^{h/2} = N_1 (\sqrt{2})^h$. This implies that $h < 2 \log n$, and so $h = O(\log n)$.
In general, to show $h=O(\log n)$ for a height-balanced tree, it suffices to show that the number of nodes $n$ grows exponentially with $h$. The crude analysis given above is good enough to obtain this result.
$\begingroup$
$\endgroup$
In the lecture it was shown that $N_h \geq 2N_{h-2}$. You can obtain the bound of $2^{h/2} $ for this recurrence by continued expansion of the r.h.s., also called unrolling the recurrence. E.g. :
$N_h \geq 2N_{h-2} = 2 * (2N_{h-4}) = 2*(2*(2N_{h-6})) = 2(2(2(...(2N_0)...)))$.
This expansion will continue until you reach $N_0$, which is 1, I think since the tree with height 0 has only the root. The number of times you can subtract 2 from $h$ is at most $\lceil h/2\rceil$, which is also the number of 2's in the expansion. Thus you have $N_h \geq 2^{\lceil h/2\rceil}$.