Problem Detail: I came across a question on which I got totally stuck 🙁 a sort of homework question) A weight-balanced tree is a binary tree in which for each node. The number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the farthest leaf) of such a tree on n nodes is best described by which of the following?
a) log_2 n b) log_{4/3} n c) log_3 {n} d) log_{3/2} n
I cant imagine to solve this one. Intuitive based answer is most welcome.
Asked By : neerajDorle
Answered By : FrankW
The height of a tree is 1 + the height of its highest subtree. Which way of distributing the nodes to the subtrees will allow you to maximize that parameter?
Put $frac 13 n$ nodes into the left tree and $frac 23 n$ into the right one (or vice versa).
If you apply this recursively, what do you get for the height?
You get the recurrence $h(1) = 1$, $h(n) = 1 + h(frac 23 n)$, $n>1$. This solves to
$h(n) = 1+log_{frac 32}n$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/21942 Ask a Question Download Related Notes/Documents
