数据结构

红黑树浅析（Java）

零、前言

重新研究HashMap和ConcurrentHashMap时（1.8版本），再一次遇到红黑树概念，以前不太留意，现在简单地理解一下红黑树。

一、性质

红黑树本质上是一种二叉查找树（就是那种可以实现二分查找，时间复杂度为O(logN)的二叉树），而且它解决了二叉查找树可能会退化成链表的缺点（这个就很牜了，不过为了解决退化的问题，红黑树的维护代价也高）。

为了防止退化，红黑树有5个约定：

  1. 根节点只能是黑色
  2. 叶子节点只能是黑色（注意：红黑树的叶子节点和B+树不一样，前者叶子节点中不放数据，后者存放数据）
  3. 任何节点要么是红色，要么是黑色，有点霸道呵
  4. 从任何节点到叶子节都有相同数量的黑色节点
  5. 红色节点只能下挂黑色节点，而黑色节点没有限制，既可以下挂红色，也可以下挂黑色。

从约定4和约定5，可以推导出红黑树中最长路径最多只能是最短路径的2倍（最短的路径必然全是黑色节点，最长的路径必然是间隔一红一黑），在如此严格的约定下，红黑树根本不可能退化成一条贼长的链表。

下面是红黑树的示意图（看起来确实只有红和黑2种颜色哈哈）：

二、增删改查的原理

既然红黑树二叉查找树树，查找与更改与二叉查找树是一样一样的，这里不展开，咱们主要来看一下插入和删除是怎么做的。

2.1 插入操作

插入和二叉查找树也比较类似，只不过是多了调整的过程。首先是找到最合适的节点（插入值比当前节点小则深入左子树，否则深入右子树，除非到了叶子节点），然后再插入到当前节点的左节点或右节点，最后再做调整，比如左旋、右旋和变色。

插入操作的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
// 红黑树节点
@AllArgsConstructor
@Data
class RBTreeNode {
    public static final int RED_COLOR = 0;
    public static final int BLACK_COLOR = 1;

    Integer value;
    int color;
    RBTreeNode parent;
    RBTreeNode leftChild; // 默认当做子节点为null时，子节点为叶子节点
    RBTreeNode rightChild;

    /**
     * 生成根节点
     * @param value
     * @return
     */
    public static RBTreeNode getRootNode(Integer value) {
        return new RBTreeNode(value, BLACK_COLOR, null, null, null);
    }
}

// 红黑树
class RBTree {

    RBTreeNode root;

    void insert(Integer value) {
        if (root == null) {
            root = RBTreeNode.getRootNode(value);
            return;
        }

        // 二分法，找到value父节点
        RBTreeNode destNode = root;
        while (true) {
            if (value < destNode.value && root.leftChild != null) {
                destNode = root.leftChild;
            } else if (value > destNode.value && root.rightChild != null) {
                destNode = root.rightChild;
            }
            break;
        }
        if (value == destNode.value) {
            return;
        }

        RBTreeNode newNode = new RBTreeNode(value, RED_COLOR, destNode, null, null);
        // 插入目标节点
        if (value < destNode.value) {
            destNode.leftChild = newNode;
        } else {
            destNode.rightChild = newNode;
        }

        // 旋转与调色，保证符合红黑树约定
        rotateAndFixColor(newNode);
    }

