一、《算法—深入浅出》N叉树的介绍
二、《算法—深入浅出》红黑树的旋转
三、《算法—深入浅出》红黑树的插入
四、《算法—深入浅出》红黑树的删除
一、前言
相信大家已经有了基本的节点旋转知识，本篇直接进入主题：新增节点。
新增节点的两条基础理论：
新增的节点一定是插入在叶子节点（除非该树为空）；
新增的节点颜色一定先涂为红色；
第1点很好理解，因为 RBT 也是 BST 树，因此，通过二分法查找到叶子节点后，再插入新的节点；
这是需要满足红黑树第5点性质（任一节点到叶子节点，所有路径上的黑色节点数都要相同），因此，新增红色节点不会改变这条性质。
二、插入
A）根据上面的基础理论，插入也就可以划分为：
- 新增节点在左子树的左叶子节点；
- 新增节点在左子树的右叶子节点；
- 新增节点在右子树的左叶子节点；
- 新增节点在右子树的右叶子节点；
B）同时考虑因为新增节点是红色节点：
- 如果其父节点是黑色，那么结束，不需要调整；
- 如果其父节点是红色，那么就违反了 RBT 第4点，上下相邻不能有连续的红色节点；
因此，我们只需要考虑（A）中四种情况 +（B）中第2种情况即可。
在调整红黑树时，我们不能只看父节点，还需要看其叔叔节点（父与叔都是其祖父的儿子节点）：
示意.png
如上图：
- 未插入 14 节点前，有可能的状态：祖父黑色、父红色、叔叔黑色；
- 插入 14 节点后，就违背第 4 点；
但如果仅仅只是改变『父节点』的颜色，可能就违背第 5 点（所有路径黑色节点数相同）；
之所有存在这种情况，是因为之前 RBT 已经满足 5 条要求，但『父节点』与『叔叔节点』颜色不一致。
可以查看《算法—深入浅出》N叉树的介绍中红黑树的例子。
所以，插入节点后，是否需要调整 RBT 要看父节点与叔叔节点这两个节点的颜色，再考虑所在的子树的左或右来旋转。
2.1、左子树 + 新增节点
- 如果父节点为黑色，则本次结束；
：当父节点存在 && 父节点为红色（祖父节点必为黑色，RBT 第4点）：
- 如果叔叔节点为红色，那么；
- 改变父节点和叔叔节点为黑色，祖父节点为红色；
- 将当前节点指向祖父节点；
- 继续；
- 如果新增节点为父节点的右节点：
- 左旋父节点；
- 互换父节点与新增节点的指针；
- 如果叔叔节点为黑色（叔叔节点不存在也是黑色，RBT 第3点 叶子NIL节点是黑色），则：
- 改变父节点为黑色，祖父节点为红色；
- 右旋祖父节点；
- 继续；
针对上面的2、3、4，我们用图来说明：
-
第4点情况示意图：
4.png
-
第3点情况示意图：
3.png
-
第2点情况示意图：
2.png
请注意，上面三个示意图中，大家请仔细的看看：
- 4.a
- 3.c
- 2.c
你会发现，第2、3点的情况，最终都会转化为第4点的初始状态！我把上面三张图再合成为一张大图大家看看：
左+新.png
2.2、右子树 + 新增节点
我们分析完了『左子树 + 新增节点』，那么『右子树 + 新增节点』实际上就是对其条件的左、右互换，以及旋转互换！
2.3、完整的图例
红黑树插入.png
三、算法实现
public class RBTree {
/*****************************************************************************
* 插入新结点
*****************************************************************************/
public void insert(TreeNode cur) {
TreeNode p = root;
TreeNode g = p;
while (p != null) {
g = p;
if (cur.value < p.value) {
p = p.left;
} else {
p = p.right;
}
}
if (g == null) {
root = cur;
} else if (cur.value < g.value) {
g.left = cur;
} else {
g.right = cur;
}
cur.parent = g;
cur.color = TreeNode.RED;
// 插入完后，修正红黑树
// 可能违背：
// 第4点：如果一个节点是红色的，则它的子节点必须是黑色的
// 第2点：新插入结点就是根节点，因此，需要着色为黑色
fixedInsert(cur);
}
/*****************************************************************************
* g: 祖父节点
* u：叔叔节点
* p：父节点
* cur：新插入节点
*****************************************************************************/
private void fixedInsert(TreeNode cur) {
TreeNode g, u;
TreeNode p;
while ((p = cur.parent) != null && p.color == TreeNode.RED) {
g = p.parent;
/******************************************************
* 【左、右】算法互为镜像
******************************************************/
if (g != null) {
/*************************************************
* 叔叔节点且红色：
* 1. 修改：p & u 为黑色；
* 2. 修改：g 为红色；
*************************************************/
u = (p == g.left ? g.right : g.left);
if (u != null && u.color == TreeNode.RED) {
u.color = TreeNode.BLACK;
p.color = TreeNode.BLACK;
g.color = TreeNode.RED;
cur = g;
continue;
}
/**************************************************
* 左子树
**************************************************/
if (p == g.left) {
/*********************************************
* g g g
* / / /
* p => cur => p
* \ / /
* cur p cur
*********************************************/
if (cur == p.right) {
rotateLeft(p);
TreeNode temp = cur;
cur = p;
p = temp;
}
/*********************************************
* 1. 叔叔节点为黑色
* 2. 叔叔节点不存在，即叶子结点NIL也是黑色
*
* g p
* / / \
* p => cur g
* /
* cur
*********************************************/
p.color = TreeNode.BLACK;
g.color = TreeNode.RED;
rotateRight(g);
} else {
/*********************************************
* g g g
* \ \ \
* p => cur => p
* / \ \
* cur p cur
*********************************************/
if (cur == p.left) {
rotateRight(p);
TreeNode temp = cur;
cur = p;
p = temp;
}
/*********************************************
* 1. 叔叔节点为黑色
* 2. 叔叔节点不存在，即叶子结点NIL也是黑色
*
* g p
* \ / \
* p => g cur
* \
* cur
*********************************************/
p.color = TreeNode.BLACK;
g.color = TreeNode.RED;
rotateLeft(g);
}
}
}
// 最后，必需确保满足根节点必需是黑色
// 因为我们的调整，到根节点（当 g 点为 null 时，表明 parent 已经为树根）
root.color = TreeNode.BLACK;
}
}
网友评论