98
правок
Изменения
Нет описания правки
Так как общее время выполнения каждой из операций порядка высоты дерева ,то все они выполняются за <tex>O(\log{n})</tex>.
Рассмотрим пример объединения двух красно-чёрных деревьев и вершины <tex>(35)</tex>:
[[Файл:Merge1.jpg|550px|]]
Узнаём чёрную высоту левого и правого дерева. Чёрная высота левого и правого деревьев равна <tex>2</tex> и <tex>1</tex> соответственно.
Так как чёрная высота левого дерева больше, то ищем в левом дереве чёрную вершину, имеющую чёрную высоту правого дерева, с наибольшим ключом.
Чёрная высота вершины <tex>(8)</tex> левого дерева равна высоте правого дерева и ключ является наибольшим. Поэтому вершина <tex>(8)</tex> становится левым сыном вершины <tex>(35)</tex>, а правое дерево будет правым сыном. Вершина <tex>(35)</tex> станет правым сыном вершины <tex>(0)</tex>:
[[Файл:Merge2.jpg|400px|]]
