На этом шаге мы рассмотрим алгоритм выполнения этой операции.
Операция объединения применяется к красно-чёрным деревьям T1 и T2 и элементу x, причём
key[x1] ≤ x, key[x2] ≥ x
Результатом операции является новое красно-чёрное дерево
T=T1 ∪ {x} ∪ T2
Кратко опишем алгоритм реализации операции объединения красно-чёрных деревьев T1 и T2.
Находим чёрные высоты этих деревьев. Пусть, например,
bh[T1] ≥ bh[T2].
Теперь в дереве T1 ищем среди чёрных вершин, имеющих чёрную высоту bh[T2], вершину y с наибольшим ключом.
Пусть Ty - поддерево с корнем y. Объединяем Ty∪{x}∪T2, причём вершина x становится красным родителем деревьев Ty и T2.
Теперь родителем вершины x становится бывший отец вершины y.
Далее, как и при добавлении вершины, необходимо восстановить свойства красно-чёрного дерева (у красной вершины - красный ребёнок). Процедура восстановления точно такая же, как и при выполнении операции "добавление узла".
Сложность алгоритма объединения двух красно-чёрных деревьев такова:
O(log2n).
На следующем шаге мы рассмотрим реализацию красно-чёрных деревьев на языке C.
