98
правок
Изменения
→Объединение красно-чёрных деревьев
=== Объединение красно-чёрных деревьев ===
Объединение двух красно-чёрных деревьев <tex>T_{1}</tex> и <tex>T_{2}</tex> по элементу x выполняется, когда <tex>key[T_{1}] \leqslant x</tex> и <tex>x \leqslant key[T_{2}]</tex>.
Найдём чёрные высоты деревьев. Предположим также, что <tex>hb[T_{1}] \geqslant hb[T_{2}]</tex>. Тогда в дереве <tex>T_{1}</tex> ищем среди чёрных вершин, имеющих чёрную высоту <tex>hb[T_{2}]</tex>, вершину <tex>y </tex> с наибольшим ключом. Пусть <tex>T_{y}</tex> — поддерево с корнем <tex>y</tex>. Объединяем это дерево с <tex>T_{2}</tex> в одно с красным корнем <tex>x</tex>. Теперь родителем вершины <tex>x </tex> становится бывший отец вершины <tex>y</tex>.
Осталось восстановить свойства красно-черного дерева, чтобы у красной вершины не было красных детей. Делается аналогично алгоритму добавления вершины.
Рассмотрим пример объединения два красно-чёрных дерева и вершины <tex>(35)</tex>:
