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 does not work on your browser (written for SUN Java 1.2.2 and higher) you can always download the source code (see below) and compile it on your machine or you can try this version. Or you can try the old applet (see below).

Usage: Move the mouse cursor to the middle of the applet (area above the buttons) and click the mouse to get focus (the Restart button will be highlighted). Type an integer. It shows up in the white rectangle to the top left of the task bar. Click on the Add Node button or type the letter 'a' to begin insertion of a red node with the specified integer value. Click on the Next Step button or type the letter 'n' to see what happens on the next iteration of insertion. Click on the Restart button or type the letter 'r' to restart from an empty tree. To delete a node, click on the Delete Node button or type the letter 'd', then click on the node you wish to delete. The node should turn green. Click on the Next Step button or type the letter 'n' 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 or type the letter 'u' to restore the tree to its state before the last node was inserted or deleted. Choose "Fast" or type the letter 'f' for normal speed. If this is too much for your computer, select "Slow" or "Crawl" or type the letter 's' or 'c'.

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. Algorithms: Sequential, Parallel, and Distributed.
      Thomson Course Technology, 2005 (ISBN:0-534-42057-5).

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 interface TokenObject needed by the Stream class is found here. The necessary applet tag is this:

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

The source code implements two interesting feastures 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:

   <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"));
   //colorit.addActionListener(this);
   //colorit.addKeyListener(this);

   //else if (evt.getSource() == colorit) colorIt();

The code is designed for SUN Java 1.2.2 or higher. If your browser does not have that then try the original applet below.

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.