Bottom-up splaying is implemented. Click on SPL button to
switch to automatic splaying mode. Click on AVL button to
activate the AVL mode. Red dot in the upper right corner of
the icon indicates the active state. When both SPL and
AVL modes are off, the tree will behave as a standard
garden-variety BST.
Alternatively, use S(play) command to splay the selected
node to the root. S(play) and R(otate) are
"manual" operations performing one individual isolated action
as opposed to multiple automatic rebalancing or splaying
rotations. Using S or R will turn the AVL mode
off, since a "forced" rotation interferes with the AVL
rules.
NIST's Dictionary of
Algorithms and Data Structures defines left (right) rotations as
".. pushing a node N down and to the left(right)..."
Both manual and automatic AVL rotations presented here conform to
this definition - the selected node will move down and to the
side. At the same time, splaying is often described as a series of
rotations up and around node's parent
(grandparent). In order to keep the terminology consistent,
within the context of this application the splayed node is never
"rotated up". In fact, the node itself is not rotated at all.
Instead, its parent and/or grandparent are rotated down and
away, effectively moving the node to the root. In "thinking" mode,
the flashing red parent or grandparent is the one to be rotated
first, and the blue node is the second.
Splay trees are a lot less compact (visually) than AVL
trees. The panel is now 100 pixels wider to accommodate the
unruly branches. Changing the shape and using the size tool
can also help to keep the nodes inside the window.
The speed tool has been modified. Up and Down arrows switch
between the fastest and slowest animation modes.
R(otate) tool now performs rotations to both sides. Click
on the left side of the icon, and the selected node will rotate to
the left. Clicking on the right side will rotate the selected
node to the... right.
Balance factors can be displayed only in AVL mode.
New animations: swapping data before deletion and discarding
deleted nodes.
Events append new information to the message line, instead of
replacing it. The resulting record reflects the sequence of events
from the beginning of the operation to its end.
Due to numerous requests for code, I will start posting the
snippets on a separate
page within the next few days. The intended purpose of
this project is to help students understand the operations of a
BST. The resulting code is inevitably (and by design)
inefficient.
Bugs: I am making every possible effort to make this application
compatible with older versions of JVM. All code is JDK 1.1 and
I am intentionally using an ancient version of Java compiler to keep
things simple. Nevertheless, the application in the present
state is reportedly not-compatible with Mozilla. Your feedback is
very much appreciated. If anyone has suggestions on a good
compiler for Linux, FreeBSD, BSDI or Windows98/NT/XP, please send me a note.
04.24.2002
New control buttons alleviate FlowLayout()'s problems.
"Balance factors" for an unbalanced tree now show the correct
difference in heights.
04.18.2002
Single and double rotations rebalancing the tree after "Insert"
and "Delete" are now animated.
Decreasing the speed and switching to "Ordered" view mode can
help to observe the rotations.
Use "Balance on" button to make the balance factors visible and
watch the pinball going up after an insertion or deletion.
Pick nodes with the mouse and rotate them manually. See if you
can you make an unbalanced tree to comply with the AVL rules.
"Think on" option will force the pinball to spend more time at
each node "deciding" where to go next.
On-screen comments provide additional information for operations
and command buttons.
Retraction of the leaves, bouncing and pinball collisions have
been modified.