Per the Sequential Access Theorem we can access every node of a splay tree in $O(n)$ time, when accessing the nodes in a specific order.

Given a link/cut tree, is it possible to access all of its nodes faster than the naive $O(n \log n)$ amortized time in the worst-case?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.