Изменения
Нет описания правки
=== Реализация операции Makeset ===
Тривиально:
# Создадим узел <tex>v</tex> и свяжем его с элементом <tex>x</tex>. Установим: <tex>p(v) := v, rank(v) := 0</tex>.
# Создадим для вершины <tex>v</tex> пустые списки <tex>\mathrm{N_{LIST}}</tex> и <tex>\mathrm{C_{LIST}}</tex>.
# Создадим <tex>\mathrm{DFS_{LIST}}</tex> с одним элементом {{---}} вершина <tex>v</tex>.
Пусть <tex> T_A, T_B </tex> {{---}} деревья, реализующие множества <tex>A</tex> и <tex>B</tex> соответственно.
Пусть размер одного из деревьев меньше <tex>4</tex>; не умаляя общности {{---}} <tex>size(T_B) < 4</tex>. Тогда действуем следующим образом:
# <tex>\forall v \in T_B : \: p(v) := root(T_A), \: rank(v) := 0</tex>.# <tex> rank(root(T_A)) := \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>.
Теперь рассмотрим случай, когда размеры обоих деревьев больше <tex>4</tex>.
Примем, не умаляя общности, что <tex>rank(root(T_A)) \geqslant rank(root(T_B))</tex>. Тогда:
# <tex>p(root(T_B)) := root(T_A)</tex>, и если <tex>rank(root(T_A)) = rank(root(T_B))</tex>, увеличим <tex>rank(root(T_A))</tex> на <tex>1</tex>.
# Вставим <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 {DFS_{LIST}} </tex>, соответствующий поддереву <tex>x</tex>, перед <tex>p(x) </tex>. Этот участок {{---}} полуинтервал <tex>[x, l)</tex>, где <tex>l</tex> {{---}} сосед <tex>x</tex> справа. Вырежем его и вставим перед <tex>p(x) </tex>.
# Если после этого у <tex>p(x)</tex> осталось менее <tex>3</tex> детей, проделаем шаги <tex>1</tex> и <tex>2</tex> и с ними тоже.
# Если после этого <tex> p(x) </tex> стал листом, присвоим <tex> rank(p(x)) := 0 </tex> и удалим <tex> p(x) </tex> из <tex>\mathrm{N_{LIST}}</tex> корня дерева.# Если после этого <tex>\mathrm{N_{LIST}}</tex> корня стал пустым (это значит, что дерево стало сокращенным), присвоим <tex> rank(root) := 1 </tex>
Очевидно, что <tex>\mathrm{Relink} </tex> выполняется за <tex>O(1)</tex>
# Если <tex>size(T) \leqslant 4</tex>, вызываем <tex>\mathrm{ReducedTreeDelete(a)}</tex>
# Иначе:
## <tex>l := \mathrm{FindLeaf(a)} </tex>
## Поменяем элементы в <tex>x</tex> и <tex>l</tex> местами.
## <tex>\mathrm{DeleteLeaf(l)}</tex>
