二 . 红黑树
Published by linzhi teng
二 . 红黑树
1. 红黑树简介
红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:
- 节点是红色或黑色。
- 根节点是黑色。
- 每个叶子节点都是黑色的空节点（NIL节点）。
- 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
2. 红黑树的修正
变色、左旋、右旋是红黑树在二叉树上的扩展操作，同时也是基于这三个操作才能遵守红黑树的五个特性。
2.1 左旋
/*
* 左旋做了三件事：
* 1. 将y的左子节点赋给x的右子节点,并将x赋给y左子节点的父节点(y左子节点非空时)
* 2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右)
* 3. 将y的左子节点设为x，将x的父节点设为y
*/
public void leftRotate(RBNode x) {
if (x == null) return;
//1. 将y的左子节点赋给x的右子节点,并将x赋给y左子节点的父节点(y左子节点非空时)
RBNode y = x.right;
x.right = y.left;
if (y.left != null) {
y.left.parent = x;
}
//2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右)
y.parent = x.parent;
if (x.parent == null) {
this.mRoot = y;
} else {
if (x == x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}
}
//3. 将y的左子节点设为x，将x的父节点设为y
y.left = x;
x.parent = y;
}
2.2 右旋
/* 右旋做了三件事：
* 1. 将x的右子节点赋给y的左子节点,并将y赋给x右子节点的父节点(x右子节点非空时)
* 2. 将y的父节点p(非空时)赋给x的父节点，同时更新p的子节点为x(左或右)
* 3. 将x的右子节点设为y，将y的父节点设为x
*/
public void rightRotate(RBNode y) {
if (y == null) return;
//1. 将x的右子节点赋给y的左子节点,并将y赋给x右子节点的父节点(x右子节点非空时)
RBNode x = y.left;
y.left = x.right;
if (x.right != null) {
x.right.parent = y;
}
//2. 将y的父节点p(非空时)赋给x的父节点，同时更新p的子节点为x(左或右)
x.parent = y.parent;
if (y.parent == null) {
this.mRoot = x;
} else {
if (y == y.parent.left) {
y.parent.left = x;
} else {
y.parent.right = x;
}
}
//3. 将x的右子节点设为y，将y的父节点设为x
x.right = y;
y.parent = x;
}
3. 红黑树节点的添加
- 红黑树的第 5 条特征规定，任一节点到它子树的每个叶子节点的路径中都包含同样数量的黑节点。也就是说当我们往红黑树中插入一个黑色节点时，会违背这条特征。
- 同时第 4 条特征规定红色节点的左右孩子一定都是黑色节点，当我们给一个红色节点下插入一个红色节点时，会违背这条特征。
- 因此我们需要在插入黑色节点后进行结构调整，保证红黑树始终满足这 5 条特征。
3.1 红黑树插入后节点的调整思想:
插入黑色节点的时候担心违背第5条，插入红色节点时担心违背第4条，所以我们将将插入的节点改为红色，然后判断插入的节点的父亲是不是红色，是的话进行修改调整（变色、左旋、右旋）。同时在调整的过程中我们需要遵守5条特性。
新插入的节点是红色的，插入修复操作如果遇到父节点的颜色为黑则修复操作结束。也就是说，只有在父节点为红色节点的时候是需要插入修复操作的。
插入修复操作分为以下的三种情况，而且新插入的节点的父节点都是红色的：
- 叔叔节点也为红色。
- 叔叔节点为空，且祖父节点、父节点和新节点处于一条斜线上。
- 叔叔节点为空，且祖父节点、父节点和新节点不处于一条斜线上。
3.1.1 插入操作-case 1(叔叔节点也为红色)
叔叔节点也为红色。
case 1的操作是将 父节点和叔叔节点 与 祖父节点 的颜色互换，这样就符合了RBTRee的定义。即维持了高度的平衡，修复后颜色也符合RBTree定义的第三条和第四条。下图中，操作完成后A节点变成了新的节点。如果A节点的父节点不是黑色的话，则继续做修复操作。
3.1.2 插入操作-case 2
叔叔节点为空，且祖父节点、父节点和新节点处于一条斜线上。
case 2的操作是：
- B和C都是左节点，将B节点进行右旋操作，并且和父节点A互换颜色。通过该修复操作RBTRee的高度和颜色都符合红黑树的定义。
- 如果B和C节点都是右节点的话，只要将操作变成B节点左旋就可以了。
3.1.3 插入操作-case 3
叔叔节点为空，且祖父节点、父节点和新节点不处于一条斜线上。
case 3的操作是：
- C是右节点，将C节点进行左旋，这样就从case 3转换成case 2了，然后针对case 2进行操作处理就行了。case2操作C节点做了一个右旋操作和颜色互换来达到目的。
- 如果C是左节点，将C节点进行右旋，转换成case2，再左旋就可以了。
4. 红黑树节点的删除
- 如果删除节点的左孩子和右孩子不同时为null，那么只需要让其子树继承删除该节点的位置
- 如果删除的节点是叶子节点，我们直接进行调整；
- 假如删除节点的左右孩子都不是null，需要后继节点替换被删除的节点和值和颜色，这样才不会引起红黑树平衡的破坏，只需要对 后继节点删除后进行调整，这样我们就回归处理情况 1 和 2 的状态；
- 后继节点为左子树最右边的子叶节点
- 后继节点为右子树最左边的叶子节点；
- 如果需要删除的节点颜色为红色，那么红黑树的结构不被破坏，也就不需要进行调整。如果我们判断删除节点的颜色为黑色，那么就进行调整；
4.1 红黑树删除之节点调整
调整思想：
为了保证删除节点的父节点左右两边黑色节点数一致，需要重点关注父节点没删除的那一边节点是不是黑色。
- 如果删除后父亲节点另一边比删除的一边黑色多，就要想办法搞到平衡。
- 1、把父亲节点另一边（即删除节点的兄弟树）其中一个节点弄成红色，也少了一个黑色。
- 2、或者把另一边多的节点（染成黑色）转过来一个
- 删除修复操作是针对删除黑色节点才有的，当黑色节点被删除后会让整个树不符合RBTree的定义的第四条。
- 当前节点是黑色的，且兄弟节点是红色的（那么父节点和兄弟节点的子节点肯定是黑色的）；
- 当前节点是黑色的，且兄弟节点是黑色的，
1）、兄弟节点的两个子节点均为黑色的；
2）、兄弟节点的左子节点是红色，右子节点时黑色的；
3）、兄弟节点的右子节点是红色，左子节点任意颜色；
4.1.1 删除操作-case 1
待删除的节点的兄弟节点是红色的节点。
将父节点涂红，将兄弟节点涂黑，然后将当前节点的父节点进行支点左旋。
case 1这样转换之后就会变成后面的case 2，case 3，或者case 4进行处理了。
4.1.2 删除操作-case 2
待删除的节点的兄弟节点是黑色的节点，且兄弟节点的子节点都是黑色的。
将兄弟节点涂红，将当前节点指向其父节点，将其父节点指向当前节点的祖父节点，继续往树根递归判断以及调整；
4.1.3 删除操作-case 3
待调整的节点的兄弟节点是黑色的节点，且和兄弟节点在一条斜线上的子节点也是黑色，另一个子节点是红色。
把当前节点的兄弟节点涂红，把兄弟节点的左子节点涂黑，然后以兄弟节点作为支点做右旋操作。
case 3的删除操作是一个中间步骤，它的目的是将左边的红色节点借调过来，这样就可以转换成case 4
4.1.4 删除操作-case 4
待调整的节点的兄弟节点是黑色的节点，且和兄弟节点在一条斜线上的子节点是红色，另一个子节点任意
把兄弟节点涂成父节点的颜色，再把父节点涂黑，把兄弟节点的右子节点涂黑，然后以当前节点的父节点为支点做左旋操作。
