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