next up previous contents index Search
Next: Insertion Operation Up: 0.2 Data Searching and Previous: References

0.2.4 Red-Black Trees

Binary search trees   are superior to array-based binary searches because they make addition and deletion from the data storage structure less costly. However, as discussed in the binary search tree section, it is possible to create degenerate trees   which suffer from poor search operation performance. These degenerate trees look like linked lists; each node in the tree has one child causing the data lookup to be a linear operation. As said in the binary search tree section, the optimal shape for a search tree data structure is a balanced tree   or one in which each node in the tree has either two or no child nodes.

The red-black tree algorithm is a method for maintaining balanced search trees. The algorithm is actually based on AVL trees which are data structures that were proposed by G. M. Adel'son-Vel'skii and E. M. Landis. As you might expect, in a red-black tree every node is given a color - either red or black. Further, in a red-black tree, unlike in a binary search tree, data is only stored at the leaf nodes   of the data structure. Internal nodes   are used as guides or reference points.

A node's color is determined by the following heuristics:

All leaf nodes in a red-black tree must be black.
On any path from the root of the tree to a leaf, two consecutive red colored nodes are not allowed.
All the leaves of the tree must have the same number of black nodes on the path from the root of the red-black tree to that leaf. This number of black nodes is called the black depth   of a node.

Scott Gasch