Visualization of Splay Tree.
Performed by Vladimir Yanovsky
under supervision of Prof. Alon Itai.
The animation of splay tree that you can see below supports
operations Find, Insert and Delete. Also, you can adjust speed of
animation with button "Speed(0..99)->" ( speed 0 is the fastest,
99 - the slowest) and suspend (resume) animation with button "Suspend"/"Resume".
Splay tree is a kind of balanced trees that
supports operations Find, Insert and Delete in amortized time O(log N)
. This tree is distinct from other kinds of trees with the same complexity
of these operations (AVL - trees, red-black trees etc.) in that it doesn't
maintain any explicit balance condition. Instead, we adjust the tree every
time we do an access or update, using a method that depends only on structure
of the access path. This heuristic, by D.D.Sleator and R.E.Tarjan, is described
in their article
"Self -adjusting binary trees" ,published at Proc. Fifteenth
Annual ACM Symposium on Theory of Computing, 1983
and in Tarjan, "Data Structures and Network Algorithm"
.
Java applet that
we created implements splay tree with operations find, insert and delete
, although thanks to the OOD of the program it's quite easy to change this
app let such that it implements any other kind of balanced trees.
For convenience, the applet
has a button suspend ( resume ) to suspend ( resume ) the animation in
the middle, and a button for changing the speed of the animation
. Values for speed are from 0 - the fastest to 99 - the slowest. Also
we limited the values of the nodes to be from 0 to 99.
Documentation of the program
can be downloaded from here .
The source
code is also available.