https://en.formulasearchengine.com/w/index.php?action=history&feed=atom&title=Short-circuit_testShort-circuit test - Revision history2026-08-10T18:14:01ZRevision history for this page on the wikiMediaWiki 1.47.0-wmf.7https://en.formulasearchengine.com/w/index.php?title=Short-circuit_test&diff=28224&oldid=preven>Tony1 at 02:50, 25 December 20132013-12-25T02:50:10Z<p></p>
<p><b>New page</b></p><div>In [[computer science]], '''tree accumulation''' is the process of accumulating data placed in [[Tree (data structure)|tree]]<br />
nodes according to their [[Tree (data structure)|tree]] structure.<ref>{{cite thesis |type=Ph.D. |first=Jeremy |last=Gibbons |title=Algebras for Tree Algorithms |publisher=Oxford University |year=1991 |url=http://www.cs.ox.ac.uk/files/3422/PRG94.pdf }}</ref> Formally, this operation is a [[catamorphism]].<br />
<br />
Upward accumulation refers to accumulating on each node information about all decedents. Downward accumulation refers to accumulating on each node information of every ancestor.<br />
<br />
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.<br />
<br />
==Formal analysis==<br />
Gibbons et al.<ref>{{cite journal|last1=Gibbons|first1=Jeremy| last2=Cai |first2=Wentong |last3=Skillcorn |first3=David B. |title=Efficient parallel algorithms for tree accumulations|journal=Science of Computer Programming|year=1994|series=Elsiver}}</ref> formally define binary tree accumulation as iterative application of a ternary operator <math>\otimes(A,B,A)</math>; where A are descendant labels and B is a junction label.<br />
<br />
==References==<br />
{{Reflist}}<br />
<br />
[[Category:Trees (data structures)]]</div>en>Tony1