自上而下的splay樹的makeEmpty（）的時間複雜度

Question

在this implementation of a 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

由於上述循環中重複刪除的最大值，它有效地訪問所有元素的順序，所以我敢肯定順序存取定理適用。