Splay Tree Demonstration

The two trees represent the same ordered set. The tree on the left is a binary search tree with no special balancing. The tree on the right is a splay tree, which maintains balance by performing a splay operation before or after every other operation. The splay operation is implemented as three separate cases. Pressing the 1, 2, or 3 button will produce a tree for which each case operates. Pressing the ? button will produce a random tree.

Actions you can perform with the mouse (select using the dropdown box):

Access: "get" the selected node in both trees. In a binary tree, this does nothing. In a splay tree, it may rebalance the tree.
Insert: Insert a new random node (if there are fewer than 20) in both trees.
Delete: Delete the specified node in both trees.
Rotate: Rotate about the selected node's parent in the tree that was clicked on.

By accessing, inserting, and deleting nodes you can see the difference in balance between a binary and splay tree. Rotate operations allow you to manually walk through the operations the splay tree performs to maintain balance.

Source Code

SplayDemo.java Splay tree logic and boilerplate to launch the demo as an applet or standalone Java program.

BinaryTree.java A generic binary tree. The splay tree is built by extending this.

Node.java Binary tree node interface.

SplayTree.java Extension of the binary tree to maintain balance.

TreeDisplay.java A JComponent that renders binary trees.

References

D.D. Sleator and R. E. Tarjan, Self-adjusting binary trees, Proc. Fifteenth Annual ACM Symposium on Theory of Computing, 1983, pp. 235-245.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA, 1989

Morgan McGuire <matrix@brown.edu> for CS250

SplayDemo.java	Splay tree logic and boilerplate to launch the demo as an applet or standalone Java program.
BinaryTree.java	A generic binary tree. The splay tree is built by extending this.
Node.java	Binary tree node interface.
SplayTree.java	Extension of the binary tree to maintain balance.
TreeDisplay.java	A JComponent that renders binary trees.