What is the name of the tree data structure where node weight equals the sum of all descendant nodes' weights?
Example:
15
/ \
10 5
/ \ / \
2 8 1 4
$\begingroup$
$\endgroup$
5
-
$\begingroup$ What makes you think there is a name for it? The great thing about language is that it lets us describe and name things for ourselves -- there are many more good ideas than existing "names", and there's no reason to think that every good idea has to have a standard "name". $\endgroup$– D.W. ♦Jul 18, 2018 at 18:14
-
$\begingroup$ Maybe someone studied this before and gave a name, I just wanted to know if there is a name. If I know how people call it I can search it on web and study it. $\endgroup$– feritJul 18, 2018 at 18:14
-
$\begingroup$ My standard advice is: figure out what you'd do with the "name", and then ask about that. If the name would help you research this to answer some question about the data structure, then ask that question. That way either someone responds with a name, or answers your question. But I don't find questions of the form "here is my data structure/algorithm, does it have a name?" very likely to be valuable to others in the future. $\endgroup$– D.W. ♦Jul 18, 2018 at 18:16
-
$\begingroup$ This looks like some type of Binary Tree but if you're asking for a specific condition where the descending nodes are equal to it's preceding node, then I don't think that has a specific name for that. $\endgroup$– user84111Jul 18, 2018 at 20:43
-
$\begingroup$ Such trees are encountered in dynamic huffman/arithmetic coders. Never seen specific name for them though $\endgroup$– BulatJul 24, 2018 at 11:05
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
It is called a SumTree. A SumTree is a Binary Tree where the value of a node is equal to sum of the nodes present in its left subtree and right subtree. An empty tree is SumTree and sum of an empty tree can be considered as 0. A leaf node is also considered as SumTree.
-
$\begingroup$ Do you have a source for this? If so, it would help to provide a link or citation to the source that proposed/introduced this terminology. (I've never heard of the term "SumTree" before.) $\endgroup$– D.W. ♦Jul 19, 2018 at 15:20
-
$\begingroup$ @D.W. I dont have exact online source for this. This was taught in my university. But if you google it you will find some good source. Here is one Check here $\endgroup$ Jul 19, 2018 at 16:43
-
$\begingroup$ That looks like a web page that defines its own term. I'm still not convinced this is a standard term that most people will have heard of or that is accepted among the community. $\endgroup$– D.W. ♦Jul 19, 2018 at 16:58
$\begingroup$
$\endgroup$
2
Like others have pointed out there is no name for it but it looks like a Binary Search Tree or a version of it AVL or WBT that is augmented.
-
2$\begingroup$ The example given specifically isn't a BST, and any version of this structure with positive weights can never be a BST. $\endgroup$– DraconisJul 19, 2018 at 0:00
-
$\begingroup$ lol I went full retard your right some of the nodes on the right are lower than its parent $\endgroup$ Jul 19, 2018 at 22:19