116
правок
Изменения
Нет описания правки
Как и в [[СНМ_(реализация_с_помощью_леса_корневых_деревьев)|обычной реализации]], выполнено следующее: <tex>rank(v) < rank(p(v))</tex>
== Идея ==
В реализации СНМ с помощью леса корневых деревьев мы не можем удалить произвольную вершину из множества за разумное время - в таком случае нам придется переподвешивать <tex>O(n) </tex> поддеревьев этой вершины. Однако, если вершина является листом, то ее можно удалять совершенно безболезненно. <br />
'''Соображение 1:''' Пусть мы умеем менять произвольные вершины местами за <tex>O(1)</tex>. Тогда для удаления некоторой вершины достаточно поменять ее местами с каким-нибудь листом и удалить этот лист. <br />
'''Соображение 2:''' Пусть мы умеем находить какой-нибудь лист (неважно, какой именно) в дереве за <tex>O(1)</tex>. Тогда, по соображению 1, мы уже умеем удалять произвольный элемент из дерева за <tex>O(1)</tex>
<br />
Все дальнейшие действия направлены на то, чтобы поддержать эти 2 операции, не испортив при этом асимптотику всех остальных.
== Реализация ==
=== Расширение структуры данных ===
