Last update 05.18.2002
Insert and 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.
05.13.2002
More snippets of the source code
posted.
05.10.2002
Red-black 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.
Reminder: (S)play
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.
05.02.2002
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.
|