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