A demonstration of top-down splaying

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.

Start with how many nodes?

[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

A Self-Adjusting Search Tree
By Jorge Stolfi