== Операции ==
=== Добавление вершины ===
Процесс включения вершины состоит из двух частей:# Прохода Пусть нам надо добавить ключ <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>. Если в результате пересчёта баланса, баланс вершины стал равен 2 или -2, то запускаем процедуру балансировки, которая делает одно из четырёх вращений.
Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.