    private void rotateAndFixColor(RBTreeNode cur) {
        while (cur.parent != null && cur.parent.color == RED_COLOR) {
            RBTreeNode parent = cur.parent;
            // 先讨论父节点是祖父节点到左孩子
            if (parent == parent.parent.leftChild) {
                // 情况1：父节点红色，叔叔节点红色，祖父节点肯定黑色；则父节点、叔节点、祖父节点颜色翻转（翻转之后以祖父节点当做当前节点，重来）
                if (parent.parent.rightChild.color == RED_COLOR) {
                    parent.color = BLACK_COLOR;
                    parent.parent.color = RED_COLOR;
                    parent.parent.rightChild.color = BLACK_COLOR;
                    cur = parent.parent;
                    continue;
                }
                // 情况2：父节点红色，叔节点黑色，当前节点为右子，则当前节点与父节点做左旋（转成情况3）
                else if (parent.parent.rightChild.color == BLACK_COLOR && cur == parent.rightChild) {
                    leftRotate(parent);

                }
                // 情况3：父节点红色，叔节点黑色，当前节点为左子，则父节点与祖父节点换色，且父节点与祖父节点右旋
                else {
                    parent.color = BLACK_COLOR;
                    parent.parent.color = RED_COLOR;
                    rightRotate(parent.parent);
                }
            }
            else {
                // 反转即可
            }
        }
    }

    private void leftRotate(RBTreeNode cur) {
        if (cur == cur.parent.getLeftChild()) {
            RBTreeNode rightChild = cur.rightChild;
            RBTreeNode parent = cur.parent;

            cur.rightChild = rightChild.leftChild;
            rightChild.leftChild.parent = cur;

            parent.leftChild = rightChild;
            rightChild.parent = parent;

            rightChild.leftChild = cur;
            cur.parent = rightChild;
        } else {
            // 反转即可
        }
    }

    private void rightRotate(RBTreeNode parent) {
    }

}
左旋

回忆一下左旋，与平衡树左旋一致，示意图：

左旋的要义在哪里呢？或者说旋转的精髓是什么？
我个人认为，旋转可以用『二把手经验日渐丰富接替一把手，一把手年纪太大退居二线，帮原来的二把手带人才发挥余热』来描述，具体到左旋里面来，当前节点A是一把手，其右子节点B是二把手，右子节点B的左子节点C是人才，B替代A，A退为B的左子节点，C成为A掉右子节点。

右旋

右旋与左旋类似，不展开讲。

插入调整

插入操作中，新增节点永远是红色。为什么是红而不是黑呢？黑色在红黑树中比较关键，毕竟黑节点被用来约束树的高度，从根节点到任意叶子的途中有相同数量的黑节点，而红色约束比较小，毕竟仅需保证父子不是同时为红色即可。如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑节点，这个是很难调整的。但是设为红色节点后，可能会导致出现两个连续红色节点的冲突，那么可以通过颜色调换（color flips）和树旋转来调整。

插入新节点之后，可能会导致整颗红黑树不再符合约定，比如红色节点下挂红色，从任意节点到各个叶子节点途中黑色节点数量不一样，这些问题都需要解决，所以在上面的伪代码中插入逻辑后面有个旋转变色的过程。

经过不断研究与反复试验，人们得出一个结论，在插入新节点后，有3种情况需要做调整：
1.当前节点的父节点是红色，父节点的兄弟（叔叔节点）是红色。
2.当前节点的父节点是红色，叔叔节点是黑色，当前节点是父节点的右孩子。
3.当前节点的父节点是红色，叔叔节点是黑色，当前节点是父节点的左孩子。

下面我们将要插入的节点标为N，N的父节点标为P，N的祖父节点标为G，N的叔父节点标为U，来讨论一下上述3种情况。

情况1：当前节点的父节点是红色，父节点的兄弟（叔叔节点）是红色

由于新增节点是红色，与红色父节点冲突，所以必须想方法解决，这里人们使用颜色翻转的策略，父节点由红变黑，叔叔节点由红变黑，祖父节点由黑变红，如下图所示：

可见经过颜色翻转，N和P不再是相接的红节点，不过有可能G是根节点或G的父节点是红色，所以我们下一步需将G当做N，重新开始处理。

情况2：当前节点的父节点是红色，叔叔节点是黑色，当前节点是父节点的右孩子

（注：在情况2与情况3中，我们假定父节点是祖父节点的左孩子，如果是右孩子，需与情况2、3左右对调）

在情况2中，我们不能使用颜色翻转（因为翻转之后G和U又成为相接的红节点），我们以P为中心执行左旋，让原本右倾斜的相接红节点变成左倾斜，如下图所示：

