A weight-balanced tree is a binary tree in which for each node, the number of…
2002
A weight-balanced tree is a binary tree in which for each node, the number of nodes in the left subtree is at least half and at most twice the number of nodes in the right subtree. The maximum possible height (number of nodes on the path from the root to the furthest leaf) of such a tree on n nodes is best described by which of the following?
- A.
log₂ n
- B.
log_{4/3} n
- C.
log₃ n
- D.
log_{3/2} n
Attempted by 22 students.
Show answer & explanation
Correct answer: D
To maximize the height for a fixed number of nodes, make the subtree on the longest path as large as possible relative to its sibling while still satisfying the weight-balance condition. If the larger subtree has size m, the smaller sibling must have at least about m/2 nodes. Thus the minimum number of nodes needed for height h satisfies N(h) ≈ 1 + N(h - 1) + N(h - 1)/2 = 1 + (3/2)N(h - 1). Hence N(h) grows like (3/2)^h. Solving n ≈ (3/2)^h gives h = Θ(log_{3/2} n). Therefore the maximum possible height is best described by log_{3/2} n.