有别于上一篇文章介绍的红黑树，在《算法<第四版>》一书中用另一套规则实现了红黑树，主要手段是递归，实现思路来自于2-3树，这本书中有详细的解读，在这里我谈谈自己对它的理解。
首先，在之前文章中介绍的红黑树，我们把节点看成红，黑两色，而这里红节点指的是它指向父亲的链接是红色的，有什么不同？当我们介绍左旋，右旋你就会看到。
来看看这套定义红黑树的规则：
- 红链接均为左链接
- 没有任何一个节点同时与两个红链接相连
- 该树是完美的黑平衡，即任何空节点到根节点的路径上的黑链接数目相同
与之前红黑树的不同：之前的红节点在左在右都行。
先来看看关于Node的定义：
private class Node {
private int size;
private Key key;
private Value value;
private Node left;
private Node right;
private boolean color;
public Node(Key key, Value value, boolean color, int size) {
this.color = color;
this.key = key;
this.value = value;
this.size = size;
}
}
只有左右两个指针没了之前的parent指针，加了个size用于记录节点个数，规则是x.size = size(x.left) + size(x.right) + 1;
再来介绍三板斧：rotateLeft， rotateRight， flipColors 这三板斧在变换过程中不会破坏黑平衡
插入操作就用到了上面这三板斧，我们将在插入操作中见识到这套规则的魅力
public void put(Key key, Value value) {
if (key == null) throw new IllegalArgumentException("first argument to put() is null");
if (value == null) {
delete(key);
}
root = put(root, key, value);
root.color = BLACK; //根节点为黑
}
private Node put(Node x, Key key, Value value) {
if (x == null) return new Node(key, value, RED, 1);
int cmp = key.compareTo(x.key);
if (cmp < 0) x.left = put(x.left, key, value);
else if (cmp > 0) x.right = put(x.right, key, value);
else x.value = value;
if (isRed(x.right) && !isRed(x.left)) x = rotateLeft(x);
if (isRed(x.left) && isRed(x.left.left)) x = rotateRight(x);
if (isRed(x.left) && isRed(x.right)) flipColors(x);
x.size = size(x.left) + size(x.right) + 1;
return x;
}
就是二叉查找树的插入操作+重平衡递归式的二产查找树实现
跟之前比简介很多，为什么？原因就在与两套红黑树规则的不同之处，即该套规则红链接均为左链接，不允许有右红节点的出现。
红黑树新插入的节点设置为红色，这样不会破环黑平衡，但可能会破坏规则1和2，可能出现的情况有三种：1.x左黑右红，左旋； 2.x左红，左左红，右旋 ；3. x左右都红，flipColor。这样能够在递归过程中保证一层层往上直到根节点都符合规则，最后要保证根节点为黑。
deleteMin
public void deleteMin() {
if (isEmpty()) throw new NoSuchElementException("the tree is empty");
//为嘛要有这步操作？我的理解：只有一种情况需要将根节点变红否则会出错，那就是头三个左链接皆为黑，
这时候不能让其调用moveRedLeft，前面说过flipColor保持平衡不变是有前提条件的，那么就带来一个问题：
上面的这种情况人为将根节点变红，而且会将这个红链接往下传，想想，这样左子树不就高度减一了吗？
不会，最后从下往上递归修复过程中会将root重新变为红，最后在将其设置为黑。
if (!isRed(root.left) && !isRed(root.right))
root.color = RED;
root = deleteMin(root);
if (!isEmpty()) root.color = BLACK;
}
private Node deleteMin(Node x) {
//为什么返回null？因为我们定义的红黑树，最小节点一定没有子节点
if (x.left == null)
return null;
//为什么判断条件是左儿左孙都为黑调用，因为如下面介绍的那样，moveRedLeft利用三板斧
就管自己的这一亩三分地，然后从上往下递归传递红链接，若存在左儿或左孙为红，那就跳到那去传递它的红链接
if (!isRed(x.left) && !isRed(x.left.left))
x = moveRedLeft(x);
x.left = deleteMin(x.left);
//在我们从上往下改变红黑树的过程中，会出现右链接为红还有两左红链接连一起的情况，
这就需要在递归从下往上过程中进行修复，因为三板斧所以不用担心会破坏平衡
return balance(x);
}
//你会发现凡是调用该方法的节点一定是红
private Node moveRedLeft(Node x) {
// assert (h != null);
// assert isRed(h) && !isRed(h.left) && !isRed(h.left.left);
flipColors(x);
if(isRed(x.right.left)) {
x.right = rotateRight(x.right);
x = rotateLeft(x);
flipColors(x);
}
return x;
}
private Node balance(Node x) {
if (isRed(x.right) &&!isRed(x.left)) x = rotateLeft(x);
if (isRed(x.left) && isRed(x.left.left)) x = rotateRight(x);
if (isRed(x.left) && isRed(x.right)) flipColors(x);
x.size = size(x.left) + size(x.right) + 1;
return x;
}
//空节点为黑
private boolean isRed(Node x) {
if (x == null) return false;
return x.color == RED;
}
如果以之前的红黑树来思考：如果x为黑，它可能有一个右红子节点，他的父亲（p）的情况，他父亲的兄弟（sib）的情况，还有sib两子节点情况，以及sib左子节点的两个子节点情况。我们需要把每种情况都考虑到，很复杂。不过一切的根源就在于x为黑，那x要是红直接删除就可以了，有没有一种办法保证x一定为红？这就是上面代码做的事，让被删除节点为红。
现在来想想怎么把它变红？直接变，这就和之前一样了，要考虑复杂的情况，从下往上的重新平衡树。
我们之前说过flipColor有它的使用前提来保证不会破坏平衡，旋转操作也不会破坏平衡，那moveRedLeft是干嘛用的？人如其名，就是要把红链接往下传的，但是又不能破坏平衡，于是用三板斧来操作，如上述代码，moveRedLeft用三板斧将当前的红链接转到了他的儿子，这样从上往下到最后最小节点一定为红无论他原来是什么（这里有个前提是空连接视为黑），从上而下改变树，这从上而下的变换结果就会让最小节点是一个红的且没有任何子节点。最后在从下往上递归中修复树，即balance函数。
deleteMax
public void deleteMax() {
if (isEmpty()) throw new NoSuchElementException("tree is null");
if (!isRed(root.left) && !isRed(root.right))
root.color = RED;
root = deleteMax(root);
if (!isEmpty()) root.color = BLACK;
}
private Node deleteMax(Node x) {
//如果x左子节点为红，直接右旋，达到rang
if (isRed(x.left))
rotateRight(x);
if (x.right == null)
return null;
if (!isRed(x.right) && !isRed(x.right.left))
x = moveRedRight(x);
x.right = deleteMax(x.right);
return balance(x);
}
//x一定为红链接，将该红链接传到原右儿子处（注意是原右儿子，因为变换后这个原来x的右儿子
可能变成了变换后x的右孙子。。。自己画图就明白了）
private Node moveRedRight(Node x) {
flipColors(x);
if (isRed(x.left.left)) {
x = rotateRight(x);
flipColors(x);
}
return x;
}
主要思想与deleteMin相同，不同在处理手段上。
这里的主要操作就是从根节点开始通过右旋或moveRedRight在从上往下递归过程中不断将红链接传下去（我们定义的红黑树它的最大节点最多有一个左红节点），最后最大节点一定是个无子节点的红节点。再通过从下往上的递归过程中balance（）红黑树。
delete
public void delete(Key key) {
if (key == null) throw new IllegalArgumentException("argument to delete is null");
if (!contains(key)) return;
if (!isRed(root.left) && !isRed(root.right))
root.color = RED;
root = delete(root, key);
if (!isEmpty()) root.color = BLACK;
}
private Node delete(Node x, Key key) {
if (key.compareTo(x.key) < 0) {
if (!isRed(x.left) && !isRed(x.right))
x = moveRedLeft(x);
x.left = delete(x.left, key);
}
else {
if (isRed(x.left))
x = rotateRight(x);
if (key.compareTo(x.key)==0 && x.right == null)
return null;
if (!isRed(x.right) && !isRed(x.right.left))
x = moveRedRight(x);
if (key.compareTo(x.key) == 0) {
Node min = min(x.right);
x.key = min.key;
x.value = min.value;
x.right = deleteMin(x.right);
}
else x.right = delete(x.right, key);
}
return balance(x);
}
public Node min(Node x) {
//assert x!=null
if (x.left == null) return x;
else return min(x.left);
}
这里的处理方式就是deleteMin对左链接和deleteMax对右链接的处理方式的综合
删除操作最终会转化为删除右子树中最小节点操作（例外是右子树为null，那么直接返回null，因为经过从上到下的变换，右子树为null的节点一定是无子节点且颜色为红）；我们从根节点开始，到这右子树的最小节点这一路径上不断变换向下传递红节点，期间并没有影响到树的原有黑平衡（除了一开始人为设置根节点为红，前面说过）。最后再从下自上修复。
总结
这种红黑树的特点：rotateLeft，rotateRight，flipColor这三个操作不会破坏树的黑平衡，于是以此为基础我们就可以来借助递归从上至下的传递红链接，即moveRedLeft，moveRedRight。最后在递归从下至上过程中修复树，即balance。它有别于之前那种红黑树，之前的是先找到目标节点然后综合考虑各种情况以达到黑平衡，是自下而上的处理。