有好奇的同学会问：你这么做也没解决问题呀，为什么要这样呢？
那是因为我们要把情况2转成情况3，在情况3中彻底解决！所以插入操作一般会执行2次旋转，先左旋再右旋。

情况3：当前节点的父节点是红色，叔叔节点是黑色，当前节点是父节点的左孩子

在这种情况中，我们让父节点P与祖父节点G互相交换颜色，父节点由红变黑，祖父节点由黑变红，然后以祖父节点G为中心执行右旋，让父节点P带领N和G两个红色节点，如下图所示：

二叉查找树 vs 二叉平衡树 vs 红黑树

二叉查找树的插入比较简单，递归地找到最适合的父节点，然后生成父节点的左孩子或右孩子即可。

二叉平衡树的插入，其原理是像二叉查找树那样插入值之后，根据父节点或祖父节点的高度差距，来决定是否左旋右旋（左子树比右子树高2层）或者双旋（左子树自身的右子树比右子树高1层），必须不断循环往上判断，所以有很多次的旋转、很多次的指针调整。

而红黑树呢？一般先左旋再右旋，比较有规律，而且旋转的次数比严格的二叉平衡树较少，性能好一些。

2.2 删除操作

二叉查找树

先回忆下二叉查找树的删除吧。如果被删除节点是叶子节点，那么直接删除即可；如果被删除节点仅有一个孩子，那么用孩子替代被删除的节点就行了（孩子直接替代父亲）；如果被删除节点有2个孩子，那就麻烦了…在有2个孩子的情况下，需要找出被删除节点的直接前驱（中序递归），用前驱顶替被删除节点，然后删除掉前驱（如果不找前驱，那找后继也是可以的）。

二叉平衡树

二叉平衡树的删除与二叉查找树比较类似，先找到被删除的节点，完成删除操作之后，从被删除的节点开始往上调整，不断地旋转，直到根节点为止。

红黑树

分3种情况，被删除节点有2个孩子、只有一个孩子和没有孩子。

2个孩子
如果有2个孩子，那么像二叉查找树一样，用前驱替代，删除前驱，而前驱节点要么没有孩子，要么只有一个孩子，所以被删除节点有2个孩子的情况可以转换为只有1个孩子或没有孩子。

1个孩子
如果只有1个孩子，那么我们根据红黑树约定『到任意节点途中的黑色节点数量相同』，得到结论：被删除节点必定是黑色，且孩子是红色，其它3种组合都不可能存在，比如被删除节点是黑色且孩子节点也是黑色。示例图如下：

这时我们可以把孩子的值拷贝到被删除节点（被删除节点颜色不变），然后放弃孩子节点即可，示例图如下：

红黑树没有孩子的情况分析

在没有孩子的情况下，直接删除最简单，但后续的调整最复杂。
注意：如果被删节点是红色，则我们不需做调整，所以这里讨论到被删除节点均是黑色。

在分析之前，我们再次温习一下红黑树的几个特性：
(1) 每个节点或者是黑色，或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点是黑色。
(4) 如果一个节点是红色的，则它的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

前面我们将”删除红黑树中的节点”大致分为两步，在第一步中”将红黑树当作一颗二叉查找树，将节点删除”后，可能违反”特性(2)、(4)、(5)”三个特性。第二步需要解决上面的三个问题，进而保持红黑树的全部特性。

为了便于分析，我们假设”x包含一个额外的黑色”(x原本的颜色还存在)，这样就不会违反”特性(5)”。为什么呢？
我们知道：删除节点y之后，x占据了原来节点y的位置。 既然删除y(y是黑色)，意味着减少一个黑色节点；那么，再在该位置上增加一个黑色即可。这样，当我们假设”x包含一个额外的黑色”，就正好弥补了”删除y所丢失的黑色节点”，也就不会违反”特性(5)”。 因此，假设”x包含一个额外的黑色”(x原本的颜色还存在)，这样就不会违反”特性(5)”。

