Problem:
For some reason which I do not understand, sometimes in Firefox in Linux typed numbers do not register in the applet. I have found that a few reloads gets it to work eventually. 
New:
As of 24 June 2006 every important rule which the applet uses to
execute an insertion or deletion step is displayed in a textfield prior
to its graphical rendering. We believe this will help understand the
complex interaction of rules and current tree configuration, especially
in the case of deletion. Rules have numbers which correspond with detailed
explanations at the bottom of this page (see the sections below on
insertion rules and deletion rules).
As of 25 June 2006 nodes that are selected for deletion remain visible in the tree until the last click on Next Step for that run. 
Java Version:
If this applet does not work with your browser it is probably because it has been compiled with Sun's Java version 1.6 and your java plugin is version 1.5 or earlier. In that case you can download the source code (see below) and compile yourself or try an older version such as this one or its maintenance version. 
Usage:
To insert a node: type an integer. It shows up in the textfield labeled value: (you may need to click somewhere into the applet first). Click on the Add Node button to begin insertion of a node with the specified integer value. Repeatedly click on the Next Step button to advance stepbystep through the insertion algorithm and see what changes are made at each iteration. As long as the sign is visible between the Restart and Undo buttons you need to keep clicking (but you can cancel by hitting the Undo button). To insert and avoid the stepbystep feature: enter a number in the textfield and hit the return key. 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. Repeatedly click on the Next Step button to see the steps involved in deleting the node as long as the sign is visible (or cancel with Undo). The delete feature has been updated as of 8 December 2002 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:
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. 
Hot Keys:
If the dot panel, Add Node button, Delete Node button, Next Step button, Undo button, or Restart button are in focus you can use key presses to enter numbers and initiate actions. To insert a node: key in a number (which should appear in the value text field) then hit the "A" key. To advance to the next step, either while inserting or deleting, repeatedly hit the "N" key. To insert and avoid the stepbystep feature: key in a number then hit the "Return" key. To restart with an empty tree, hit the "R" key. To delete a node: hit the "D" key, then use the mouse to select a node to delete, then use the "N" key to advance. To undo the previous move, hit the "U" key. Speed and the choice of duplicates are not controlled by hot keys. To put the dot panel in focus, just click on it. 
Deletion colors:
A node that is selected for deletion turns green when it is selected. The deletion algorithm uses the notion of successor node (also predecessor node  see below). If a successor or predecessor is needed, on the next step the selected node is returned to its original color and remains part of the red/black tree until it is replaced at the end of the deletion run, otherwise it stays green until the run is completed whereupon it is deleted. If a successor or predecessor node is needed, it becomes yellow and stays yellow for the entire run of the deletion algorithm. The green and yellow nodes are not considered part of the red/black tree but are needed for reference so they retain positions as though they are part of the red/black tree until the end of the run. At that point, either there is a yellow node and it replaces the node originally selected for deletion with its color changed to red or black as necessary, or there is a green node and it is just deleted. 
Sentinels:
It is possible to implement red/black tree algorithms by using Null to indicate the absence of a child. However, we take the more customary approach of attaching invisible black nodes called sentinels to red/black tree nodes instead. This means there really are no leaves among the visible nodes. Using sentinels makes the algorithms easier to implement but causes peculiarities in some descriptions during deletion. A description might say we need to worry about the "near" nephew of a node but that "near" nephew is nowhere to be found! That is OK, there really is a near nephew: it is a black sentinel. 
Documentation:
As of 8 December 2002 this applet uses insertion and deletion procedures
as described in:
Berman and Paul. Sequential and Parallel Algorithms. These rules and a description of red/black trees are repeated in the sections below after the Source Code section. How a successor or predecessor is chosen is discussed in the last section below. 
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 necessary applet tag looks like this:
<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: <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"> </applet>To see how this looks click here (the applet you will be directed to only works on Java 1.2.2 and higher interpreters so the buttons may not work on your browser). Secondly, there is code for including a button called Color so that clicking on a node and then the Color button will reverse the node's color. You can try it in the applet above if your buttons are working. Just uncomment the lines //saved_pick = pick;in the mousePressed method of class RedBlack, //p1.add(colorit = new Button("Color")); //colorit.addActionListener(this);in the init method of class RedBlack and //else if (evt.getSource() == colorit) colorIt();in the actionPerformed method of class RedBlack. The code is designed for SUN Java 1.6. If your browser cannot comprehend this applet try this version or compile the source code above. 

These are binary trees with the following properties.
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. 
When a node is inserted in the tree it is given the color red. This
does not affect the black node count on any path to a leaf. But it
could lead to a single pair of consecutive red nodes in the tree. If the
new node becomes a child of a black node there is no problem. But it
may become a child of a red node. The double red violation will begin
at a leaf. The rules below are designed to move the double violation
up toward the root without affecting any path's black node count until
it can be eliminated by bringing down a black from above or it reaches
the root where it can be eliminated since the root can be colored
black without consequence.
Let current refer to the red node that has a red child thereby identifying the location of the violation. The parent of current will always be black. The list below shows all possible states for current. The insertion algorithm performs the action associated with the correct state and either terminates or repeats.

Let current refer to the node whose parent and siblings
are queried in a deletion step. Initially current is the
node selected for deletion. Suppose it has two children. Then
another node is selected for deletion instead: namely, either a
successor of current (a leaf or a node with only a right child of next
greater value), or a predecessor of current (a leaf or node with
only a left child of next smaller value). Either is easy to find
and rules for doing so are in the next section. The deleted successor
or predecessor is saved until the run terminates and then it replaces
the node originally selected to be deleted. If a successor or
predecessor is necessary, it becomes current when it is found.
Due to the use of a successor, only nodes with at most one child need to
be considered for deletion.
Assume current initially has at most one child. Consider five cases (with labels  the red ones are impossible cases):

The algorithm is made as simple as possible by reducing all
nontrivial cases to either deleting a red leaf or black node that
has at most one leaf child via the notions of successor and
predecessor. The successor of a node of value X is
the node of the tree whose value is the least that is greater than
X. The predecessor of a node of value X is a node of
the tree whose value is the greatest that is less than X.
Each is easy to find: just do a depth first search on leftmost
child, in the case of successor, and rightmost child, in the case of
predecessor. The search ends when a leftmost or rightmost child
does not exist. Therefore, the search ends at a node with at most
one child. Moreover, if the node is red, it must be a leaf and if
it is black its only possible child must be a red leaf. Thus, after
rebalancing, the successor or predecessor can assume the position of
the deleted node without violating the red/black property number 2.
In the case of a red leaf below a black successor or predecessor,
the red leaf can simply be moved up to be a child of the successor's
or predecessor's former parent and its color changed to black.
Actually, the only hard cases involve a black successor or
predecessor with no children.
This deletion algorithm may use either a successor or a predecessor. The decision is made as follows: the successor is used if it is red or it is not a black leaf (that is, it could be black with a red leaf); otherwise the predecessor is used. Whether a predecessor or successor is used, either is referred to as the successor in the above description. 