红黑树02——基本属性与旋转.md

0. 前言

前文我们提到过，红黑树是一种平衡搜索树，即它源于二叉搜索树。它通过额外引入的5条规则（有的书上浓缩成了3条）来维持二叉树的平衡。另外，又因为它并不要求绝对平衡，所以操作效率比其他树要高效得多，也正是因为如此，红黑树在工业界应用范围较广。本文代码是用Java写的，大家可以看一下ConcurrentHashMap的源码，里面用到了红黑树来解决键冲突的问题。

红黑树的核心是维护结点的红黑颜色平衡，这是本文要探讨的重点。

这个系列的红黑树讲解中，代码实现基本源于《算法导论》上的伪码。请大家对比着看就好了。特别强调一下：用nil来替代null，使之成为一个真正的对象，能极大地简化边界的处理，一定要仔细体会其中的妙处。

1. 红黑树的属性

1. 每个结点不是红色就是黑色。
2. 根结点是黑色。
3. 每个叶子结点是黑色。
4. 不允许两个连续的红色结点（某个结点为红色，它的两个子结点为黑色）。
5. 从根到每个叶子结点的路径上，黑色结点的个数相等。

1和3当成不成文的规则，不需要在代码里面特别维护，所以我们可以去掉，修改成3规则版本（因为数量少，记忆方便）。另外还有一个事实——结点刚插入时统一为红色，没有体现在这些属性里面。

1.1 三规则版本

1. 不允许两个连续的红色结点。
2. 从根到每个叶子结点的路径上，黑色结点的个数相等。
3. 根是黑色的。

1.2 示例

图1-错误红黑树示例

上图中的3棵树都不是合法的红黑树。第1棵，根结点不是黑色的；第2棵右边黑色结点多1个；第3棵有两个连续的红色结点。

2. 树的旋转

旋转的目的：用来调整某一侧黑色结点数目的不平衡。
《算法导论》说：左旋以x到y的链为『支轴』进行。它使y成为该子树新的根结点，x成为y的左孩子，y的左孩子成为x的右孩子。反正我是记不住，所以才有本文的存在。
旋转有左旋和右旋，它们是对称的关系，所以这里只讨论一种。

图2-左旋结点1

将图2右边子树的结点1左旋，可得到左边的子树。注意，图2中的树并不是合法的红黑树，这里只是用来演示旋转的效果。我们来看几个东西：

1. 树的旋转，没有影响搜索树的性质：比父结点小的在左子树、比父结点大的在右子树。
2. 旋转可以使子树的某一侧多一个某颜色的结点，同时不减少另一侧该颜色的结点数量。我们看图2的右边子树，结点1的右边比左边多了一个黑色，旋转之后，黑色上升到根部，左边多了1个黑色结点，同时右边还是1个黑色并没有减少。正因为如此，当树中黑色结点不平衡时，我们会通过旋转来调整黑色结点数目。
3. 旋转操作到底是怎样做的呢？图2的例子中，我们可以想象1和它的右孩子3，围绕图中标示的正方形中间的蓝点，往左边方向（逆时针）旋转90度。旋转之后我们还需要处理子结点：1的右孩子原来是3，旋转之后空出来了，而3的左孩子2的位置被1霸占了，所以我们把2挂在1的右侧。

3. 旋转练习

下面放几个树的插入与删除过程需要旋转的示例，请大家认真练习一下，然后观察旋转之后树的红黑结点有什么变化。只有熟练掌握了旋转，之后在讲插入与删除时树的调整，才能更好地理解和掌握。需要旋转的结点在图标题上会注明，下一幅图就是答案，在看答案之前，请自己先试着做一遍。

图3-请左旋结点4 图4-请右旋结点9

注意：在左旋结点4之后，这里额外把8和9的颜色修改了，这是插入调整中的某一步，先不管它，继续练习旋转即可。调整之后注意看左右子树黑色结点的数目哦！

图5-新平衡状态下的红黑树

下图是某个删除过程的一个中间态，请左旋结点3.

图5-请左旋结点3 图6-左旋3后达到新平衡

左旋3之前，右边的每条路径比左边的每条路径多1个黑色结点，通过左旋结点3，使黑色结点5上升到根部，从而达到新的平衡。

4. 旋转的代码实现

    private void rotateLeft(Node x) {
        Node y = x.right;

        x.right = y.left;
        if (y.left != nil) {
            y.left.parent = x;
        }

        Node parent = x.parent;
        y.parent = parent;

        if (parent == nil) {
            root = y;
        } else if (parent.left == x) {
            parent.left = y;
        } else {
            parent.right = y;
        }

        y.left = x;
        x.parent = y;
    }

    private void rotateRight(Node x) {
        Node y = x.left;

        x.left = y.right;
        if (y.right != nil) {
            y.right.parent = x;
        }

        Node parent = x.parent;
        y.parent = parent;

        if (parent == nil) {
            root = y;
        } else if (parent.left == x) {
            parent.left = y;
        } else {
            parent.right = y;
        }

        y.right = x;
        x.parent = y;
    }

5. 结语

之前在学校的时候，发现自己和许多的同学都弄不懂红黑树是怎么一回事，永远搞不懂为什么插入有3种情况、删除有4种情况，别提记住了，更别提能把代码写出来了。本文就是为后面的理解打好基础。

通过本文的练习，想必大家对旋转的原理、旋转的步骤、旋转的效果都掌握得比较清楚了，下一章我们将正式进入红黑树的难点——插入与删除。

源码

https://github.com/readyou/algorithm-introduction-code/blob/master/src/main/java/me/wxl/demo/data/struct/RedBlackTree.java

作者微信

wx.png

转载声明

如果您需要转载，请注明转载来源。