Red/Black Trees

Red/Black trees, introduced by R. Bayer, are binary search trees that adhere to a few extra structuring rules, and that have a few extra properties in each node. These new rules and properties make it easier to keep the tree structure balanced when inserting and deleting elements. The extra properties found in the nodes of a Red/Black tree are

In a Red/Black tree, the color code of each node is either red or black. The extra structuring rules that Red/Black trees adhere to are

A NIL node will be a special sentinel node used to indicate an empty leaf.

When insert and delete operations observe these structural rules, the tree remains well balanced. The number of black nodes between a leaf of the tree and its root is called the black-height of the tree. Looking at the structuring rules closely, you can determine that any path from a leaf to the root can never be more than twice the length of any other leaf-to-root path. This is because the minimum path contains only black nodes (number of nodes equals black-height), and the maximum path contains a red node between each black node (number of nodes equals black-height multiplied by 2).

The following sections explain how the new properties and rules are put to use in order to maintain a well-balanced tree.

Inserting Theory

In order to insert an element into a Red/Black tree, the tree is traversed to find an appropriate insertion point. An element is always inserted in the place of a leaf node. The newly inserted node is given the color red, and it will have two black leaf nodes (which are, according to structuring rule 2, in fact NIL nodes). Because of this, structuring rules 2 and 3 still hold after inserting a new element. And if the parent of the inserted element happens to be black, the operation is completed. However, structuring rule 1 will be violated when the parent happens to be a red node—according to rule 1 a red parent is only allowed to have black children. This means that after inserting an element, the tree structure may need to be rebalanced.

Two tools are used in rebalancing the tree structure. The first is simply changing the color of a node, the second is rotating nodes around in the structure. The remainder of this section will show that there are actually two situations in which a rebalancing of the tree structure is needed: one when the parent of the new element is red and its uncle is black, and the other when both the parent and the uncle of the element are red.

Rebalancing a Red/Black Tree for a Red Parent and a Black Uncle

Figure 11.11 shows one of the two situations in which the tree structure needs to be rebalanced after insertion of an element.

In the left half of Figure 11.11, part of a Red/Black tree is shown, containing the following elements: 50 (Black), 25 (Red), 80 (Black). The element 12 is inserted (Red). The parent of element 12 will be element 25. For reference sake, element 80 will be called the uncle of element 12. The Red/Red parent-child link of elements 12 and 25 is a violation of rule 1 and needs to be rebalanced. The rebalancing is shown in the right half of Figure 11.11. The rebalancing consists of elements 50 and 25 changing place and color. In effect, element 50 becomes the right child of the element that used to be its left child. After this rotation of elements, the Red/Black tree structure is valid again; the top of the changed tree (element 25) is black, so the color of its parent does not matter. Also, the black-height of the tree is unchanged. The tree structure is valid.

Rebalancing a Red/Black Tree for a Red Parent and a Red Uncle

However, it is also possible that the uncle of a newly inserted element is red instead of black. Figure 11.12 shows what happens in that case.

In the left half of Figure 11.12, part of a Red/Black tree is shown containing the following elements: 50 (Black), 25 (Red), 80 (Red). The element 12 is inserted (Red). The parent of element 12 will be element 25; the uncle is element 80. In rebalancing the Red/Red parent-child link of elements 12 and 25, retyping can be used. The parent (25) will be colored black, removing the illegal Red/Red parent-child link. But now a new violation is created; the number of black nodes between the leaf and the root is increased. The grandparent of the new element (50) therefore has to be retyped also. In doing this, element 50 has become a red node with a red child (80). This child is retyped also. This brings us to the right half of Figure 11.12. Note that no further changes need to be made to the subtree represented by element 80. Element 80 is black and can thus contain both red and black children, and the black-height is maintained because element 50 is now red.

Inserting Practice

