1
$\begingroup$

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?

$\endgroup$
1

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.