How is $\frac{n}{2^{h+1}}$ the maximum possible number of nodes at height $h$ for a binary search tree or heap tree? I saw this as proof to asymptotically bound the build_heap function in the book, but I don't get it.
$\begingroup$
$\endgroup$
3
asked Oct 31, 2012 at 21:24
-
1$\begingroup$ What book? What have you tried? Also, the answer is likely "It just is, here's a proof." Try proving and/or finding a counter-example! $\endgroup$– Raphael ♦Oct 31, 2012 at 23:13
-
$\begingroup$ Is it assumed that the tree is balanced? $\endgroup$– JoeNov 1, 2012 at 0:42
-
$\begingroup$ It doesn't matter if the tree is balanced or not; this is just the maximum possible number of nodes. $\endgroup$– MerbsNov 1, 2012 at 1:54
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
I actually touched upon this in response to your previous question, but the general idea is that there are $n$ nodes in a binary tree, and starting from the root, at each depth there is: 1, 2, 4, 8, 16 ... maximum nodes. We see that at the greatest depth, there is (at most) half of all nodes ($n/2$). Remember that the height of a node is the distance from the node to a leaf, such that the height of a leaf is 0 (and the height of the root is the height of the tree). So for a leaf, $\frac{n}{2^{0+1}}=n/2$. For the root, $h=\log_2 n$, so $\frac{n}{2^{\log_2 n+1}}=n/n=1$. And the rest of the tree follows from there.
$\begingroup$
$\endgroup$
1
I think it should be a full binary tree to support maximum number of nodes at a particular height.
A full binary tree (sometimes proper binary tree or 2-tree or strictly binary tree) is a tree in which every node other than the leaves has two children.
At successive level, number of nodes would be $1, 2, 4, 8,\ldots,n/2$.
For $h=0$, nodes = $\frac{n}{2^{0+1}} = \frac n2$.
For $h=\log_2n$, nodes = $\frac{n}{2^{\log_2n+1}} = 1$.