现在，x不仅包含它原本的颜色属性，x还包含一个额外的黑色。即x的颜色属性是”红+黑”或”黑+黑”，它违反了”特性(1)”。所以，我们面临的问题，由**解决”违反了特性(2)、(4)、(5)三个特性”转换成了”解决违反特性(1)、(2)、(4)三个特性”**。

我们需要做的就是通过算法恢复红黑树的特性(1)、(2)、(4)，思想是：将x所包含的额外的黑色不断沿树上移(向根方向移动)，直到出现下面的姿态：
① 情况说明：x是“红+黑”节点。
处理方法：直接把x设为黑色，结束。此时红黑树性质全部恢复。为什么能这么做？因为黑色在红黑树中地位很高，而删除一个红色（转为黑）并不会违背约定。
② 情况说明：x是“黑+黑”节点，且x是根。
处理方法：什么都不做，结束。此时红黑树性质全部恢复。
③ 情况说明：x是“黑+黑”节点，且x不是根。
处理方法：这种情况又可以划分为4种子情况。
Case1:x是”黑+黑”节点，x的兄弟节点是红色
Case2:x是“黑+黑”节点，x的兄弟节点是黑色，x的兄弟节点的两个孩子都是黑色
Case3:x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的左孩子是红色，右孩子是黑色的。
Case4:x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的右孩子是红色的，x的兄弟节点的左孩子任意颜色。

红黑树4种特殊情况分析
(Case 1)x是”黑+黑”节点，x的兄弟节点是红色

1.1 现象说明
x是”黑+黑”节点，x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。
1.2 处理策略
(01) 将x的兄弟节点设为“黑色”。
(02) 将x的父节点设为“红色”。
(03) 对x的父节点进行左旋。
(04) 左旋后，重新设置x的兄弟节点。
下面谈谈为什么要这样处理(建议理解的时候，通过下面的图进行对比)：
这样做的目的是将“Case 1”转换为“Case 2”、“Case 3”或“Case 4”，从而进行进一步的处理，既然兄弟节点是红色，兄弟节点有黑色孩子，那就把兄弟黑色孩子借过来，这样就转成其它Case了！怎么做到呢，对x的父节点进行左旋！为了保持左旋后红黑树特性，就需要在左旋前将x的兄弟节点设为黑色，同时将x的父节点设为红色，简单讲就是父亲和兄弟换色；左旋后，由于x的兄弟节点发生了变化，需要更新x的兄弟节点，从而进行后续处理。
1.3 示意图

(Case 2) x是”黑+黑”节点，x的兄弟节点是黑色，x的兄弟节点的两个孩子都是黑色

2.1 现象说明
x是“黑+黑”节点，x的兄弟节点是黑色，x的兄弟节点的两个孩子都是黑色。
2.2 处理策略
(01) 将x的兄弟节点设为“红色”。
(02) 设置“x的父节点”为“新的x节点”。
下面谈谈为什么要这样处理(建议理解的时候，通过下面的图进行对比)：
这个情况的处理思想：是将“x中多余的一个黑色属性上移(往根方向移动)”。 x是“黑+黑”节点，我们将x由“黑+黑”节点 变成 “黑”节点，多余的一个“黑”属性移到x的父节点中，即x的父节点多出了一个黑属性(若x的父节点原先是“黑”，则此时变成了“黑+黑”；若x的父节点原先时“红”，则此时变成了“红+黑”)。 此时，需要注意的是：所有经过x的分支中黑节点个数没变化；但是，所有经过x的兄弟节点的分支中黑色节点的个数增加了1(因为x的父节点多了一个黑色属性)！为了解决这个问题，我们需要将“所有经过x的兄弟节点的分支中黑色节点的个数减1”即可，那么就可以通过“将x的兄弟节点由黑色变成红色”来实现。
经过上面的步骤(将x的兄弟节点设为红色)，多余的一个颜色属性(黑色)已经跑到x的父节点中。我们需要将x的父节点设为“新的x节点”进行处理。若“新的x节点”是“黑+红”，直接将“新的x节点”设为黑色，即可完全解决该问题；若“新的x节点”是“黑+黑”，则需要对“新的x节点”进行进一步处理。
核心原理是黑+黑的节点原来是x，现在变成x的父亲，这样就把额外的黑色不断上移！
2.3 示意图

