微信公众号：I am CR7
如有问题或建议，请在下方留言;
最近更新：2018-09-05
TreeMap之插入
通过上一篇文章，介绍了二分查找树的缺陷，引出了红黑树的介绍。进一步分析TreeMap中插入元素的源码，最后借助示例来加深对于红黑树的理解。详细请看TreeMap之元素插入
TreeMap之删除
1、删除指定key对应的元素：
1public V remove(Object key) {
2 //根据key获取键值对
3 Entry<K,V> p = getEntry(key);
4 if (p == null)
5 return null;
6 //删除该键值对，并返回value值
7 V oldValue = p.value;
8 deleteEntry(p);
9 return oldValue;
10}
2、删除节点，并对树进行平衡调整：
2.1、源码：
1private void deleteEntry(Entry<K,V> p) {
2 modCount++;
3 size--;
4
5 //如果存在左右节点，则获取其后继节点，完成key、value的复制，p指向后继节点
6 //此处思想就是将有左右节点的节点p的删除转化为其后继节点的删除
7 if (p.left != null && p.right != null) {
8 Entry<K,V> s = successor(p);
9 p.key = s.key;
10 p.value = s.value;
11 p = s;
12 } // p has 2 children
13
14 //获取删除节点的替代节点
15 Entry<K,V> replacement = (p.left != null ? p.left : p.right);
16
17 //如果存在替代节点，则进行替代。接着先删除节点p，再进行删除的平衡调整
18 if (replacement != null) {
19 //用替代节点替代删除节点
20 replacement.parent = p.parent;
21 if (p.parent == null)
22 root = replacement;
23 else if (p == p.parent.left)
24 p.parent.left = replacement;
25 else
26 p.parent.right = replacement;
27
28 //删除节点p
29 p.left = p.right = p.parent = null;
30
31 //如果删除节点为黑色，必然影响树的平衡，进行平衡调整
32 if (p.color == BLACK)
33 fixAfterDeletion(replacement);
34 } else if (p.parent == null) { // return if we are the only node.
35 root = null;
36 } else { //如果不存在替代节点，不需要替代。接着先进行删除的平衡调整，再删除节点p
37 //如果删除节点为黑色，必然影响树的平衡，进行平衡调整
38 if (p.color == BLACK)
39 fixAfterDeletion(p);
40
41 //删除节点p
42 if (p.parent != null) {
43 if (p == p.parent.left)
44 p.parent.left = null;
45 else if (p == p.parent.right)
46 p.parent.right = null;
47 p.parent = null;
48 }
49 }
50}
51
52//注意该方法执行的前提是t节点有左右节点，所以返回的是右子树里最左边的非空
53static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
54 if (t == null)
55 return null;
56 else if (t.right != null) { //存在右子树
57 Entry<K,V> p = t.right;
58 while (p.left != null) //一直往左走
59 p = p.left;
60 return p; //返回右子树里最左的非空节点
61 } else {
62 Entry<K,V> p = t.parent;
63 Entry<K,V> ch = t;
64 while (p != null && ch == p.right) {
65 ch = p;
66 p = p.parent;
67 }
68 return p;
69 }
70}
通过上述逻辑我们知道，删除节点分为下面几种情况：
- 有左右孩子节点
- 只有一个孩子节点
- 无孩子节点(叶子节点)【情况最为复杂，后面会详细讲解】
2.2、代码整理成流程图：
2.3、示例：
- 有左右孩子，且无替代节点：【先调整后删除的流程】
图注:有左右孩子但无替代节点
无替代节点，说明后继节点走到了叶子节点。需要调整说明后继节点为黑色，正如上图所示。此时就转化为对于叶子节点10的删除操作了，处理过程请往后看。
- 有左右孩子，且有替代节点：【先删除后调整的流程】
图注:有左右孩子且有替代节点
有替代节点，说明后继节点未走到叶子节点，那么后继节点肯定只有一个孩子节点，否则必可以走到叶子节点(此处可以画图体会体会)。一个节点只有一个孩子节点，那么只有一种可能，就是节点为黑，孩子为红，否则树不平衡，正如上图所示。此时，替代节点为红色，调整逻辑就很简单了，就是将该红色节点改成黑色节点即可。
- 只有一个孩子节点，必有替代节点：【先删除后调整的流程】
图注:只有一个孩子->必有替代节点
只有一个孩子节点，替代节点获取的规则就是要么左节点，要么右节点，所以必有替代节点。一个节点只有一个孩子节点，那么只有一种可能，就是节点为黑，孩子为红，否则树不平衡，正如上图所示。此时，替代节点为红色，调整逻辑就很简单了，就是将该红色节点改成黑色节点即可。
2.4、总结：
通过上述的分析，凡是先进行删除，后进行调整的情况，其调整逻辑都很简单，就是只需要将节点颜色从红色变成黑色即可。先进行调整，后进行删除的情况，才是逻辑最为复杂的，请继续往下看。
3、对树进行删除后的调整：
1private void fixAfterDeletion(Entry<K,V> x) {
2 //只要x不为根节点且为黑色，就需要调整
3 while (x != root && colorOf(x) == BLACK) {
4 //X是否为父亲节点的左节点
5 if (x == leftOf(parentOf(x))) {
6 //获取X右兄弟节点sib
7 Entry<K,V> sib = rightOf(parentOf(x));
8 //X兄弟节点为红色转化为X兄弟节点为黑色的情况
9 if (colorOf(sib) == RED) {
10 //设置X兄弟节点为黑色
11 setColor(sib, BLACK);
12 //设置X父亲节点为红色
13 setColor(parentOf(x), RED);
14 //以X父亲节点为中心进行左旋
15 rotateLeft(parentOf(x));
16 //sib指向X的兄弟节点
17 sib = rightOf(parentOf(x));
18 }
19
20 //兄弟节点左右节点都为黑色
21 if (colorOf(leftOf(sib)) == BLACK &&
22 colorOf(rightOf(sib)) == BLACK) {
23 //兄弟节点改成红色
24 setColor(sib, RED);
25 //X指向父节点
26 x = parentOf(x);
27 } else {
28 //X远侄节点为黑色转化为X远侄节点为红色的情况
29 if (colorOf(rightOf(sib)) == BLACK) {
30 //近侄节点改成黑色
31 setColor(leftOf(sib), BLACK);
32 //兄弟节点改成红色
33 setColor(sib, RED);
34 //以兄弟节点为中心进行右旋
35 rotateRight(sib);
36 //sib指向X右兄弟节点
37 sib = rightOf(parentOf(x));
38 }
39 //设置sib为X父节点颜色
40 setColor(sib, colorOf(parentOf(x)));
41 //设置X父节点为黑色
42 setColor(parentOf(x), BLACK);
43 //设置远侄节点为黑色
44 setColor(rightOf(sib), BLACK);
45 //以X父亲节点为中心进行左旋
46 rotateLeft(parentOf(x));
47 //X指向根，结束循环
48 x = root;
49 }
50 } else { // symmetric
51 //获取X左兄弟节点sib
52 Entry<K,V> sib = leftOf(parentOf(x));
53 //X兄弟节点为红色转化为X兄弟节点为黑色的情况
54 if (colorOf(sib) == RED) {
55 //设置X兄弟节点为黑色
56 setColor(sib, BLACK);
57 //设置X父亲节点为红色
58 setColor(parentOf(x), RED);
59 //以X父亲节点为中心进行右旋
60 rotateRight(parentOf(x));
61 //sib指向X的兄弟节点
62 sib = leftOf(parentOf(x));
63 }
64
65 //兄弟节点左右节点都为黑色
66 if (colorOf(rightOf(sib)) == BLACK &&
67 colorOf(leftOf(sib)) == BLACK) {
68 //兄弟节点改成红色
69 setColor(sib, RED);
70 //X指向父节点
71 x = parentOf(x);
72 } else {
73 //X远侄节点为黑色转化为X远侄节点为红色的情况
74 if (colorOf(leftOf(sib)) == BLACK) {
75 //近侄节点改成黑色
76 setColor(rightOf(sib), BLACK);
77 //兄弟节点改成红色
78 setColor(sib, RED);
79 //以兄弟节点为中心进行左旋
80 rotateLeft(sib);
81 //sib指向X左兄弟节点
82 sib = leftOf(parentOf(x));
83 }
84 //设置sib为X父节点颜色
85 setColor(sib, colorOf(parentOf(x)));
86 //设置X父节点为黑色
87 setColor(parentOf(x), BLACK);
88 //设置远侄节点为黑色
89 setColor(leftOf(sib), BLACK);
90 //以X父亲节点为中心进行右旋
91 rotateRight(parentOf(x));
92 //X指向根，结束循环
93 x = root;
94 }
95 }
96 }
97
98 //设置X为黑色
99 setColor(x, BLACK);
100}
3.1、代码整理为流程图：
高清图请看：https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/9/7/165b3848ec1c7eee~tplv-t2oaga2asx-image.image
3.2、优化的流程图：
高清图请看：https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/9/7/165b3848ec062ee1~tplv-t2oaga2asx-image.image
3.3、流程图解析说明：
兄弟节点为黑色，远侄节点为红色(删除节点X为叶子节点，且为黑色[如果为红直接删除即可])
图注:兄弟为黑，远侄为红 兄弟节点为黑色，远侄节点为黑色(删除节点X为叶子节点，且为黑色[如果为红直接删除即可])
图注:兄弟为黑，远侄为黑
兄弟节点为黑色，并且删除节点X为黑色，且为叶子节点->远侄节点如果为黑色，必然是null节点，否则树不平衡。兄弟节点为黑色，远侄近侄节点都为黑色(删除节点X为叶子节点，且为黑色[如果为红直接删除即可])
图注:兄弟为黑，远近侄为黑 兄弟节点为红色(删除节点X为叶子节点，且为黑色[如果为红直接删除即可])
图注:兄弟为红
兄弟节点为红色，X为黑色，且是叶子->远侄节点和近侄节点必为null节点，否则树不平衡。
3.4、示例：
兄弟节点为红色
图注:兄弟为红
高清图请看：https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/9/7/165b33e01bf074ab~tplv-t2oaga2asx-image.image兄弟节点为黑色，远侄节点为红色
图注:兄弟为黑，远侄为红
高清图请看：https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/9/7/165b33e02c61c338~tplv-t2oaga2asx-image.image兄弟节点为黑色，远侄节点为黑色
图注:兄弟为黑，远侄为黑
高清图请看：https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/9/7/165b3848ed9e566b~tplv-t2oaga2asx-image.image兄弟节点为黑色，远侄近侄节点都为黑色
图注:兄弟为黑，远近侄为黑
高清图请看：https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/9/7/165b33e03146c697~tplv-t2oaga2asx-image.image
总结
红黑树的删除相对于插入而言，复杂了不少。但是只要时刻记住五条性质，对于包含的每种场景动手去练习，我想理解它应该也不是难事。
文章的最后，感谢大家的支持，欢迎扫描下方二维码，进行关注。如有任何疑问，欢迎大家留言。
