红黑树的原理分析和算法设计
云华00 2015-07-21
红黑树是60年代中期计算机科学界找寻一种算法复杂度稳定，容易实现的数据存储算法的产物。在优先级队列、字典等实用领域都有广泛地应用，更是70年代提出的关系数据库模型--B树的鼻祖。在Linux kernel中，高精度定时器也工作在红黑树之上。为便于初学者掌握其基本算法，本文一步一步地演示了红黑树的创建过程。
首先回顾一下红黑树的基本性质：
1. 红黑树本质上是一个二叉查找树（BST），但是它从根到最远叶子的长度不会超过到最近叶子长度的两倍，因此是近似平衡的。
2. 红黑树的节点不是黑的就是红的，不会有第三种颜色。
3. 树根必须是黑色。
4. 叶子所指的空节点必须是黑色。
5. 如果某个节点是红色，那么它的两个儿子必须都是黑色。
6. 从任意节点出发的所有向下的路径上包含相同个数的黑节点。这个个数我们称为黑高度Bh。
有了上面的认识，我们要从无到有构造一颗红黑树的话，心里就有底了。这个构造的过程可以分两步：
第一步：执行BST的插入算法；
第二步：对节点着色；
第一步不会有什么问题，关键是第二步怎么对节点着色才不会违反红黑树的基本性质；
这是一个难点，我在写这篇文章的时候脑子也卡了一下，节点不多的时候好办，但是如果节点很多了，就必须找到一种普遍适用的算法来处理。通过这两天的观察，我发现这六条性质中最关键的其实是最后一条---从任意结点出发的任意路径黑高度相等！这才是红黑树算法保持近似平衡的精华所在！其它性质要么是这条性质的产物，要么就是为这条性质服务的。
现在我演示一下怎么从无到有生成一棵红黑树。
例如我们有一组数：{9，7，15，6，11，19}，现在按照从左到右的顺序存放在一颗红黑树中。
第一个数是9，很自然地成为了树根，如图：
图-1
每个新节点都默认地被渲染成了红色，为什么要这么做呢？后面我们将会看到它的好处！现在先忽略不谈。
根节点9是红色，这违背了性质3，所以必须改成黑色，如图：
图-2
下一个数字是7，显然要被插入到9的左边，并且这时满足红黑树的所有性质，如图:
图-3
下一个数字是15，要插入到9的右边，并且也满足红黑树的所有性质，如图：
图-4
下一个数字是6，要插入到7的左边，这回似乎有麻烦了，性质5被违背了，如图：
图-5
可能有人会说，那很简单，既然违背了性质5，那我改一下6的颜色不就OK了？
图-6
现在，恭喜你---也走进了我曾经走过的误区：）你的无意之举改变了新增节点路径上面的黑高度，这棵树已经不是红黑树了！
写代码的人都知道，对树的遍历，最简单的方法就是递归，那么树的数学模型就是一个可穷举的递归式。递归式中每一步的正确性都建立在前一步正确的基础之上。现在我们回过头来想想为什么每次插入的新节点都被渲染成红色呢？你肯定猜到了，因为我们要保证红黑树的核心性质--黑高度不发生变化，虽然牺牲了性质5，但这是可以补救的，并且代价很小。再来看看图-5
既然我们不能通过改变新插入节点的颜色来维持红黑树的性质，那么就只好从原来的树结构入手了。
我们注意到新插入的节点的父亲是一个红节点，其叔叔也是一个红节点。那么假如我把它的父亲改成黑色，则恢复了性质5，可是从树根出发的黑高度还是不相等，干脆把它的叔叔也改成黑色吧！结果如下：
图-7
现在它满足红黑树所有的性质。好了，我们继续。
插入数字11和19的过程平淡无奇，不深入探讨，最终的树如图：
图-8
如果现在要插入数字10怎么办？它肯定会是11的左节点：
图-9
明显违背了性质5！难道依葫芦画瓢，把11和19都改成黑色？这样从树根出发的左边路径黑高度还是2，而右边两条路径的黑高度将变成了3，老办法失效了！
图-10
其实不然，改了新增节点的父亲和叔叔的颜色以后，右边路径黑高度全加一，但我们只要把它的爷爷改成红色不就又减去了多出来的黑高度吗？
图-11
如果你认真看到这里，我想你的潜意识一定告诉你---这里存在某种规律等着我们去发现。
让我们再仔细审视一下图-5
在生成树的过程中，我们已经两次遇到类似情况了，归纳一下，这个场景就是：新节点的父亲是红色，叔叔也是红色。
至于别的节点，我们大可不必关心，因为很显然，这个场景是原子的。
我们的处理办法是把7和15渲染成黑色，就像图-7那样，可是因为这是一个普遍适用的场景，所以要做一个扩展：假设在这个原子树的每个节点上还有别的分支。那么图-7就不能保证所有路径的黑高度相等了，即使把9改成红色也无济于事，因为9也许还有父节点，所以也许它的父节点又是红色，这就再次违反了性质5。我最喜欢的作家之一--柯南.道尔，曾说过：“历史就像车轮的辐条，每一根都终将再次转回来。”眼前的场景正是如此---我们设计的原子场景再次出现。
一个清晰的递归算法呈现在我们面前：
1. 新增节点渲染成红色；
2. 如果它的父亲是红色，则违反了性质5；
3. 如果它的叔叔也是红色，则通过同时修改其父亲和叔叔的颜色为黑色来恢复性质5；
4. 如果它的爷爷不是根节点，则有可能在另外的路径上再次违反性质5，于是我们把它的爷爷改成红色；
5. 可是如果他的太爷爷也是红色呢？很自然地，我们重新回到步骤2；
6. 不断循环，直到第二步满足就可以结束。
最后留给感兴趣的同学两个问题：
1. 如果新增节点的父亲是红色，但它的叔叔是黑色，该怎么办？（提示：使用旋转）
2. 有人说，下面这种场景，我设计的算法就失效了，真的吗？（粉色的6是新插入的节点）
