Class 10: Red-Black Trees

Definitions

 

A red-black tree is a binary search tree with one extra item per node: its color, which can be either RED or BLACK. By constraining the color of nodes, red-black trees ensure the following balancing rule:

 

 

Each node contains the following fields: color, key, left, right, and parent. If a child of a node does not exist, it is referred by NIL. NILs are leaf nodes that are called external nodes, and all other key bearing nodes are internal nodes. A read-black tree must satisfy the following 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 paths from the node to descendant leaves contain the same number of black nodes.

 

We use a single sentinel nil[T] to represent NIL. Its color field is BLACK, and all other fields are set to arbitrary values. All pointers to NIL are replaced by pointers to sentinel nil[T].

 

We call the number of black nodes from, but not including a node x down to a leaf the black-height of the node, denoted bh(x). By property 5, this notion is well defined.

 

Lemma 13.1

 

A red-black tree with n internal nodes has height at most 2lg(n+1).

 

Proof. First, show that the subtree rooted at any node x contains at least 2bh(x)-1 internal nodes. We prove it by induction on the height of x-based subtree. If the height of x is 0, then x is nil[T], hence it contains 0 nodes = 20-1.

 

Now, consider an internal node x with two children. Each child has a black-height of bh(x) (if it is RED), or bh(x)-1 (if it is BLACK). By our hypothesis, each child has at least 2bh(x)-1-1 (for the BLACK one) nodes. Thus, the subtree x contains at least

 

2*(2bh(x)-1-1) + 1 = 2bh(x)-1 internal nodes, which proves the claim. Note that, in the case of one child, that child cannot be BLACK (to not violate property 5). Hence, if the child y is RED, its bh(y)=bh(x) => N(x) >= 2bh(x)-1 + 1.

To complete the proof, let h be the height of the tree. According to property 4, at least half the nodes on any simple path from the root to a leaf, not including the root, must be black. (The simple path includes only one child, which must be black for each red node.) Consequently, the black-height of the root must be at least h/2; hence:

 

n >= 2h/2-1 <=>

 

2h/2 <= n+1 <=>

 

h/2 lg2 <= lg(n+1) <=>

 

h <= 2 lg(n+1) ¢

 

Rotations

 

The insert and delete operations when run on a red-black tree take O(lgn) time. However, they modify the tree, which may violate the red-black tree properties. To restore those properties, we must change the colors of some nodes and the pointers structure.

 

The pointer structure is changed through rotation, which is a local operation in a search that preserves the binary-search tree property. There are two kinds of rotations: left and right. The left rotation for node x assumes its right child y is not nil[T]. It "pivots" around the link from x to y:

 

 

x

a                                  y

                        b                      c

 

--->

 

                                    y

x                                  c

a                      b

 

A rotation operation preserves the BST properties:

 

 

Left-Rotate(T,x)

1     y = right[x]

2      right[x] = left[y]

3     if left[y] <> nil[T]

4           parent[left[y]] = x

5      parent[y] = parent[x]

6     if parent[x] = nil[T]

7           root[T] = y

8     else

9           if x = left[parent[x]]   // x is left child

10                left[parent[x]] = y

11          else                    // x is right child

12                right[parent[x]] = y

13      left[y] = x

14      parent[x] = y

 

The rotation operation runs in O(1) time; only pointers are changed, all other fields remain the same.