c++ - 自顶向下展开树的 makeEmpty() 的时间复杂度

Question

在展开树的这个实现中，列出的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

因为上述循环反复删除最大值，它有效地按顺序访问所有元素，所以我很确定顺序访问定理适用。