Time Complexity of the makeEmpty() of the Top-Down splay tree

Question

In this implementation of a splay tree, the listed time complexity of the makeEmpty() function (which removes all elements) is O(n). It is implemented as follows:

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

Given that both findMax and remove might have time complexity proportional to the height of the tree, why will this take O(n) time in the worst-case?

Thanks!

Answer 1

Three words: The Sequential Access Theorem.

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

Because the above loop repeatedly removes the maximum value, it effectively visits all of the elements in sequence, and so I'm pretty certain the sequential access theorem applies.