Rake-Compress деревья
Задача, которая решается с помощью динамических деревьев (англ. dynamic tree), формулируется следующим образом. Необходимо поддерживать лес деревьев и выполнять на нем следующие операции:
- добавить ребро . Вершина должна быть корнем некоторого дерева. Вершины и должны находиться в разных деревьях,
- удалить ребро . Ребро должно присутствовать в графе,
- некоторый запрос относительно структуры дерева.
Примером последней операции может быть запрос "достижима ли вершина из ?", "сколько ребер на кратчайшем пути из в ?" или "какова сумма номеров вершин, которые находятся в поддереве вершины ?". Можно легко реализовать структуру данных, которая будет выполнять данные операции за время , где — количество вершин в графе. Динамические деревья нужны для того, чтобы обрабатывать запросы более эффективно. В частности, все предложенные операции возможно выполнять за время .
Описание
Rake-Compress Tree — структура данных, которая хранит лес деревьев и поддерживает следующие операции:
- — все листья дерева сжимаются к своим родителям,
- — выбирается и объединяется некоторое множество несмежных друг с другом вершин, имеющих ровно одного сына.
Входными данными для алгоритма Rake-Compress является лес корневых деревьев. К нему поочередно применяются операции и до тех пор, пока существует хотя бы одна живая вершина.
Во время каждой из этих операций выбирается некоторое множество попарно несмежных вершин, которое сжимается к своим родителям. После каждой операции лес сохраняется в специальном виде, что в дальнейшем дает возможность отвечать на запросы о структуре леса.
Современная реализация Rake-Compress деревьев была предложена Р. А. Тарьяном и Р. Ф. Вернеком.
См. также
Источники информации
- Wikipedia — Parallel Tree Contraction
- Б. Ю. Минаев — Реализация динамических Rake-Compress деревьев в случае отсутствия ограничения на степени вершин
- G. L. Miller, J. H. Reif — Parallel Tree Contraction

