介绍

　　今天我们来介绍另一种平衡二叉树：红黑树（Red Black Tree），红黑树由Rudolf Bayer于1972年发明，当时被称为平衡二叉B树（symmetric binary B-trees），1978年被Leonidas J. Guibas 和 Robert Sedgewick改成一个比较摩登的名字：红黑树。

　　红黑树和之前所讲的AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。自从红黑树出来后，AVL树就被放到了博物馆里，据说是红黑树有更好的效率，更高的统计性能。不过在我了解了红黑树的实现原理后，并不相信这是真的，关于这一点我们会在后面进行讨论。

　　红黑树和AVL树的区别在于它使用颜色来标识结点的高度，它所追求的是局部平衡而不是AVL树中的非常严格的平衡。之前我们在讲解AVL树时，已经领教过AVL树的复杂，但AVL树的复杂比起红黑树来说简直是小巫见大巫。红黑树是真正的变态级数据结构。

　　首先来一个Silverlight做的红黑树的动画，它有助于帮你理解什么是红黑树。这里需要注意，必须安装Silverlight 2.0 RTW 才能正常运行游戏，下载地址：

　　http://www.microsoft.com/silverlight/resources/install.aspx?v=2.0

　　使用注意事项：

　　l　　　　 结点只接收整数，如果在添加和删除操作中输入非法字串，则会随机添加或删除一个0~99之间的整数。

　　l　　　　 可以不在编辑框中输入数字，直接单击添加和删除按钮进行添加和删除操作。

　　l　　　　 可以拖动拖动条控制动画速度。

　　红黑树的平衡

　　红黑树首先是一棵二叉查找树，它每个结点都被标上了颜色（红色或黑色），红黑树满足以下5个性质：

　　1、 每个结点的颜色只能是红色或黑色。

　　2、 根结点是黑色的。

　　3、 每个叶子结点都带有两个空的黑色结点（被称为黑哨兵），如果一个结点n的只有一个左孩子，那么n的右孩子是一个黑哨兵；如果结点n只有一个右孩子，那么n的左孩子是一个黑哨兵。

　　4、 如果一个结点是红的，则它的两个儿子都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。

　　5、 对于每个结点来说，从该结点到其子孙叶结点的所有路径上包含相同数目的黑结点。

　　红黑树的这5个性质中，第3点是比较难理解的，但它却非常有必要。我们看图1中的左边这张图，如果不使用黑哨兵，它完全满足红黑树性质，结点50到两个叶结点8和叶结点82路径上的黑色结点数都为2个。但如果加入黑哨兵后（如图1右图中的小黑圆点），叶结点的个数变为8个黑哨兵，根结点50到这8个叶结点路径上的黑高度就不一样了，所以它并不是一棵红黑树。

　　要看真正的红黑树请在以上动画中添加几个结点，看看是否满足以上性质。

　　红黑树的旋转操作

　　红黑树的旋转操作和AVL树一样，分为LL、RR、LR、RL四种旋转类型，差别在于旋转完成后改变的是结点的颜色，而不是平衡因子。旋转动画演示请参考AVL这篇文章中的Flash动画：

　　http://www.cnblogs.com/abatei/archive/2008/11/17/1335031.html

　　红黑树上结点的插入

　　在讨论红黑树的插入操作之前必须要明白，任何一个即将插入的新结点的初始颜色都为红色。这一点很容易理解，因为插入黑点会增加某条路径上黑结点的数目，从而导致整棵树黑高度的不平衡。但如果新结点父结点为红色时（如图2所示），将会违返红黑树性质：一条路径上不能出现相邻的两个红色结点。这时就需要通过一系列操作来使红黑树保持平衡。

　　为了清楚地表示插入操作以下在结点中使用“新”字表示一个新插入的结点；使用“父”字表示新插入点的父结点；使用“叔”字表示“父”结点的兄弟结点；使用“祖”字表示“父”结点的父结点。插入操作分为以下几种情况：

　　1、黑父

　　如图3所示，如果新点的父结点为黑色结点，那么插入一个红点将不会影响红黑树的平衡，此时插入操作完成。红黑树比AVL树优秀的地方之一在于黑父的情况比较常见，从而使红黑树需要旋转的几率相对AVL树来说会少一些。

　　2．红父

