Накопление деревьев - Tree accumulation

В Информатика, скопление деревьев это процесс накопления данных, помещенных в дерево узлов в соответствии с их дерево структура.[1] Формально эта операция представляет собой катаморфизм.

Накопление вверх означает накопление на каждом узле информации обо всех потомках. Нисходящее накопление относится к накоплению на каждом узле информации каждого предка.

Одно приложение будет вычислять результаты национальных выборов. Постройте дерево с корневым узлом как всей нацией и каждым уровнем, представляющим уточненные географические области, такие как штаты / провинции, округа / округа, города / поселки и избирательные округа как листья. Накапливая итоги голосов по избирательным округам, можно вычислить итоги голосов для каждой из более крупных географических областей.

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

Гиббонс и др.[2] формально определить накопление двоичного дерева как итеративное применение тернарного оператора ; где A - дочерние метки, а B - метка соединения.

использованная литература

  1. ^ Гиббонс, Джереми (1991). Алгебры для древовидных алгоритмов (PDF) (Кандидат наук.). Оксфордский университет.
  2. ^ Гиббонс, Джереми; Цай, Вентун; Skillcorn, Дэвид Б. (1994). «Эффективные параллельные алгоритмы накопления деревьев». Наука компьютерного программирования. Эльсивер.