このスプレー ツリーの実装では、リストされているmakeEmpty()関数 (すべての要素を削除する) の時間計算量は O(n) です。次のように実装されます。
while( !isEmpty( ) )
{
findMax( ); // Splay max item to root
remove( root->element );
}
と の両方が木の高さに比例する時間の複雑さを持っている可能性があることを考えるとfindMax、remove最悪の場合、なぜこれに O(n) の時間がかかるのでしょうか?
ありがとう！