Doubt on Performance Comparison of Splay Trees

Question

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?

Answer 1

There have been various real world applications that use splay tree. One of the most prominent examples is the gcc compiler that applies splay tree. There are many other examples. In fact, ACM Kanellakis Theory and Practice Award 1999 was given to Daniel Sleator and Robert Tarjan for their seminal work on the splay tree data structure.

It looks like you have some misconception on the splay tree about its worst performance.

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 in terms of the number of tree rotations is $O(1)$. The proven constant factor, $4.5$, is pretty small.

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 about $\log_2(n)$ search operations initially, 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.