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:

- No red node has a red child.
- 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]