c++data-structuresbig-otime-complexitysplay-tree

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

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!

Solution

  • 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.