Где применяется
1. Задача
В уроке про дерево поиска вставка была простой: спускаешься вниз и кладёшь новое значение на пустое место. С удалением сложнее. Если убрать значение из середины дерева, на его месте остаётся дыра, а под ней висят два целых поддерева (поддерево это узел со всеми, кто под ним). Какой узел поставить в дыру, сразу не видно. Сделаешь небрежно, и одно поддерево потеряется: на него больше не будет ссылки. Или нарушится правило «слева меньше, справа больше», а на нём держится каждый следующий поиск.
Нужно уметь убрать любое значение так, чтобы дерево осталось правильным деревом поиска (BST). Каждое оставшееся значение должно стоять там, где его будет искать поиск.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи, где из дерева нужно удалить узлы и не повредить остальное. Спускайся рекурсией, записывай вернувшееся поддерево обратно в root.left или root.right, а узел с двумя детьми заменяй его преемником, следующим значением по порядку.
Задача урока под тем же именем.
Узел меньше low заменяется своей обрезанной правой частью, а узел больше high своей обрезанной левой.
Та же запись вернувшегося ребёнка обратно, а дети каждого удалённого узла становятся новыми корнями.