98
правок
Изменения
→Удаление вершины
=== Удаление вершины ===
При удалении вершины могут возникнуть три случая в зависимости от количества её детей:
# Если у вершины нет детей, то изменяем указатель на неё у родителя на <tex>nil</tex>.
# Если у неё только один ребёнок, то делаем у родителя ссылку на него вместо этой вершины.
# Если же имеются оба ребёнка, то находим вершину со следующим значением ключа. У такой вершины нет левого ребёнка. Удаляем уже эту вершину описанным во втором пункте способом, скопировав её ключ в изначальную вершину.
Проверим балансировку дерева. Т.к. Так как при удалении красной вершины свойства дерева не нарушаются, то восстановление балансировки потребуется только при удалении чёрной. Рассмотрим ребёнка удалённой вершины.
1. Если брат этого ребёнка красный, то делаем вращение вокруг ребра между отцом и братом, тогда брат становится родителем отца. Красим его в чёрный, а отца - в красный цвет.
