红黑树是一颗二叉搜索树,每个结点包含如下五个属性:color、key、left、right、p,其中color的取值为BLACK或RED,表示该结点的颜色,key表示该结点的值,left、right、p则分别表示该结点的左右结点和父结点,若一个结点不存在子节点或父节点,则将相应的节点指向一个哨兵节点NIL。我们将NIL视为指向红黑树的叶结点(外部结点)的指针,而把带有关键字的结点视为红黑树的内部结点。
红黑树满足以下五个性质:
1、每个结点的颜色必然是红色或黑色。
2、根节点是黑色的。
3、每个叶结点(NIL)是黑色的。
4、如果一个结点是红色的,则它的两个子结点都是黑色的。
5、对每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点。
NIL结点的color属性为BLACK,也即其为黑色,而其他字段可以为任意值。
黑高:从某个结点x出发(不含该结点)到达一个叶结点的任意一条简单路径上的黑色结点的个数,用bh(x)来表示,根据性质5可知,从该结点出发到任意叶结点的简单路径的黑结点个数都相同,因此bh(x)的值对于每个x而言是确定的。
红黑树的黑高:该红黑树的根节点的黑高。
这里介绍几个引理及其证明:
Q:一个有n个内部结点的红黑树的高度至多为2lg(n+1)
A:为证明该命题,首先要证明如下命题:
任一结点x为根的子树至少包含 2^{bh(x)}-1 个内部结点
证明过程如下:
若x的高度为0,则x必为叶结点,那么该子树至少包含 2^{bh(x)}-1=2^0-1=0 个内部结点。
若存在一个高度为正值且有两个子结点的内部结点x,那么每个子结点的黑高必然是bh(x)或bh(x)-1(取决于子结点的颜色),由于x子结点的高度比x本身要低,那么根据假设可知,x子结点至少有 2^{bh(x)-1}-1 个内部结点,即以x为根的子树至少包含 (2^{bh(x)-1}-1)+(2^{bh(x)-1}-1)+1=2^{bh(x)}-1 个内部结点,上述命题得证。
设h为该红黑树的告诉,根据性质4,容易推断,从根结点到叶结点的任何一条简单路径(不包含根结点)上都至少有一半的结点为黑色,则,根的黑高至少为 \frac{h}{2}
因此可以得知: n\geq 2^{\frac{h}{2}}-1 ,或 h \leq 2lg(n+1)
根据该引理就可以得知,红黑树上的查找、求最小值、求最大值、求前驱和求后继操作的时间复杂度均为O(lgn)。
我这里整理了主要部分,剩下的操作细节可以参考《算法导论》第13章的相关说明。