Изменения

1. "Дядя" этого узла тоже красный. Тогда просто перекрашиваем "отца" и "дядю" в чёрный цвет, а "деда" - в красный. Проверяем, не нарушает ли он теперь балансировку. Если в результате этих перекрашиваний мы дойдём до корня, то в нём в любом случае ставим чёрный цвет.

2. "Дядя" чёрный. Если выполнить только перекрашивание, то может нарушиться постоянство чёрной высоты дерева по всем ветвям. Поэтому выполняем поворот. Если добавляемый узел был правым потомком, то необходимо сначала выполнить левое вращение, которое сделает его левым потомком.

* '''Удаление вершины.'''При удалении вершины могут возникнуть три случая в зависимости от количества её детей:

1. Если брат этого ребёнка красный, то делаем вращение вокруг ребра между отцом и братом, тогда брат становится родителем отца. Красим его в чёрный, а отца - в красный цвет.

2. Если брат текущей вершины был чёрным, то получаем три случая:

* Оба ребёнка у брата чёрные. Красим брата в красный цвет и рассматриваем далее отца вершины.

* Если у брата правый ребёнок чёрный,а левый красный, то перекрашиваем брата и его левого сына и делаем вращение.

* В же у брата правый ребёнок красный, то перекрашиваем брата в цвет отца, его ребёнка и отца - в чёрный, делаем вращение и выходим из алгоритма.

Продолжаем тот же алгоритм, пока текущая вершина чёрная и мы не дошли до корня дерева. При удалении выполняется не более трёх вращений.