Изменения

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