Is there a binary tree structure with fast access to recently accessed elements and worst $O \left( \log n \right )$ complexity?

The idea of splay trees is very nice as they move frequently accessed elements to the top, which can gain a considerable speed up in many applications. The drawback is that in the worst case an operation can have $O(n)$ complexity.
(Although amortized bounds are $O(n\log n)$ if we perform at least $n$ operations.)

Is there a self-adjusting search tree structure that has both? Favoring recently accessed elements and with worst $O(\log n)$ complexity for a single operation?

The amortized cost of entering an element to splay tree is $O(\log n)$ so in the worst case $n$ operations would do $O(n\log n)$ steps. There is a conjecture about splay tree that says that it is as optimal as a binary search tree up to constant factor called Dynamic optimality conjecture.

Tango trees are online, self adjacent trees that achive $O(\log \log n)$ competitive ratio compared to offline optimal binary search tree which is the best known.

StackExchange Computer Science Q#11772, answer score: 5