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