These two techniques—rotation and retyping—may both be needed in this second situation because the rebalancing is not finished yet. Further changes may be needed above element 50 in Figure 11.12, because it may have a red parent. This can cause another Red/Red parent-child violation. So, in effect, retyping can propagate all the way up to the root of the tree. Sometime during this rebalancing, a rotation may also be needed; for example, when a black node is turned to red while having a black uncle. Luckily, as you have seen in this section, after a rotation the tree structure is valid and the rebalancing can stop. Listing 11.10 rebalances a Red/Black tree after an insert.

Code Listing 11.10. Rebalancing a Red/Black Tree After Inserting a New Left Element

template <class T >
void RedBlackTree<T>::InsertRebalance(Node <T>*newNode)
{
    Node <T>*tempNode;

    // Continue checking up to the root, as long as the parent is RED.
    while (newNode != root && newNode->parent->color == RED)
    {
        if (newNode->parent == newNode->parent->parent->left)
        {
            tempNode = newNode->parent->parent->right;
            if (tempNode->color == BLACK)
            {
                if (newNode == newNode->parent->right)
                {
                    newNode = newNode->parent;
                    RotateLeft(newNode);
                }
                newNode->parent->parent->color = RED;
                newNode->parent->color = BLACK;
                RotateRight(newNode->parent->parent);
            }
            else
            {
                tempNode->color = BLACK;
                newNode->parent->color = BLACK;
                newNode->parent->parent->color = RED;
                newNode = newNode->parent->parent;
            }
        }

This template function can be found in the file 11Source02.cpp that can be found on the Web site. Note also that this is actually only half of the solution. In Figure 11.12 the new elements were inserted to the left of their parents. However, it is also possible that an element needs to be inserted to the right of a parent. In that case, the implementation code has to be mirrored: left becomes right and right becomes left. This can be seen in the second half of the InsertRebalance function. Listing 11.11 shows this mirroring code.

Code Listing 11.11. Rebalancing a Red/Black Tree After Inserting a New Right Element

        else
        {
            tempNode = newNode->parent->parent->left;
            if (tempNode->color == BLACK)
            {
                if (newNode == newNode->parent->left)
                {
                    newNode = newNode->parent;
                    RotateRight(newNode);
                }
                newNode->parent->parent->color = RED;
                newNode->parent->color = BLACK;
                RotateLeft(newNode->parent->parent);
            }
            else
            {
                newNode->parent->parent->color = RED;
                newNode->parent->color = BLACK;
                tempNode->color = BLACK;
                newNode = newNode->parent->parent;
            }
        }
    }
    root->color = BLACK;
}

As you can see in the diagrams in this section, insertion is an O(log2 n) + O(h) operation. This is because the search for the place to insert is a binary search (O(log2 n), and the rebalancing is either a rotation that is not dependent on the number of elements in the tree (O(1)) or a retyping that can propagate all the way to the root of the tree (O(h)), where h = tree height.

Deleting

Deleting an element from a Red/Black tree starts the same way as with a normal binary tree. After this, a balancing action may be needed, which is very similar to the one used after inserting an element. As you might expect, deleting a red node from a Red/Black tree does not cause any violations. Looking at how elements are deleted from a normal binary tree, the following cases of violations can be identified when deleting an element from a Red/Black tree:

The violations need to be removed once again using the two techniques explained in the section on inserting: rotation and retyping. An implementation of the rebalancing delete operation can be found in the file 11Source02.cpp that can be found on the Web site.

Searching

Searching a Red/Black tree is no different from searching any other balanced binary search tree. The changes made to transform a normal binary tree into a Red/Black tree only affect the ability to balance the structure after insert and delete operations. Searching a balanced binary tree is then an O(log2 n) operation

Sorting

Sorting Red/Black trees, just like sorting any binary tree, is not very useful. The tree structure is sorted by the way elements are inserted into the tree.

Traversing

Traversing a Red/Black tree is no different from traversing any other binary search tree.