算法:什么是红黑树?（红黑树的算法）

写这篇红黑树算法的目的：一是为了自己学习的总结；二是能够与大家一起交流沟通一起努力。

文中有些内容学习自《算法导论》一书，部分来自于维基百科，我会在文中标注出来，有不明白的地方可以通过留言大家一起沟通。

首先，什么是红黑树呢？ 红黑树是一种“平衡的”二叉查找树，它是一种经典高效的算法，能够保证在最坏的情况下动态集合操作的时间为O（lgn）。红黑树每个节点包含5个域，分别为color,key,left,right和p。 color是在每个节点上增加的一个存储位表示节点的颜色，可以是RED或者BLACK。key为结点中的value值，left,right为该结点的左右孩子指针，没有的话为NIL，p是一个指针，是指向该节的父节点。如下图（来自维基百科）表示就是一颗红黑树，NIL为指向外结点的指针。（外结点视为没有key的结点）

红黑树有什么性质呢？一般称为红黑性质，有以下五点：

1）每个结点或者是红的或者是黑的；

2）根结点是黑的；

3）每个叶结点（NIL）是黑的；

4）如果一个结点是红的，则它的两个孩子都是黑的；

5）对每个结点，从该结点到其他其子孙结点的所有路径上包含相同数目的黑结点。

为了后面的分析，我们还得知道以下知识点。

（1）黑高度：从某个结点x出发（不包括该结点）到达一个叶结点的任意一条路径上，黑色结点的个数称为该结点x的黑高度。

（2）一颗有n个内结点的红黑树的高度至多为2lg(n+1)。 （内结点视为红黑树中带关键字的结点）

（3）包含n个内部节点的红黑树的高度是 O(log(n))。

证明（来自维基百科）：

定义:

• h(v) = 以节点v为根的子树的高度。

• bh(v) = 从v到子树中任何叶子的黑色节点的数目(如果v是黑色则不计数它)(也叫做黑色高度)。

引理: 以节点v为根的子树有至少2bh(v) ? 1个内部节点。

引理的证明(通过归纳高度):

基础: h(v) = 0

如果v的高度是零则它必定是 nil，因此 bh(v) = 0。所以:

2bh(v) ? 1 = 20 ? 1 = 1 ? 1 = 0

归纳假设: h(v) = k 的v有 2bh(v) ? 1 ? 1 个内部节点暗示了 h(v') = k+1 的v'有2bh(v') ? 1 个内部节点。

因为 v' 有 h(v') > 0 所以它是个内部节点。同样的它有黑色高度要么是 bh(v') 要么是 bh(v')-1 (依据v'是红色还是黑色)的两个儿子。通过归纳假设每个儿子都有至少2bh(v') ? 1 ? 1 个内部接点，所以v' 有:

2bh(v') ? 1 ? 1 + 2bh(v') ? 1 ? 1 + 1 = 2bh(v') ? 1

个内部节点。

使用这个引理我们现在可以展示出树的高度是对数性的。因为在从根到叶子的任何路径上至少有一半的节点是黑色(根据红黑树属性4)，根的黑色高度至少是h(root)/2。通过引理我们得到:

因此根的高度是O(log(n))。

到这里，红黑树基本的概念理解就到一段落。