(Case 3)x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的左孩子是红色，右孩子是黑色的

3.1 现象说明
x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的左孩子是红色，右孩子是黑色的。
3.2 处理策略
(01) 将x兄弟节点的左孩子设为“黑色”。
(02) 将x兄弟节点设为“红色”。
(03) 对x的兄弟节点进行右旋。
(04) 右旋后，重新设置x的兄弟节点。
下面谈谈为什么要这样处理(建议理解的时候，通过下面的图进行对比)：
我们处理“Case 3”的目的是为了将“Case 3”进行转换，转换成“Case 4”,从而进行进一步的处理。转换的方式是对x的兄弟节点进行右旋；为了保证右旋后，它仍然是红黑树，就需要在右旋前“将x的兄弟节点的左孩子设为黑色”，同时“将x的兄弟节点设为红色”；右旋后，由于x的兄弟节点发生了变化，需要更新x的兄弟节点，从而进行后续处理。
目的只是为了让兄弟节点的红左孩子到右边去。
3.3 示意图

(Case 4)x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的右孩子是红色的，x的兄弟节点的左孩子任意颜色

4.1 现象说明
x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的右孩子是红色的，x的兄弟节点的左孩子任意颜色。
4.2 处理策略
(01) 将x父节点颜色 赋值给 x的兄弟节点。
(02) 将x父节点设为“黑色”。
(03) 将x兄弟节点的右子节设为“黑色”。
(04) 对x的父节点进行左旋。
(05) 设置“x”为“根节点”。
下面谈谈为什么要这样处理。(建议理解的时候，通过下面的图进行对比)
我们处理“Case 4”的目的是：去掉x中额外的黑色，将x变成单独的黑色，思路是对x的父节点进行左旋，借一个黑色父亲节点（case1是借黑色兄弟）！。下面，我们来分析是如何实现的。
为了便于说明，我们设置“当前节点”为S(Original Son)，“兄弟节点”为B(Brother)，“兄弟节点的左孩子”为BLS(Brother’s Left Son)，“兄弟节点的右孩子”为BRS(Brother’s Right Son)，“父节点”为F(Father)。
我们要对F进行左旋。但在左旋前，我们需要调换F和B的颜色，并设置BRS为黑色。为什么需要这里处理呢？因为左旋后，F和BLS是父子关系，而我们已知BL是红色，如果F是红色，则违背了“特性(4)”；为了解决这一问题，我们将“F设置为黑色”。 但是，F设置为黑色之后，为了保证满足“特性(5)”，即为了保证左旋之后：
第一，“同时经过根节点和S的分支的黑色节点个数不变”。
若满足“第一”，只需要S丢弃它多余的颜色即可。因为S的颜色是“黑+黑”，而左旋后“同时经过根节点和S的分支的黑色节点个数”增加了1；现在，只需将S由“黑+黑”变成单独的“黑”节点，即可满足“第一”。
第二，“同时经过根节点和BLS的分支的黑色节点数不变”。
若满足“第二”，只需要将“F的原始颜色”赋值给B即可。之前，我们已经将“F设置为黑色”(即，将B的颜色”黑色”，赋值给了F)。至此，我们算是调换了F和B的颜色。
第三，“同时经过根节点和BRS的分支的黑色节点数不变”。
在“第二”已经满足的情况下，若要满足“第三”，只需要将BRS设置为“黑色”即可。
经过，上面的处理之后。红黑树的特性全部得到的满足！接着，我们将x设为根节点，就可以跳出while循环(参考伪代码)；即完成了全部处理。至此，我们就完成了Case 4的处理。理解Case 4的核心，是了解如何“去掉当前节点额外的黑色”。
4.3 示意图