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?

4 Answers

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".

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.

I am not quite sure what you want to achieve with your data structure. Indeed, Splay-trees are a cool data structure. They are known to have the static optimality property. This means if you know the distribution of you search queries in advance and you built the optimal binary search tree for this distribution, then a splay-tree (without knowing the distribution) will perform asymptotically as good as the binary search tree. Of course, you may say this is cheating since the binary search tree cannot readjust, but it is still a very impressive property. People also expect, that splay trees are as good as any self-adjusting data-structure (known as dynamic optimally conjecture) - but this is one of the most prominent open question in the area of data structures.

Back to your question, since splay-trees are statically optimal, you have to sacrifice something. This means that if you access an element with low probability you might have to perform a more expansive operation. However, this is justified since the element is only rarely requested - and every statical optimal data structure will show this behavior. Of course you can always us a balanced binary search tree, but then you lose static optimality.

How about this procedure (works only for static BSTs).

With every node, you maintain a pointer to another node, which exists in the sub-tree rooted at that node. Along with the pointer, you also maintain the level number of the node being pointed to (along with your level number). The root is at level 0, and levels increase as you go down the tree. Initially, the pointer at a node points back to the node itself. The invariant is that you will only ever point to a node at a lower or equal level than the level number of the node.

When you search for an element in the tree, it will either:

1. Be found at its location in the BST, or
2. Be found along a path to its location because some node along the node to root path has a pointer to this node, or
3. Not be found at all.


In either case, we first make a forward pass to find the node, and if it is found, we bubble down the pointed nodes along the root to node path for the found node. If the node was found as a result of case-2, we only bubble down till the node that was pointing to the target node (this allows us to be quick for recently accessed nodes).

If a node is going to be bubbled down to a level greater than the node itself, we delete the node from the mapping set.

If a node that has no mapping is accessed, we create a new mapping for that node, and set it to replace whatever mapping existed at the node, and bubble it up progressively.

When a node is accessed, it is bubbled up all the way to the top.