Author |
Topic: Heaviest subtree (Read 4716 times) |
|
Terps.Go
Newbie
Gender: 
Posts: 13
|
 |
Heaviest subtree
« on: Apr 26th, 2005, 1:19pm » |
 Quote  Modify
|
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.
|
| « Last Edit: Apr 26th, 2005, 1:21pm by Terps.Go » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Heaviest subtree
« Reply #1 on: Apr 26th, 2005, 1:38pm » |
Quote Modify
|
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  )
|
| « Last Edit: Apr 26th, 2005, 1:40pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Terps.Go
Newbie
Gender:
Posts: 13
|
|
Re: Heaviest subtree
« Reply #2 on: Apr 26th, 2005, 1:45pm » |
Quote Modify
|
Any subtree. The whole tree is the solution ONLY if the value of each node is non-negative.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Heaviest subtree
« Reply #3 on: Apr 26th, 2005, 2:47pm » |
Quote Modify
|
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.
|
| « Last Edit: Apr 26th, 2005, 2:47pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Terps.Go
Newbie
Gender:
Posts: 13
|
|
Re: Heaviest subtree
« Reply #4 on: Apr 27th, 2005, 6:03pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Heaviest subtree
« Reply #5 on: Apr 27th, 2005, 7:36pm » |
Quote Modify
|
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.  )
|
| « Last Edit: Apr 27th, 2005, 7:39pm by Deedlit » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Heaviest subtree
« Reply #6 on: Apr 28th, 2005, 2:47am » |
Quote Modify
|
on Apr 27th, 2005, 6:03pm, 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.
|
| « Last Edit: Apr 28th, 2005, 2:55am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
VincentLascaux
Guest
|
on Apr 26th, 2005, 2:47pm, 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);
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Heaviest subtree
« Reply #8 on: Apr 28th, 2005, 12:59pm » |
Quote Modify
|
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.
How about if you can replace a parent node by one of the descendants.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Heaviest subtree
« Reply #9 on: Apr 28th, 2005, 7:51pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Heaviest subtree
« Reply #10 on: Apr 29th, 2005, 1:00am » |
Quote Modify
|
Doesn't that mean you can just take all positive nodes?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Heaviest subtree
« Reply #11 on: Apr 29th, 2005, 2:07am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove