红黑树

一颗二叉查找树如果满足下面的红黑性质,则为一颗红黑树:

1)      每个结点或是红的,或是黑的.

2)      根结点是黑的.

3)      每个叶结点(NIL)是黑的. (孩子结点指向null的结点重定向到NIL)

4)      如果一个结点是红的,则它的两个儿子都是黑的.

5)      对每个结点,从该结点到其子孙结点的所有路径上包含相同数目的黑结点.

由这个定义可知, 红黑树并不是平衡二叉树, 它只是一种近似平衡的二叉搜索树.

我们知道, 在动态构建二叉树的过程中, 一定要避免出现单支树的情况; 因为在那种急坏的情况下, 查找结点的时间复杂度会大大升高. 所以才引出了平衡二叉树, 但是广泛采用的构建平衡二叉树的两种方法各有各的缺点.

一种是利用一个平衡因子的方法: 平衡因子（Balance Factor,BF）定义为该节点的左子树的深度减去其右子树的深度, 则平衡二叉树上所有节点的平衡因子只可能是-1、0和1. 只要树上有一个节点的平衡因子的绝对值大于1, 则该二叉树就是不平衡的了. 利用平衡因子可以快速准确地判断二叉树的平衡状况, 但缺点在于每次插入新结点都要迭代地去更新父结点的平衡因子, 知道根节点.

另一种是利用一个标志位去存储当前的层数: 虽然这种方法操作起来方便, 但是在旋转时需要更新旋转结点的所有子树的标志位, 而且会占用大量的空间去存储这些信息.

所以, 第一种方法需要向上迭代到根, 第二种方法需要向下迭代到叶子. 在较坏情况下的效果都不会好.

而红黑树则没有这些缺点, 它在最坏的情况下也是只需要改变有限的几个结点的颜色.

下面看看红黑树的具体实现:

插入结点:

针对插入新结点, 如果它的父节点是黑色, 这时候不会违背五条性质中的任何一条.

当然, 我们关心的是那种它的父节点是红色的情况, 因为这时候它违背了性质4. 所以必须对树的结构进行一定的调整使其继续满足红黑树的五个性质.

因为要考虑新插入结点的父亲是左孩子还是右孩子, 这些结构在拓扑上是完全对称的, 所以我们只考虑它父亲是左孩子的情况.

需要改变树的结果, 有3×2 = 6种情况:

Case1:

           B

          / 

         R    R

        /   /  

      new

新插入的结点是红的, 它父亲是红的, 它父亲的兄弟也是红的.

违背了性质4, 这时候需要进行一个调整, 使其在满足性质4的情况下而不违背性质5.

染色: 父亲与叔父染成黑的, 爷爷染成红色;

这样从它爷爷的角度去看满足了性质4, 但不能保证整个树满足性质4 (因为爷爷的父亲可能是红色); 但从整棵树的角度去看肯定是满足性质5的, 因为没有在一个分支上加入多余的黑结点.

迭代: 为了保障整棵树的角度满足性质4, 需要将新插入结点的爷爷当作新插入的结点去考虑.

Case2 & Case3:

共同的前提: 新插入的结点是红的, 它父亲是红的, 但它父亲的兄弟是黑的.

我的推论: 这时候它父亲的兄弟是NIL, 即它的爷爷只有它父亲一个孩子. 因为它爷爷有两个孩子, 但左孩子是红色, 而右孩子不是红色, 这必然会违背性质5. 即在插入前, 从它的爷爷出发到它的父亲的叶子节点之间的路径上是没有黑色结点的, 而从它爷爷向着爷爷的右孩子出发到叶子节点之间至少有一个黑色结点. 所以违背了性质5.

Case2:新插入的结点是左孩子.

           B

          / 

         R    B

        /   

      new

Case3:新插入的结点是右孩子.

           B

          / 

         R    B

        /   

          new

对于Case3:对新插入结点的父亲进行左旋,进而转换为Case2.

Case2:违背了性质4,但不违背性质5.

