*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, with 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. Splay trees are described in dozens of text books and
papers. A few examples are the references below. In my experience,
splay trees are simpler, more space-efficient, more flexible, and
faster than any other balanced tree scheme.

Reference [2] below is the classic reference on splay trees. The paper is available here. The code used in the demo below is adapted from simple top-down splay, at the bottom of page 669 of [2]. It can be downloaded here.

This demo allows you to see how a splay tree evolves. It will first ask you to choose how many nodes you want in your tree. It then constructs a maximally skewed tree with that number of nodes, and draws it. You can then specify a node you wish to splay, after which the resulting tree is drawn, and you can insert and delete nodes. Have fun.

[1] *Data Structures and Their Algorithms*, Lewis and Denenberg,
Harper Collins, 1991, pp 243-251.

[2] "Self-adjusting Binary Search Trees", Sleator and Tarjan,
JACM Volume 32, No 3, July 1985, pp 652-686.

[3] *Data Structure and Algorithm Analysis*, Mark Weiss,
Benjamin Cummins, 1992, pp 119-130.

[4] *Data Structures, Algorithms, and Performance*, Derick Wood,
Addison-Wesley, 1993, pp 367-375

**
D. Sleator
<sleator@cs.cmu.edu>
**
(web interface by
Darrell
Kindred)

sleator@cmu.edu

By Jorge Stolfi