1

Given:

  • a list of 'leaves' that each have a cost,
  • the cost of creating an 'edge'
  • The constraint that a constructed tree node can at most have two children.

We now want to find the tree with the lowest maximum cost when adding up the cost of edges from each leaf up to the root node.

When naïvely attempting to build all different possible binary trees, one sees that this takes O(C(n)) steps, where C(n) is the n-th Catalan Number

A simple dynamic programming-solution is isomorph with solving the Matrix Chain Multiplication Ordering problem, but filling the matrix used by this algorithm will take a ridiculous amount of memory.

I expect that it is possible to find a solution that is a lot more efficient (both in terms of time and memory).

How can you find out what the optimal tree structure would be?

How can you determine what the highest cost (cost of the leaf node + cost of the edges between it and the root node) would be in such a tree?

|improve this question
  • You seem to have have left something out: what constraint do you have on your trees such that you're searching through all possible trees? – walpen Mar 19 '17 at 16:26
  • @walpen I have added the sentence "We want to find the tree with the lowest cost". Does that clarify it, or do you mean something else? – Qqwy Mar 19 '17 at 17:13
  • I'm probably missing something here, but isn't a balanced tree the one with the least number of edges and thus the one with the minimal total cost? – Daniel Jour Mar 19 '17 at 18:26
  • @DanielJour The 'total cost' does not change between a balanced tree and an unbalanced one, as the amount of edges remains the same. But the maximum of (leaf node cost + edges up to root cost) does change. – Qqwy Mar 19 '17 at 19:38
  • 1
    The amount of edges is not the same: consider two leaves. Case one: a root node holding the two leaves. Two edges. Case two: a single inner node below root holding the two leaves. Three edges. – Daniel Jour Mar 19 '17 at 19:51
3

The number of edges is constant.

You should construct a Huffman tree, and use the cost of each leaf as the frequency.

|improve this answer

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.