188
правок
Изменения
м
Примером последней операции может быть запрос "достижима ли вершина <tex>u</tex> из <tex>v</tex>?", "сколько ребер на кратчайшем пути из <tex>u</tex> в <tex>v</tex>?" или "какова сумма номеров вершин, которые находятся в поддереве вершины <tex>u</tex>?". Можно легко реализовать структуру данных, которая будет выполнять данные операции за время <tex>O(n)</tex>, где <tex>n</tex> {{---}} количество вершин в графе. Динамические деревья нужны для того, чтобы обрабатывать запросы более эффективно. В частности, все предложенные операции возможно выполнять за время <tex>O(\log{n})</tex>.
Входными данными для алгоритма Rake-Compress является лес К лесу корневых деревьев. К нему поочередно применяются операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> до тех пор, пока существует хотя бы одна живая несжатая вершина.<br>Во время каждой из этих операций выбирается некоторое множество попарно несмежных вершин, которое сжимается к своим родителям. После каждой операции лес сохраняется в специальном виде, что в дальнейшем дает возможность отвечать на запросы о структуре леса.<br>Современная реализация Rake-Compress деревьев была предложена Р. А. Тарьяном и Р. Ф. Вернеком.
Нет описания правки
Задача, которая решается с помощью '''[[Link-Cut Tree|динамических деревьев''' (англ. ''dynamic tree'')]], формулируется следующим образом. Необходимо поддерживать лес деревьев и выполнять на нем следующие операции:
* добавить ребро <tex>(u, v)</tex>. Вершина <tex>u</tex> должна быть корнем некоторого дерева. Вершины <tex>u</tex> и <tex>v</tex> должны находиться в разных деревьях,
* удалить ребро <tex>(u, v)</tex>. Ребро <tex>(u, v)</tex> должно присутствовать в графе,
* некоторый запрос относительно структуры дерева.
__TOC__
<td>[[Файл:Rctree-compress.png|x180px|thumb|Операция <tex>\mathrm{Compress}</tex>]]</td>
</tr></table>
Рассмотрим, как изменяется количество вершин в дереве после применения к нему операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex>. Разобьём все вершины дерева на три группы: входящая степень которых равна нулю, одному и больше одного. Обозначим их количество за <tex>T_0, T_1</tex> и <tex>T_2</tex> соответственно.
