If we have a quad tree where each node must have 0 or 4 children, is there an expression that can me the maximum height of a quad tree with $n$ nodes?
Asked
Active
Viewed 2,752 times
1 Answers
3
A tree of height $m$ where at each level only one node has children will have $1+4(m-1)$ nodes, assuming a tree with only one node has height one. The height will be $m=\frac{n+3}{4}$ for $n$ nodes. If your number of nodes is not $1 \pmod 4$, it won't work as each branch adds 4 nodes.
Ross Millikan
- 374,822
-
I think you've used $n$ for both the height and the number of nodes. – joriki Apr 06 '11 at 19:25
-
@joriki: You are right. Fixed. Thanks. – Ross Millikan Apr 06 '11 at 19:32