Home > Research > Red Black Trees

Description

In Introduction to Algorithms, Cormen, Leiserson, and Rivest describe efficient algorithms for inserting nodes into and deleting nodes from red-black trees. If some binary trees satisfying the definition of red-black trees cannot be built by these algorithms, then theoretical analyses of red-black trees that consider all binary trees satisfying the definition of red-black trees may not accurately describe the behaviour of red-black trees in practice. In our paper in progress, we show that any binary tree shape that satisfies the definition of red-black trees can be built using only the insertion algorithm, RB-Insert, of Cormen, Leiserson and Rivest. The applet above is an implementation of out algorithm, RB-Shape, which, given any red-black tree T, will construct an insertion sequence for T. When the constructed sequence is inserted into the empty tree using RB-Insert, the result is a red-black tree with the same shape as T. Our paper contains a proof of correctness for RB-Shape.

Instructions

• To insert individual nodes, enter an integer greater than zero into the box beside the "Insert" button, then click "Insert" or hit return.
• To insert a group of nodes into an empty tree, enter the list of indices in the text area at the bottom of the applet, and click the "Read (I)" button.
• To enter a tree in standard format (see below for definition), use the text area at the bottom of the applet and click the "Read (SF)" button. The indices that are generated for the nodes are sequential, starting at 1.
• To clear the tree, press the "Clear" button.
• To view the insertion order generated by algorithm RBShape, click "Display (I)". The insertion order will then be displayed in the text area at the bottom of the applet.
• To view the standard format description of the tree, click the "Display (SF)" button. The standard format representation will then be displayed in the text area at the bottom of the applet.

Standard Format

One way of entering trees for this applet is to use Frank Ruskey's Standard Format.

Standard Format is a way of representing a red-black tree shape by a string of digits. Using a preorder traversal of the tree, the node colour is recorded when the node is visited. A black internal node is recorded as 1, a red node as 2, and a leaf as 0.

Sample Trees

The following are sample trees I constructed while working out the algorithm and proof. I may add explanations of the files at a later time.

Standard Format:

bigtree, bigtree190, bigtree205, bigtree214, bigtree218, bigtree218R, bigtree220, bigtree221, bigtreeR, prob23, probchild, smalltree, t0, t1, t2, t2b, t3

Insertion Order:

alt220io, alt220io2, bf3, fpttest1, fpttest2, io10, io220, io3, rio10, test1, test2, test3, test4_res, tst, uglytree1

Source Code

• Interface code for the applet.

• Red-black tree class, including the code for algorithm RBShape.
• Also includes code for tidy tree drawing.

• Canvas which displays the red-black tree.

Related Publications

Constructing Red-Black Tree Shapes
Andrea Mantler and Helen Cameron International Journal of Foundations of Computer Science, 13(6): 837-863, 2002.

• Construction of Red-Black Trees by a Sequence of Insertions, Iryna Skypnyk, Helen Cameron and Andrea Mantler, August 2003.
• Counting Red-Black Tree Shapes, Andrea Mantler, July 2000.