1632
правки
Изменения
м
1. # Если у вершины нет детей, то изменяем указатель на неё у родителя на nil.2. # Если у неё только один ребёнок, то делаем у родителя ссылку на него вместо этой вершины.3. # Если же имеются оба ребёнка, то находим вершину со следующим значением ключа. У такой вершины нет левого ребёнка. Удаляем уже эту вершину описанным во втором пункте способом, скопировав её ключ в изначальную вершину.
31.1 Если брат этого ребёнка красный, то делаем вращение вокруг ребра между отцом и братом, тогда брат становится родителем отца. Красим его в чёрный, а отца - в красный цвет.
32.2 Если брат текущей вершины был чёрным, то получаем три случая:
rollbackEdits.php mass rollback
* '''Удаление вершины.'''При удалении вершины могут возникнуть три случая в зависимости от количества её детей:
Проверим балансировку дерева. Т.к. при удалении красной вершины свойства дерева не нарушаются, то восстановление балансировки потребуется только при удалении чёрной. Рассмотрим ребёнка удалённой вершины.
[[Файл:D3.jpg|390px|]]
* Оба ребёнка у брата чёрные. Красим брата в красный цвет и рассматриваем далее отца вершины.
* [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]
