6.1 Balancing Rule

To most clearly express the red-black balancing rule, we need a few new vocabulary terms. First, define a non-branching node as a node that does not “branch” the binary tree in different directions, i.e., a node with exactly zero or one children.

Second, a path is a list of one or more nodes in a binary tree where every node in the list (except the last node, of course) is adjacent (see adjacent) in the tree to the one after it. Two nodes in a tree are considered to be adjacent for this purpose if one is the child of the other. Furthermore, a simple path is a path that does not contain any given node more than once.

Finally, a node p is a descendant of a second node q if both p and q are the same node, or if p is located in one of the subtrees of q.

With these definitions in mind, a red-black tree is a binary search tree in which every node has been labeled with a color (see color), either “red” or “black”, with those colors distributed according to these two simple rules, which are called the “red-black balancing rules” and often referenced by number:

1. No red node has a red child.
2. Every simple path from a given node to one of its non-branching node descendants contains the same number of black nodes.

Any binary search tree that conforms to these rules is a red-black tree. Additionally, all red-black trees in libavl share a simple additional property: their roots are black. This property is not essential, but it does slightly simplify insertion and deletion operations.

To aid in digestion of all these definitions, here are some red-black trees that might be produced by libavl:

In this book, black nodes are colored black and red nodes are colored gray, as shown here.

The three colored BSTs below are not red-black trees. The one on the left violates rule 1, because red node 2 is a child of red node 4. The one in the middle violates rule 2, because one path from the root has two black nodes (4-2-3) and the other paths from the root down to a non-branching node (4-2-1, 4-5, 4-5-6) have only one black node. The one on the right violates rule 2, because the path consisting of only node 1 has only one black node but path 1-2 has two black nodes.

See also:  [Cormen 1990], section 14.1; [Sedgewick 1998], definitions 13.3 and 13.4.

Exercises:

*1. A red-black tree contains only black nodes. Describe the tree's shape. [answer]

2. Suppose that a red-black tree's root is red. How can it be transformed into a equivalent red-black tree with a black root? Does a similar procedure work for changing a RB's root from black to red? [answer]

3. Suppose we have a perfectly balanced red-black tree with exactly pow (2, n) - 1 nodes and a black root. Is it possible there is another way to arrange colors in a tree of the same shape that obeys the red-black rules while keeping the root black? Is it possible if we drop the requirement that the tree be balanced? [answer]

• Analysis of Red-Black Balancing Rule