Изменения

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