Red-black trees are one of many search-tree schemes that are "balance" in order to guarantee that basic dynamic-set operations take O(lg n) time in the worst case.
A red-black tree with n internal nodes has height at most 21g(n + 1).
Proof We first show 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), 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 3, 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,
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 21g (n + 1).
An immediate consequence of this lemma is that the dynamic-set operations SEARCH, MINIMUM, MAXIMUM, SUCCESSOR, and PREDECESSOR can be implemented in O(lg n) time on red-black trees, since they can be made to run in O(h) time on a search tree of height h and any red-black tree on n nodes is a search tree with height O(lg n).