Изменения

Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её и вызовем балансировку всех её предков в порядке от родителя к корню. Иначе , иначе найдём самую близкую по значению вершину и <tex>a</tex>, переместим её на место удаляемой вершины, при этом вызвав процедуру её удаленияи удалим вершину <tex>a</tex>. В процедуре удаления От удалённой вершины будем идти от переданной вершины подниматься вверх к корню и, если пришли пересчитывать баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева , то <tex>diff[i]</tex> увеличивается уменьшается на единицу, если из правого, то уменьшается увеличивается на единицу. Где требуется балансировкаПодъём останавливается, когда приходим в вершину, баланс которой равен нулю, то есть <tex>diff[i] = 0</tex>. Если в результате пересчёта баланса, баланс вершины стал равен 2 или -2, то запускаем процедуру балансировки, которая делает одно из четырёх вращений.

В результате указанных действий процедура удаления вызывается не более 3 раз, так как у на удаление вершины, удаляемой по 2-му вызову, нет хотя бы одного из поддеревьев. На и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.