|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.
|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.|
|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 step-by-step 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 step-by-step 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 email@example.com. 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".|
|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.|
|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 step-by-step 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.|
|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.|
|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.|
|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
It uses a Stream class found
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.
Successors and Predecessors: