Изменения

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

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

416 байт добавлено, 21:34, 15 мая 2015
Удаление вершины
2. Если брат текущей вершины был чёрным, то получаем три случая:
* Оба ребёнка у брата чёрные. Красим брата в красный цвет и рассматриваем далее отца вершины. Делаем его черным, это не повлияет на количество чёрных узлов на путях, проходящих через <tex>b</tex>, но добавит один к числу чёрных узлов на путях, проходящих через <tex>x</tex>, восстанавливая тем самым влиянние удаленного чёрного узла. Таким образом, после удаления вершины черная глубина от отца этой вершины до всех листьев в этом поддереве будет одинаковой.
[[Файл:Untitled-4.png|400px|]]
577
правок

Навигация