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