之前介绍过二叉查找数，平均情况下查找和插入时间复杂需为1.39logn；最坏情况下为n。算法的改进就引出了红黑树，在插入，删除操作中能够保持树本身高度平衡（红黑树并不是标准平衡二叉树，它以下面的性质 5 作为一种平衡方法，使自己的性能得到了提升）的数据结构。红黑树本质上是一种二叉查找树，但它在二叉查找树的基础上额外添加了一个标记（颜色），同时具有一定的规则。这些规则使红黑树保证了一种平衡，插入、删除、查找的最坏时间复杂度都为 O(logn)。下面来看看这种数据结构的定义：
- 每个节点要么是红色，要么是黑色；
- 根节点永远是黑色的；
- 所有的叶节点都是是黑色的（注意这里说叶子节点其实是上图中的 NIL 节点）；
- 每个红色节点的两个子节点一定都是黑色；
-
从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；
来看看红黑树保持平衡的三板斧：rotateRight, rotateLeft, setColor
接下来以TreeMap来介绍红黑树的实现：
private void rotateLeft(Entry<K,V> p) {
if (p != null) {
Entry<K,V> r = p.right;
p.right = r.left;
if (r.left != null)
r.left.parent = p;
r.parent = p.parent;
if (p.parent == null)
root = r;
else if (p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
r.left = p;
p.parent = r;
}
}
private void rotateRight(Entry<K,V> p) {
if (p != null) {
Entry<K,V> l = p.left;
p.left = l.right;
if (l.right != null) l.right.parent = p;
l.parent = p.parent;
if (p.parent == null)
root = l;
else if (p.parent.right == p)
p.parent.right = l;
else p.parent.left = l;
l.right = p;
p.parent = l;
}
}
private static <K,V> void setColor(Entry<K,V> p, boolean c) {
if (p != null)
p.color = c;
}
对照着上面的图来理解代码。
插入操作
新增的节点默认是红色，这样就不会增加树的高度，但是问题来了，你的父节点是红色怎么办，违背了性质4。上面提到的三板斧出场，以TreeMap为例：
private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED;
while (x != null && x != root && x.parent.color == RED) {
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else {
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;
}
逻辑非常清楚，按照父节点（相对于x）是左节点还是有节点分两大块，这两大块操作对称，我们就以父节点是左节点为例：
- 父节点P的兄弟节点为红，那就让你两兄弟全变成黑，爷爷节点变红，现在我们来看看以爷爷节点为根的这个子树在经过变换后满足黑平衡和性质4，接下来就是确认爷爷节点与在往上的节点有没有冲突，也就是 x = parentOf(parentOf(x))，再while循环往上继续检查。
-
P为黑，接下来分两种：
1)，N是左子节点，将其父节点改为黑，爷爷节点改为红，右旋爷爷节点。看变换后左右的黑平衡都维持原样。
2)，N是左子节点，以P为中心左旋，之后处理同上。
为什么这样？这一切操作都是为了保持红黑树的性质不被破坏。
删除
删除操作是最复杂的。
TreeMap本质上是一个二叉查找树，他的删除操作是这样的：删除节点x，若其左右子树都不为null，则找到右子树最小节点代替x，将问题转化为删除删除右子树最小节点；若节点x有一子树为null，则直接删除再余下顶上。但是它是一个红黑树，若x是个黑节点，则红黑平衡被打破，所以我们拿出三板斧来对树进行修复。（以下分析都是以x在左这一边来分析的，x在右操作方法与左对称）
private void fixAfterDeletion(Entry<K,V> x) {
while (x != root && colorOf(x) == BLACK) {
if (x == leftOf(parentOf(x))) {
Entry<K,V> sib = rightOf(parentOf(x));
代码块一
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
代码块二
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
代码块三
if (colorOf(rightOf(sib)) == BLACK) {
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
代码块四
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root; 为了终止循环
}
} else { 主要对x为左孩子分析，右孩子与其处理方式相同
Entry<K,V> sib = leftOf(parentOf(x));
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateRight(parentOf(x));
sib = leftOf(parentOf(x));
}
if (colorOf(rightOf(sib)) == BLACK &&
colorOf(leftOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(leftOf(sib)) == BLACK) {
setColor(rightOf(sib), BLACK);
setColor(sib, RED);
rotateLeft(sib);
sib = leftOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(leftOf(sib), BLACK);
rotateRight(parentOf(x));
x = root;
}
}
}
setColor(x, BLACK); 性质2：红黑树的根节点一定是黑色
}
先总结一下：再TreeMap中fixAfterDeletion（x）的调用说明被删除的节点为黑，红黑平衡被打破，两种处理办法：1，将x父节点拉下来，使得x这一便高度加一并维持另一边高度不变；2，1处理失效，那么就让以x父节点为根的这颗子树高度整体减一，往上父节点变为x再进行 1 操作。
fixAfterDeletion（x）中x代表什么？两种情况：1，代表被删除节点的左/右子孩子。2，代表将要被删除的节点，其左右子树皆为空。代码逻辑再TreeMap的remove操作里。
情况一：x的兄弟节点为红，那么x的父节点一定为黑，x颜色不用管，如何让x这一边高度加一同时不影响另一边？
经过代码块一之后的模样，此时x这一边高度仍不平衡，其它边平衡没有被打破，兄弟节点变为A，问题接着往下走，沿着代码块来到情况二。
情况二：x的兄弟节点为黑，其左右子树皆为黑。至于父节点P颜色不用管，这里画为红色是因为承接情况一变化而来。
让B变为红色，此时B为根的子树整体高度减去一，则父节点P的左右子树高度相等，P为根的子树现在整体高度比原来小一，P变为x，往上循环比较，目的让P这颗子树高度加一。
情况三：x的兄弟节点的左孩子节点为红。不用考虑P的颜色情况
执行代码块三：A改为黑，B改为红，右旋B。接着代码块往下来到情况四。
情况四：x的兄弟节点为黑，其右孩子节点为红，P，A的颜色任意。
代码块四的逻辑：将B的颜色改为与父节点颜色相同，将父节点P颜色改为黑，将兄弟节点B的右孩子节点K改为黑，左旋P。现在看X到P高度增加一，其它边高度不变，红黑重新平衡。
总结
在我看来红黑树=二叉查找树+红黑平衡
再前面的文章中贴过二叉查找树的代码，是递归版本的，接下来分析TreeMap文章里在介绍其非递归版本。
我想如果我自己实现红黑树，我会针对每种情况写一段代码，而我们看上面的源码，他很巧妙的将其合并统一，区区几十行代码。
前面的图片是来自于看过的多篇分析红黑树的文章，后面删除操作里 的图片是利用EDraw自己画的。
