577
правок
Изменения
→Удаление вершины
Проверим балансировку дерева. Так как при удалении красной вершины свойства дерева не нарушаются, то восстановление балансировки потребуется только при удалении чёрной. Рассмотрим ребёнка удалённой вершины.
1. Если брат этого ребёнка красный, то делаем вращение вокруг ребра между отцом и братом, тогда брат становится родителем отца. Красим его в чёрный, а отца - в красный цвет, сохраняя таким образом черную высоту дерева.
[[Файл:Untitled-3.png|400px|]]
2. Если брат текущей вершины был чёрным, то получаем три случая:
* Оба ребёнка у брата чёрные. Красим брата в красный цвет и рассматриваем далее отца вершины. Таким образом, после удаления вершины черная глубина от отца этой вершины до всех листьев в этом поддереве будет одинаковой.
[[Файл:Untitled-4.png|400px|]]
* Если у брата правый ребёнок чёрный, а левый красный, то перекрашиваем брата и его левого сына и делаем вращение. Все пути по-прежнему содержат одинаковое количество чёрных узлов, но теперь у <tex>x</tex> есть чёрный брат с красным правым потомком, и мы переходим к следующему случаю. Ни <tex>x</tex>, ни его отец не влияют на эту трансформацию.
[[Файл:Untitled-5.png|400px|]]
* Если у брата правый ребёнок красный, то перекрашиваем брата в цвет отца, его ребёнка и отца - в чёрный, делаем вращение . Поддерево по-прежнему имеет тот же цвет корня, поэтому свойство <tex>3</tex> и выходим <tex>4</tex> не нарушаются. Но у <tex>x</tex> теперь появился дополнительный чёрный предок: либо <tex>a</tex> стал чёрным, или он и был чёрным и <tex>b</tex> был добавлен в качестве чёрного дедушки. Таким образом, проходящие через <tex>x</tex> пути проходят через один дополнительный чёрный узел. Выходим из алгоритма.
[[Файл:Untitled-6.png|400px|]]
