116
правок
Изменения
Нет описания правки
Реализация системы непересекающихся множеств с помощью [[СНМ_(реализация_с_помощью_леса_корневых_деревьев)|леса корневых деревьев]] не поддерживает операцию удаления элемента из множества. Приведенная ниже модификация этой структуры данных вводит поддержку операции удаления за О(1) в худшем случае, сохраняя асимптотику для операций Union и Find и потребление памяти O(n).
== Введение ==
Наша структура данных должна поддерживать следующие операции:
* <tex>makeset(x)</tex> - создать новое множество из 1 элемента <tex>x </tex>. Время: <tex>O(1)</tex>
* <tex>union(A, B)</tex> - объединить множества A и B в одно. Время: <tex> O(1) </tex>, без учета времени на операцию <tex>find()</tex>, которая используется, если множества A и B заданы своими произвольными представителями.
* <tex>find(x)</tex> - найти множество, в котором содержится элемент <tex> x </tex>. Время; <tex>O(log n)</tex> в худшем случае, <tex>O(\alpha(n))</tex> - в среднем (<tex>\alpha(n)</tex> - обратная функция Аккермана), где n - размер множества.
* <tex>delete(x)</tex> - удалить элемент x из содержащего его множества. Время: O(1)
В дальнейшем мы будем использовать следующие понятия и обозначения:
* <tex>size(A)</tex> - размер множества A (количество элементов в нем).
* <tex>root(T_A)</tex> - корень дерева <tex>T_A</tex>
* <tex>h(v)</tex> - высота вершины <tex>v</tex>: если <tex>v</tex> является листом, то <tex>h(v) = 0</tex>, иначе <tex>h(v) = max { h(w) | w - ребенок v } </tex>.
* <tex>p(v)</tex> - родитель вершины <tex>v</tex>. Если <tex>v</tex> - корень, то считаем, что <tex>p(v) = v</tex>
* <tex>rank(v)</tex> - ранг вершины, некоторая верхняя оценка на ее высоту. Как и в [[СНМ_(реализация_с_помощью_леса_корневых_деревьев)|обычной реализации]], выполнено следующее: '''ранг родителя вершин
== Реализация ==
=== Расширение структуры данных ===
