Jump to content

Tree accumulation

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by GrEp (talk | contribs) at 20:40, 2 November 2012 (Added a simple example.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In Computer Science, tree accumulation is the process of accumulating data placed in tree nodes according to their tree structure. Formally this operation is a catamorphism.

Upward accumulation refers to accumulating on each node information about all decedents. Downward accumulation refers to accumulating on each node information of every ancestor.

One application would be calculating national election results. Construct a tree with the root node as the entire nation and each level representing refined geographical areas such as states/provinces, counties/parishes, cities/townships, and polling districts as the leaves. By accumulating the vote totals from the polling districts one can compute the vote totals for each of the larger geographic areas.


Gibbons, Jeremy (1991). Algebras for Tree Algorithms (PDF) (Ph.D.). Oxford University.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Tree_accumulation&oldid=521106579"