Akumulace stromu - Tree accumulation

v počítačová věda, akumulace stromu je proces shromažďování dat umístěných do strom uzly podle jejich strom struktura.^[1] Formálně je tato operace a katamorfismus.

Nahromadění nahoru znamená hromadění informací o všech potomcích v každém uzlu. Kumulace dolů se týká akumulace informací o každém předku na každém uzlu.

Jednou z aplikací by byl výpočet výsledků národních voleb. Postavte strom s kořenem jako celým národem a každou úrovní představující rafinované geografické oblasti, jako jsou státy / provincie, okresy / farnosti, města / městyse a volební obvody jako listy. Shromážděním součtů hlasů z volebních obvodů lze vypočítat součty hlasů pro každou z větších geografických oblastí.

Formální analýza

Gibbons a kol.^[2] formálně definovat akumulaci binárního stromu jako iterativní aplikaci ternárního operátoru ${ displaystyle otimes (A, B, A)}$; kde A jsou potomkové štítky a B je spojovací štítek.

Reference