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

 1 NIL

. For a red-black tree

 1 T

, the sentinel

 1 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

 1 NIL

are replaced by pointer to the sentinel

 1 T.nil

.

We use the sentinel so that we can treat a

 1 NIL

child of a node $x$ as an ordinary node whose parent is $x$.

• Although we instead could add a distinct sentinel node for each
 1 NIL

in the tree, so that the parent of each

 1 NIL

is well defined, that approach would waste space.

• Instead, we use the one sentinel
 1 T.nil

to represent all the

 1 NIL

s — 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 $x$ down to a leaf the black-height of the node, denoted

 1 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 $n$ internal nodes has height at most $2 \lg(n+1)$.

proof:

As an immediate consequence of this lemma, we can implement the dynamic-set operations in $O(\lg n)$ time on red-black trees, since each can run in $O(h)$ time on a binary search tree of height $h$ and any red-black tree on $n$ nodes is a binary search tree with height $O(\lg n)$. Although the algorithms TREE-INSERT and TREE-DELETE in Binary Search Tree run in $O(\lg(n))$ 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 $n$ keys, take $O(\lg n)$ 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 $x$, we assume that its right child $y$ is not $T.nil$; $x$ may be any node in the tree whose right child is not $T.nil$.
• The left rotation “pivots” around the link from $x$ to $y$. It makes $y$ the new root of the subtree, with $x$ as $y$‘s left child and $y$‘s left child as $x$‘s right child.

The pseudocode for LEFT-ROTATE assumes that $x.right \neq T.nil$ and that the root’s parent is $T.nil$.

```
1LEFT-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

 1 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 $n$-node red-black tree in $O(\lg(n))$ time. To do so, we use a slightly modified version of the TREE-INSERT procedure to insert node $z$ into the tree $T$ as if it were an ordinary binary search tree, then we color $z$ 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 $z$, whose keys is assumed to have already been filled in, into the red-black tree $T$.

```
1RB-INSERT(T, z)

```

The procedures

 1 TREE-INSERT

and

 1 RB-INSERT

differ in four ways.

• First, all instance of NIL in TREE-INSERT are replaced by
 1 T.nil

.

• Second, we set
 1 z.left

and

 1 z.right

to

 1 T.nil

in lines 14-15 of

 1 RB-INSERT

, in order to maintain the proper tree structure.

• Third, we color $z$ red.
• Fourth, because coloring $z$ red may cause a violation of one of the red-black properties, we call
 1 RB-INSERT-FIXUP(T, z)

of RB-INSERT to restore the red-black properties.

```
123456789101112131415161718RB-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

 1 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 $z$ is inserted and colored red.
• Second, we shall examine the overall goal of the
 1 while

loop in line 1-15.

• Finally, we shall explore each of the three cases within the
 1 while

loop’s body and see how they accomplish the goal.

Figure 4 shows how

 1 RB-INSERT-FIXUP

operates on a sample red-black tree.

4. Deletion

```
1RB-DELETE-FIXUP(T, x)

```

1 thought on “Introduction to Algorithms — Red-Black Tree”

1. I like this introduction to this tree structure. I found the code examples to be easy to follow and the post, in general, does a great job explaining the data structure!

This site uses Akismet to reduce spam. Learn how your comment data is processed.