Home

The inset below illustrates the behaviour of binary search trees.
Donald Knuth. "The Art of Computer Programming": Searching and Sorting Algorithms.
G.M. Adelson-Velskii and E.M. Landis. "An algorithm for the organization of information", 1962
D. Sleator and R. Tarjan. "Self-adjusting Binary Search Trees", 1985
"Symmetric binary B-trees.  Data structure and maintenance algorithms.":  R.Bayer, 1972
"A diochromatic framework for balanced trees.":  L.J. Guibas and R. Sedgewick, 1978

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.

 
Many thanks to Misha Melikov for the great looking b lls.

 

Comments, suggestions, bug reports to Arsen Gogeshvili

The Java source code will be released when the optimization is completed and all /* comments */ are in place. Due to the visualization requirements, almost all recursive functions in the applet had to be sacrificed and replaced with modified methods which may not be suitable for a real-life application. If you are looking for working (and efficient) insertion/deletion algorithms, www.purists.org is an excellent resource.