算法导论 红黑树基础知识

红黑树的五个特点：

1.      每个节点颜色或红或黑

2.      根节点是黑色

3.      每个叶节点为黑色（通常为了简便，所有叶子节点都用一个黑节点代替，或者在图中是直接省略）

4.      如果一个节点是红的，那么它的两个字节点一定是黑的

5.      对于任意一个节点，从这个节点出发直到叶子的两条路径上的黑节点的数目相同（对于一般树的情况，则是所有路径上的黑节点数目相同）

概念：

black

定理：

一个有n个节点红黑树的高度不超过2*lg(n+1)。

证明：要证h<=2*lg(n+1)，只要证n>=2h/2 -1，因为

              h(x)<2*bh(x)        x为红节点

              h(x)=2*bh(x)        x为黑节点

所以h(x)<=2*bh(x)

要证n>=2h/2 -1，只要证n>=2bh(x)  -1，用归纳法。

对于只有一个内节点的情况，由性质2可知，black height等于1，n=2bh(x)  -1

令以节点x为根的子树的black height为bh(x)，子树节点总数为n>=2bh(x)  -1

对于x的两个子节点，其black height至少为bh(x)-1，所以两个子树的节点数目之和不少于(2bh(x)-1 -1)+(2bh(x)-1 -1)，再加上根节点，节点总数为(2bh(x)-1 -1)+(2bh(x)-1 -1)+1=2bh(x)  -1

即n>=2bh(x)  -1。而bh(x)>=h(x)/2，所以n>=2h/2 -1。