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 deleteion. 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. |
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 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 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 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. |
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. |
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 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.5. If your browser cannot comprehend this applet try this version or compile the source code above. |
Tree Relatives :
|
Red/Black Trees :
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. |
Insertion Rules :
| 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.
|
Deletion Rules :
| Let current refer to the node whose parent and siblings are queried in a deleteion 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):
|
Successors and Predecessors :
| The algorithm is made as simple as possible by reducing all non-trivial cases to either deleting a red leaf or black node that has at most one leaf child via the notions of successorand 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. |
