105
правок
Изменения
м
# 1. "Дядя" этого узла тоже красный. Тогда просто перекрашиваем "отца" и "дядю" в чёрный цвет, а "деда" - в красный. Проверяем, не нарушает ли он теперь балансировку. Если в результате этих перекрашиваний мы дойдём до корня, то в нём в любом случае ставим чёрный цвет. # [[Файл:D1.jpg|200px|]] 2. "Дядя" чёрный. Если выполнить только перекрашивание, то может нарушиться постоянство чёрной высоты дерева по всем ветвям. Поэтому выполняем поворот. Если добавляемый узел был правым потомком, то необходимо сначала выполнить левое вращение, которое сделает его левым потомком. [[Файл:D2.jpg|275px|]]
# 1. Если брат этого ребёнка красный, то делаем вращение вокруг ребра между отцом и братом, тогда брат становится родителем отца. Красим его в чёрный, а отца - в красный цвет.# [[Файл:D3.jpg|390px|]] 2. Если брат текущей вершины был чёрным, то получаем три случая:## * Оба ребёнка у брата чёрные. Красим брата в красный цвет и рассматриваем далее отца вершины.## [[Файл:D4.jpg|390px|]] * Если у брата правый ребёнокчёрный, такой же, как и сам брат(т.е. правый или а левый) чёрныйкрасный, то красим перекрашиваем брата в красный цвет и его левого сына и делаем вращение.## [[Файл:D5.jpg|390px|]] * В остальных случаях же у брата правый ребёнок красный, то перекрашиваем брата в цвет отца, а его ребёнка и отца - в чёрный, делаем вращение и выходим из алгоритма. [[Файл:D6.jpg|390px|]]
Дмитрий Мурзин переименовал страницу Красно-чёрное дерево в Красно-чёрное дерево (удалить): Статью нужно удалить, так как существует…
==Операции==
* '''Вставка элемента.''' Каждый элемент вставляется вместо листа, поэтому для выбора места вставки идём от корня до тех пор, пока указатель на следующего сына не станет nil(т.е. этот сын - лист). Вставляем вместо него новый элемент с nil-потомками и красным цветом. Теперь проверяем балансировку. Если отец нового элемента красный, то достаточно рассмотреть только два случая:
* '''Удаление вершины.'''При удалении вершины могут возникнуть три случая в зависимости от количества её детей:
# Если же имеются оба ребёнка, то находим вершину со следующим значением ключа. У такой вершины нет левого ребёнка. Удаляем уже эту вершину описанным во втором пункте способом, скопировав её ключ в изначальную вершину.
Проверим балансировку дерева. Т.к. при удалении красной вершины свойства дерева не нарушаются, то восстановление балансировки потребуется только при удалении чёрной. Рассмотрим ребёнка удалённой вершины.
Продолжаем тот же алгоритм, пока текущая вершина чёрная и мы не дошли до корня дерева. При удалении выполняется не более трёх вращений.
* [http://ru.wikipedia.org/wiki/%CA%F0%E0%F1%ED%EE-%F7%B8%F0%ED%EE%E5_%E4%E5%F0%E5%E2%EE Википедия.]
* [http://algolist.manual.ru/ds/rbtree.php]
* [http://lectures.stargeo.ru/alg/algorithms.htm#_Toc241931998]
