Накопичення по дереву

В інформатиці, накопичення по дереву — процес накопичення даних у вузлах дерева відповідно до його структури. Формально ця операція є Шаблон:Не перекладено.

Висхідним є накопичення, за якого кожен вузол містить інформацію про своїх нащадків. Низхідним є накопичення, за якого кожен вузол містить інформацію про свого предка.

Одним із застосувань є підрахунок результатів загальнонаціональних виборів. За такого завдання, можна побудувати дерево з кореневим вузлом, що позначає цілу державу, а кожен рівень дерева відображає окремі географічні регіони (як-от області, райони, міста/села, виборчі округи) в ролі листків. Зібравши дані про результати голосувань на виборчих округах, можна обчислити результати голосування в кожному із великих географічних регіонів.

Формальний аналіз

Ґіббонс та ін. формально визначили накопичення по бінарному дереву як ітеративне застосування тернарного оператора $\otimes (A,B,A)$; де A є мітками-нащадками, а B є міткою-з'єднанням.