Is there a general name for a tree in which the leaves have some arbitrary values and the value of every other node is some "aggregate" function of its children?

An example where the aggregate function is the sum:

 /  \
4   10
   / | \
  7  1  2

The function could also be the min, max, or any other function of the form $f:S^n\to S$.

  • $\begingroup$ Whether and how to actually store these values may be an implementation detail from the perspective of classic algorithmics. (Recursive) Functions on trees are just that; I don't know of a special name. $\endgroup$
    – Raphael
    Oct 4 '17 at 17:41

Such tree is called Sum Tree or SumTree, where the property is maintained in bottom up fashion. In general if the value is additional value (node property) for some existing one like AVL it is Sum augmented AVL Tree.

If the property is inherent, like maintaining the prefix sum, it would be Fenwick Tree.

As far as I know there is no established name, but for other functions it is partial statistics tree. preferable name would be Tree augmented with $f$, to make it explicit.


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.