Tubetrue01
0%

从 TreeMap 源码剖析红黑树（下）删除

发表于 更新于

引言

本篇文章作为红黑树的最后一篇文章，介绍红黑树的删除操作，也是最难的一部分。我们话不多说，直接进入正题。

2-3-4 树的删除

我们知道红黑树的本质是 2-3-4 树，所以在介绍红黑树的删除操作前，需要先了解 2-3-4 树的删除操作。

上图是一棵 2-3-4 树，其中包含了 2 节点、3 节点、4 节点。接下来我们逐个分析下对每种节点的删除。

三节点的删除

如图 1 所示，其中（1、2），（8、9），（7、10）为三节点。但是对于它们的删除其实是不同的。首先（1、2）、（8、9）作为叶子节点，我们可以删除任意一个元素而不破坏树的平衡。

但是对于（7、10）而言，对于 7、10 任意元素的删除都会使其变成二节点，那么此时树的平衡被打破，就需要进行调整，如图所示：

当 7 被删除时，树的平衡被破坏，此时必须要找到一个可以替换它的节点。所以沿着它的右子树寻找，找到 8 之后，变把 8 的值替换掉被删的 7。然后删掉 8，此时树又恢复平衡了。

为什么不是用 6 替换 7 而是 8 呢？原因很简单，因为 6 是一个二节点，而（8、9）是一个三节点。用 8 替换 7 的成本是最低的。也就是说它会优先选择非二节点的子节点中的元素来替换自己。不信？我们看下图：

我们删除 4，在分析 4 的两个子节点时发现 3 是二节点，5 是四节点，那不用说还是选择 5 替换自己吧。然后在把 5 替换成自身之后，把它删了。

但是，那如果子节点都是二节点的情况呢？我们看下图：

我们继续删除元素 8。此时 8 的两个子节点都是单节点。如果此时删除 8 时，它会发现 8 的两个子节点都是单节点，那就把 6、8、9 合并成，然后删除 8 。其实也就是把 8 的两个子节点进行合并。

四节点删除

三节点分析完了，我们继续分析四节点的删除，当然作为叶子节点的删除情况就不再赘述了，因为不涉及平衡问题，直接删就对了。

删除 2 时，会对 2 的两个子树进行分析，如果都是单子节点，那么就会将 2 跟它的两个子节点合并，再删除 2。

对于 4 的删除与 2 类似，就不再赘述。

对于 6 的删除其实原理都是一样的，会从它的子节点中进行选择，如果是三、四节点那么就用子替换自己，如果是二节点，那么就会将两个子节点进行合并。

二节点删除

其实理解了三节点、四节点的删除之后，二节点的删除也大同小异，但我觉得还是再举一个不同的例子介绍一下吧。

2 作为二节点，没错，它就是我们本次的删除对象。分析了一下，2 有两个单子节点，运用我们之前学过的知识，1、2、3 合并，然后删除 2，于是就得到了下面的结果：

2 已经顺利删除了，但是看这棵树怎么感觉这么别扭？1、3 组成的三节点是 4 的左节点与 6 平级了，但是 6 还有下一级。好像出错翻车了。。。

我们回想一下三节点、四节点，之所以行得通是因为它们并不是孤单一人。但二节点删除了就真的没了。所以就不能直接删除，那么到底怎么删除我们看下图：

节点 2 会向上分析它的父跟兄弟节点，发现可以组合，那么 2、4、6 会组合成四节点。至此你会发现，2 不再是孤单一人，就可以运用之前的知识，对 2 的两个子进行合并，然后删除 2。

当然也会遇到无法合并的场景，如下图：

由于 6、8 是三节点，所以 2、4 无法跟 6、8 再组合了。那此时如何处理呢？显然自己的孩子是帮不了自己了，那么只能向自己的老父亲求助了，我们看下图：

此时 4 会下来跟 2 合并，但是 4 的位置不能空着，所以作为 4 的右孩子 6 就会顶替 4 的位置。此时 2 跟 4 合并之后，就跟之前的场景一样了。

