Introduction to Red-Black Trees

AVL trees is a self-balancing BST tree. Every node of the tree maintains a height difference between the left and the right sub-tree as 0, -1 or 1. Therefore, any BST operation, such as a search, or an insertion, or a deletion, on an AVL tree with n nodes requires O(log n) time. If and when the balance is disturbed, the balance can be restored by applying rotation. The rotation operation should be applied as often as the tree loses its balance. We have explored AVL tree in sufficient detail in the last couple of blogs.

Red-black tree is also a self-balancing BST. It relaxes the requirement for frequent maintenance of node balance. The readers may refer to wikipedia for the history around the discovery of red-black trees. The performance of red-black trees is about 10-20% faster than that of AVL trees. A red-black tree makes fewer structural changes to a BST than AVL. If the performance is not very important, AVL is simpler and preferable. If performance is important, then probably preference will be to use B-trees. However, red-black tree is a challenging exercise for the students for mastering data structures.

A red-black tree has two different types of nodes, viz., red and black. The nodes are distinguished by storing a color bit with each. A 0, and a 1 represent red and black nodes, respectively. The important characteristics of a red-black tree are as follows:

1. Order invariant: It preserves the ordering property of a BST.
2. Node colors: The nodes are either colored red or black.
3. External nodes: Leaf nodes black are external nodes, they store NULL pointers and are colored black.
4. Internal nodes: An internal node stores a key, pointers to left and right child. Any or both child pointers may point to leaf nodes.
5. Black root: The root is always colored black, and all leaf nodes are colored black.
6. Color invariant: No two consecutive nodes are colored red. Equivalently no red node has a red child.
7. Height invariant: The number of black nodes on any path from the root to a leaf is the same.

A new node gets red color when it is inserted. A new insertion may, therefore, violate color invariant. Two red nodes may appear as parent and child in the tree after insertion. A color fixing operation is applied whenever two red nodes appear consecutively. The fixing is performed by recoloring the nodes so that the height invariant (black height) is preserved. Maintaining black height is important because the timecomplexities of an operation depend on black height.

Black height: Black height of a node n in a red-black tree is equal to the number of black height from n to the farthest leaf node from n.

Figure below depicts a red-black tree of black height 3. It does not include external nodes.

The black height of the above tree is 3. Every path from the root to any leaf node has exactly 3 black-colored nodes. The black height of node 8 is two. All leaf nodes are external nodes. A leaf node does not store actual elements. However, the presence of external nodes makes the tree strictly binary. Therefore, a red-black tree is not only a self-balancing BST but also a strictly binary tree.

The black height of a red-black tree T with root r is denoted by bh(r). We can prove the following property about black height.

Minimum number of internal node: Let the black height of a RBT T with root r be bh(r). Then T consists of at least 2^{bh(r)}-1 internal nodes.

The proof relies on a recurrence relation and induction. If r is a leaf node then T has no internal node. It consist of 2⁰ - 1 internal nodes.

Induction hypothesis: Assume that any sub-tree of T with height less bh(r) satisfies the stated property.

Induction step: Since the root is alway black, it implies each of the two sub-trees of r has a black height of bh(r)-1. We apply the induction to both sub-tree separately and reach the following conclusions:

• Right sub-tree of T has at least 2^bh(r)-2 internal nodes
• Left sub-tree of T has at least 2^bh(r)-2 internal nodes

Combining the above two results, we conclude that tree T must have 2*2^{bh(r)-2</sub> = 2bh(r)-1</i>.}

Height of a red-black tree: The height of a red-black tree with n nodes is O(log n).

If a red-black tree T with root r has a black of height of </i>bh(r)</i>, then we know from the previous property that n > 2^bh(r)-1. Further, at least half the nodes in a path from root to a leaf node in any red-black tree are black. Leaf is also black. Therefore, bh(r)  ≤  h/2, where h is the height of T. It implies, h/2  ≥  log (n+1). Hence, h = O(log n).

Another way of proving the above property is by collapsing the nodes of a red-black tree. The pictures below depict the sequence of collapsing operation on the nodes of a red-black tree.

We observe the following points about the tree after collapsing operation is complete:

• Each node in the compact red-black tree consists of only black nodes
• All the external nodes are at the same depth from the root
• An internal node may have 2, or 3, or at most four children
• The height of the collapsed tree h’ ≥  h/2

The number of internal nodes in the collapsed tree n ≥  2^h’ - 1  ≥  2^h/2 -1 Therefore, h ≤  2 log (n+1)2 log (n+1)</i>

We summarize the properties again for the readers’ understanding:

1. A node is colored either red or black.
2. The root node is always black.
3. A leaf or an external node is always colored black.
4. A leaf stores null pointers for its right and left child.
5. A red node does not have a red child. Its children must be black.
6. A black node may have a red node as one of its children
7. All paths from a node to descendant leaves must have the same number of black nodes.

Back to Index