Сложность по времени для makeEmpty () дерева сплайсинга сверху вниз

В эта реализация Splay Tree, перечисленная временная сложность makeEmpty() функция (которая удаляет все элементы) — это O (n). Это реализовано следующим образом:

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

Учитывая, что оба findMax а также remove может иметь временную сложность, пропорциональную высоте дерева, почему это займет O (n) время в худшем случае?

Спасибо!