Splay Trees

The component code for the Tree<> class template implements splay trees, as defined and analyzed in [5], and is based on sources by Daniel Sleator, who released them to the public domain. The original, top-down-splay.c, can also be obtained drilling down from Daniel Sleator's home page. He explains in comments from that source file as follows:

``Splay trees'', or ``self-adjusting search trees'' are a simple and efficient data structure for storing an ordered set. The data structure consists of a binary tree, without parent pointers, and no additional fields. It allows searching, insertion, deletion, deletemin, deletemax, splitting, joining, and many other operations, all with amortized logarithmic performance. Since the trees adapt to the sequence of requests, their performance on real access patterns is typically even better.

The splay algorithm in the code by Sleator is adapted from simple top-down splay, as given at the bottom of p. 669 in [5]. Sleator goes on to explain his adaptation:

The chief modification here is that the splay operation works even if the item being splayed is not in the tree, and even if the tree root of the tree is nil. So the line:

\begin{displaymath}{\tt t = splay(i, t);}\end{displaymath}

causes it to search for item with key i in the tree rooted at t. If it's there, it is splayed to the root. If it isn't there, then the node put at the root is the last one before nil that would have been reached in a normal binary search for i. (It's a neighbor of i in the tree.) This allows many other operations to be easily implemented ...

See Figures C.6 and C.7.

Figure C.6: Set maps

Figure C.7: Map inheritance

Bill Pippin 2010-01-14