Операции вставки и удаления
Гоша: Я понял, как искать уже существующие в дереве элементы.
А если нужно записать новый или удалить старый элемент?
Тимофей: Всё очень похоже на поиск! Начнём с операции вставки.
Мы также спускаемся вниз по дереву, сравнивая каждое значение с тем, которое хотим вставить.
Если значение нового элемента меньше значения в текущем узле, то перейдём к его левому потомку. Если левого потомка нет, создадим его, поместив в него узел со значением нового элемента.
Иначе перейдём к правому потомку. Если правого потомка нет, создадим его, поместив в него узел со значением нового элемента.
Рассмотрим этот алгоритм на примере:
Дано дерево, в которое нужно вставить новый элемент 14. Порядок действий:
- Сравним 14 со значением в корне. 14 больше 10, перейдём к правому потомку.
- Сравним 14 и 15. 14 меньше 15, перейдём к левому потомку.
- Сравним 12 и 14. 12 меньше 14, перейдём к правому потомку. Но у вершины со значением 12 отсутствует потомок. Значит, создадим его и присвоим значение 14.
Получим такое дерево:
Гоша: Здорово! Это так же просто, как искать элементы в дереве. Осталось разобраться с удалением и я стану специалистом по деревьям!
Тимофей: Дендрологом?
Гоша: (Обиженно) Алгоритмическим...
Тимофей: С удалением всё немного сложнее.
Возможны 3 случая:
- Нет потомков, удалим узел родителя.
- Один потомок, переставим узел родителя на потомка.
Гоша: А в чём сложность?
Тимофей: А что, по-твоему, нужно делать, если у вершины два потомка?
Гоша задумался.
- Два потомка, найдём самый левый лист в правом поддереве и заменим им удаляемый.
Гоша: Ну да, это посложнее будет... Но вроде понятно!
Решите задачи C, D: https://contest.yandex.ru/contest/18996/problems/C/.