14、数据结构与算法 - 基础：红黑树（3）删除元素
摘要
红黑树删除节点，和 B 树删除节点的情况非常的接近。理解红黑树删除节点之后的恢复操作前，再过一下 B 树的删除逻辑，这样会更好的理解红黑树的删除逻辑。各种处理操作就不会离开一个主要思想，就是红黑树的 5 条性质。
在B树中，最后真正需要删除的一定是叶子节点，就算删除的不是叶子节点，也可以先和它的前驱或者后继交换位置之后，删除被交换到叶子的节点。红黑树可以简单的移动一下节点的位置，就能变成 B 树（如下图所示），所以红黑树的删除就可以转换为对 B 树的删除。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-huKQAtRO-1641388184611)(https://cdn.jsdelivr.net/gh/shPisces/writing_pic/img/RBT-remove2.png)]
红黑树的节点被删除之后，就要判断是否还符合红黑树性质，若不符合性质时，就要做恢复红黑树的处理。判断的依据就是红黑树的 5 条性质，尤其是性质 4。
红黑树的 5 条性质：
- 节点必须是 RED 或者 BLACK；
- 根节点是 BLACK；
- 叶子节点都是 BLACK，这里要特别留意，叶子节点存在两个空节点，只有一个子树的节点，另外一个不存在的子树也是一个空节点。
- RED 节点的子节点都是 BLACK，RED 节点的父节点也都是 BLACK。保证从根节点到叶子节点的所有路径上，不会出现 2 个连续的 RED 节点。
- 从任意一个节点到叶子节点的所有路径上包含的 BLACK 节点数量相同。
首先看删除的叶子节点是 RED，那么就不需要做任何处理，依然满足红黑树的性质。比如删除元素 17、33、55 和 72。如下图所示：
接下来，删除的叶子节点是 BLACK，就有 3 种情况，首先第一种就是有两个 RED 子节点（如下图元素 25），因为有两个叶子节点，所以若要删除也是找子节点替换，然后删除与它交换的叶子节点，不可能直接删除的，所以不考虑。第二种呢，是有一个 RED 子节点（比如元素 46、76），这种情况就可以直接拿这个 RED 子节点替换 BLACK 节点，然后将这个 RED 子节点染成 BLACK，依然满足红黑树的性质。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-la1SeISr-1641388184615)(https://cdn.jsdelivr.net/gh/shPisces/writing_pic/img/RBT-remove.png)]
第三种就是它既是 BLACK，也是叶子节点（比如元素 88），删除这个节点会造成 B 树下溢出。那么就要做调整来消除下溢的影响。
这里要拿它的兄弟节点（sibling）来帮助处理。如果它的 sibling 是 BLACK时，若 sibling 至少有一个 RED 的子节点，就可以根据它的失衡情况做旋转，旋转之后的中心节点染成 parent 的颜色，他的左右节点就染成 BLACK。
若sibling 一个 RED 节点都没有，而 parent 是 RED 时，就直接将 sibling 染成 RED，parent 染成 BLACK，就满足了红黑树的性质。但是 parent 是 BLACK 时，就会导致 parent 下溢，那么就把 parent 当作被删除的节点去处理即可。
若sibling 是 RED，那么就需要将 sibling 染成 BLACK，parent 染成 RED，进行旋转之后，就会回到 sibling 是 BLACK 的情况。然后继续按照 sibling 是 BLACK 的情况继续处理。
现在开始代码实现删除红黑树的节点之后的处理：
删除节点之后，当前节点位置要不就是不存在，为 null，要不就是其他节点被替换到当前节点。所以下面函数中传递的参数就是删除位置的节点：
void afterRemove(Node<E> node) {
}
这里要判断当前节点的颜色，如果是红色，那么就染黑处理。下溢情况会再次调用 afterRemove 函数。
// 如果删除的节点是红色
// 或者 用于取代删除节点的子节点是红色
if (isRed(node)) {
black(node);
return;
}
接下来就是要判断，删除的节点是否是根节点，如果是，就根节点，也可以不用操作：
Node<E> parent = node.parent;
// 删除的是根节点
if (parent == null) return;
下面就是被删除的节点是黑色节点，那么这时候就要看它的兄弟节点是否可以拿出来一个节点来补位。这里先以兄弟节点是当前节点的右侧来处理，兄弟节点是当前节点的左侧刚好与前面情况相反。
boolean left = parent.left == null || node.isLeftChild();
Node<E> sibling = left ? parent.right : parent.left;
if (left) {
// 被删除的节点在左侧，兄弟节点在右侧
// 实现逻辑
}
这时，如果兄弟节点是红色，那么就可以替换过来：
if (isRed(sibling)) {
// 兄弟节点是红色
black(sibling);
red(parent);
rotateLeft(parent);
// 更换兄弟
sibling = parent.right;
}
经过这一番处理之后，剩下的过程必然是处理兄弟节点是黑色的情况了。
这时就只有两种情况了，第一种就是兄弟节点没有子节点可以借出，那只能把父节点向下合并了，向下合并之后可能产生下溢。所以就需要把父节点重新走一遍 afterRemove 函数。
// 兄弟节点必然是黑色
if (isBlack(sibling.left) && isBlack(sibling.right)) {
// 兄弟节点没有一个红色子节点，父节点要向下跟兄弟节点合并
boolean parentBlack = isBlack(parent);
black(parent);
red(sibling);
if (parentBlack) {
afterRemove(parent);
}
} else {
// 实现
}
第二种情况，就是兄弟节点中有子节点可以借出，那就借节点：
// 兄弟节点必然是黑色
if (isBlack(sibling.left) && isBlack(sibling.right)) {
// 实现
} else {
// 兄弟节点至少有一个红色节点，向兄弟节点借元素
// 兄弟节点的右边是黑色，兄弟要先旋转
if (isBlack(sibling.right)) {
rotateRight(sibling);
sibling = parent.left;
}
color(sibling, colorOf(parent));
black(sibling.right);
black(parent);
rotateLeft(parent);
}
最后就是要处理兄弟节点是当前节点的左侧情况，它和上面的情况正相反：
// 删除的是黑色叶子节点【下溢出】
// 判断删除的 node 是左还是右
boolean left = parent.left == null || node.isLeftChild();
Node<E> sibling = left ? parent.right : parent.left;
if (left) {
// 被删除的节点在左侧，兄弟节点在右侧
// 实现
} else {
// 删除的节点在右边，兄弟节点在左边
if (isRed(sibling)) {
// 兄弟节点是红色
black(sibling);
red(parent);
rotateRight(parent);
// 更换兄弟
sibling = parent.left;
}
// 兄弟节点必然是黑色
if (isBlack(sibling.left) && isBlack(sibling.right)) {
// 兄弟节点没有一个红色子节点，父节点要向下跟兄弟节点合并
boolean parentBlack = isBlack(parent);
black(parent);
red(sibling);
if (parentBlack) {
afterRemove(parent);
}
} else {
// 兄弟节点至少有一个红色节点，向兄弟节点借元素
// 兄弟节点的右边是黑色，兄弟要先旋转
if (isBlack(sibling.left)) {
rotateRight(sibling);
sibling = parent.right;
}
color(sibling, colorOf(parent));
black(sibling.left);
black(parent);
rotateRight(parent);
}
}
这这里已经全部梳理完红黑树删除节点之后恢复的处理了。删除节点要加入 B 树的思维在里面才能更好的理解它的删除。