Изменения
→Добавление вершины
Процесс включения вершины состоит из двух частей:
# Прохода по пути поиска, пока не убедимся, что ключа в дереве нет.
# "Отступления" назад по пути поиска, вплоть до корня и пересчета высот в каждой вершине на обратном пути. При необходимости осуществляется балансировка. Если пришли из левого поддерева <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу.
Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.
