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

Реализация системы непересекающихся множеств с помощью леса корневых деревьев не поддерживает операцию удаления элемента из множества. Приведенная ниже модификация этой структуры данных вводит поддержку операции удаления за О(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] (где необходимо) для каждого из вышеперечисленных списков, а так же ссылку на соответствующий вершине элемент множества;
  • элемент множества - объект, содержащий значение элемента и ссылку на соотв. вершину дерева.