红黑树
1.前言
一棵高度为h的二叉搜索树，基本操作时间复杂度为O(h)，当二叉搜索树高度较低时，效率较高，如果二叉搜索树高度较高则效率较低了，极限情况下，向二叉搜索树顺序插入一个数组，那么二叉搜索树的效率为O(n)。
红黑树也是一种二叉搜索树，它在每一个结点上添加了颜色，颜色可以是红或黑。通过相关规则约束，红黑树确保没有一条路径会比其它路径长出2倍，因此红黑树是近似平衡的，不会出现前文所说的极限情况。
红黑树必须满足以下五个条件：
- 每个结点颜色是红色或者是黑色
- 根结点是黑色的
- 每个叶结点（指空结点，非叶子结点）是黑色的
- 如果一个结点是红色的，那么它的两个子结点都是黑色的
- 对每一个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
一棵典型的红黑树：
rbtree.jpg
为什么红黑树没有一条路径会比其它路径长两倍呢？
红黑树中最短的路径，一定是全黑结点，最长的路径一定是黑红相间节点，要保持性质5，所以最长路径是最短路径的2倍
2、红黑树插入
红黑树的插入和二叉搜索树插入类似，根据结点值的大小，确定它的位置。
public void rb_insert(RBNode z){
RBNode y = null;
RBNode x = mRoot;
while (x != null) {
y = x;
if (z.value < x.value) {
x = x.left;
}else {
x = x.right;
}
}
z.parent = y;
if (y == null) {
mRoot = z;
}else if (z.value < y.value) {
y.left = z;
}else {
y.right = z;
}
z.left = null;
z.right = null;
z.color = RED;
rb_insert_fixup(z);
}
由于新插入节点可能破坏红黑树的性质， 所以插入最后必须进行红黑树性质的修复。
为了尽量少违背红黑树的性质，设定新插入节点的颜色均为红色
由于新插入节点为红色，可能出现以下几种情况：
- 新插入节点为根节点，直接置黑即可
- 新插入节点的父节点为黑色，不违背任何规则
- 新插入节点的父节点为红色，违背规则4
如果违背规则4，那么也有以下三种情况出现（新插入节点为z）
1、父节点及叔叔节点均为红色，祖父节点为黑色（根据红黑树性质，未插入前没有任何规则被破坏，那么祖父节点不可能为红色）
Paste_Image.png
此时，规则4被破坏，则规则5是正常的，只需将父节点、叔叔节点置为黑色，祖父节点置为红色，此当前子树完成平衡。采取递归思想，将整棵子树当成一个新的红色节点向上循环处理，设置z等于祖父节点
2、z的叔叔节点为黑色且z是右子节点
Paste_Image.png
红黑树插入修复的终极思想是，把多余的红色节点向根节点方向移动，变成根节点
根据插入修复思想，目前z是一个多余的红色节点，且此时节点不平衡，为了让z向根节点方向移动，则以z的父节点左旋转即可
3、z的叔叔节点为黑色且z是左子节点
Paste_Image.png
此时，以z的祖父节点右旋转，同时将z的父节点设置为黑色，祖父节点设置为红色，此时，红黑树平衡了。
仔细观察，其实情况2这么做，也是为了满足情况3的初始条件，以便旋转后，达到新的平衡。
//添加修复核心思想为，将多作的红色节点向根节点移动，最后把根节点弄成黑色即可
public void rb_insert_fixup(RBNode z){
RBNode y = null;
while (z.parent != null && z.parent.color == RED) {
if (z.parent == z.parent.parent.left) {
y = z.parent.parent.right;
//z的父节点为红，叔叔节点也为红
if (y.color == RED) {
z.parent.color = BLACK;
y.color = BLACK;
z.parent.parent.color = RED;
z = z.parent.parent;
}else if (z == z.parent.right) {
//叔叔节点为黑，且z是z的父亲的右子节点
z = z.parent;
leftRotate(z);
}else {
//叔叔节点为黑，且z是z的父亲的左子节点
z.parent.color = BLACK;
z.parent.parent.color = RED;
rightRotate(z.parent.parent);
}
}else {
y = z.parent.parent.left;
if (y.color == RED) {
z.parent.color = BLACK;
y.color = BLACK;
z.parent.parent.color = RED;
z = z.parent.parent;
}else if (z == z.parent.left) {
//叔叔节点为黑，且z是z的父亲的右子节点
z = z.parent;
rightRotate(z);
}else {
//叔叔节点为黑，且z是z的父亲的左子节点
z.parent.color = BLACK;
z.parent.parent.color = RED;
leftRotate(z.parent.parent);
}
}
}
mRoot.color = BLACK;
}
3、红黑树删除
红黑树的删除比插入更复杂，情况更多，但思想是一致的。类似二叉搜索树，找节点删除，维持二叉搜索树的性质，再修复红黑树的性质
public void rb_delete(RBNode z){
RBNode y = z;
RBNode x = null;
int yOriginColor = y.color;
if (z.left == null) {
x = z.right;
rb_transplant(z, z.right);
}else if (z.right == null) {
x = z.left;
rb_transplant(z, z.left);
}else {
y = treeMin(z.right);
yOriginColor = y.color;
x = y.right;
if (y.parent == z) {
x.parent = y;
}else {
rb_transplant(y, y.right);
y.right = z.right;
y.right.parent = y;
}
rb_transplant(z, y);
y.left = z.left;
y.left.parent = y;
y.color = z.color;
}
if (yOriginColor == BLACK) {
rb_delete_fixup(x);
}
}
删除节点的关键是：
- 如果删除的是红色节点，那么不会破坏性质
- 如果删除的是黑色节点，那么，这个路径上会少一个黑色节点，性质5被破坏。所以删除算法就是通过重新着色、旋转，来恢复性质5
1、节点n为黑色，兄弟节点s也为黑色，s的子节点也为黑色
Paste_Image.png
将s节点设置为红色，当前子树已经恢复平衡，但由于删除了一个黑色节点，整体仍未平衡。以递归思想处理，将n赋值为p，以整个子树为新的n
2、承接上文，s节点为红，且s的子节点都为黑
Paste_Image.png
将s和p节点颜色互换，同时在p节点左旋
3、s左节点为红，自身为黑时
Paste_Image.png
交换s和sl颜色，同时以s中心右旋转
4、s右节点为红，自向为黑
Paste_Image.png
将s颜色置为s父节点的颜色，s父节点颜色置黑，右节点颜色置黑，同时以s父节点左旋转
//删除修复的核心思想是，x代替了y原来的位置，如果y是黑的，y位置移动了，那么规则5可能被破坏
//如果想象x有两个颜色，自身加一个黑色，替补y的黑色，那规则5则不再破坏
//如果x自身为红色加额外黑色，则此时所有规则都ok
//如果x自身为黑，额外也是黑，那么规则5则被破坏
//现在则要想办法将x弄成红色+黑色的模式，将多余黑色向根节点移动
public void rb_delete_fixup(RBNode x){
if (x == null) {
return;
}
RBNode w = null;
while (x != mRoot && x.color == BLACK) {
if (x == x.parent.left) {
w = x.parent.right;
if (w.color == RED) {
w.color = BLACK;
x.parent.color = RED;
leftRotate(x.parent);
w = x.parent.right;
}else if ((w.left == null || w.left.color == BLACK)
&& (w.right == null || w.right.color == BLACK)) {
w.color = RED;
x = x.parent;
}else if (w.right == null || w.right.color == BLACK) {
w.left.color = BLACK;
w.color = RED;
rightRotate(w);
w = x.parent.right;
}else {
w.color = x.parent.color;
x.parent.color = BLACK;
w.right.color = BLACK;
leftRotate(x.parent);
x = mRoot;
}
}else {
w = x.parent.left;
if (w.color == RED) {
w.color = BLACK;
x.parent.color = RED;
rightRotate(x.parent);
w = x.parent.left;
}else if ((w.left == null || w.left.color == BLACK)
&& (w.right == null || w.right.color == BLACK)) {
w.color = RED;
x = x.parent;
}else if (w.left == null || w.left.color == BLACK) {
w.right.color = BLACK;
w.color = RED;
leftRotate(w);
w = x.parent.left;
}else {
w.color = x.parent.color;
x.parent.color = BLACK;
w.left.color = BLACK;
rightRotate(x.parent);
x = mRoot;
}
}
}
x.color = BLACK;
}
以上即是红黑树删除操作，在算法导论上，红黑树删除思想是，设置N节点有两重颜色，自已本身颜色加上额外黑色，用以补偿被删除的黑色节点，然后想办法将N的颜色置为红色加黑色或者是根节点，然后置为黑色，则整个红黑树重新平衡。但以上四种情况也是一样的
红黑树的插入删除操作都挺复杂的，本人自己也有很多不理解的，现在记录如上，相信随意时间推移，会有更多新的理解。
以上所有代码均上传到本人github，欢迎访问。
