Накопичення по дереву
В інформатиці, накопичення по дереву — процес накопичення даних у вузлах дерева відповідно до його структури.[1] Формально ця операція є катамофізмом[en].
Висхідним є накопичення, за якого кожен вузол містить інформацію про своїх нащадків. Низхідним є накопичення, за якого кожен вузол містить інформацію про свого предка.
Одним із застосувань є підрахунок результатів загальнонаціональних виборів. За такого завдання, можна побудувати дерево з кореневим вузлом, що позначає цілу державу, а кожен рівень дерева відображає окремі географічні регіони (як-от області, райони, міста/села, виборчі округи) в ролі листків. Зібравши дані про результати голосувань на виборчих округах, можна обчислити результати голосування в кожному із великих географічних регіонів.
Ґіббонс та ін.[2] формально визначили накопичення по бінарному дереву як ітеративне застосування тернарного оператора ; де A є мітками-нащадками, а B є міткою-з'єднанням.
- ↑ Gibbons, Jeremy (1991). Algebras for Tree Algorithms (PDF) (Ph.D.). Oxford University. Архів оригіналу (PDF) за 5 березня 2021. Процитовано 1 березня 2021.
- ↑ Gibbons, Jeremy; Cai, Wentong; Skillcorn, David B. (1994). Efficient parallel algorithms for tree accumulations. Science of Computer Programming. Elsiver.