Red/Black Tree Demonstration


Usage: Type an integer into the text field. 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 start 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 is has been updated as of 13 Dec 01 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 it's state before the last node was inserted or deleted. See any elementary data structures text for a description of the rules of insertion and deletion including rotation and color reversals.

Source Code: For maintenance only. The code is ugly and uncommented as I was mainly interested in amusing myself and my class. RB.java.

Maintenance Version: Here is another version of the software which allows you to start the applet with a pre-built tree. There is also a button which allows you to change the color of any node. Maintenance version.

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.

Insertion: The rules for readjustment when inserting depend on the concept of rotation.