188
правок
Изменения
Нет описания правки
* <tex>\mathrm{link(u, v)}</tex> {{---}} добавить ребро <tex>(u, v)</tex>. Вершина <tex>u</tex> должна быть корнем некоторого дерева. Вершины <tex>u</tex> и <tex>v</tex> должны находиться в разных деревьях,
* <tex>\mathrm{cut(u, v)}</tex> {{---}} удалить ребро <tex>(u, v)</tex>. Ребро <tex>(u, v)</tex> должно присутствовать в графе,
* <tex>\mathrm{query()}</tex> {{---}} некоторый запрос относительно структуры дерева.
[[Файл:RC_graph_tree.png|500px|center|thumb|RC-tree для дерева <tex>T</tex>.]]
Поскольку матожидание количества раундов {{---}} логарифм, то такое дерево будет сбалансированным.<br>
<tex>\mathrm{RC}</tex> дерево можно использовать для ответа на динамические запросы для статического дерева. Для этого в <tex>\mathrm{RC}</tex> дереве сохраним требуемую информацию (необходимо модифицировать для пересчёта информации операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex>) и используем обход для ответа на запросы. Поскольку дерево с большой вероятностью является сбалансированным, обход дерева также можно осуществить за логарифм.<br>
Для динамических деревьев, например, если доступны операции добавления/удаления ребра (операции <tex>\mathrm{link}</tex> и <tex>\mathrm{cut}</tex>), нужно эффективно перестраивать отдельные кластеры, пересчитывая данные. Для этого можно обновлять данные начиная с листа дерева, соответствующего обновляемой вершине в исходном дереве, и подниматься вверх.
==Реализация==
