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.)
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
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.
Copyright (c) 1996
Doug Ierardi and
All rights reserved.
Developed with the assistance of C Aydin, S Deng, C Kawahara, S Kolim and J Tsou.
GifImage and UnZip. Copyright (c) 1996 Tadashi Hamano.