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>bhhb[T_{1}] \geqslant bhhb[T_{2}]</tex>. Тогда в дереве <tex>T_{1}</tex> ищем среди чёрных вершин, имеющих чёрную высоту <tex>bhhb[T_{2}]</tex>, вершину y с наибольшим ключом. Пусть <tex>T_{y}</tex> — поддерево с корнем y. Объединяем это дерево с <tex>T_{2}</tex> в одно с красным корнем x. Теперь родителем вершины x становится бывший отец вершины y.
Осталось восстановить свойства красно-черного дерева, чтобы у красной вершины не было красных детей. Делается аналогично алгоритму добавления вершины.
