Изменения
→Удаление вершины
=== Удаление вершины ===
Для простоты опишем рекурсивный алгоритм удаления.
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её и вызовем балансировку всех её предков в порядке от родителя к корню. Если Иначе найдём самую близкую по значению вершину и переместим её на место удаляемой вершины, при этом вызвав процедуру её удаления. В процедуре удаления будем идти от переданной вершины к корню и, если пришли из левого поддерева <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу.Иначе найдём самую близкую по значению вершину и переместим её на место удаляемой вершиныГде требуется балансировка, при этом вызвав запускаем процедуру её удалениябалансировки.
В результате указанных действий процедура удаления вызывается не более 3 раз, так как у вершины, удаляемой по 2-му вызову, нет хотя бы одного из поддеревьев. На балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.
