Изменения

Перейти к: навигация, поиск

Красно-черное дерево

28 байт добавлено, 19:34, 20 июня 2012
Удаление вершины
1. Если брат этого ребёнка красный, то делаем вращение вокруг ребра между отцом и братом, тогда брат становится родителем отца. Красим его в чёрный, а отца - в красный цвет.
[[Файл:D_3Untitled-3.png|390px400px|]]
2. Если брат текущей вершины был чёрным, то получаем три случая:
* Оба ребёнка у брата чёрные. Красим брата в красный цвет и рассматриваем далее отца вершины.
[[Файл:D_4Untitled-4.png|390px400px|]]
* Если у брата правый ребёнок чёрный, а левый красный, то перекрашиваем брата и его левого сына и делаем вращение.
[[Файл:D_5Untitled-5.png|390px400px|]]
* Если у брата правый ребёнок красный, то перекрашиваем брата в цвет отца, его ребёнка и отца - в чёрный, делаем вращение и выходим из алгоритма.
[[Файл:D_6Untitled-6.png|390px400px|]]
Продолжаем тот же алгоритм, пока текущая вершина чёрная и мы не дошли до корня дерева.
98
правок

Навигация