Изменения

Реализация системы непересекающихся множеств с помощью [[СНМ_(реализация_с_помощью_леса_корневых_деревьев)|леса корневых деревьев]] не поддерживает операцию удаления элемента из множества. Приведенная ниже модификация этой структуры данных вводит поддержку операции удаления за Оистинную <tex>O(1) в худшем случае</tex>, сохраняя асимптотику для операций <tex>\mathrm{ Union } </tex> и <tex>\mathrm{Find }</tex> и потребление памяти <tex>O(n)</tex>.

* <tex>makeset\mathrm {Makeset(x)}</tex> - создать новое множество из 1 элемента <tex>x </tex>. Время: <tex>O(1)</tex>* <tex>union\mathrm {Union(A, B)}</tex> - объединить множества A и B в одно. Время: <tex> O(1) </tex>, без учета времени на операцию <tex>find</tex>, которая используется, если множества A и B заданы своими произвольными представителями.* <tex>find\mathrm {Find(x)}</tex> - найти множество, в котором содержится элемент <tex> x </tex>. Время; <tex>O(log n)</tex> в худшем случае, <tex>O(\alpha(n))</tex> - в среднем (<tex>\alpha(n)</tex> - обратная функция Аккермана), где n - размер множества.* <tex>delete\mathrm{Delete(x)}</tex> - удалить элемент x из содержащего его множества. Время: O(1)