Изменения

Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.

Процесс включения вершины состоит из двух частей:

# Прохода по пути поиска, пока не убедимся, что ключа в дереве нет.

Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.

Для простоты опишем рекурсивный алгоритм удаления.

Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её и вызовем балансировку всех её предков в порядке от родителя к корню.

В результате указанных действий процедура удаления вызывается не более 3 раз, так как у вершины, удаляемой по 2-му вызову, нет хотя бы одного из поддеревьев. На балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.

Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.