577
правок
Изменения
→Объединение красно-чёрных деревьев
Найдём чёрные высоты деревьев. Предположим также, что <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>hb[T_{1}] \leqslant hb[T_{2}]</tex>, то слияние происходит аналогично, только теперь мы ищем в дереве <tex>T_{2}</tex> среди чёрных вершин, имеющих чёрную высоту <tex>hb[T_{1}]</tex>, вершину <tex>y</tex> с наименьшим ключом.
Так как общее время выполнения каждой из операций порядка высоты дерева ,то все они выполняются за <tex>O(\log{n})</tex>.
