wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Heaviest subtree
        
(Message started by: Terps.Go on Apr 26^th, 2005, 1:19pm)

Title: Heaviest subtree
Post by Terps.Go on Apr 26^th, 2005, 1:19pm

There is a tree, not binary tree, each node can have several children. Each node on the tree is associated with a value which is an integer which can be negative, 0, or positive. The weight of a subtree is the sum of all values of nodes in that subtree. Find the heaviest subtree. The heaviest subtree is the subtree with largest weight.
Derive an efficient algorithm to find the heaviest tree.

Title: Re: Heaviest subtree
Post by towr on Apr 26^th, 2005, 1:38pm

Do you want subtrees whose roots are the children of the root of the whole tree, or just any subtree, or something more specific?
(Just any subtree is easy, because the whole tree is also a subtree of itself ;D )

Title: Re: Heaviest subtree
Post by Terps.Go on Apr 26^th, 2005, 1:45pm

Any subtree. The whole tree is the solution ONLY if the value of each node is non-negative.

Title: Re: Heaviest subtree
Post by towr on Apr 26^th, 2005, 2:47pm

Ah, I missed that part. I really should learn to read more carefully.

A simple O(n) algorithm:

Code:

global tree maxST=0;
global int maxWt=-inf;

int fun(tree T)
{
weight=T.value;
for t in T.children
{
weight += fun(t);
}

if weight > maxWt
{
maxST=T;
maxWt=weight;
}

return weight;
}

main()
{
tree T;
read(T);
fun(T);
print(maxST);
}

Unless of course you want the heaviest pruned subtree (from which sub-subtrees may have been cut away), which makes it a little bit trickier.

Title: Re: Heaviest subtree
Post by Terps.Go on Apr 27^th, 2005, 6:03pm

Not correct Towr!
You have a wrong definition of subtree. The subtree of a tree T is a tree with its root is one of node in the tree T, and all its descendants in T.

Title: Re: Heaviest subtree
Post by Deedlit on Apr 27^th, 2005, 7:36pm

Seems that a recursive procedure like

procedure maxT (tree T, var integer W, var tree maxST, var integer maxW) begin maxW = -inf; W := T.value; for t in T.children begin maxT (t, tW, tmaxST, tmaxW); W := W + tW; if tmaxW > maxW then begin maxW := tmaxW; maxST := tmaxST; end; end; if W > maxW then begin maxW := W; maxST := T; end; end;

should work. (Sorry for the Pascalese - it seemed I would need pointers in C, and I shy away from pointers for some reason. As you can see, I haven't programmed in a while. :P )

Title: Re: Heaviest subtree
Post by towr on Apr 28^th, 2005, 2:47am

on 04/27/05 at 18:03:39, Terps.Go wrote:

Not correct Towr!
You have a wrong definition of subtree. The subtree of a tree T is a tree with its root is one of node in the tree T, and all its descendants in T.

Which are defined by the top node in the subtree.
I really don't see where you think I made a mistake. The tree I return is a proper subtree.

And my algorithm is in fact the same as Deedlits, though in different (pseudo)code.

Title: Re: Heaviest subtree
Post by VincentLascaux on Apr 28^th, 2005, 12:39pm

on 04/26/05 at 14:47:06, towr wrote:

Unless of course you want the heaviest pruned subtree (from which sub-subtrees may have been cut away), which makes it a little bit trickier.

I think that you can have this one by just changing one line in your code:
weight += fun(t); becomes
weight += max(fun(t), 0);

Title: Re: Heaviest subtree
Post by towr on Apr 28^th, 2005, 12:59pm

That should give the correct root node, but you still have to cut away the dead branches. So ok, it's hardly even a bit trickier than the original. ;D

How about if you can replace a parent node by one of the descendants.

Title: Re: Heaviest subtree
Post by Deedlit on Apr 28^th, 2005, 7:51pm

Oops - I took Terps' word that towr had solved the wrong problem, without checking it carefully. :-[ The confusion probably comes from the use of global variables, which makes the recursion a bit more subtle. I tend to use var parameters or pointers instead of global variables, as they confuse me sometimes.

Another interesting variant: how about the largest embedded tree? The difference with a pruned tree is that you can go straight from a node to any descendent, skipping the nodes in between.

Title: Re: Heaviest subtree
Post by towr on Apr 29^th, 2005, 1:00am

Doesn't that mean you can just take all positive nodes?

Title: Re: Heaviest subtree
Post by Deedlit on Apr 29^th, 2005, 2:07am

Sorry, I left out the condition that for any two nodes in the embedded tree, you have to also have their lowest common ancestor in the embedded tree. So, if for example A is the root node with child B, and B has children C and D, we can't take A,C,D as the embedded tree - taking C and D means we take B as well. This may be the same as your 'children to parent' variant.

I guess it's not that complicated, though. We recurse the function through each of the children, keeping track of the maximum tree and its value, and compare that to the root node plus all the sum of all children with positive values.