red-black trees: A red-black tree is a binary search tree with one extra bit of storage per node: its color, which can be either RED or BLACK. By constraining the way nodes can be colored on any 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 fields color, key, left, right, and p. If a child or the parent of a node does not exist, the corresponding pointer field of the node contains the value NIL. We shall regard these NIL's as being pointers to external nodes (leaves) of the binary search tree and the normal, key-bearing nodes as being internal nodes of the tree.
A binary search tree is a red-black tree if it satisfies the following red-black properties:
Every node is either red or black.
The root is black.
Every leaf (NIL) is black.
If a node is red, then both its children are black.
For each node, all paths from the node to descendant leaves contain the same number of black nodes.
Figure 13.1(a) shows an example of a red-black tree.
The following lemma shows why red-black trees make good search trees.
Proof We start by showing that the subtree rooted at any node x contains at least 2bh(x) - 1 internal nodes. We prove this claim by induction on the height of x. If the height of x is 0, then x must be a leaf (nil[T]), and the subtree rooted at x indeed contains at least 2bh(x) - 1 = 20 - 1 = 0 internal nodes. For the inductive step, consider a node x that has positive height and is an internal node with two children. Each child has a black-height of either bh(x) or bh(x) - 1, depending on whether its color is red or black, respectively. Since the height of a child of x is less than the height of x itself, we can apply the inductive hypothesis to conclude that each child has at least 2bh(x)-1 -1 internal nodes. Thus, the subtree rooted at x contains at least (2bh(x)-1 - 1) (2bh(x)-1 - 1) 1 = 2bh(x) - 1 internal nodes, which proves the claim.
To complete the proof of the lemma, 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. Consequently, the black-height of the root must be at least h/2; thus,
n ≥ 2h/2 - 1.
Moving the 1 to the left-hand side and taking logarithms on both sides yields lg(n 1) ≥ h/2, or h ≤ 2 lg(n 1).