Introduction to Algorithms — Red-Black Tree

1. Properties of red-black trees

A red-black tree is a binary search tree with one extra bit of storage per node: its color, which can either RED or BLACK. By constraining the node colors on any simple path from the root to a leaf, red-black trees ensure that no such path is more than twice as long as any other, so that the tree is approximately balanced.

Each node of the tree now contains the attributes color, key, left, right, and p. If a child or the parent of a node does not exist, the corresponding pointer attribute of the node contains the value NIL. We shall regard these NILs as being pointers to leaves (external nodes) of the binary search tree and the normal, key-bearing nodes as being internal nodes of the tree.

A red-black tree is a binary tree that satisfies the following red-black properties:

1. Every node is either red or black.
2. The root is black.
3. Every leaf (NIL) is black.
4. If a node is red, then both its children are black.
5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.



As a matter of convenient in dealing with boundary conditions in red-black tree code, we use a single sentinel to represent NIL. For a red-black tree T, the sentinel T.nil is an object with the same attributes as an ordinary node in the tree.

• Its color attribute is BLACK, and its other attributes — p, left, right, and key can take on arbitrary values.

As Figure (b) shows, all pointers to NIL are replaced by pointer to the sentinel T.nil.

We use the sentinel so that we can treat a NIL child of a node as an ordinary node whose parent is .

• Although we instead could add a distinct sentinel node for each NIL in the tree, so that the parent of each NIL is well defined, that approach would waste space.
• Instead, we use the one sentinel T.nil to represent all the NILs — all leaves and the root’s parent. The values of the attributes p, left, right, and key of the sentinel are immaterial, although we may set them during the course of a procedure for our convenience.



We generally confine our interest to the internal nodes of a red-black tree, since they hold the key values. In the remainder of this article, we omit the leaves when we draw red-black trees, as shown in (c).



We call the number of black nodes on any simple path from, but not including, a node down to a leaf the black-height of the node, denoted bh(x). By property 5, the notion of black-height is well defined, since all descending simple paths from the node have the same number of black nodes. We define the black-height of a red-black tree to be the black-height of its root.

The following lemma shows why red-black tree make good search trees.

Lemma 1

A red-black tree with internal nodes has height at most .

proof:

As an immediate consequence of this lemma, we can implement the dynamic-set operations in time on red-black trees, since each can run in time on a binary search tree of height and any red-black tree on nodes is a binary search tree with height . Although the algorithms TREE-INSERT and TREE-DELETE in Binary Search Tree run in time when given a red-black tree as input, they do not directly support the dynamic-set operations INSERT and DELETE, since they do not guarantee that the modified binary search tree will be a red-black tree.

---

2. Rotations

The search-tree operations TREE-INSERT and TREE-DELETE, when run on a red-black tree with keys, take time. Because they modify the tree, the result may violate the red-black properties enumerated in Section 1. To restore these properties, we must change the colors of some the nodes in the tree and also change the pointer structure.

We change the pointer structure through rotation, which is a local operation in a search tree that preserves the binary-search-tree property. Figure 2 shows the two kinds of rotations: left rotations and right rotations.

• When we do a left rotation on a node , we assume that its right child is not ; may be any node in the tree whose right child is not .
  • The left rotation “pivots” around the link from to . It makes the new root of the subtree, with as ‘s left child and ‘s left child as ‘s right child.

The pseudocode for LEFT-ROTATE assumes that and that the root’s parent is .



LEFT-ROTATE(T, x)
  

Figure 3 shows an example of how LEFT-ROTATE modifies a binary search tree. The code for RIGHT-ROTATE is symmetirc. Both LEFT-ROTATE and RIGHT-ROTATE run in O(1) time. Only pointers are changed by a rotation; all other attributes in a node remain the same.



3. Insertion

We can insert a node into an -node red-black tree in time. To do so, we use a slightly modified version of the TREE-INSERT procedure to insert node into the tree as if it were an ordinary binary search tree, then we color red. To guarantee that the red-black properties are preserved, we then call an auxiliary procedure RB-INSERT-FIXUP to recolor node and perform rotations. The call RB-INSERT(T, z) inserts node , whose keys is assumed to have already been filled in, into the red-black tree .

RB-INSERT(T, z)
  

The procedures TREE-INSERT and RB-INSERT differ in four ways.

• First, all instance of NIL in TREE-INSERT are replaced by T.nil.
• Second, we set z.left and z.right to T.nil in lines 14-15 of RB-INSERT, in order to maintain the proper tree structure.
• Third, we color red.
• Fourth, because coloring red may cause a violation of one of the red-black properties, we call RB-INSERT-FIXUP(T, z) of RB-INSERT to restore the red-black properties.

RB-INSERT-FIXUP(T, z)
  while z.p.color == RED
    if z.p == z.p.p.left
        y = z.p.p.right
        if y.color == RED
            z.p.color = BLACK           // case 1
            y.color = BLACK             // case 1
            z.p.p.color = RED           // case 1
            z = z.p.p                   // case 1
        else if z == z.p.right
                  z = z.p               // case 2
                  LEFT-ROTATE(T, z)     // case 2
        else
            z.p.color = BLACK           // case 3
            z.p.p.color = RED           // case 3
            RIGTH-ROTATE(T, z.p.p)      // case 3
    else (same as then clause with "right" and "left" exchanged)
  T.root.color = BLACK            

To understand how RB-INSERT-FIXUP works, we shall our examination of the code in three major steps.

• First, we shall determine what violations of the red-black properties are introduced in RB-INSERT when node is inserted and colored red.
• Second, we shall examine the overall goal of the while loop in line 1-15.
• Finally, we shall explore each of the three cases within the while loop’s body and see how they accomplish the goal.

Figure 4 shows how RB-INSERT-FIXUP operates on a sample red-black tree.



---

4. Deletion

RB-DELETE-FIXUP(T, x)

---