СНМ с операцией удаления за О(1) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Расширение структуры данных)
Строка 6: Строка 6:
 
* Для корня каждого дерева храним двусвязный список <tex> \mathrm{NL_{list}} </tex> его детей, не являющихся листьями.
 
* Для корня каждого дерева храним двусвязный список <tex> \mathrm{NL_{list}} </tex> его детей, не являющихся листьями.
 
* Для каждого дерева (включая поддеревья) храним циклический двусвязный список <tex> \mathrm{DFS_{list}} </tex> его вершин, располагаемых в порядке обхода в глубину, начиная с левой вершины.
 
* Для каждого дерева (включая поддеревья) храним циклический двусвязный список <tex> \mathrm{DFS_{list}} </tex> его вершин, располагаемых в порядке обхода в глубину, начиная с левой вершины.
* Разделим понятия ''вершина дерева'' и ''элемент множества'': ''вершиной дерева'' назовем объект, содержащий ссылки <tex>next</tex>, <tex>prev</tex> и <tex>head</tex> (где необходимо) для каждого из вышеперечисленных списков
+
* Разделим понятия '''вершина дерева''' и '''элемент множества''': '''вершиной дерева''' назовем объект, содержащий ссылки <tex>next</tex>, <tex>prev</tex> и <tex>head</tex> (где необходимо) для каждого из вышеперечисленных списков, а так же ссылку на соответствующий вершине '''элемент множества'''; ''''элемент множества''' - объект, содержащий значение элемента и ссылку на соотв. '''вершину дерева'''.

Версия 00:21, 26 апреля 2014

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

Реализация

Расширение структуры данных

Расширим [СНМ_(реализация_с_помощью_леса_корневых_деревьев)|лес корневых деревьев] следующим образом:

  • Для каждой вершины дерева, не являющейся листом, будем хранить двусвязный список [math] \mathrm{C_{list}} [/math] ее детей. Будем считать, что дети упорядочены по направлению списка слева направо.
  • Для корня каждого дерева храним двусвязный список [math] \mathrm{NL_{list}} [/math] его детей, не являющихся листьями.
  • Для каждого дерева (включая поддеревья) храним циклический двусвязный список [math] \mathrm{DFS_{list}} [/math] его вершин, располагаемых в порядке обхода в глубину, начиная с левой вершины.
  • Разделим понятия вершина дерева и элемент множества: вершиной дерева назовем объект, содержащий ссылки [math]next[/math], [math]prev[/math] и [math]head[/math] (где необходимо) для каждого из вышеперечисленных списков, а так же ссылку на соответствующий вершине элемент множества; 'элемент множества - объект, содержащий значение элемента и ссылку на соотв. вершину дерева.