总结

2-3-4 树的删除就全部介绍完了，为什么花大篇幅的介绍 2-3-4 树就是要想弄懂红黑树就一定要先搞懂 2-3-4 树。所以有了以上的基础，我们再来看红黑树就简单多了。

红黑树的删除

终于开始红黑树了，我想你一定等不及了。在开始之前，还是先啰嗦一句，对于红黑树的删除操作，一定都是发生在 2-3-4 树的叶子节点上的，从上文的 2-3-4 树就可以得知。

删除方式

红黑树的删除需要记住的是并不会真正的将当前节点删除掉，而是查找对应的子节点，利用子节点的值替换删除节点的值，然后将子节点删除掉。以此达提高删除的效率，降低删除成本。

从 2-3-4 树的删除中，我们可以得知，在删除目标节点之前，会查找可以替换自己的子子节点。但是，如果同时存在两个节点时，应该选择哪个呢？如果选择左节点，我们称为前驱删除，如果选择后继节点，我们称为后继删除。TreeMap 采用了后继的删除方式，网站【Data Structure Visualizations】 则是采用的前驱删除。

前驱删除

所谓前驱删除，就是查找小于当前值的最大值。

如图所示，如果删除元素 5，采用前驱删除法，那么从 5 的左节点开始，一直向右子节点查询，直到元素 4。

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
/**
 * 查询 t 节点的前驱节点，也就是找到比 t 小的最大值
 *
 *       5 (t)       5 (t)         5 (t)
 *      / \         / \           / \
 *     3   8  ->  (3)  8   ->    3   8
 *    / \         / \           / \
 *   1   4       1   4         1  (4)
 */
