Red/Black Tree Demonstration

Attention: Apparently there are enough versions of Java around that we need to supply two versions of the applet. If this version (using SUN Java 1.1 API) does not work on your browser you can always download the source code (see below) and compile it on your machine or you can try this version.

Usage: Move the mouse cursor to the textfield (white rectangle to the top left of the task bar) and click. Type an integer. It shows up in the textfield. Click on the Add Node button to begin insertion of a red node with the specified integer value. Click on the Next Step button to see what happens on the next iteration of insertion. Click on the Restart button to restart from an empty tree. To delete a node, click on the Delete Node button then click on the node you wish to delete. The node should turn green. Click on the Next Step button repeatedly to see the steps involved in deleting the node. The delete feature has been updated as of 8 Dec 02 to eliminate all previously reported problems. If you find a problem please send email to franco@gauss.ececs.uc.edu. Click on the Undo button to restore the tree to its state before the last node was inserted or deleted. Choose "Fast" for normal speed. If this is too much for your computer, select "Slow" or "Crawl".

Quick add: This is a new feature. Type an integer into the textfield and hit return. The new object will be inserted into the red-black tree without having to hit the Next button at all.

Documentation: As of December 8, 2002 this applet uses insertion and deletion procedures as described in:

      Berman and Paul. Sequential and Parallel Algorithms.
      Brooks/Cole PWS Publishing Co, 1997 (ISBN:0-534-94674-7).

Source Code: The source code is now in reasonable shape and includes comments which point to the cases described in the text cited above. It may be found here. It uses a Stream class found here to facilitate "next" step pauses. The special interace TokenObject needed by the Stream class is found here. The necessary applet tag looks like this (be sure to remove the blank before the word "applet"):

   < applet code="RedBlack.class" height=560 width=900>

The source code implements two interesting features for helping to speed the understanding of red-black trees. A parameter tag may be added to the applet tag in order to start the applet with a series of quick insertions. This is done, for example, as follows (be sure to remove the first blanks):

   < applet code="RedBlack.class" height=560 width=900>
   < param name="args" value="12 6 25 10 3 18 55 11 7 4 2 15 21 33 98 12 9 13 16 20 22 26 50 17 19 31 51 1 0 5 9 8 13 14 15 16 17 18">
   < /applet>

   //p1.add(colorit = new Button("Color"));

   //else if (evt.target.equals(colorit)) colorIt();

The code is designed for SUN Java 1.1. If your browser is using a later version, use this version of the applet.

Red/Black Trees: These are binary trees with the following properties.

1. Every node has a value.
2. The value of any node is greater than the value of its left child and less than the value of its right child.
3. Every node is colored either red or black.
4. Every red node that is not a leaf has only black children.
5. Every path from the root to a leaf contains the same number of black nodes.
6. The root node is black.

An n node red/black tree has the property that its height is O(lg(n)). Another important property is that a node can be added to a red/black tree and, in O(lg(n)) time, the tree can be readjusted to become a larger red/black tree. Similarly, a node can be deleted from a red/black tree and, in O(lg(n)) time, the tree can be readjusted to become smaller a red/black tree. Due to these properties, red/black trees are useful for data storage.