　　如果新点的父结点为红色，这时就需要进行一系列操作以保证整棵树红黑性质。如图3所示，由于父结点为红色，此时可以判定，祖父结点必定为黑色。这时需要根据叔父结点的颜色来决定做什么样的操作。青色结点表示颜色未知。由于有可能需要根结点到新点的路径上进行多次旋转操作，而每次进行不平衡判断的起始点（我们可将其视为新点）都不一样。所以我们在此使用一个蓝色箭头指向这个起始点，并称之为判定点。

　　2.1 红叔

　　当叔父结点为红色时，如图4所示，无需进行旋转操作，只要将父和叔结点变为黑色，将祖父结点变为红色即可。但由于祖父结点的父结点有可能为红色，从而违反红黑树性质。此时必须将祖父结点作为新的判定点继续向上进行平衡操作。

　　需要注意，无论“父”在“叔”的左边还是右边，无论“新”是“父”的左孩子还是右孩子，它们的操作都完全一样。

　　2.2 黑叔

　　当叔父结点为黑色时，需要进行旋转，以下图示了所有的旋转可能

　　情形1：

　　情形2：

　　情形3：

　　情形4：

　　可以观察到，当旋转完成后，新的旋转根全部为黑色，此时不需要再向上回溯进行平衡操作，插入操作完成。需要注意，上面四张图的“叔”、“1”、“2”、“3”结点有可能为黑哨兵结点。

　　其实红黑树的插入操作不是很难，甚至比AVL树的插入操作还更简单些。但删除操作就远远比AVL树复杂得多，下面就介绍红黑树的删除操作。

　　红黑树上结点的删除

　　红黑树本身是一棵二叉查找树，它的删除和二叉查找树的删除类似。首先要找到真正的删除点，当被删除结点n存在左右孩子时，真正的删除点应该是n的中序遍在前驱，关于这一点请复习二叉查找树的删除。如图9所示，当删除结点20时，实际被删除的结点应该为18，结点20的数据变为18。

　　所以可以推断出，在进行删除操作时，真正的删除点必定是只有一个孩子或没有孩子的结点。而根据红黑树的性质可以得出以下两个结论：

　　1、删除操作中真正被删除的必定是只有一个红色孩子或没有孩子的结点。

　　2、如果真正的删除点是一个红色结点，那么它必定是一个叶子结点。

　　理解这两点非常重要，如图10所示，除了情况(a)外，其他任一种况结点N都无法满足红黑树性质。

　　在以下讨论中，我们使用蓝色箭头表示真正的删除点，它也是旋转操作过程中的第一个判定点；真正的删除点使用“旧”标注，旧点所在位置将被它的的孩子结点所取代（最多只有一个孩子），我们使用“新”表示旧点的孩子结点。删除操作可分为以下几种情形：

　　1、旧点为红色结点

　　若旧点为红色结点，则它必定是叶子结点，直接删除即可。如图11所示

　　2、一红一黑

　　当旧点为黑色结点，新点为红色结点时，将新点取代旧点位置后，将新点染成红色即可（如图12所示）。这里需要注意：旧点为红色，新点为黑色的情况不可能存在。

　　3、双黑

　　当旧点和新点都为黑色时（新点为空结点时，亦属于这种情况），情况比较复杂，需要根据旧点兄弟结点的颜色来决定进行什么样的操作。我们使用“兄”来表示旧点的兄弟结点。这里可分为红兄和黑兄两种情况：

　　3.1 红兄

　　由于兄弟结点为红色，所以父结点必定为黑色，而旧点被删除后，新点取代了它的位置。下图演示了两种可能的情况：

　　红兄的情况需要进行RR或LL型旋转，然后将父结点染成红色，兄结点染成黑色。然后重新以新点为判定点进行平衡操作。我们可以观察到，旋转操作完成后，判定点没有向上回溯，而是降低了一层，此时变成了黑兄的情况。

　　3.2 黑兄

　　黑兄的情况最为复杂，需要根据黑兄孩子结点（这里用“侄”表示）和父亲结点的颜色来决定做什么样的操作。

　　3.2.1 黑兄二黑侄红父

　　如图14所示，这种情况比较简单，只需将父结点变为黑色，兄结点变为黑色，新结点变为黑色即可，删除操作到此结束。

　　3.2.2黑兄二黑侄黑父

