Animating Algorithms, I

Interactive animations of several types of binary search trees
Version 0.4

The inset below presents a non-interactive illustration of the animated binary search tree applet - in this case, repeating a sequence of operations on a splay tree. This first demo operates in two cycles: first labelling active nodes, and then omitting labels (for those of you with slower machines). Feel free to pull and query the individual nodes. Both interactive and non-interactive demos of several varieties of binary search trees (BSTs) are available from the links below. We suggest starting with the interactive splay trees.
Note that recent security enhancements in Netscape browsers (e.g. Atlas 3.0b4) appear to lead to security violations in some of the interactive demos when threads are suspended and resumed. We'll work on these problems once the cause is clarified.)

Sorry! You need a Java-capable browser to view these applets!

These applets were designed both to serve as animated figures to illustrate a set of lecture notes on advanced algorithms and data structures, and to provide interactive examples of these data structures in action. The current set of applets focuses on several varieties of BSTs.

All but the first of these utilize rotations to restructure the tree. The final set of notes should be online by mid May ... so stay tuned. A second set of applets illustrating heaps - binary heaps, skew or leftist heaps, binomial and fibonnaci heaps, and pairing heaps - and a few related, useful data structures (e.g. disjoint sets) is in preparation.

The algorithms implemented so far include the following:

Standard, garden-variety binary search trees.

Splay trees [Sleator and Tarjan], which are a sexy self-adjusting data structure based on the splay operation. The applet (also shown here) uses bottom-up splaying. Another demo by Kindred and Sleator implements the top-down version.

Red-images/small/white trees, an implementation of 2-3-4 trees based on binary trees. A second demo is provided here.

Randomized binary search trees based on treaps [Aragon and Seidel]. These provide an elegant BST-based alternative to Pugh's randomized skip lists.

The inset above illustrates a sequence of

: insertions; deletions; locations or finds

on a splay tree. The splay operation essentially drags the last accessed node (

) to the root of the tree, using a sequence of rotations applied in pairs (

) through its ancestors (

). The steps of the algorithm are illustrated in more detail here.

The applets themselves are configurable - either to serve as interactive demos or to repeat a particular fixed sequence of operations. Some aspects of the applet's layout, and of the trees' presentation and physics, can also be reset by parameters passed to the applet or by menus available on the interactive demos above. Most of these options should be self-explanatory.

Notes. This package has been developed under Linux 1.3.x using the Linux port of Sun's JDK (tm). This updated version makes use of the classes GifImage and UnZip by Tadashi Hamano to reduced transfer time for uploading its image archive.

To do. Single step mode (for graphics and textual display of algorithm).

Known bugs. There appears to be a lingering problem with the resetting of fonts in pulldown menus under Netscape.

You are the visitor to this page since 11 April 1996.

We're COOL! Copyright (c) 1996 Doug Ierardi and Ta-Wei Li. All rights reserved.
Developed with the assistance of C Aydin, S Deng, C Kawahara, S Kolim and J Tsou.
You can contact the development team at java-games@langevin.usc.edu. Links to our other projects can be found here.
GifImage and UnZip. Copyright (c) 1996 Tadashi Hamano.