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):

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.


Morgan McGuire <matrix@brown.edu> for CS250