116
правок
Изменения
→Реализация union(A, B)
Очевидно, что операция соблюдает инварианты и выполняется за <tex>O(1)</tex>
=== Реализация <tex>union(A, B)</tex> операции Union ===
Пусть <tex> T_A, T_B </tex> - деревья, реализующие множества <tex>A</tex> и <tex>B</tex> соответственно.
Пусть размер одного из деревьев меньше 4; не умаляя общности - <tex>size(T_B) < 4</tex>. Тогда действуем следующим образом:
# <tex>\forall v \in T_B : \: p(v) \leftarrow root(T_A), \: rank(v) \leftarrow 0</tex>
# <tex> rank(root(T_A)) \leftarrow max \: \{ rank(root(T_A)), 1 \: \}</tex>
# Добавим все вершины Присоединим <tex>\mathrm{ DFS_{LIST}} </tex> и <tex>\mathrm{C_{LIST}}</tex> для <tex>T_B </tex> в конец <tex>\mathrm{ DFS_{LIST}} </tex> и <tex>\mathrm{C_{LIST}}</tex> корня для <tex>T_A</tex> Теперь рассмотрим случай, когда размеры обоих деревьев больше 4.Примем, не умаляя общности, что <tex>rank(root(T_A)) \geq rank(root(T_B))</tex>. Тогда:# <tex>p(root(T_B)) \leftarrow root(T_A)</tex>, и если <tex>rank(root(T_A)) = rank(root(T_B))</tex>, увеличим <tex>rank(root(T_A))</tex> на 1.# Вставим <tex>root(T_B)</tex> в начала <tex>\mathrm{ N_{LIST}} </tex> и <tex>\mathrm{C_{LIST}}</tex> для <tex>T_A</tex># Вставим <tex>\mathrm{ DFS_{LIST}} </tex> для <tex>T_B </tex> в <tex>\mathrm{ DFS_{LIST}} </tex> для <tex>T_A </tex> сразу после <tex>root(T_A)</tex># Сделаем <tex>\mathrm{ N_{LIST}} </tex> для <tex>T_B </tex> пустым. (Мы работаем в предположении, что очистка списка не подразумевает удаления каждого элемента вручную) Если в качестве идентификаторов множеств нам переданы произвольные представители этих множеств, нам придется запустить процедуру <tex>find</tex> для каждого из них, чтобы найти корни деревьев. Без учета вызова процедуры <tex>find</tex>мы сделаем O(1) операций.
