Last update 05.18.2002
Delete animations have been enhanced with better visuals for the Split
and Join operations on splay trees.
All "standard" tree operations (Insert,
Find, Delete, Delete All and Traverse) can be accelerated as long as the
tree is not rebalancing. For example, you do not have to wait for the
current Insert animation to be completed in order to insert the next
key. A series of fast Inserts will quickly build a large tree with
pseudo-random keys. Even though the step-by-step rebalancing is
unobserved, the resulting tree will look exactly the same way as if you
were inserting data one item at a time. Clicking on Delete All the
second time will delete the tree immediately. Fast clicking on any
command in SPL mode will allow you to see the result of multiple
splays without waiting.
All AVL and Splay methods used in the
applet have been posted.
Mozilla bug. Some versions of Mozilla do not handle
BorderLayout() controls correctly. I was able to
reproduce the problem on a Redhat 7.2 running Mozilla 0.9.2.1 with JVM
1.3.1. Dr. Monge from Cal State successfully tested the applet with
Mozilla 1.0 RC2. If command buttons do not work in your browser, please
send me a note with your OS,
browser and plugin info.
More snippets of the source code posted.
functionality has been implemented.
The Thinker does a much better job now.
After the insertion or deletion process is completed, he will pause
the animation to show the nodes which will be rebalanced, rotated
and/or repainted. If two rotations are pending, the numbers on the top
of the flashing arrows will indicate the rotation
order. Decreasing the animation speed will make the "thinking"
pause longer. If you get impatient, click anywhere on the panel to
proceed to the next iteration.
and (R)otate are "manual" commands. Using them in AVL or
Red-Black mode will almost always break the rules of the current
algorithm. The result is a good olde BST.
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
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
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
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.
New control buttons alleviate FlowLayout()'s problems.
"Balance factors" for an unbalanced tree now show the correct
difference in heights.
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
"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.