49
правок
Изменения
Нет описания правки
'''Объединение красно-чёрных деревьев.''' Объединение двух красно-чёрных деревьев <tex>T_{1}</tex> и <tex>T_{2}</tex> по элементу x выполняется, когда <tex>key[T_{1}] \leqslant x</tex> и <tex>x \leqslant key[T_{2}]</tex>.
Найдём чёрные высоты деревьев. Предположим также, что <tex>bh[T_{1}] \geqslant bh[T_{2}]</tex>. Тогда в дереве <tex>T_{1}</tex> ищем среди чёрных вершин, имеющих чёрную высоту <tex>bh[T_{2}]</tex>, вершину y с наибольшим ключом. Пусть <tex>T_{y}</tex> — поддерево с корнем y. Объединяем это дерево с <tex>T_{2}</tex> в одно с красным корнем x. Теперь родителем вершины x становится бывший отец вершины y. Теперь надо Осталось восстановить свойства красно-черного дерева, чтобы у красной вершины не было красных детей, . Делается аналогично алгоритму добавления вершины. ==Ссылки.== * [http://rain.ifmo.ru/cat/view.php/vis/trees/red-black-2002 Визуализатор.]* [http://ru.wikipedia.org/wiki/%CA%F0%E0%F1%ED%EE-%F7%B8%F0%ED%EE%E5_%E4%E5%F0%E5%E2%EE Википедия.]* [http://algolist.manual.ru/ds/rbtree.php]
