《算法—深入浅出》红黑树的删除
2021-01-21 本文已影响0人
青叶小小
一、《算法—深入浅出》N叉树的介绍
二、《算法—深入浅出》红黑树的旋转
三、《算法—深入浅出》红黑树的插入
四、《算法—深入浅出》红黑树的删除
一、前言
在《红黑树的旋转》一篇中提到过，RBT的删除稍微比插入要复杂一点，那么如何复杂？又是如何删除与调整？本篇将会给大家揭开面纱！
为了能更清楚简单的描述整个过程，本篇将分为：
- 查找要删除的节点；
- 查找可以替换删除的节点；
- 删除后不满足红黑树条件时的调整；
二、查找要删除的节点
给定一个节点key 或 value，根据红黑树的特点：
- 所有左子树上的节点值一定小于根节点的值；
- 所有右子树上的节点值一定大于根节点的值；
那么，我们就可以通过二分法，来快速查找我们要删除的节点的 key 或 value。
public class RBTree {
/*******************************************************************************************************************
* 删除指定结点
*******************************************************************************************************************/
public void remove(int value) {
if (root == null) {
return;
}
/**************************************************************************************
* 二分法，先查找需要删除的节点
**************************************************************************************/
TreeNode p = root;
while (p != null) {
if (p.value == value) {
break;
} else if (p.value > value) {
p = p.left;
} else {
p = p.right;
}
}
// 没有找到指定值的节点
if (p == null) {
return;
}
// 查找可以替换删除的节点
......
// 调整红黑树
......
}
}
三、查找可替换删除的节点
如下图，我们要删除值为5的节点：
image.png
如果我们直接删除节点5，那么就要选择节点2 或者 节点8为新的根节点（取代节点5这个根，不是整个 RBT 的根），无论选择哪个节点为新根节点，都会不满足红黑树的第5点，从 RBT 的根到任意叶子节点，其路径上的黑色节点数相同。
那么，我们就没有好的办法了么？
办法肯定是有的，而且还有两种办法，当然，实际上只是一种方法，只是采取的策略不同而已！
首先，我们发现，比5次小的数是节点2的右节点，而比5次大的数是节点8的左节点，因此，我们可以选举节点3或节点6来成为新的节点，我们看看分别选用新的节点后，红黑树的结果如何？
前驱or后继.png
我们发现，无论是采用『前驱选举法』还是『后继选举法』选举出的新根节点，来取代老节点，都满足红黑树的5条要求，而且不用调整（后文中会讲道哪些情况下不用调整，哪些情况下需要调整）。
那么前驱与后继是如何实现的，又有什么要求？
- 被删除的节点只要存在儿子节点：
a. 如果左儿子存在，则先定位到其左儿子节点，然后不断的定位到右儿子节点，直到下一个右儿子节点为NULL；
a. 同理，右儿子存在，则先定位到其右儿子节点，再不断定位左儿子节点，直到下一个左儿子节点为NULL；
c. 对于 a 或者 b，只需要将最右或最左节点的值赋值给被删除的节点，然后将删除的指向指到最右或最左子节点；
d. 对于最右或最左，可能也存在儿子，因此，继续执行第 1 点，；
e. 如果最右或最左没有儿子，则执行第 2 点； - 如果两个儿子都不存在，则查看下节内容；
-
递归查找替换节点（后继）：
红黑树的删除递归.png
查找前驱或后继节点，并替换删除节点的值（若有两个儿子，先前驱还是先后继都可以）
public class RBTree {
public void remove(int value) {
// 二分法查找待删除的节点
......
// 查找可以替换删除的节点
p = findPreOrNextNode(p);
// 调整红黑树
......
}
/*******************************************************************************************************************
* 查找后继或前驱节点，最终转化为删除（含有一个 or 零个）的子节点
* 【返回最终要删除的子节点】
*******************************************************************************************************************/
private TreeNode findPreOrNextNode(TreeNode p) {
if (p.left != null || p.right != null) {
// g 为指向删除的节点
TreeNode g = p;
/**********************************************************************************
* 查找
* 1. 后继：仅比待删除节点次大的节点
* or
* 2. 前驱：仅比待删除节点次小的节点
**********************************************************************************/
if (p.right != null) {
// 查找后继节点
p = p.right;
while (p.left != null) {
p = p.left;
}
} else {
// 查找前驱节点
p = p.left;
while (p.right != null) {
p = p.right;
}
}
/**********************************************************************************
* 交换【待删除节点】与【后继/前驱】的值，改为删除【后继/前驱】节点
**********************************************************************************/
g.value = p.value;
p = findPreOrNextNode(p);
} else {
/**********************************************************************************
* 待删除节点没有左、右儿子，就是删除自己
**********************************************************************************/
}
return p;
}
}
四、调整红黑树
如果两个儿子都不存在，则需要考虑被删除节点的颜色（右节点同理，只是条件相左）：
- 如果是红色，则直接删除，不用后续调整；
- 如果是黑色，则需要考虑其兄弟节点颜色，以及兄弟节点的儿子情况：
如果兄弟节点是红色，则要满足红黑树第5点，兄弟节点必有两个黑色的儿子，则修改兄弟节点的左儿子为红色，兄弟节点为黑色，对父节点左旋，调整完毕；
如果兄弟节点是黑色（如果有儿子，则一定是红色，黑色则不满足红黑树第5点）：
兄弟节点有一个右儿子：将父节点颜色给兄弟节点，修改父节点和兄弟右儿子节点为红色，对父节点左旋，调整完毕；
兄弟节点有一个左儿子，互换兄弟与其左儿子节点颜色，对兄弟节点右旋，此时和 2.b.i 一样，执行即可；
兄弟节点没有儿子，因为删除的节点为黑色，为了动态平衡，直接修改兄弟节点的颜色为红色，但此时可能不满足红黑树第4点（父节点可能是红色），因此，将待调整节点指为父节点，继续执行第 2 点；
先假设各节点的名称：
- X为待删除节点；
- P为父节点；
- B为兄弟节点；
- BL为兄弟节点的左节点；
- BR为兄弟节点的右节点；
下面将对第 2 点中的 5 种情况用图来直观的分析：
-
2.a：X = 黑色，B = 红色，BL = 黑色，BR = 黑色
2.a.png
-
2.b.i：X = 黑色，B = 黑色，BR = 红色
-
2.b.ii：X = 黑色，B = 黑色，BL = 红色
-
2.b.iii：X = 黑色，B = 黑色，BL = 红色，BR = 红色
2.b.i-iii.png
-
2.b.iv：X = 黑色，B = 黑色
2.b.iv.png
-
删除结点后的检查或调整：
public class RBTree {
public void remove(int value) {
// 二分法查找待删除的节点
......
// 查找可以替换删除的节点
......
// 调整红黑树，并将 X 节点移除
fixedRemove(p);
if (p == p.parent.left) {
p.parent.left = null;
} else {
p.parent.right = null;
}
}
/*******************************************************************************************************************
* cur为新的删除节点，需要考虑：
* 1、cur 没有儿子：
* 1.1、cur 为红色节点，则直接删除；
* 1.2、cur 为黑色节点，需要考虑其兄弟节点；
* 2、cur 有一个儿子：
* 2.1、交互 cur 与其儿子节点的值，改为删除儿子节点；
* 2.2、重复第1步；
* 3、cur 不可能有两个儿子：
* 3.1、根据 remove，cur 要么为后继、要么为前驱、要么没有儿子；
* 3.2、所以只存在上述1、2；
* 3.3、且第2步最终也转化为第1步需要考虑的 1.1 或 1.2 情况；
*******************************************************************************************************************/
private void fixedRemove(TreeNode cur) {
while (cur != root && cur.color == TreeNode.BLACK) {
/***********************************************************************************************************
* cur 为待删除节点
* b 为兄弟节点
* p 为父节点
*
* 【以下分析基于 cur 为左节点，若为右节点，则条件相反】
* 因为 cur 节点存在且为黑色，所以，其兄弟节点一定存在：
*
* 1、若 b 节点为红色，则满足红黑树条件的情况下，b 的儿子节点一定存在，且有两个为黑色的儿子：
* 设 b 左儿子为红色，b 为黑色，对 p 向左旋转；
*
* 2、若 b 节点为黑色：
* 2.1、b 有一个右儿子（一定是红色），将 p 的颜色给 b，p 和 b 的右儿子设为黑色，对 p 向左旋转；
* 2.2、b 有一个左儿子（一定是红色），将儿子设为黑色，b设为红色，b 是右节点，对 b 向右旋转；（此时情况同 2.1）
* 2.3、b 有两个儿子（一定是红色），此时，处理同 2.1；
*
* 2.4、b 没有儿子，则设 b 为红色，cur 指向 p，继续向上递归至根节点，或遇到红色节点为止；
* 之所以要向上递归，是因为 p 可红可黑，b 从黑色改变为红色，此时就少了一个黑色节点，条件5可能不满足，
* 需要检查 p 节点颜色及其兄弟；
***********************************************************************************************************/
TreeNode p = cur.parent;
TreeNode b;
if (cur == p.left) {
/*********************************************************************************
* 待删除节点为左节点
*********************************************************************************/
b = p.right;
// 1
if (b.color == TreeNode.RED) {
b.left.color = TreeNode.RED;
b.color = TreeNode.BLACK;
rotateLeft(p);
break;
}
// 2.4
if (b.left == null && b.right == null) {
b.color = TreeNode.RED;
cur = p;
continue;
}
// 2.2
if (b.left != null && b.right == null) {
b.left.color = TreeNode.BLACK;
b.color = TreeNode.RED;
rotateRight(b);
}
// 2.1、2.3 以及 2.2 -> 2.1
b.color = p.color;
p.color = b.right.color = TreeNode.BLACK;
rotateLeft(p);
break;
} else {
/******************************************************************************
* 待删除节点为右节点
******************************************************************************/
b = p.left;
// 1
if (b.color == TreeNode.RED) {
b.right.color = TreeNode.RED;
b.color = TreeNode.BLACK;
rotateLeft(p);
break;
}
// 2.4
if (b.left == null && b.right == null) {
b.color = TreeNode.RED;
cur = p;
continue;
}
// 2.2
if (b.right != null && b.left == null) {
b.right.color = TreeNode.BLACK;
b.color = TreeNode.RED;
rotateLeft(b);
}
// 2.1、2.3 以及 2.2 -> 2.1
b.color = p.color;
p.color = b.left.color = TreeNode.BLACK;
rotateRight(p);
break;
}
}
// 可能是2.4退出，将 p 节点强制黑色，以实现动态平衡
cur.color = TreeNode.BLACK;
}
}
五、测试及结果
public class Main {
public static void main(String[] args) {
rbTree();
}
private static void rbTree() {
int[] values = new int[]{
12, 1, 9, 2, 0, 11, 7, 19, 4, 15, 18, 5, 14, 13, 10, 16, 6, 3, 8, 17
};
RBTree tree = new RBTree(null);
// 保持输出与【https://www.cs.usfca.edu/~galles/visualization/RedBlack.html】一致的效果
// 优先前驱
tree.setLeftFirst(true);
for (int value : values) {
tree.insert(value);
}
tree.doPreTravel();
tree.remove(14);
tree.doPreTravel();
}
}
-
完全插入完的RBT
完整的RBT.png
-
删除节点14后的RBT
删除节点14后的RBT.png
