СНМ с операцией удаления за О(1) — различия между версиями
(→Расширение структуры данных) |
|||
| Строка 1: | Строка 1: | ||
| − | Реализация системы непересекающихся множеств с помощью [СНМ_(реализация_с_помощью_леса_корневых_деревьев)|леса корневых деревьев] не поддерживает операцию удаления элемента из множества. Приведенная ниже модификация этой структуры данных вводит поддержку операции удаления за О(1) в худшем случае, сохраняя асимптотику для операций Union и Find и потребление памяти O(n). | + | Реализация системы непересекающихся множеств с помощью [[СНМ_(реализация_с_помощью_леса_корневых_деревьев)|леса корневых деревьев]] не поддерживает операцию удаления элемента из множества. Приведенная ниже модификация этой структуры данных вводит поддержку операции удаления за О(1) в худшем случае, сохраняя асимптотику для операций Union и Find и потребление памяти O(n). |
== Реализация == | == Реализация == | ||
=== Расширение структуры данных === | === Расширение структуры данных === | ||
| − | Расширим [СНМ_(реализация_с_помощью_леса_корневых_деревьев)|лес корневых деревьев] следующим образом: | + | Расширим [[СНМ_(реализация_с_помощью_леса_корневых_деревьев)|лес корневых деревьев]] следующим образом: |
* Для каждой вершины дерева, не являющейся листом, будем хранить двусвязный список <tex> \mathrm{C_{list}} </tex> ее детей. Будем считать, что дети упорядочены по направлению списка слева направо. | * Для каждой вершины дерева, не являющейся листом, будем хранить двусвязный список <tex> \mathrm{C_{list}} </tex> ее детей. Будем считать, что дети упорядочены по направлению списка слева направо. | ||
* Для корня каждого дерева храним двусвязный список <tex> \mathrm{NL_{list}} </tex> его детей, не являющихся листьями. | * Для корня каждого дерева храним двусвязный список <tex> \mathrm{NL_{list}} </tex> его детей, не являющихся листьями. | ||
Версия 00:25, 26 апреля 2014
Реализация системы непересекающихся множеств с помощью леса корневых деревьев не поддерживает операцию удаления элемента из множества. Приведенная ниже модификация этой структуры данных вводит поддержку операции удаления за О(1) в худшем случае, сохраняя асимптотику для операций Union и Find и потребление памяти O(n).
Реализация
Расширение структуры данных
Расширим лес корневых деревьев следующим образом:
- Для каждой вершины дерева, не являющейся листом, будем хранить двусвязный список ее детей. Будем считать, что дети упорядочены по направлению списка слева направо.
- Для корня каждого дерева храним двусвязный список его детей, не являющихся листьями.
- Для каждого дерева (включая поддеревья) храним циклический двусвязный список его вершин, располагаемых в порядке обхода в глубину, начиная с левой вершины.
- Разделим понятия вершина дерева и элемент множества:
- вершиной дерева назовем объект, содержащий ссылки , и (где необходимо) для каждого из вышеперечисленных списков, а так же ссылку на соответствующий вершине элемент множества;
- элемент множества - объект, содержащий значение элемента и ссылку на соотв. вершину дерева.
