Misplaced Pages

Tree accumulation

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

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 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 ⊗ ( A , B , A ) {\displaystyle \otimes (A,B,A)} ; where A are descendant labels and B is a junction label.

References

  1. Gibbons, Jeremy (1991). Algebras for Tree Algorithms (PDF) (Ph.D.). Oxford University.
  2. Gibbons, Jeremy; Cai, Wentong; Skillcorn, David B. (1994). "Efficient parallel algorithms for tree accumulations". Science of Computer Programming. Elsiver.
Category: