# Doubt on Performance Comparison of Splay Trees

I'm trying to understand splay tree performance compared to a standard balanced tree like AVL/red-black. In practice, I am pretty skeptical of the amortized bounds Tarjan and Sleator proves in their paper. Maybe because I am not that smart to actually understand these proofs, but I am still curious of one certain pathological case.

Suppose that we have a splay tree with $$n$$ nodes. These nodes are ordered from $$1$$-$$n$$ according to their height/level in the tree. You then access them starting from the highest level to the lowest level nodes ($$n$$ to $$1$$). In this way, it would guarantee the worst case access sequence of the tree. My intuition says that this case would be significantly slower than an AVL tree. It's probably proven somewhere that even in this case, the asymptotic access time is the same. However, I am also accounting for constant factors for a direct comparison of raw performance. How practical are they in real world application?

• How practical? You explained yourself how to check it. – Yuval Filmus May 27 at 19:24

Take the example you have mentioned, where we access a splay tree of $$n$$ nodes that labelled from $$1$$ to $$n$$ according to their level in the tree, starting from $$n$$ down to $$1$$. Your intuition indicates "this case would be significantly slower than an AVL tree." Indeed, the height of the tree before and after those search operations is $$n-1$$. That is, the tree is the most unbalanced tree before and after that search operations.
However, contrary to your intuition, it turns out that case is a showcase of the stellar performance of a splay tree. Although an $$O(n)$$-time operation is needed to access the first few nodes, the average cost for all search operations is smaller than a constant that is not dependent on $$n$$ (assuming the usual RAM arithmetic computation model)! In fact, we have the sequential access theorem for splay tree, which says that if you look up all $$n$$ elements in a splay tree in ascending or descending order, the amortized cost of each lookup is $$O(1)$$. You cannot achieve such amazing performance with any kind of search tree that keeps intact during a search, including an AVL tree. To experience that phenomenon, you can go to splay tree visualization. Enter $$32$$. Hit "insert". Enter $$31$$. Hit "insert". And so on until you have inserted $$1$$. Then find $$32, 31, \cdots, 1$$. Observe what is happening.
Once you have that experience, it is not hard to understand that extraordinary phenomenon. After initial about $$\log_2(n)$$ search operations, the tree becomes almost completely balanced, that is, its height is about $$\log_2(n)$$. Since that point of time on, accessing each next node will take at most $$\log_2(n)$$ time. Furthermore, whenever a node that is somewhat far from the root is accessed, the nodes along its path to the root are brought up significantly closer to the root. In the end, the vast majority of the nodes will be found within some constant time.