Изменения

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