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