红黑树性质

红黑树是一棵二叉搜索树，它在每个结点上增加了一个存储位用来表示结点颜色，可以是Red或者Black。通过对任意一条从根到叶子的简单路径上各个结点颜色的约束，红黑树可以确保没有一条路径会比其它路径长出2倍，因而是近似于平衡的。
红黑树满足下面的性质：

1. 每个结点要么是红色的，要么是黑色的。
2. 根结点是黑色的。
3. 每个叶结点（NIL）是黑色的。
4. 如果一个结点是红色的，那么它的两个子结点都是黑色的。
5. 对每个结点，从该结点开始到其所有后代叶结点的简单路径上，包含的黑色结点的数目相同。

树高

定义：从某个结点\(x\)出发（不包含该结点），达到其后代叶节点的简单路径上包含的黑色结点的数目为黑高（black-height），记为\(bh(x)\)，由性质5可知这一定义是明确的。
引理：一棵有n个内部结点（不包含NIL叶结点）的红黑树的高度至多为\(2lg(n+1)\)。
证明： 先证明以\(x\)为根的子树中至少包含\(2^{bh(x)}-1\)个内部结点。这里采用归纳法证明。
当\(x\)的高度为0时，\(x\)是叶结点，黑高\(bh(x)=0\)，所以至少包含\(2^0-1=0\)个内部结点，满足条件。
当\(x\)的高度大于0时，\(x\)的两个子结点的黑高要么为\(bh(x)\)，要么为\(bh(x)-1\)，取决于子结点是红色还是黑色，所以以\(x\)为根的子树至少包含\((2^{bh(x)-1}-1)+(2^{bh(x)-1}-1)+1=2^{bh(x)}-1\)个内部结点。
所以以\(x\)为根的子树中至少包含\(2^{bh(x)}-1\)个内部结点。
为了完成引理的证明，设\(h\)为树的高度，由性质4可知黑高至少为\(\frac{h}{2}\)，于是有：

\[n\ge 2^{\frac{h}{2}}-1 \]

推出

\[h\le 2lg(n+1) \]

即得证