Red-Black Trees

From

Revision as of 17:06, 9 April 2009

Another approach to self-balancing binary search trees was published in 1978 by L. J. Guibas and R. Sedgewick. These trees are called Red-Black Trees because every node has a color: either red or black. In addition, when a node pointer is null, it is said to point to an “external node”.

Red-Black Tree Behavior

There are three rules for a Red-Black Tree:

1. The root and all external node are colored black.
   
2. Along any path from the root to an external node, there cannot be two consecutive red nodes.
   
3. All paths from the root to an external node must have the same number of black nodes.
   

Whenever a node is inserted into a tree, it is initially considered to be a red node, since the insertion of a black node into an existing Red-Black tree automatically violates rule 3. With an insertion or a deletion, the tree must be checked to see if the three rules are still adhered to; however, this can be determined by looking at only three nodes: the node inserted or deleted, the parent and the grandparent of that node.

In some cases, no action needs to be taken. In other cases, only a color swap is necessary. For example, a red node is inserted that results in two consecutive red nodes. If the parent is red, but the grandparent is black, swapping the color of the parent and grandparent might bring the tree back into compliance. Once there is a color swap, we may need to continue up the path to the root to be sure there are no two consecutive red nodes. Otherwise, a single rotation will bring the tree back into compliance.

In general, Red-Black trees and AVL trees have similar performance as Dictionary structures. The Search, Insert, and Delete operations for both trees are Θ( log2 N) in the average case and Ω( log2 N ) in the worst case.

AA Trees

This is a Red-Black Tree with an extra condition: the left child may not be red. Also, this structure uses a horizontal link to connect siblings.