红黑树
排序二叉树虽然可以快速检索，但在最坏的情况下：如果插入的节点集本身就是有序的，要么是由小到
大排列，要么是由大到小排列，那么最后得到的排序二叉树将变成链表：所有节点只有左节点（如果插
入节点集本身是大到小排列）；或所有节点只有右节点（如果插入节点集本身是小到大排列）。在这种
情况下，排序二叉树就变成了普通链表，其检索效率就会很差。
为了改变排序二叉树存在的不足，Rudolf Bayer 与 1972 年发明了另一种改进后的排序二叉树：红黑
树，他将这种排序二叉树称为”对称二叉 B 树”，而红黑树这个名字则由 Leo J. Guibas 和 Robert
Sedgewick 于 1978 年首次提出。
红黑树是一个更高效的检索二叉树，因此常常用来实现关联数组。典型地，JDK 提供的集合类 TreeMap
本身就是一个红黑树的实现。
红黑树在原有的排序二叉树增加了如下几个要求：
性质 1：每个节点要么是红色，要么是黑色。
性质 2：根节点永远是黑色的。
性质 3：所有的叶节点都是空节点（即 null），并且是黑色的。
性质 4：每个红色节点的两个子节点都是黑色。（从每个叶子到根的路径上不会有两个连续的红色
节点）
性质 5：从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。
Java 实现的红黑树
上面的性质 3 中指定红黑树的每个叶子节点都是空节点，而且并叶子节点都是黑色。但 Java 实现
的红黑树将使用 null 来代表空节点，因此遍历红黑树时将看不到黑色的叶子节点，反而看到每个
叶子节点都是红色的。
Java 中实现的红黑树可能有如图 6 所示结构：
else if (p.parent == null)
{
root = null;
}
else
{
if (p.color == BLACK)
// 修复红黑树
fixAfterDeletion(p); // ②
if (p.parent != null)
{
// 如果 p 是其父节点的左子节点
if (p == p.parent.left)
p.parent.left = null;
// 如果 p 是其父节点的右子节点
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}图 6. Java 红黑树的示意
备注：本文中所有关于红黑树中的示意图采用白色代表红色。黑色节点还是采用了黑色表示。
根据性质 5：红黑树从根节点到每个叶子节点的路径都包含相同数量的黑色节点，因此从根节点到叶子
节点的路径中包含的黑色节点数被称为树的”黑色高度（black-height）”。
性质 4 则保证了从根节点到叶子节点的最长路径的长度不会超过任何其他路径的两倍。假如有一棵黑色
高度为 3 的红黑树：从根节点到叶节点的最短路径长度是 2，该路径上全是黑色节点（黑节点 – 黑节点
– 黑节点）。最长路径也只可能为 4，在每个黑色节点之间插入一个红色节点（黑节点 – 红节点 – 黑节
点 – 红节点 – 黑节点），性质 4 保证绝不可能插入更多的红色节点。由此可见，红黑树中最长路径就是
一条红黑交替的路径。
由此我们可以得出结论：对于给定的黑色高度为 N 的红黑树，从根到叶子节点的最短路径长度为 N-1，
最长路径长度为 2 * (N-1)。
提示：排序二叉树的深度直接影响了检索的性能，正如前面指出，当插入节点本身就是由小到大排列
时，排序二叉树将变成一个链表，这种排序二叉树的检索性能最低：N 个节点的二叉树深度就是 N-1。
红黑树和平衡二叉树
红黑树并不是真正的平衡二叉树，但在实际应用中，红黑树的统计性能要高于平衡二叉树，但极端
性能略差。
红黑树通过上面这种限制来保证它大致是平衡的——因为红黑树的高度不会无限增高，这样保证红黑树
在最坏情况下都是高效的，不会出现普通排序二叉树的情况。
由于红黑树只是一个特殊的排序二叉树，因此对红黑树上的只读操作与普通排序二叉树上的只读操作完
全相同，只是红黑树保持了大致平衡，因此检索性能比排序二叉树要好很多。
但在红黑树上进行插入操作和删除操作会导致树不再符合红黑树的特征，因此插入操作和删除操作都需
要进行一定的维护，以保证插入节点、删除节点后的树依然是红黑树。
添加节点后的修复
上面 put(K key, V value) 方法中① 号代码处使用 fixAfterInsertion(e) 方法来修复红黑树——因此每
次插入节点后必须进行简单修复，使该排序二叉树满足红黑树的要求。
插入后的修复
在插入操作中，红黑树的性质 1 和性质 3 两个永远不会发生改变，因此无需考虑红黑树的这两个
特性。
插入操作按如下步骤进行：
1. 以排序二叉树的方法插入新节点，并将它设为红色。
2. 进行颜色调换和树旋转。这种颜色调用和树旋转就比较复杂了，下面将分情况进行介绍。在介绍中，我们把新插入的节点定义为
N 节点，N 节点的父节点定义为 P 节点，P 节点的兄弟节点定义为 U 节点，P 节点父节点定义为 G 节
点。
下面分成不同情形来分析插入操作
情形 1：新节点 N 是树的根节点，没有父节点
在这种情形下，直接将它设置为黑色以满足性质 2。
情形 2：新节点的父节点 P 是黑色
在这种情况下，新插入的节点是红色的，因此依然满足性质 4。而且因为新节点 N 有两个黑色叶子节
点；但是由于新节点 N 是红色，通过它的每个子节点的路径依然保持相同的黑色节点数，因此依然满足
性质 5。
情形 3：如果父节点 P 和父节点的兄弟节点 U 都是红色
在这种情况下，程序应该将 P 节点、U 节点都设置为黑色，并将 P 节点的父节点设为红色（用来保持性
质 5）。现在新节点 N 有了一个黑色的父节点 P。由于从 P 节点、U 节点到根节点的任何路径都必须通
过 G 节点，在这些路径上的黑节点数目没有改变（原来有叶子和 G 节点两个黑色节点，现在有叶子和 P
两个黑色节点）。
经过上面处理后，红色的 G 节点的父节点也有可能是红色的，这就违反了性质 4，因此还需要对 G 节点
递归地进行整个过程（把 G 当成是新插入的节点进行处理即可）。
图 7 显示了这种处理过程：
图 7. 插入节点后进行颜色调换
备注：虽然图 11.28 绘制的是新节点 N 作为父节点 P 左子节点的情形，其实新节点 N 作为父节点 P 右
子节点的情况与图 11.28 完全相同。
情形 4：父节点 P 是红色、而其兄弟节点 U 是黑色或缺少；且新节点 N 是父节点 P 的右子节点，而父
节点 P 又是其父节点 G 的左子节点。
在这种情形下，我们进行一次左旋转对新节点和其父节点进行，接着按情形 5 处理以前的父节点 P（也
就是把 P 当成新插入的节点即可）。这导致某些路径通过它们以前不通过的新节点 N 或父节点 P 的其中
之一，但是这两个节点都是红色的，因此不会影响性质 5。
图 8 显示了对情形 4 的处理：图 8. 插入节点后的树旋转
备注：图 11.29 中 P 节点是 G 节点的左子节点，如果 P 节点是其父节点 G 节点的右子节点，那么上 面
的处理情况应该左、右对调一下。
情形 5：父节点 P 是红色、而其兄弟节点 U 是黑色或缺少；且新节点 N 是其父节点的左子节点，而父节
点 P 又是其父节点 G 的左子节点。
在这种情形下，需要对节点 G 的一次右旋转，在旋转产生的树中，以前的父节点 P 现在是新节点 N 和
节点 G 的父节点。由于以前的节点 G 是黑色，否则父节点 P 就不可能是红色，我们切换以前的父节点 P
和节点 G 的颜色，使之满足性质 4，性质 5 也仍然保持满足，因为通过这三个节点中任何一个的所有路
径以前都通过节点 G，现在它们都通过以前的父节点 P。在各自的情形下，这都是三个节点中唯一的黑
色节点。
图 9 显示了情形 5 的处理过程：
图 9. 插入节点后的颜色调整、树旋转
备注：图 11.30 中 P 节点是 G 节点的左子节点，如果 P 节点是其父节点 G 节点的右子节点，那么上面
的处理情况应该左、右对调一下。
TreeMap 为插入节点后的修复操作由 fixAfterInsertion(Entry<k,v> x) 方法提供，该方法的源代码如
下：
// 插入节点后修复红黑树
private void fixAfterInsertion(Entry<K,V> x)
{
x.color = RED;
// 直到 x 节点的父节点不是根，且 x 的父节点不是红色
while (x != null && x != root
&& x.parent.color == RED){
// 如果 x 的父节点是其父节点的左子节点
if (parentOf(x) == leftOf(parentOf(parentOf(x))))
{
// 获取 x 的父节点的兄弟节点
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
// 如果 x 的父节点的兄弟节点是红色
if (colorOf(y) == RED)
{
// 将 x 的父节点设为黑色
setColor(parentOf(x), BLACK);
// 将 x 的父节点的兄弟节点设为黑色
setColor(y, BLACK);
// 将 x 的父节点的父节点设为红色
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
}
// 如果 x 的父节点的兄弟节点是黑色
else
{
// 如果 x 是其父节点的右子节点
if (x == rightOf(parentOf(x)))
{
// 将 x 的父节点设为 x
x = parentOf(x);
rotateLeft(x);
}
// 把 x 的父节点设为黑色
setColor(parentOf(x), BLACK);
// 把 x 的父节点的父节点设为红色
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
}
// 如果 x 的父节点是其父节点的右子节点
else
{
// 获取 x 的父节点的兄弟节点
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
// 如果 x 的父节点的兄弟节点是红色
if (colorOf(y) == RED)
{
// 将 x 的父节点设为黑色。
setColor(parentOf(x), BLACK);
// 将 x 的父节点的兄弟节点设为黑色
setColor(y, BLACK);
// 将 x 的父节点的父节点设为红色
setColor(parentOf(parentOf(x)), RED);
// 将 x 设为 x 的父节点的节点
x = parentOf(parentOf(x));
}
// 如果 x 的父节点的兄弟节点是黑色
else
{
// 如果 x 是其父节点的左子节点
if (x == leftOf(parentOf(x)))
{
// 将 x 的父节点设为 x显示较少
删除节点后的修复
与添加节点之后的修复类似的是，TreeMap 删除节点之后也需要进行类似的修复操作，通过这种修复来
保证该排序二叉树依然满足红黑树特征。大家可以参考插入节点之后的修复来分析删除之后的修复。
TreeMap 在删除之后的修复操作由 fixAfterDeletion(Entry<k,v> x) 方法提供，该方法源代码如下：
x = parentOf(x);
rotateRight(x);
}
// 把 x 的父节点设为黑色
setColor(parentOf(x), BLACK);
// 把 x 的父节点的父节点设为红色
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
// 将根节点设为黑色
root.color = BLACK;
}
// 删除节点后修复红黑树
private void fixAfterDeletion(Entry<K,V> x)
{
// 直到 x 不是根节点，且 x 的颜色是黑色
while (x != root && colorOf(x) == BLACK)
{
// 如果 x 是其父节点的左子节点
if (x == leftOf(parentOf(x)))
{
// 获取 x 节点的兄弟节点
Entry<K,V> sib = rightOf(parentOf(x));
// 如果 sib 节点是红色
if (colorOf(sib) == RED)
{
// 将 sib 节点设为黑色
setColor(sib, BLACK);
// 将 x 的父节点设为红色
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
// 再次将 sib 设为 x 的父节点的右子节点
sib = rightOf(parentOf(x));
}
// 如果 sib 的两个子节点都是黑色
if (colorOf(leftOf(sib)) == BLACK
&& colorOf(rightOf(sib)) == BLACK)
{
// 将 sib 设为红色
setColor(sib, RED);
// 让 x 等于 x 的父节点
x = parentOf(x);
}
else
{
// 如果 sib 的只有右子节点是黑色if (colorOf(rightOf(sib)) == BLACK)
{
// 将 sib 的左子节点也设为黑色
setColor(leftOf(sib), BLACK);
// 将 sib 设为红色
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
// 设置 sib 的颜色与 x 的父节点的颜色相同
setColor(sib, colorOf(parentOf(x)));
// 将 x 的父节点设为黑色
setColor(parentOf(x), BLACK);
// 将 sib 的右子节点设为黑色
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
}
}
// 如果 x 是其父节点的右子节点
else
{
// 获取 x 节点的兄弟节点
Entry<K,V> sib = leftOf(parentOf(x));
// 如果 sib 的颜色是红色
if (colorOf(sib) == RED)
{
// 将 sib 的颜色设为黑色
setColor(sib, BLACK);
// 将 sib 的父节点设为红色
setColor(parentOf(x), RED);
rotateRight(parentOf(x));
sib = leftOf(parentOf(x));
}
// 如果 sib 的两个子节点都是黑色
if (colorOf(rightOf(sib)) == BLACK
&& colorOf(leftOf(sib)) == BLACK)
{
// 将 sib 设为红色
setColor(sib, RED);
// 让 x 等于 x 的父节点
x = parentOf(x);
}
else
{
// 如果 sib 只有左子节点是黑色
if (colorOf(leftOf(sib)) == BLACK)
{
// 将 sib 的右子节点也设为黑色
setColor(rightOf(sib), BLACK);
// 将 sib 设为红色
setColor(sib, RED);
rotateLeft(sib);
sib = leftOf(parentOf(x));
}
// 将 sib 的颜色设为与 x 的父节点颜色相同
setColor(sib, colorOf(parentOf(x)));
// 将 x 的父节点设为黑色检索节点
当 TreeMap 根据 key 来取出 value 时，TreeMap 对应的方法如下：
显示较少
从上面程序的粗体字代码可以看出，get(Object key) 方法实质是由于 getEntry() 方法实现的，这个
getEntry() 方法的代码如下：
setColor(parentOf(x), BLACK);
// 将 sib 的左子节点设为黑色
setColor(leftOf(sib), BLACK);
rotateRight(parentOf(x));
x = root;
}
}
}
setColor(x, BLACK);
}
public V get(Object key)
{
// 根据指定 key 取出对应的 Entry
Entry>K,V< p = getEntry(key);
// 返回该 Entry 所包含的 value
return (p==null ? null : p.value);
}
final Entry<K,V> getEntry(Object key)
{
// 如果 comparator 不为 null，表明程序采用定制排序
if (comparator != null)
// 调用 getEntryUsingComparator 方法来取出对应的 key
return getEntryUsingComparator(key);
// 如果 key 形参的值为 null，抛出 NullPointerException 异常
if (key == null)
throw new NullPointerException();
// 将 key 强制类型转换为 Comparable 实例
Comparable<? super K> k = (Comparable<? super K>) key;
// 从树的根节点开始
Entry<K,V> p = root;
while (p != null)
{
// 拿 key 与当前节点的 key 进行比较
int cmp = k.compareTo(p.key);
// 如果 key 小于当前节点的 key，向"左子树”搜索
if (cmp < 0)
p = p.left;
// 如果 key 大于当前节点的 key，向"右子树”搜索
else if (cmp > 0)
p = p.right;
// 不大于、不小于，就是找到了目标 Entry
else
return p;
}
return null;显示较少
上面的 getEntry(Object obj) 方法也是充分利用排序二叉树的特征来搜索目标 Entry，程序依然从二叉树
的根节点开始，如果被搜索节点大于当前节点，程序向”右子树”搜索；如果被搜索节点小于当前节点，
程序向”左子树”搜索；如果相等，那就是找到了指定节点。
当 TreeMap 里的 comparator != null 即表明该 TreeMap 采用了定制排序，在采用定制排序的方式下，
TreeMap 采用 getEntryUsingComparator(key) 方法来根据 key 获取 Entry。下面是该方法的代码：
显示较少
其实 getEntry、getEntryUsingComparator 两个方法的实现思路完全类似，只是前者对自然排序的
TreeMap 获取有效，后者对定制排序的 TreeMap 有效。
通过上面源代码的分析不难看出，TreeMap 这个工具类的实现其实很简单。或者说：从内部结构来看，
TreeMap 本质上就是一棵”红黑树”，而 TreeMap 的每个 Entry 就是该红黑树的一个节点。