A weight-balanced tree is a binary tree in which for each node

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 furthest leaf) of such a tree on n nodes is best described by which of the following?

A. log2(n)

B. log4/3(n)

C. log3(n)

D. log3/2(n)

My Try:

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.

There n nodes in the tree, one node is root now (n-1) nodes are left. to get the maximum height of the tree we divide these (n-1) nodes in three parts each of size n−13 Now keep two parts in LST and one part in RST. LST = 2∗(n−1)/3, and RST=(n−1)/3

Therefore, T(n)= T(2/3(n-1) + (n-1)/3) and for maximum height we will only consider H(n)=H(2/3(n-1))+1 and H(1)=0 I tried to solve the H(n) Recurrence using substitution but i'm stuck at a point: 2^k/3^k(n-k)=1 Here how to solve for k ? Please help

Answer 1

• You have done almost correct but there is a mistake in the recursion statement.

• It is should be like this : Root + Left Sub Tree + Right Sub Tree.

• And if we have taken 1 node for root than it will be 1 and rest remaining nodes will be (n-1). And from the remaining nodes we have to distribute in such a way that we get maximum height with the following condition.

• Let nodes in LST be : nl and Let nodes in RST be : nr

• Equation/Condtion : nr/2 <= nl <= 2*nr

• From that we can get the value of nr which will be n-1/3. Refer the figure for calculation.

• Now we came to the point where you have done the mistake.

  T(n) = T(n-1/3) + T(2(n-1)/3) + 1 Where T(1) = 1 And T(0) = (0)

And then we will get log 3/2 n in the end.

Figure with calculations :