Изменения
Нет описания правки
* <tex>size(A)</tex> {{---}} размер множества <tex>A</tex> (количество элементов в нем).
* <tex>root(T_A)</tex> {{---}} корень дерева <tex>T_A</tex>
* <tex>h(v)</tex> {{---}} высота вершины <tex>v</tex>: если <tex>v</tex> является листом, то <tex>h(v) = 0</tex>, иначе <tex>h(v) = \max \{ h(w) \: | \: w - \mathrm{ child \: of } \: v \} + 1</tex>.
* <tex>p(v)</tex> {{---}} родитель вершины <tex>v</tex>. Если <tex>v</tex> {{---}} корень, то считаем, что <tex>p(v) = v</tex>
* <tex>rank(v)</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>
