本文的实现都来自《算法导论》
所有的东西都是根据书中的思路来的，加上我自己的理解。（推荐配合书本来阅读）。但是，这篇文章，我不会像《算法导论》一样逐个逐个情况地分析，我会捉住关键思想。其实，我觉得，如果你想非常严谨地考察红黑树的插入、删除修复，没有什么会比《算法导论》更加好。
本文中，我假设你已经熟悉普通二叉树的插入、删除算法。
修复的总体思想
-
自底向上:
1.2 对于删除，我们会看到，它的修复一定也是从最底部开始。所有删除情况都可以转换成在这两种：
1.1 对于插入，新插入的结点一定在最底部，所以修复一定从最底部开始
如果能局部（i.e. 在当前树内）通过旋转或改变颜色完成修复，那么就修复它，并结束。比如上图，如果我们能在当前树（i.e. 以"z"为根的树）内解决问题，那么我们就可以结束了。
如果不能，我们改变当前树某些结点的颜色，然后向上传递。
从这里，我们就可以看出，为什么红黑树在插入、删除频繁的场景下比AVL树优。因为对于插入的修复，红黑树会一直向上传递，然后在适当的地方执行最多两次旋转，然后结束。对于删除的修复，红黑树会一直向上传递，然后在适当的地方执行最多三次旋转，然后结束。而AVL树，它的插入修复策略也是一直向上传递，然后在适当的地方执行旋转，然后结束；但是它的删除修复策略是一边向上传递，一边旋转，直至到达根。
更深一步
有必要强调这个事实：
未做修改前，树是满足所有红黑性质的
- 删除"z"结点后：
"z"结点的所有组先都不满足性质五。亦即，我们的修复有可能要涉及"z"一直到根节点这条路径，而且，也只会涉及这条路径。 - 插入”x"结点后：
”x"结点位于最底部，树中只有”x"结点这一处可能破坏了红黑性质，然后我们向上传递直至能局部修复。任意时刻，我们保证树中只有一处地方破坏了一个红黑性质，或是性质四，或是性质二。（这个证明在《算法导论中》，最好看一看） - 红黑性质对每一个结点都有约束，比如性质五：任一个结点到它的后代叶子结点的路径上的黑结点数量都相同。在向上传递时，很重要的一件事就是：我们必须先把当前树的所有红黑性质都修复好，然后再向上传递。然后去到上一层后，我们就不再需要关心下面的树了。这是一个回溯算法的思想。只不过我们用parent来回溯。
实现红黑树的顺序：
-
leftRotate(Node x) 和 rightRotate(Node y) 平衡二叉树的左旋和右旋操作。这两个操作在实现AVL树也要用到。写代码时，只需要把x和y当成平衡二叉树的结点就可以了。实现时，可以参考书中的图，非常清晰：
isValidBST()验证是否为平衡二叉树（这个代码通过LeetCode测试的，应该无问题），每次调用 leftRotate() 和 rightRotate()后就验证一次。
isValidRBT()根据红黑树的五个性质逐一验证。直接看代码就可以了，个人认为比较清晰。
insert() 找到要插入的位置，执行插入，然后调用isValidBST()验证是否仍为平衡二叉树，然后调用fixAfterInsertion()，之后再调用isValidRBT()验证是否红黑树。
package datastru;
import java.util.Random;
//3.5 has bug
//int version
public class RedBlackTree {
private static final boolean RED = true;
private static final boolean BLACK = false;
/**
* sentimal, used as parent of root and leaf-node
*/
private Node NIL = new Node(0, null, null, null, BLACK);
private Node root = NIL; //root of red black tree
private static class Node {
int key;
Node left;
Node right;
Node parent;
boolean color;
public Node(int key, Node left, Node right, Node parent, boolean color) {
this.key = key;
this.left = left;
this.right = right;
this.parent = parent;
this.color = color;
}
}
public void insert(int keyToInsert) {
insert(new Node(keyToInsert, NIL, NIL, NIL, RED));
}
private void insert(Node z) {
//x is used to traverse, and y is always the parent of x
Node y = NIL;
Node x = root;
while(x != NIL) {
y = x;
if(z.key < x.key)
x = x.left;
else if(z.key > x.key)
x = x.right;
else
return;
}
//let z become y's children
z.parent = y;
if(y == NIL)
/* by the way, this indicates:
This is an empty red-black-tree(i.e a tree that just contains a NIL) */
root = z;
else if(z.key < y.key)
y.left = z;
else
y.right = z;
assert isValidBST();
fixAfterInsertion(z);
assert isValidBST();
assert isRBT();
}
private void fixAfterInsertion(Node z) {
/* 红黑树有5个性质
一、每个结点非红即黑
二、根节点是黑色
三、叶子结点是黑色
四、红结点的两个子节点都是黑节点
五、对每个结点，从它到它的后代叶子结点的所有简单路径上，黑节点的数量都相同
*/
/*
z为新插入的结点，它是红色的，它的两个孩子都是叶子节点(NIL)
所以，如果此时红黑树性质被破坏，只有两种可能：
1. z就是根节点，这破坏了性质二
2. z和z.parent都是红色，这破坏了性质四
*/
/*
z在这个函数中的语义：
就像下面的invariants(3)提到的，整个修复过程，红黑树只有一处违反了红黑性质
且这一处，要么违反的是性质二，要么违反的是性质四。（如果你迷糊了，只要这样想：
未插入之前，这是一颗红黑树，插入时在最底部进行的，那么当然此时只可能在一处违反红黑性质，
然后，我们的修复策略每次都会将这一处修复，然后向上传递，直至能够在某个地方完全修复，
或一直传递到顶部）
所以我们只需关注：z, z.parent, z的uncle
*/
/* How fix strategy works?
在情况一中：为什么能够只通过更换颜色来修复 "z和z.parent都是红色"
在情况二和情况三中：我们为什么能够通过旋转来修复 "z和z.parent都是红色"
the shared answer:
对于z的两个子树、z.parent的一个子树、uncle的两个子树，
它们的根都是黑色，而且它们都具有相同的黑高
*/
/*
如果进入了循环（也就是 z.parent.color == RED 为true），
那么我们在循环体中修复 "z和z.parent都是红色" ，
a)如果是通过情况二或情况三修复的，那么直接退出循环。
b)如果是通过情况一修复的，将z上移两层。新的z将会是红色，
那么我们在下一次循环就看下：新的z和它的父亲是否都是红色，
是就继续执行修复，否就退出循环。(i.e. 向上传递。。。)
invariants:
1. z是红色的
2. 如果z.parent为根节点，那么z.parent是黑色的（也就是性质二没有被破坏)
3. 如果有任何红黑性质被破坏，则至多只有一条被破坏，或是性质二，或是性质四。
3.1如果是性质二，那么就是：z.parent为根节点，且z.parent是红色的，出现这种情况的原因是
经过一次或多次向上传递(i.e. 执行一次或多次循环体的情况一)，z从红黑树的底部传到最顶部了
3.2如果是性质四，那么就是：z和z.parent都是红色的，这正正就是while循环体要修复的
这三个invariants在：
第一次循环开始之前都成立、（初始）
在循环的每次迭代后(i.e. 每次循环体执行完毕后)成立、（保持）
在循环终止后也成立（终止） 这能推导出一个有用的性质
/
/
\/
invariants(3)指出要么是性质二不成立，要么是性质四不成立，
现在z的父亲为黑色，那么性质四肯定成立，性质二有可能不成立
具体场景看最后一行代码
*/
while(z.parent.color == RED) {
//当在循环体中引用z的爷爷时，由invariants(2)可知，z的爷爷必定存在(i.e. 不为NIL)
if(z.parent == z.parent.parent.left) {
Node uncle = z.parent.parent.right;
if(uncle.color == RED) { //case 1
uncle.color = z.parent.color = BLACK;
z.parent.parent.color = RED;
z = z.parent.parent; //向上传递
//case 1结束后有可能退出循环，也有可能继续循环
}
else {
if(z == z.parent.right) { //case 2，转变为case3
z = z.parent;
leftRotate(z);
}
//case 3:
z.parent.color = BLACK;
z.parent.parent.color = RED;
rightRotate(z.parent.parent);
//case 3结束后必定退出循环
assert z.parent.color == BLACK;
}
}
else { //与上面代码基本一样，对称
if(z.parent == z.parent.parent.right) {
Node uncle = z.parent.parent.left;
if(uncle.color == RED) {
uncle.color = z.parent.color = BLACK;
z.parent.parent.color = RED;
z = z.parent.parent;
}
else {
if(z == z.parent.left) {
z = z.parent;
rightRotate(z);
}
z.parent.parent.color = RED;
z.parent.color = BLACK;
leftRotate(z.parent.parent);
assert z.parent.color == BLACK;
}
}
}
}
/*
经过若干次迭代后，如果z是根节点，且它是红色，
那么z的父亲(i.e. NIL)就是黑色，循环终止。此时性质二不成立。
现在修复它：
*/
root.color = BLACK;
}
public void delete(int keyToDelete) {
Node x = root;
while(x != NIL) {
if(x.key < keyToDelete)
x = x.right;
else if(x.key > keyToDelete)
x = x.left;
else {
delete(x);
break;
}
}
}
private Node successor(Node t) {
if(t.left == NIL)
return t;
return successor(t.left);
}
private void delete(Node z) {
assert z != NIL;
if(z.left != NIL && z.right != NIL) {
Node successor = successor(z.right);
z.key = successor.key;
//not recursion, just an way to turn if-case to else-case
//and more importantly, highlight the semantic
delete(successor);
}
else {
Node x = (z.left != NIL) ? z.left : z.right; //NOTE that, x may be NIL
boolean needToFixUp = z.color == BLACK;
//make the subTree rooted at 'x' be the child of z.parent
x.parent = z.parent;
if(z.parent == NIL)
root = x;
else {
if(z.parent.left == z)
z.parent.left = x;
else
z.parent.right = x;
}
//now, x is replacement of the deleted Node
if(needToFixUp)
fixAfterDeletion(x);
}
}
private void fixAfterDeletion(Node x) {
/*
只考虑x为左孩子的情况，x是右孩子的情况对称。。。
*/
}
//treat x as a binary-search-tree node, left rotate it
private void leftRotate(Node x) {
assert x.right != NIL;
Node y = x.right;
Node subTree = y.left;
x.right = subTree;
if(subTree != NIL)
subTree.parent = x;
Node p = x.parent;
y.parent = p;
if(p == NIL)
root = y;
else if(p.left == x)
p.left = y;
else
p.right = y;
x.parent = y;
y.left = x;
assert isValidBST();
}
//treat y as a binary-search-tree node, right rotate it
private void rightRotate(Node y) {
assert y.left != NIL;
Node x = y.left;
Node subTree = x.right;
y.left = subTree;
if(subTree != NIL)
subTree.parent = y;
Node p = y.parent;
x.parent = p;
if(p == NIL)
root = x;
else if(p.left == y)
p.left = x;
else
p.right = x;
x.right = y;
y.parent = x;
assert isValidBST();
}
/* Debug methods: */
private boolean isRBT() {
if(root == NIL) //empty
return true;
return root.color == BLACK && isRBT(root);
}
private boolean isRBT(Node t) {
Node tp = t.parent, tl = t.left, tr = t.right;
if (tp != NIL && t != tp.left && t != tp.right)
return false;
if (tl != NIL && (tl.parent != t || tl.key > t.key))
return false;
if (tr != NIL && (tr.parent != t || tr.key < t.key))
return false;
if (t.color == RED && tl != NIL && tl.color == RED)
return false;
if (t.color == RED && tr != NIL && tr.color == RED)
return false;
if(!hasSameNumberOfBlackNodeInAllPaths(t))
return false;
//recursive check
if (tl != NIL && !isRBT(tl))
return false;
if (tr != NIL && !isRBT(tr))
return false;
return true;
}
private int expectedBlackNodeCount;
private boolean hasSameNumberOfBlackNodeInAllPaths(Node t) {
//for convenience, when computing how many black node in a path:
//root(t) is included
//leaf(NIL) is included
expectedBlackNodeCount = 1; //there must be a leaf node in any path
Node x = t;
while(x != NIL) {
if(x.color == BLACK)
expectedBlackNodeCount ++;
x = x.left;
}
return backTrack(t, 0);
}
private boolean backTrack(Node t, int count) {
if(t == NIL)
return count + 1 == expectedBlackNodeCount;
if(t.color == BLACK)
count ++;
return backTrack(t.left, count) &&
backTrack(t.right, count);
}
private boolean isValidBST(Node root, Integer lowerBound, Integer uppperBound) {
if(root == NIL)
return true;
boolean isRootInRange = (lowerBound == null || root.key > lowerBound) &&
(uppperBound == null || root.key < uppperBound);
if(!isRootInRange)
return false;
return isValidBST(root.left, lowerBound, root.key) &&
isValidBST(root.right, root.key, uppperBound);
}
private boolean isValidBST() {
return isValidBST(root, null, null);
}
/*some tests*/
private static void insertAscendly() {
RedBlackTree rbt = new RedBlackTree();
for(int i = 1; i < 1000; i ++)
rbt.insert(i);
}
private static void insertDescendly() {
RedBlackTree rbt = new RedBlackTree();
for(int i = 1000; i >= 0; i --)
rbt.insert(i);
}
private static void insertRandomly() {
RedBlackTree rbt = new RedBlackTree();
Random ra =new Random();
for (int i = 0 ;i < 1000; i++) {
rbt.insert(ra.nextInt(10000000));
}
}
private static void testDeleteWithoutFixUp() {
RedBlackTree rbt = new RedBlackTree();
Random ra =new Random();
int[] keys = new int[1000];
for (int i = 0 ;i < 1000; i++) {
keys[i] = ra.nextInt(10000000);
rbt.insert(keys[i]);
}
for(int i = 0; i < 100; i ++) {
rbt.delete(keys[i]);
}
assert rbt.isValidBST();
rbt = new RedBlackTree();
for(int i = 1000; i >= 0; i --)
rbt.insert(i);
for(int i = 1000; i >= 0; i --)
rbt.delete(i);
assert rbt.isValidBST();
rbt = new RedBlackTree();
for(int i = 0; i < 1000; i ++)
rbt.insert(i);
for(int i = 0; i < 1000; i ++)
rbt.delete(i);
assert rbt.isValidBST();
}
public static void main(String[] args) {
insertAscendly();
insertDescendly();
insertRandomly();
}
}
