403
правки
Изменения
→remove
remove(T.aux, high(x)); // то удаляем информацию, что это поддерево не пусто
</pre>
Оценка времени работы операции <tex>remove</tex> такая же, как и у операции <tex>insert</tex>. На каждом уровне дерева мы совершаем <tex>O(1)</tex> операций и переходим к удалению элементов максимум в двух деревьях(в одном поддереве и во вспомогательном дереве), чьи высоты на один меньше текущей. Но если мы производим операцию удаления из вспомогательного дерева, значит удаление из поддерева потребовало <tex>O(1)</tex> операций, так как оно содержало всего один элемент. В итоге, количество операций пропорционально высоте дерева, то есть <tex>O(\log k)</tex>.
== next и prev ==