　　如图15所示，此时将父结点染成新结点的颜色，新结点染成黑色，兄结点染成黑色即可。当新结点为红色时，父结点被染成红色，此时需要以父结点为判定点继续向上进行平衡操作。

　　3.2.3 黑兄红侄

　　黑兄红侄有以下四种情形，下面分别进行图示：

　　情形1：

　　情形2：

　　情形3：

　　情形4：

　　由以上图例所示，看完以上四张图的兄弟有可能会有一个疑问，如果情形1和情形2中的两个侄子结点都为红色时，是该进行LL旋转还是进行LR旋转呢？答案是进行LL旋转。情形3和情形4则是优先进行RR旋转的判定。

　　红黑树的代码实现

　　本以为红黑树的代码非常容易，因为System.Collections.Generic.SortedDictionary类就是使用红黑树实现的，把代码的算法部分抠出来就搞定了。但看了SortedDictionary源码后有些失望，C#中真正实现红黑树的是TreeSet类，SortedDictionary只是在TreeSet的基础上进一步抽象，加上了Key/Value泛型对。TreeSet使用了一种新的红黑树算法，它在搜索插入点和删除点时预先进行旋转和染色操作，从而避免插入和删除后的回溯。这种算法看上去很美，但仔细想想，如果插入的是一个已经存在的结点，删除的结点并不存在，那这些预平衡处理不是白做了吗？更可怕的是如果在一条路径上间隔进行一次插入和一次删除，而这些操作没有命中目标，那么大家就会看到结点的颜色变来变去，这些都是无用功。来看看在寻找插入和删除点的路径上TreeSet每前进一步都要做些什么：给四个变量赋值；判断每个结点的两个孩子结点的颜色。这种算法在《java数据结构和算法》这本书中有详细讲述，不过只讲解了插入算法。另外国内也专门有一篇论文描述这个算法，他的测试结果是这种算法优于其他算法，估计测试时没有不命中目标的情况发生。总之我并不相信这是一个好的算法。

　　为了证实我的想法，我不得不自己实现红黑树，实现思路跟AVL树很类似，也是使用一个数组保存访问路径以进行回溯，当然，考虑到红黑树不严格的平衡，数组的长度设为64，这并不会给性能带来什么影响。过程很艰辛，需要做大量测试。很不幸，写完后继续做红黑树的Silverlight动画时不小心把原来的代码给覆盖掉了，结点删除部分的代码丢失。当时几乎崩溃，不过重写并没有我想象的那么困难，很快完成，感觉思路清晰了很多，实现比原来也有了改进，感谢上帝！

　　3、 每个叶子结点都带有两个空的黑色结点（被称为黑哨兵），如果一个结点n的只有一个左孩子，那么n的右孩子是一个黑哨兵；如果结点n只有一个右孩子，那么n的左孩子是一个黑哨兵。

　　4、 如果一个结点是红的，则它的两个儿子都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。

　　5、 对于每个结点来说，从该结点到其子孙叶结点的所有路径上包含相同数目的黑结点。

　　红黑树的这5个性质中，第3点是比较难理解的，但它却非常有必要。我们看图1中的左边这张图，如果不使用黑哨兵，它完全满足红黑树性质，结点50到两个叶结点8和叶结点82路径上的黑色结点数都为2个。但如果加入黑哨兵后（如图1右图中的小黑圆点），叶结点的个数变为8个黑哨兵，根结点50到这8个叶结点路径上的黑高度就不一样了，所以它并不是一棵红黑树。

　　要看真正的红黑树请在以上动画中添加几个结点，看看是否满足以上性质。

　　红黑树的旋转操作

　　红黑树的旋转操作和AVL树一样，分为LL、RR、LR、RL四种旋转类型，差别在于旋转完成后改变的是结点的颜色，而不是平衡因子。旋转动画演示请参考AVL这篇文章中的Flash动画：

　　http://www.cnblogs.com/abatei/archive/2008/11/17/1335031.html

　　红黑树上结点的插入

　　在讨论红黑树的插入操作之前必须要明白，任何一个即将插入的新结点的初始颜色都为红色。这一点很容易理解，因为插入黑点会增加某条路径上黑结点的数目，从而导致整棵树黑高度的不平衡。但如果新结点父结点为红色时（如图2所示），将会违返红黑树性质：一条路径上不能出现相邻的两个红色结点。这时就需要通过一系列操作来使红黑树保持平衡。