49
правок
Изменения
Нет описания правки
Отсюда также получаем, что высота дерева не более <tex>2log_2 N+1</tex>, где N - число элементов дерева, т.е. <tex>O(log N)</tex>
==Операции==
* '''Вставка элемента.''' Каждый элемент вставляется вместо листа, поэтому для выбора места вставки идём от корня до тех пор, пока указатель на следующего сына не станет nil(т.е. этот сын - лист). Вставляем вместо него новый элемент с nil-потомками и красным цветом. Теперь проверяем балансировку. Если отец нового элемента красный, то достаточно рассмотреть только два случая:
# "Дядя" этого узла тоже красный. Тогда просто перекрашиваем "отца" и "дядю" в чёрный цвет, а "деда" - в красный. Проверяем, не нарушает ли он теперь балансировку. Если в результате этих перекрашиваний мы дойдём до корня, то в нём в любом случае ставим чёрный цвет.
# "Дядя" чёрный. Если выполнить только перекрашивание, то может нарушиться постоянство чёрной высоты дерева по всем ветвям. Поэтому выполняем поворот. Если добавляемый узел был правым потомком, то необходимо сначала выполнить левое вращение, которое сделает его левым потомком.
* '''Удаление вершины.'''При удалении вершины могут возникнуть три случая в зависимости от количества её детей:
# Если у вершины нет детей, то изменяем указатель на неё у родителя на nil.
# Если у неё только один ребёнок, то делаем у родителя ссылку на него вместо этой вершины.
Продолжаем тот же алгоритм, пока текущая вершина чёрная и мы не дошли до корня дерева. При удалении выполняется не более трёх вращений.
* '''Объединение красно-чёрных деревьев.''' Объединение двух красно-чёрных деревьев <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.
Осталось восстановить свойства красно-черного дерева, чтобы у красной вершины не было красных детей. Делается аналогично алгоритму добавления вершины.
Т.к. общее время выполнения каждой из операций порядка высоты дерева ,то все они выполняются за <tex>O(\log{n})</tex>.
==Ссылки.==
