0
$\begingroup$

I have a tree with percentages of the following form

        100
       /   \
      /     \
     /       \
    /         \
   25          75
  /  \       / | \
 15  10    35  10 30
    /  \      / \
   1    9    5   5
      / | \
     3  3  3

So child nodes are added up in the parent node.

Does a tree with this attribute has a already defined name in the algorithmic world?


Thanks for the positive feedback so far.

In this case the nodes hold actually values which are added up in the parent and the example tree shows the percentages of these values in comparison to the root.

I have to implement an algorithm to find those nodes which have the biggest impact and add up to 95 percent.

Since the problem description in case what "biggest impact" means, is pretty open I was thinking about setting the percentage in relation to its child nodes + itself.

Therefore node 25 would have a weight of 25/8, node 75 would have on of 75/6 and so on.

In the next step I would order by weight, min amount of children, in descending order and add up the percentages of the nodes until I reach 95 percent. Always removing a sub node from the result when the parent is added.

I hope I could make myself clear

$\endgroup$

migrated from stackoverflow.com Jun 6 '14 at 17:46

This question came from our site for professional and enthusiast programmers.

2
$\begingroup$

Building off of Matt Ball's answer, there's an implementation of this here on SO, and there's some mention of it here. It sounds like a second-cousin of a heap, and it's the reverse of a Fenwick tree, in some sense.

However, it's hard to imagine a situation where this would be useful.

$\endgroup$
2
$\begingroup$

I believe it is creatively called a "sum tree."

Algorithmically it's not especially useful nor interesting because it is not efficiently modifiable.

$\endgroup$
  • 2
    $\begingroup$ A reference would be nice. Just like with supernatural beings, I want evidence, not belief. $\endgroup$ – rightfold Jun 6 '14 at 16:56
  • $\begingroup$ @rightfold I agree, but evidence suggests this "data structure" isn't really used. $\endgroup$ – Matt Ball Jun 6 '14 at 18:22

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.