Rake-Compress деревья

Задача, которая решается с помощью динамических деревьев (англ. dynamic tree), формулируется следующим образом. Необходимо поддерживать лес деревьев и выполнять на нем следующие операции:

• добавить ребро [math](u, v)[/math]. Вершина [math]u[/math] должна быть корнем некоторого дерева. Вершины [math]u[/math] и [math]v[/math] должны находиться в разных деревьях,
• удалить ребро [math](u, v)[/math]. Ребро [math](u, v)[/math] должно присутствовать в графе,
• некоторый запрос относительно структуры дерева.

Примером последней операции может быть запрос "достижима ли вершина [math]u[/math] из [math]v[/math]?", "сколько ребер на кратчайшем пути из [math]u[/math] в [math]v[/math]?" или "какова сумма номеров вершин, которые находятся в поддереве вершины [math]u[/math]?". Можно легко реализовать структуру данных, которая будет выполнять данные операции за время [math]O(n)[/math], где [math]n[/math] — количество вершин в графе. Динамические деревья нужны для того, чтобы обрабатывать запросы более эффективно. В частности, все предложенные операции возможно выполнять за время [math]O(\log{n})[/math].

Описание

Rake-Compress Tree — структура данных, которая хранит лес деревьев и поддерживает следующие операции:

• [math]\mathrm{Rake}[/math] — все листья дерева сжимаются к своим родителям,
• [math]\mathrm{Compress}[/math] — выбирается и объединяется некоторое множество несмежных друг с другом вершин, имеющих ровно одного сына.

Операция [math]\mathrm{Rake}[/math]

Операция [math]\mathrm{Compress}[/math]

Входными данными для алгоритма Rake-Compress является лес корневых деревьев. К нему поочередно применяются операции [math]\mathrm{Rake}[/math] и [math]\mathrm{Compress}[/math] до тех пор, пока существует хотя бы одна живая вершина.
Во время каждой из этих операций выбирается некоторое множество попарно несмежных вершин, которое сжимается к своим родителям. После каждой операции лес сохраняется в специальном виде, что в дальнейшем дает возможность отвечать на запросы о структуре леса.
Современная реализация Rake-Compress деревьев была предложена Р. А. Тарьяном и Р. Ф. Вернеком.

См. также

• Link-Cut Tree

Источники информации

• Wikipedia — Parallel Tree Contraction
• Б. Ю. Минаев — Реализация динамических Rake-Compress деревьев в случае отсутствия ограничения на степени вершин
• G. L. Miller, J. H. Reif — Parallel Tree Contraction