0. 前言
我们采用nil代替null来简化操作。如果你之前学过，有一些印象，那跟随本文从上到下画一画插入与删除的全过程，将大大地加深你的印象与熟练程度。
插入和删除的主逻辑，与前面的文章——红黑树01——前传-二叉搜索树中基本一致，只是特别处理了一下nil。最大的不同是，当插入结点和它的父结点都为红色时，违反了红黑树的属性，需要重新调整，共有3种情况（本来是6种，因为是对称的，所以只讨论一半）；删除结点时若涉及到黑结点的删除（或替换），会导致一侧黑结点数目减少，违反了红黑树的规则，所以也需要调整，共有4种情况。
本章内容比较长，如果看得吃力了，可以停下，回头再看。但长不可怕，可怕的是看不懂，我尽可能地把那些操作的前因后果讲清楚，希望大家能耐心看下去。经过测试，我指导过的同学，能轻松记住整个过程，且能写出来全部代码。一定要坚持看完弄懂，请相信我，欠下的债迟早要还的。
1. 插入后的调整
为了便于说明，设新插入结点为x，x的父结点为p，p的兄弟结点为pb，x父结点的父结点为pp，pb的左孩子为pbl, pb的右孩子为pbr。因为对称性，我们这里只讨论p == pp.left的情况。已经x和p当前均为红色，pp肯定为黑色。
因为有两个红色结点，我们需要把其中一个变成黑色，变黑的肯定不是x，因为新插入的结点是红色（为什么新插入的是红色呢，因为如果不插入红色的话，那就没有红色了。但为什么不担心没有黑色了呢？因为我们在调整的过程中，会把根置为黑色，所以能保证一定有黑色，另外前面也说了会把p变成黑色），所以变黑的是p。
但这样就多了一个黑色，解决办法有两个，办法1是pb也由红变黑，pp由黑转红，这样两边都一增一减就平衡了。办法2是pp由黑转红，但这样右边会少一个黑色。我们上一篇文章说过旋转就是为了解决这个问题的，所以我们把pp右旋（思考题：变红的pp会不会违反性质？）。
| 分类 | 描述 | 处理方式 | 后续说明 |
|---|---|---|---|
| 1 | pb为红色 | 将p和pb置为黑色，pp颜色置为红色，x指向pp，进行下一轮循环判断。 | pp由黑变红，可能会违反不能有连续两个红结点的规则，故循环继续。 |
| 2 | pb为黑色，x、p、pp不在一条直线上 | p左旋，使之在一条直线上 | 转化为情况3。 |
| 3 | pb为黑色，x、p、pp不在一条直线上 | p变黑，pp变红，pp右旋 | 已经平衡，结束。 |
private void insertFixup(Node node) {
while (node.parent != nil && node.parent.color == RED) {
Node p = node.parent;
// 因为父节点为红色，而根节点为黑色，所以父节点肯定不为根，故祖父节点存在，所以这里不需要判断为nil。
Node pp = node.parent.parent;
if (pp.left == p) {
Node pb = pp.right;
if (pb.color == RED) {
insertFixUpStats[0]++;
p.color = BLACK;
pb.color = BLACK;
pp.color = RED;
node = pp;
continue;
}
if (node != p.left) {
insertFixUpStats[1]++;
rotateLeft(p);
node = p;
p = node.parent;
}
insertFixUpStats[2]++;
p.color = BLACK;
pp.color = RED;
rotateRight(pp);
} else {
Node pb = pp.left;
if (pb.color == RED) {
insertFixUpStats[0]++;
p.color = BLACK;
pb.color = BLACK;
pp.color = RED;
node = pp;
continue;
}
if (node != p.right) {
insertFixUpStats[1]++;
rotateRight(p);
node = p;
p = node.parent;
}
insertFixUpStats[2]++;
p.color = BLACK;
pp.color = RED;
rotateLeft(pp);
}
}
root.color = BLACK;
}
2. 删除
当黑色结点被替代者替换时，会导致黑色结点的缺失而违反性质4，我们需要对替代者做一些处理，使树恢复平衡。设被删除的结点为x，x的左孩子为xl(left)，右孩子为xr(right)，x的后继为s(successor)，后继的右孩子为sr，替代者为r(replacement)，被替代的颜色为rc(replacedColor)，x的父结点为p，x的兄弟节点为b，b的左右孩子分别为bl, br。
因为删除调整也是对称的，下面我们只讨论x == p.left的情况。
2.1 确定替代者与被替代的颜色
- 如果xl或xr不存在时，直接把xr或xl替换x即可，故r为xr或xl，rc为x.color；否则转2。
- 如果
xr == s，则只发生一次替换：s -> x，故r为s，rc为x.color。 - 如果
xr != s，则发生两次替换：sr -> s, s -> x。我们保留x位置的颜色不变，则在颜色上的替换只有一次：sr -> s，我们只需要调整一个结点的黑色结点问题，此时r为s.right，rc为s.color。
2.2 调整替代者
因为少了一个黑色的结点，前人发明了一招来治标：假设r指针附带了一层额外的黑色（这个黑色是跟着r指针走的，当r向上移动的时候，这层黑色也会跟着走），这样少的那个黑色又加回来了。但怎么治本呢？我们需要把r上移到某个红色位置，然后再强制给r加上黑色，让虚拟的黑色转为实在的黑色，从而达到治本的效果。当然当r已经到根了，那就直接把根置黑就完事了。
那要怎样才能让r移动呢？答案是不断地制造冲突，是的，要搞点事情出来才能打破僵局，不破不立嘛。一个原则：不能减少左边结点上的黑色（只能将r上移来减少虚拟的黑色）。
首先区分出4种情况：按b的颜色可分为两种情况，而b为黑时，又根据bl, br的颜色，可分为全黑、左红、右红3种情况（为什么不考虑全红：因为单独考虑左红、右红已经包含全红了。另外，右红经过左旋可转化为左红，是的，跟上面插入时一样，如果不在一条直线上则旋转到一条直线上）。然后再逐个攻破。
- 情况1：如果b为红色，则p、bl和br都为黑色。因不能连续两红，故p、bl、br都不能变色，唯一能变化的只能是b，故将其置为黑色，这样右边又多了一个黑色，现在多了2个黑色；那就把p置红（这里为什么敢置红呢？先试试嘛，万一不行不变就是了，恰好接下来的左旋操作，使得p的父亲变成黑色的b，所以不会出现两个红色），右边黑色数目恢复，但左边又少了一个黑色。那就p左旋（对，旋转就是用来将一边的颜色添加到另一边的），这时b的黑色作用到两边使左右两边的黑色数目都恢复。另外p左旋导致原来的bl成了p.right，成为x的新兄弟，且bl是黑色的，故转换为情况2/3/4的一种。
- 情况2：b, bl, br都为黑色，但bl, br不能置红（因为它们的子结点不知道什么情况，如果是红色的就会出现两个连续红色从而违反红黑树的性质），同样p不知道什么颜色，故唯一能变化的只能是b变红。这样右边少一个黑色，将r上移指向p，相当于给右边添加了一层虚拟的黑色，恢复平衡。于是进入下一次循环继续判断。
- 情况3：b为黑色，bl为红色，因p, b, bl不在一条直线上，故b置红，bl置黑，右旋b，再重置b，转为情况4。
- 情况4：b为黑色，br为红色，则p, b, br在一条直线上，这个时候怎么搞事情呢？因为br是红色，所以b不能再变红，而bl和p颜色不确定，所以也不能直接修改颜色。故只能将br置黑，则右边多了一个黑色。因为不能将p置红来减少右边的黑色，唯一能做的就是想办法把b的黑色弄到左边去。首先想到的就是左旋p，但如果p是黑色的，左旋p会导致右边黑色减1左边加1，最终左边黑色数目比右边多2（算上那个虚拟黑色），所以不能直接左旋p。我们试着交换p和b的颜色，再左旋p，则p原来的颜色还在右边，b的黑色成功置换到左边了。但现在左边又多了一个黑色，我们把r移走，指向root，则总体平衡了（右边黑色一加一减不变，左边增加了一个），结束处理。
所以将来大家记不住4种情况分别是什么时，不妨自己在纸上画画，强迫自己搞点事情出来，再逐步恢复之前的局势，想必能帮助你想起来。
| 分类 | 描述 | 处理方式 | 后续说明 |
|---|---|---|---|
| 1 | b为红 | b置黑，p置红，左旋p，重置b，继续 | 转化为情况2/3/4的一种 |
| 2 | b, bl, br均为黑 | b置红，r指向p，继续 | 2和3、4是排他的，而3和4在同一次循环操作中 |
| 3 | b为黑，bl为红 | b置红，bl置黑，右旋b，再重置b | 转化为情况4 |
| 4 | b为黑，br为红 | br置黑，p, b互换颜色，左旋p，r指向root | 结束 |
private void deleteFixUp(Node node) {
while (node != root && node.color == BLACK) {
Node parent = node.parent;
if (node == parent.left) {
Node brother = parent.right;
if (brother.color == RED) {
deleteFixUpStats[0]++;
brother.color = BLACK;
parent.color = RED;
rotateLeft(parent);
brother = parent.right;
}
// 因为有哨兵nil，所以这里不需要判断brother.left是否存在。
if (brother.left.color == BLACK && brother.right.color == BLACK) {
deleteFixUpStats[1]++;
brother.color = RED;
node = parent;
} else {
if (brother.left.color == RED) {
deleteFixUpStats[2]++;
brother.left.color = BLACK;
brother.color = RED;
rotateRight(brother);
brother = parent.right;
}
deleteFixUpStats[3]++;
// 旋转与变色是相互独立的，所以顺序不是固定的，随意就行。不妨把下面这句rotateLeft(parent)换个地方试试。
// rotateLeft(parent);
brother.color = parent.color;
parent.color = BLACK;
brother.right.color = BLACK;
rotateLeft(parent);
node = root;
}
} else {
Node brother = parent.left;
if (brother.color == RED) {
deleteFixUpStats[0]++;
brother.color = BLACK;
parent.color = RED;
rotateRight(parent);
brother = parent.left;
}
if (brother.left.color == BLACK && brother.right.color == BLACK) {
deleteFixUpStats[1]++;
brother.color = RED;
node = parent;
} else {
if (brother.right.color == RED) {
deleteFixUpStats[2]++;
brother.right.color = BLACK;
brother.color = RED;
rotateLeft(brother);
brother = parent.left;
}
deleteFixUpStats[3]++;
brother.color = parent.color;
parent.color = BLACK;
brother.left.color = BLACK;
rotateRight(parent);
node = root;
}
}
}
node.color = BLACK;
}
3. 示例
下面我将演示按{6, 3, 5, 4, 2, 1, 0}的顺序逐个插入，再按{6, 4, 5, 0, 1, 3, 2}的顺序逐个删除结点，演示插入的3种情况和删除的4种情况。话说你这两串数字怎么得来了，你怎么能知道能出现所有的情况？嘿嘿，多运行几次代码，你就能挑到一个满足条件的。
开始插入5
前面两个结点太简单，就不演示了。我们从插入5开始，现在3和5连续两个红结点，且6、3、5不在一条直接线，为插入情况2，我们左旋3，转化为情况3；然后5变黑，6变红，右旋6.
完成插入5
接下来插入4之后，3和6都为红，为情况1，所以将3和6置黑，5置红。然后继续判断的时候，x已经指向根，所以将根置黑即结束。
插入4
接下来插入2，不需要调整，所以不演示了，继续插入1.此时2和4均为红，为情况1，将2和4置黑，3变红，因为3的父结点5不再是红色，所以处理结束。
插入2和1
插入0，0、1、2在一条直线上，为情况3，所以1置黑，2置红，右旋2.
插入0
现在插入完毕，哈哈，看起来左边高很多，但也只是2倍啦，还是一棵合法的红黑树。接下来我们开始删除操作{6, 4, 5, 0, 1, 3, 2}。继续使用上文中的符号来表示。
删除6。因6的左孩子为nil，所以r为其右孩子（也是nil，但没关系，我们把nil当成普通结点看待），rc为6的颜色黑色，所以需要做调整。b为3，颜色为红，符合情况1。所以将3置黑色，5置红色，右旋5，再重置b。
此时b(4)为黑色，左右孩子均为nil，也为黑色，符合情况2，故4变红，r指向5。
此时r本身为红色了，所以结束循环，将其置黑，结束处理。总结一下，删除结点6，我们共进行了2次调整，分别为情况1和情况2。
删除6
继续删除结点4。因为4左孩子不存在，所以r为其右孩子，rc为4的颜色红色，故不需要调整，这里不再单独作图。
再删除5。因5的左孩子不存在，故r为其右孩子nil，rc为5的颜色黑色，所以需要调整。因为b(1)为黑色，且其右孩子为红色，符合情况3，故1变红，2变黑，b左旋，2成为新的b，转情况4；情况4中，将bl(1)置黑，p(3)颜色给b，p置黑，右旋3，r指向root。
总结一下，删除结点5，我们共进行了2次调整，情况3和情况4.
删除5
接下来删除0，因它没有左右结点，且颜色为红色，不需要调整，直接删除即可，不再画图。接下来删除1。1没有左结点，故r为1，rc为1的颜色黑色，b为3，颜色为黑色，且3的左右孩子均为黑色（nil的颜色），符合情况2，故将b置红，r指向p。因为此时p已经是根了，将其置黑结束处理。
删除1
接下来删除3，3为红色，不需要调整，删除2树为空，也不需要调整，不再画图。
5. 结语
通过本文的练习，如果能正确得到结果，证明你已经基本掌握了红黑树的插入与删除操作。记得，插入调整的3种情况和删除调整的4种情况，都可以通过自己演练出来，记不住了，就在纸上画画，试着随便去做一些调整（如果调整造成了其他的冲突，则想办法往回调整），最终会得到正确的解决办法。
源码
作者微信
wx.png
转载声明
如果您需要转载，请注明转载来源。
网友评论