这就要求进行一种旋转保障不违背性质5的前提下修正违背的性质4.

染色: 父亲染为黑的,爷爷染为红的.

旋转: 右旋爷爷.

           B                R               B

          /               /              / 

         R   NIL >   B   NIL >      new  R

        /             /                    / 

    new         new                         NIL

之后即满足了所有的5个性质.

删除结点:

如果被删除的结点是红色的,则当结点被删除后,红黑性质仍然得以保持,理由如下:

a)树中各结点的黑高度都没有变化.

b)不存在两个相邻的红色结点.

c)因为如果该节点是红的,就不可能是根,所以跟仍然是黑色的.

如果被删除的结点是黑色的, 则会产生三个问题

    要删除的结点y，如果y有个不是NIL的孩子，则x为y的唯一孩子；如果y没有孩子，则x为NIL，把x的父节点(原来是y)赋值为y的父节点

①如果y原来是根结点，而y的一个红色的孩子成为了新的根，这就违反了性质2)。

②如果x和p[y](现在也是p[x])都是红的，就违反了性质4)。

③删除y将导致先前包含y的任何路径上黑结点个数少1。因此，性质5)被y的一个祖先破坏了。补救这个问题的一个办法就是把结点x视为还有额外的一重黑色。也就是说，如果将任意包含结点x的路径上黑结点的个数加1，则这种假设下，性质5)成立。当将黑节点y删除时，将其黑色“下推”至其子节点。现在问题就变为结点x可能既不是红，也不是黑，从而违反了性质1)。结点x是双重黑色或红黑，这就分别给包含x的路径上黑结点的贡献2个或1个。x的color属性仍然是red(如果x是红黑的)或者black(如果x是双重黑色)。换言之，一个结点额外的黑色反映在x指向它，而不是他的color属性。

四种情况

Case1:x的兄弟w是红的.

Case2:x的兄弟w是黑的,而且w的两个孩子都是黑的.

Case3:x的兄弟w是黑的,w的左孩子是红色的,右孩子是黑色的.

Case4:x的兄弟w是黑的,而且w的右孩子是红色的.

情况1：x的兄弟w是红色的

因为w必须有黑色的孩子，我们可以改变w和p[x]颜色，再对p[x]做一次左旋，从而红黑性质得以继续保持。现在，x的新兄弟是旋转之前w的某个孩子，其颜色为黑色。这样，我们已经将情况1)转化为情况2), 3)或4)了.

情况2：x的兄弟w是黑色的，而且w的两个孩子都是黑色的

因为w也是黑色的，故从x和w上去掉一重黑色，从而x只有一重黑色而w为红色。为了补偿从x和w中去掉一重黑色，我们想在原来是红色或者黑色的p[x]内新增一重额外的黑色。通过以p[x]为新结点x来恢复while循环。注意如果从情况1进入情况2，则新结点x是红黑色的，因为原来的p[x]是红色的。因此，新结点x的color属性的值c为red，并且在测试循环条件后循环结束。然后新结点x在第23行中被（单独）着为黑色。

情况3：x的兄弟w是黑色的，w的左孩子是红色的，右孩子是黑色的

可以交换w和其左孩子left[w]的颜色，并对w进行右旋，而红黑性质仍然保持。现在x的新兄弟w是一个有红色右孩子的黑节点，这样我们从情况3转换成情况4

情况4：x的兄弟w是黑色的，而且w的右孩子是红色的

通过做某些颜色修改并对p[x]做一次左旋，可以去掉x的额外黑色来把它变成单独黑色，而不破坏红黑性质。将x置为根后，当while循环测试其循环条件时循环结束。

本文参考了：

《算法导论》

《算法导论》笔记－－红黑树（一） http://liyiwen.javaeye.com/blog/345800

《算法导论》笔记－－红黑树（二） http://liyiwen.javaeye.com/blog/345799

抄袭了：

算法导论 红黑树 http://www.886s.com/blog/?p=30