Сложность по времени makeEmpty() из дерева спуска сверху вниз

Question

В этой реализации Splay Tree указана временная сложность makeEmpty() функция (которая удаляет все элементы) - это O(n). Это реализовано следующим образом:

 while( !isEmpty( ) )
 {
     findMax( );        // Splay max item to root
     remove( root->element );
 }

Учитывая, что оба findMax а также remove может иметь временную сложность, пропорциональную высоте дерева, почему это займет O (n) время в худшем случае?

Спасибо!

Answer 1

Три слова: теорема о последовательном доступе.

http://www.wseas.us/e-library/conferences/cairns2001/papers/632.pdf

Поскольку вышеприведенный цикл многократно удаляет максимальное значение, он эффективно посещает все элементы в последовательности, и поэтому я почти уверен, что применима теорема о последовательном доступе.