In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...
, tree accumulation is the process of accumulating data placed in
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
nodes according to their
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
structure. Formally, this operation is a
catamorphism.
Upward accumulation refers to accumulating on each node information about all descendants. 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.
Formal analysis
Gibbons et al.
formally define binary tree accumulation as iterative application of a ternary operator
; where A are descendant labels and B is a junction label.
References
{{Reflist
Trees (data structures)