private static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.left != null){
        // 从左节点开始找
        Entry<K, V> l = t.left;
        while(l.right != null){
            l = l.right;
        }
        return l;
    }else {
        /*
         *  这里是另外一种特殊的场景，也就是说，t 没有左子树那就需要顺着 t 的父向上找
         *
         *             5            (p) 5       (ch) 5     p = null
         *            / \              / \          / \
         *       (p) 3   8   ->  (ch) 3   8   ->   3   8
         *          / \              / \          / \
         *  (t,ch) 2   4        (t) 2   4    (t) 2   4
         * ===========================================
         *            5                5
         *           / \              / \
         *      (p) 3   8   ->      (3)  8
         *         / \              / \
         *        2   4 (t,ch)     2   4 (t)
         */
        Entry<K, V> p = t.parent;
        Entry<K, V> ch = t;
        while(p != null && ch == p.left){
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

后继删除

后继删除就是查找大于当前值的最小值。

如图所示，如果采用后继删除法，会沿着 5 的右节点开始，一直向左子节点查询，直到元素 7。

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
/**
 * 查询 t 节点的后继节点，也就是比 t 大的最小值
 *
 *       5 (t)       5 (t)         5 (t)
 *      / \         / \           / \
 *     3   8  ->   3  (8)   ->   3   8
 *        / \         / \           / \
 *       7   9       7   9        (7)  9
 */
private static <K,V> Entry<K,V> successor(Entry<K,V> t) {
    if(t == null) return null;
    // 如果 t 还右子树，那么顺着右子树找到大于 t 的最小值
    else if (t.right != null) {
      Entry<K, V> r = t.right;
      while(r.left != null){
          r = r.left;
      }
      return r;
    }else {
        /*
         *  这里是另外一种特殊的场景，也就是说，t 没有右子树，那就需要顺着 t 的父向上找
         *
         *             5              5
         *            / \            / \
         *       (p) 3   8   ->    (3)  8
         *          / \            / \
         *  (t,ch) 2   4      (t) 2   4
         * ===========================================
         *            5            (p) 5            (5)
         *           / \              / \           / \
         *      (p) 3   8   ->  (ch) 3   8  ->     3   8
         *         / \              / \           / \
         *        2   4 (t,ch)     2   4 (t)     2   4 (t)
         */
        Entry<K, V> p = t.parent;
        Entry<K, V> ch = t;
        while(p != null && ch == p.right){
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

无论是前驱删除还是后继删除，都会存在另外一种没有子节点的情况，也就是对应代码中的 else，当然了，如果是删除操作，是不会遇到这种情况的。我们看下图：

如果查找元素 4 的前驱或者后继，我们发现它根本没有子节点。那么也就是说 4 没有前驱或者后继节点了吗？那肯定不是，毕竟图中的 3 跟 5 已经很明显的告诉你了，它们就是 4 的前驱及后继。

针对这种场景，我们需要变换个方向，向父节点方向查找就行了。如图：

删除开始

为了将删除操作简单化，我们还是以图例的方式，将涉及到的场景列出来，即使代码注释中已经存在了。

场景一 删除节点有两个子

节点 5 是目标删除节点也就是图中的 p。首先，按照后继删除法，找到 p 的后继节点 7（图中的 s）。然后将 s 的 key、val 替换掉节点 p。同时 p 指向 s。再找到 p 的子节点 replacement。此时你可能会有疑问，如果此时的 p 有两个子节点呢？不可能，为什么？因为如果 p 有两个子节点，那么查找后继的过程中，p 的左节点一定是 s，而不是现在的 p 了。

找到 replacement 之后，我们需要把它的指向 p 的父节点，然后将 p 的父节点指向 replacement。最后断开 p 的双向指针，等系统回收。

最后我们发现 8、9 两个红色相连了，不要紧，我们这次只是删除。树的调平工作交给其他方法来做（这也是单一职责的一种体现）。问题来了，怎么判断是否需要调平衡呢？其实只需要知道 p 的颜色就行了。只有 p 为黑色时，才需要调平衡。

场景二 删除节点有一个子

如果删除节点为根节点的话，那么直接让子节点成为新的根即可，然后进行调平。

当删除节点 p 时，它只有一个子 replacement，此时直接修改 replacement 的指向以及断开 p 即可。

场景三 删除节点没有子

如果删除节点没有任何子节点时，说明它是叶子节点。首先需要根据它的颜色来判断是否需要调整。然后再将其与父的双向指针断开即可。

场景四 删除节点是根

如果删除的节点没有任何子，同时它又是根时，只需要把它置空即可。

有了以上的基础，我们再来看代码实现就简单明了了：

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
/**
 * 比如删除 5 元素，那么可以采用后继或者前驱的方式找到节点，替换 5 元素。
 * 这里按照 TreeMap 采用后继的方式删除，也就是说找到比 5 大的最小值，这里是 7。
 *     (p) 5                   7
 *        (黑)                (黑)
 *        / \                 / \
 *       3   9               3   9
 *     (黑)  (红)    ->     (黑)  (红)
 *      /    / \            /    / \
 *     2    7   10         2    7   10
 *   (红)  (黑)  (黑)     (红)  (黑)  (黑)
 *          \                  (p)
 *           8                   \
 *          (红)                  8
 *                               (红)
 *                              (replacement)
 *
 */
private void deleteEntry(Entry<K,V> p) {
    // 如果 p 有两个子节点
    if (p.left != null && p.right != null) {
        Entry<K, V> s = successor(p);
        p.k = s.k;
        p.v = s.v;
        p = s;
    }

    Entry<K, V> replacement = p.left != null ? p.left : p.right;

    if (replacement != null){
        // 先修改父的指向
        replacement.parent = p.parent;

        /*
         *     5 (p)
         *    /
         *   3 (replacement)
         */
        if (p.parent == null)
            root = replacement;
        else if(p == p.parent.left)
            p.parent.left = replacement;
        else 
            p.parent.right = replacement;
        
        p.left = p.right = p.parent = null;
        // 如果删除掉的节点是黑色的，那么就需要调整平衡了
        if (p.color = BLACK)
            fixAfterDeletion(replacement);
        
    }
    // 如果当前节点的父节点为 null，说明是根节点。因为既没有子又没有父，那肯定是根无误了
    else if (p.parent == null){
       root = null;
    } else {
        /*
         *    5
         *   /
         *  2（p）
         */
        // 到这里说明替换的节点是叶子节点，直接删就对了。
        if (p.color == BLACK)
            fixAfterDeletion(p);
        // 经过调整之后，判断当前 p 的父节点是否为 null
        if (p.parent != null){
            if (p == p.parent.left)
                p.parent.left = null;
            else if (p == p.parent.right)
                p.parent.right = null;
            p.parent = null;
        }
    }

}

读到这里，你可能发现红黑树的删除也不过如此，与 2-3-4 树的删除其实就是一回事（本文为了保证内容的连贯性，并没有做两者的等价关系）。如果你是这么想的，那么你可能太乐观了，因为重头戏马上就来了！

树的调整

对目标节点删除之后，我们就需要根据情况来选择是否进行调整了。从删除的逻辑中我们可以得知只有删除的节点时黑色的时候才需要调整。

场景一 目标节点为根节点

这个没什么好说的了，直接染黑就行了。

场景二 目标节点为红色

上图是双节点的删除操作的最终状态，此时 x 节点并非根节点，同时它又是红色，我们从图中就能看出，只要将其染成黑色就行了。

上图是针对于单节点删除的最终状态，我们只需要对 x 染黑即可完成树的平衡。

场景三 兄弟节点不可借

以上红黑树，我们需要删除节点 4 作为本次场景的起点，注意：节点 4 被标记为 p 说明将来是需要被拿掉的，这点与 replacement 标记不同。

判断出 x 是左子节点还是右节点。上图 x 为左节点，也就是左倾树。我们根据 x 找到它的兄弟节点 sib。根据 sib 的颜色来判断 sib 是否是 x 的真正兄弟节点。什么意思？当 sib 为红色时，它并不是 x 的真正兄弟。图中的 6、8 对应的其实是 2-3-4 树中的三节点，也就是说 6、8 是处于同一级的。我们把它转成 2-3-4 树，你就明白了：

从 2-3-4 树中，我们可以明显的看出，7 才是 x 的兄弟节点，8 并不是。所以对于红黑树而言，只有兄弟节点是黑色时，它才是自己的亲兄弟。

怎么才能找到 x 的亲兄弟呢？我们需要以 x 的父为中心进行左旋，在旋转之前，需要将当前 sib 染成黑色，x 的父节点染成红色。经过旋转之后就能拿到真正的 sib 了。

获取到真正兄弟之后，要判断它有几个子节点。注意这里有一个比较有意思的地方，那就是对于 colorOf(x) == BLACK 的判断，不知道你还记得 colorOf(x) 的实现吗？

1
2
3
private static <K, V> boolean colorOf(Entry<K, V> p) {
    return (p == null ? BLACK : p.color);
}

有两种情况使得 colorOf(x) == BLACK，一个是为 null，一个是含有节点且为黑色。对于当前这个场景而言，sib 要不有两个子节点，要不没有任何子节点。这两种我们当成一回事。

那么有没有一种情况是一个节点为 null，一个节点为黑色呢？毕竟为 null 也是返回黑色？不可能！为什么？我们看 sib 是红色节点，它的父节点一定为黑色，所以 sib 是一个三节点元素。那么作为三节点元素，要不是以叶子形式存在的，要不是一定存在三个节点。不可能存在两个节点的情况。也就是说 sib 要不没有任何子节点，要不两个节点都在且为黑色。

回到正题，拿到 sib 之后，由于没有任何可辅助 x 平衡的节点，那就只能让 sib 自损了，它的变成红色，谁让 x 失去一个黑色节点呢。sib 自损之后，就得让 x 跟 sib 的父去辅助平衡了。也就是说父节点必须是红色的才行，如果是黑色的，那还得向上找。不过不要紧，因为当前的父节点是经过左旋得到的，而左旋之前原有的 sib 是红色的。所以此时 x 的父一定是红色的。那把它染成黑色，树就平衡了。

那么可能还有一种场景，就是 sib 原本就是黑色的，那怎么办？我们看下图：

为了打破平衡，我们删掉树中的节点 2，得到下图：

其中 p 指向了节点 3。记住，p 是需要被删除的节点。由于 p 没有任何子节点，所以需要先进行调平，之后删除！

此时 sib 为黑色，也就是 x 的亲兄弟。按照正常思路，需要将 sib 染红。此时向父的方向查找，直到找到红色的父节点。但是我们从图中可以看到，根本没有红色的父，不过也不要紧，每向上找到一级的父节点，我们就将当前父的兄弟节点染红。直到遇到红色的父节点或者根节点为止。

但是你可能会说，如果 sib 为红色怎么办？其实 sib 为红色时不就又回到第一种场景了？需要先左旋找到 x 的真正兄弟。也真是由于左旋，那么它们的父就会变成红色。只要将其染黑就解决了。

总结

该场景是调整中最难的了，它不像常规那种子节点替换完成平衡，它只能向上查找。不过我们可以思考总结一下。当 x 所在节点树少一个黑色节点后，树就会失去平衡。所以只能看兄弟节点是否可以借出一个，如果不能借，那就让兄弟节点自损一个。此时两者等同，由于两者都少一个黑节点，那么就只能更让它们的父来补偿。也就是将红色的父变成黑色。

但是如果父也是黑色的，那就只能找父的兄弟借，如果不能借，那就把它的兄弟也变红。直到根或者找到红色的父节点。

场景四 兄弟节点可借

此时又分为两种情况，一种是存在单节点：

首先找到 x 的兄弟节点，兄弟节点可借的情况说明它存在单红节点或者双红节点。对于单红节点也就是 2-3-4 树的三节点，需要先旋转一次。如图所示，定位到 sib 之后，旋转之前，需要将 sib 染红，sib 的子节点染黑。然后以 sib 为中心进行旋转，同时变更 sib 为 x 父的右节点。

将 x 的父节点颜色赋给 sib，x 的父及 sib 的子染黑。然后以 x 的父节点为中心旋转。变更 x 为 root，调整完成。

另一种就是存在双红子节点：

当兄弟节点存在两个红色子节点时，也就是 2-3-4 树的四节点，那么相比三节点，只需要旋转一次就行了。如图所示，定位到 sib 之后，将 sib 的颜色设置为 x 的父节点颜色。将 x 的父节点及 sib 的右节点染红，然后以 x 的父节点左旋。最后将 x 指向 root，完成树的平衡。

整个树的调整逻辑就介绍完了，再来看代码就简单很多了：

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
private void fixAfterDeletion(Entry<K, V> x) {
    // 如果 x 不为根以及 x 为黑色的时候才进入循环。毕竟 x 是根的话，直接染色就行了；如果是红色，删除根本不受影响
    while (x != root && colorOf(x) == BLACK) {
        // 如果是左倾树
        if (x == leftOf(parentOf(x))){
            // 获取 x 的兄弟节点
            Entry<K, V> sib = rightOf(parentOf(x));

            /*
             * 找到 x 的真正兄弟节点
             *        10                     10
             *       (黑)                    (黑)
             *      /    \                  /    \
             *     6      15               8      15
             *    (黑)    (黑)      ->    (黑)     (黑)
             *    / \     / \            /  \      /  \
             *   4   8   14  18         6    9    14   18
             * (黑) (红) (黑)  (黑)     (红)  (黑)  (黑)  (黑)
             *  x   sib                / \
             *      / \               4   7
             *     7   9              x  (黑)
             *    (黑) (黑)               sib
             *==============================================
             * 由于红黑树本质是 2-3-4 树，上图中，在红黑树看来，8 是 x 的兄弟节点，实际上并非如此：
             *
             *             10
             *         /       \
             *       6  8      15
             *       / | \    /  \
             *      4  7  9  14  18
             *
             * 还原到 2-3-4 树之后发现 7 才是 4 的兄弟节点，所以在红黑树看来，如果当前节点是黑色，
             * 兄弟节点是红色时，由于它们 并非处于同一级，所以此时的兄弟节点并非真正的兄弟节点，所以
             * 需要旋转得到
             *
             *
             */
            if (colorOf(sib) == RED){
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateLeft(parentOf(x));
                // 获取真正的兄弟节点
                sib = rightOf(parentOf(x));
            }

            // 如果兄弟节点没有子节点，也就是兄弟节点无法辅助平衡
            if(colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK){
                // 将兄弟节点染成红色，然后向上递归查找直到父亲节点的颜色为红色时，停止。然后将其染黑，完成平衡
                setColor(sib, RED);
                x = parentOf(x);
            }else {
                /*
                 * 兄弟节点有子节点，也就是说兄弟节点可以辅助平衡
                 *            10                          10
                 *           (黑)                         (黑)
                 *          /    \                       /    \
                 *        8      15                     8      15
                 *       (黑)     (黑)                 (黑)     (黑)
                 *       /  \      /  \               /  \      /  \
                 *      5    9    14   18            5    9    14   18
                 *     (红)  (黑)  (黑)  (黑)    ->  (红)  (黑)  (黑)  (黑)
                 *     / \                          / \
                 *    4   7                        4   6
                 *    x  (黑)                      x   (黑)
                 *       sib                           sib
                 *        /                              \
                 *       6                                7
                 *      (红)                              (红)
                 *
                 *
                 */
                // 如果右节点为空，那就说明是左节点，那么就需要单独转一次，如果不为空
                // 说明是左倾树或者是四节点树，这样整体一次左旋转就行了
                if (colorOf(rightOf(sib)) == BLACK){
                    // 先染色，避免红红相连
                    setColor(leftOf(sib), BLACK);
                    // 既然子节点已经是黑色了，那么 sib 就需要染成红色，避免多一个黑节点
                    setColor(sib, RED);
                    rotateRight(sib);
                    sib = rightOf(parentOf(x));
                }

                /*
                 *======================3 节点情况======================
                 *               10                             10
                 *              (黑)                            (黑)
                 *             /    \                          /    \
                 *            8      15                       8      15
                 *          (黑)      (黑)                    (黑)     (黑)
                 *          /  \      /  \                   /  \     /  \
                 *         5    9    14   18                6    9    14   18
                 *        (红)  (黑)  (黑)  (黑)    ->      (红)  (黑)  (黑)  (黑)
                 *        / \                              / \
                 *       4   6                            5   7
                 *       x   (黑)                        (黑)  (黑)
                 *           sib                         /
                 *             \                        4
                 *              7                       x
                 *             (红)
                 *======================4 节点情况======================
                 *               14                            14
                 *              (黑)                           (黑)
                 *            /      \                       /      \
                 *           10      15                     10      15
                 *          (黑)      (黑)                 (黑)      (黑)
                 *          /  \      /  \                /  \      /  \
                 *         5    12   14   18             8    12   14   18
                 *        (红)  (黑)  (黑)  (黑)        (红)  (黑)  (黑)  (黑)
                 *        / \                   ->     / \
                 *       4   8                        5   9
                 *       x  (黑)                     (黑)  (黑)
                 *          sib                      / \
                 *          / \                     4   7
                 *         7   9                    x   (红)
                 *       (红)  (红)
                 *
                 * 如果是 4 节点情况，只需要左旋一次就完成了
                 */
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(rightOf(sib), BLACK);
                rotateLeft(parentOf(x));
                x = root;
            }

        }else {
        // 右倾树的处理
            Entry<K, V> sib = leftOf(parentOf(x));

            /*
             * 如果 x 的兄弟节点 sib 是红色，说明 sib 并不是 x 真正兄弟节点（兄弟节点是在同一级的）
             *        10                     10
             *       (黑)                    (黑)
             *      /    \                  /    \
             *     6      16               8      14
             *    (黑)    (黑)      ->    (黑)     (黑)
             *    / \     / \            /  \      /  \
             *   4   8   14  18         6    9    13   16
             * (黑) (黑) (红)  (黑)     (黑)  (黑)  (黑)  (红)
             *          sib    x                        / \
             *          / \                            15  18
             *         13  15                         (黑)  (黑)
             *        (黑) (黑)                        sib    x
             */
            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateRight(parentOf(x));
                // 此时的 sib 才是 x 的真正兄弟节点
                sib = leftOf(parentOf(x));
            }

            // 如果兄弟节点没有子节点，无法辅助平衡，那就向上递归查找它们红色的父节点，找到之后，将颜色变为黑色
            if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) {
                setColor(sib, RED);
                x = parentOf(x);
            } else {
                // 如果兄弟节点有子节点，此时要判断是一个子还是两个子（也就是涉及到几次旋转）
                // 只要有一个子为空，就说明是单子节点
                if (colorOf(leftOf(sib)) == BLACK) {
                    /*
                     * 如果是单子节点，那么就先需要一次左旋或者右旋
                     *        10                          10
                     *       (黑)                         (黑)
                     *      /    \                       /    \
                     *      8      14                   8      14
                     *    (黑)     (黑)                (黑)     (黑)
                     *   /  \      /  \               /  \      /  \
                     *  6    9    13   17            6    9    13   17
                     * (黑)  (黑)  (黑)  (红)   ->   (黑)  (黑)  (黑)  (红)
                     *                  / \                          / \
                     *                 15  18                       16  18
                     *                (黑)  (黑)                    (黑)  (黑)
                     *                sib    x                      sib   x
                     *                  \                            /
                     *                  16                          15
                     *                 (红)                        (红)
                     */
                    setColor(rightOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateLeft(sib);
                    sib = leftOf(parentOf(x));
                }
                /*
                 * 此时，无论是单节点情况还是双子节点情况，都需要左一次旋转
                 *
                 *===================单子节点情况，接上图===================
                 *        10                           10
                 *        (黑)                         (黑)
                 *       /    \                       /    \
                 *      8      14                    8      14
                 *     (黑)     (黑)                (黑)     (黑)
                 *    /  \      /  \               /  \      /  \
                 *   6    9    13   17            6    9    13   15
                 *  (黑)  (黑)  (黑)  (红)        (黑)  (黑)  (黑)  (红)
                 *                  / \     ->                    sib
                 *                 16  18                          / \
                 *                (黑)  (黑)                      16  17
                 *                sib   x                       (黑) (黑)
                 *                  /                                  \
                 *                 15                                  18
                 *                 (红)                                (黑)
                 *                                                      x
                 *======================双节点情况=======================
                 *
                 *         10                           10
                 *        (黑)                          (黑)
                 *       /    \                        /    \
                 *      8      12                     8      12
                 *     (黑)     (黑)                 (黑)     (黑)
                 *    /  \      /  \                /  \      /  \
                 *   6    9    11   17             6    9    11   15
                 *  (黑)  (黑)  (黑) (红)   ->     (黑)  (黑)  (黑)  (红)
                 *                   / \                           sib
                 *                  15  18                         / \
                 *                 (黑)  (黑)                      14  17
                 *                 sib   x                       (黑)  (黑)
                 *                 / \                                 / \
                 *                14  16                             16  18
                 *               (红) (红)                           (红) (黑)
                 *                                                        x
                 *
                 *
                 */
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(leftOf(sib), BLACK);
                rotateRight(parentOf(x));
                x = root;
            }

        }
    }
    // 别忘了最后一步的染黑
    setColor(x, BLACK);
}

尾声

至此，整个红黑树就介绍完了。希望读完红黑树三篇文章之后，你能彻底掌握红黑树！