3
$\begingroup$

I am given $n$ positive integers $x_1,x_2,\cdots,x_n$ as input. These are the weights of the leaves in a full binary tree, $x_1$ being the leftmost leaf and $x_n$ the rightmost leaf. The weight of an internal node $v$ is defined as the sum of weights of the leaves in the subtree rooted at $v$. The balance of an internal node is defined as the larger ratios of the weights of its two children. The balance of a tree is the maximum of the balances of its internal nodes.

I need to find the least possible balance of any full binary tree with $x_1,x_2,\cdots,x_n$ as the weights of its leaves. I don't need to output the tree, just the value.

I am having trouble finding the sub-problems. I have tried doing some examples, say the input is: $(5, 4, 3, 4, 4)$. I found the least possible balance of this to be $1.5$ by drawing all the possible trees. The tree that I ended up with is below and I put the balance beside each internal node: tree1

For the example input, a smaller sub-problem would obviously be $(4,3,4,4)$, but I don't see how knowing the least possible balance of that helps me find the least possible balance of the tree with leaves $(5, 4, 3, 4, 4)$. I tried finding the balance for $(4,3,4,4)$ which came to be $1.33$. The tree I ended up with is: tree2

I am looking for some hints as to what the sub-problems might be.

$\endgroup$
2
  • $\begingroup$ I think you should be focusing on a greedy algorithm that seeks to partition the input into a set of two lists of balanced sums, which will correlate with overall balance of the tree. Though there are other approaches. $\endgroup$
    – Taekahn
    Nov 10, 2014 at 5:24
  • $\begingroup$ @Taekahn That approach does not yield optimal BSTs. $\endgroup$
    – Raphael ♦
    Nov 10, 2014 at 13:12

2 Answers 2

Reset to default
2
$\begingroup$

You should think about how your binary tree can be arranged. For each tree you have some nodes $x_1,\dots,x_k$ to the left and some $x_{k+1}, \dots, x_n$ to the right of the root. Now, the best possible imbalance for that root will be the arrangement that gives you the smaller ratio. So, you have to figure out a way of doing this evaluation in every internal node of your tree (considering the subtree rooted there). Another tip is to consider growing your tree while preserving the minimum imbalance. The "matrix-chain" problem is quite similar to this one, so you should take a look at it too. Good luck.

$\endgroup$
2
  • $\begingroup$ Welcome to Computer Science Stack Exchange! You can use $\LaTeX$ to format your posts: I've edited yours but here's a link explaining how to do it yourself. I also edited the text of your post slightly as there seemed to be a couple of missing words -- please check I didn't mess anything up! $\endgroup$
    – David Richerby
    Nov 10, 2014 at 21:02
  • $\begingroup$ So how would one define the least balance of a tree with just one leaf (that is what would happen when $k= 1$ and we get $x_1, x_1$ )? $\endgroup$
    – user130554
    Nov 10, 2014 at 21:42
1
$\begingroup$

The crucial fact is that you are given the leaves in order. The obvious way to use dynamic programming is to compute for all $i,j$ the best tree which has leaves $x_i,\ldots,x_j$ in order. This leads to an $O(n^3)$ algorithm. I'll let you think over the details.

If you remove the constraint that the leaves are ordered, then the problem looks much harder, and is probably NP-complete. A dynamic programming approach would consider all subsets and would take time $\tilde{O}(2^n)$, which is better than exhaustive search.

$\endgroup$
2
  • $\begingroup$ Would you be able to elaborate a little on the computation please? So for my example, I should compute the balance for inputs $(5),(5,4),(5,4,3),(5,4,3,4)$ and once I have done this, how would these help me in computing $(5,4,3,4,4)$? Did I understand it correctly? $\endgroup$
    – user130554
    Nov 10, 2014 at 6:06
  • $\begingroup$ No, you have to compute the best solution for all sub-intervals, not only those starting at $x_1$. When processing $x_i,\ldots,x_j$, you consider all possible ways of splitting the interval into two parts $x_i,\ldots,x_k;x_{k+1},\ldots,x_j$. I'll let you take it from there. $\endgroup$
    – Yuval Filmus
    Nov 10, 2014 at 6:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.