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

Problem Detail: 

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?

Asked By : Petr Pudlák

Answered By : jbapple

It sounds like you're looking for a binary search tree with the working-set property; this is a good bit weaker than dynamic optimality. In fact, there are no known binary search trees with dynamic optimality, according to Iacono's "In pursuit of the dynamic optimality conjecture" from June 2013.

But, if you're looking for the simpler working-set property, you're in luck! The working-set property is that the time to access an item $x$ is proportional to the log of the number of items accessed since $x$ was last accessed.

There are a variety of structures with the working-set property. There is even one that is a binary tree, meets both the logarithmic worst-case bound and the working-set property in the worst-case, not just the amortized case: Bose et al's "Layered Working-Set Trees".

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11772