Homepage eng | kor

Splay Tree - Demo Applet

---

The basic idea of the splay tree is that after a node is accessed, it is pushed to to the root by a series of rotations similar to AVL tree rotations. Notice that if a node is deep, there are many nodes on the path that are also relatively deep, and by restructuring we can make future accesses faster on all these nodes. Thus, if the node is unduly deep, then we want this restructuring to have the side effect of balancing the tree.

This applet demonstrates Splay Tree operations. However, it shows only the final result of self-restructuring (i.e. the most-recently-accessed data is promoted the root of the tree), not the sequence of rotations. In the history pane, however, it shows some detailed statistics of the performed rotations. So, it's better to draw your own picture and compare it with the applet demo.

Notes on source codes: The implementation is not dedicated to Splay Tree data structure itself. Instead, the splay tree class is embedded in the java applet class with some other optional methods for demonstration purpose. Also, note that the source codes is not efficiently written in terms of complexity of running time, and minor bugs are observed in DELETE method.   view source code (to download, just right-click on the link and save it as .java file)

Command Syntax :

RESET,  DELAY number,  INSERT number,  FIND number,  DELETE number,  FIND-MIN,  FIND-MAX,  STAT-MODE

NOTE : All commands should be capitalized, and some commands involved numbers should be followed by a single space and then a integer number.
　

Execute the following commands to test INSERT, FIND, DELETE, FIND-MIN, and FIND-MAX operation of the splay tree.
(COPY and PASTE the whole series of commands into the Text Area. Then, click on the Execute button)

DELAY 200 ; pause 200 ms between updates. INSERT 2 INSERT 4 INSERT 3 INSERT 6 INSERT 5 INSERT 8 INSERT 7 INSERT 10 INSERT 9 INSERT 12 INSERT 11 INSERT 14 INSERT 13 INSERT 15 INSERT 16 INSERT 17 INSERT 18 INSERT 19 INSERT 20 DELAY 2000 ; pause 2000 ms between updates INSERT 99 ; insert 99 and splay at the node, as a result 99 becomes the new root INSERT 1 INSERT 2 ; 2 is already in the tree, but still splay at the node FIND 30 ; 30 is NOT in the splay tree FIND 3 ; 3 is in the splay tree, after splaying, 3 is the new root FIND 17 DELETE 13 ; after delete, splay at the parent of the deleted node DELETE 20 DELETE 8 FIND-MIN ; find the min in the tree, then splay at the node FIND-MAX ; find the max in the tree, then splay at the node

Execute the following commands to test STAT-MODE, which shows interesting statistics of splaying in the history pane.

NOTE: Decreased Avg. depth is the depth of OLD FAMILY nodes of a splayed node - parent, sibling, and left, right child, NOT the whole tree. In that way, we can see how the data near the most-recently-accessed data are improved for a faster access in future by the side effect of splaying.

RESET DELAY 100 INSERT 2 INSERT 4 INSERT 3 INSERT 6 INSERT 5 INSERT 8 INSERT 7 INSERT 10 INSERT 9 INSERT 12 INSERT 11 INSERT 14 INSERT 13 INSERT 15 DELAY 3000 STAT-MODE ; shows additional statistics in the status bar and history pane FIND 4 ; see the decreased depth of the old family of the splayed node. Very improved! FIND 6 ; INSERT 1 FIND 10

---

by Hyung-Joon Kim, CSE373, University of Washington

   This page is XHTML and CSS validated and safe for any browser.
Copyright © 2006 blue mojo [hyung-joon Kim]. All rights reserved.