2L

Properties
1. Every node is either red or black.
2. The root is black.
3. Every leaf ( NIL ) is black.
4. If a node is red, then both its children are black.
5. For each node, all simple paths from the node to descendant leaves contain the
same number of black nodes.
性质
1、节点为红色或黑色
2、根节点为黑色
3、叶子节点（空节点）为黑色
4、节点为红色，则其两个孩子节点都是黑色
5、对于每个节点，所有从该节点到叶子节点的简单路径都包含相同个数的黑色节点。

Lemma:
A red-black tree with n internal nodes has height at most 2lg(n+1).
引理：
n个内节点的红黑树，其高度最大为2lg(n+1)。
证明：
1、证明在红黑树的任意子树x至少有2^bh(x) - 1 个内节点。
bh: black height，即子树x到叶子节点的路径中黑色节点的个数（不包括x自身，取最大值）
首先，叶子节点本身至少有2^bh(x) - 1 = 2^0 - 1 = 0个内节点
其次，假如对任意子树x结论成立
那么如果x是内部节点，且有两个孩子节点，
则孩子节点的bh值可能为bh(x) [当x为红色] 或者 bh(x) - 1 [当x为黑色]
由于bh(x) 肯定是大于 bh(x) - 1的，
当左右孩子都取bh(x) - 1（即子树x为黑色）时，反过来就得到
子树x的内节点至少有{ 2^[bh(x)-1] - 1 } 左 + { 2^[bh(x)-1] - 1 } 右 + 1 自己 = 2^bh(x) - 1个
2、证明结论
h表示树的高度
由于性质4，任意两个红色节点不能相邻，
所以从根节点到叶子节点的任意路径中，
至少有一半的节点（不包括根节点）是黑色的。
所以由1可得，根节点的bh至少为h/2，而且，内节点n满足
n >= 2^(h/2) - 1
所以lg(n+1) >= h/2 即 h <= 2lg(n+1)