patternMinor
Maximum number of nodes with height h
Viewed 0 times
nodesnumbermaximumheightwith
Problem
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.Solution
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.
Context
StackExchange Computer Science Q#6405, answer score: 9
Revisions (0)
No revisions yet.