深入理解经典红黑树 | 京东物流技术团队
本篇我们讲红黑树的经典实现，Java中对红黑树的实现便采用的是经典红黑树。前一篇文章我们介绍过左倾红黑树，它相对来说比较简单，需要大家看完上篇再来看这一篇，因为旋转等基础知识不会再本篇文章中赘述。本篇的大部分内容参考 《算法导论》和 Java 实现红黑树的源码，希望大家能够有耐心的看完。在正文开始之前我们先看如下问题：
[*]为什么红黑树比AVL树要应用得更广泛呢？
关于红黑树和 AVL 树，大家可能看过“在最坏情况下，AVL 树和红黑树的查找次数都是对数级别的，虽然红黑树的系数更高一些，但是没有本质的区别，是可以容忍的。AVL 树最致命的地方在于删除节点时旋转次数是对数级别的，而红黑树最多只需要 3 次旋转，这导致了红黑树应用相比于 AVL 树要广泛得多”的观点，但实际上这并不是根本原因，根本原因是在以任意序列插入和删除操作混合进行的情况下，红黑树均摊时间复杂度保持在 O(1)，而 AVL 树的均摊时间复杂度为 O(logn)。
经典红黑树与2-3-4搜索树 同构，它相比于左倾红黑树（2-3树）的实现，在维持红黑树平衡性开销更小。下文中我们会将经典红黑树简称为红黑树，开始吧：
2-3-4 搜索树
2-3-4搜索树是在2-3搜索树中增加了4-节点，在前文中已经介绍过4-节点，我们先来看一下2-3-4搜索树的样子：
新节点插入2-节点或3-节点的情况我们就不在这里赘述了，我们重点看一下新节点插入4-节点的情况。当有新节点插入的节点为4-节点时，需要先将4-节点转换成3个2-节点，再在其中的2-节点中执行插入操作，如下所示，其中黄色节点为新插入的节点，对应了插入4-节点中的四种情况：
我们再以情况（4）为例，在2-3-4搜索树中执行插入值为34的节点：
将4-节点转换成3个2-节点并完成插入新节点34后，需要将“根节点25”插入到父节点中，如上图所示。这和我们在前文中在2-3搜索树中讲到的基本类似，需要不断分解临时的5-节点，并将原来4-节点分解成3个2-节点的根节点插入到更高的父节点中，直到遇到2-节点或3-节点，将其转换成不需要继续分解的节点，如果最终插入到根节点后使其为5-节点，同样需要进行分解再插入的操作，完成后树高加一。
2-3-4树的插入操作使树本身的改变也是局部的，除了相关的节点和引用之外，不必修改和检查树的其他部分，这些局部变换不会影响到树的全局有序性和平衡性，在插入的过程中，2-3-4树始终是完美平衡二叉树。
经典红黑树
经典红黑树与2-3-4搜索树同构，如果我们把2-3-4搜索树样例转换成红黑树的话，会如下图所示（指向红色节点的链接我们同样也染成红色）：
它满足如下性质：
[*]节点颜色为红色或黑色
[*]根节点是黑色的
[*]叶子节点（null 节点）为黑色（null 节点在图中未画出来）
[*]红色节点的两个子节点为黑色（不能出现连续的红色节点）
[*]任意叶子节点到根节点路径上的黑色节点数量相同，即该树是黑色平衡的
黑色平衡这条性质我们在讲解左倾红黑树时已经讲过，在这里我们不厌其烦地再叙述一遍：2-3-4树始终能保持完美平衡，那么任意叶子节点到达根节点的距离是相等的，红黑树又是一颗2-3-4搜索树，其中的黑链接是2-3-4搜索树中的普通链接，那么红黑树中被黑色链接引用的黑色节点也必然是完美平衡的，所以任意叶子节点到根节点路径上的黑色节点数量必然相同。
下面我们结合图示和Java中 TreeMap 源码来讲解红黑树的插入和删除节点操作：
节点定义
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
// ...
}我们可以发现节点定义除了有表示颜色信息和左右子节点的引用外，还增加了 parent 针对父节点的引用。
插入节点
插入2-节点
直接将节点插入2-节点的情况非常简单，如下图所示的两种情况，2-节点转换成3-节点：
插入3-节点
插入3-节点我们需要分左斜3-节点和右斜3-节点两种情况讨论：
[*]插入左斜的3-节点的左节点或右节点，需要将其转换成4-节点，如下图所示：
[*]插入右斜的3-节点的左节点或右节点，需要将其转换成4-节点，如下图所示：
插入4-节点
以上两种情况都是不会发生“向上合并”，如果插入的4-节点，需要将其分解成3个2-节点，之后将2-节点的“根节点”合并到它的父节点中（如果有的话），我们同样需要分情况讨论：
[*]插入4-节点的左侧红色节点：
[*]插入4-节点的右侧红色节点：
目前插入新节点的所有情况已经讨论完了，下面我们看一下 TreeMap 中的源码，大家注意其中的注释即可：
public V put(K key, V value) {
Entry<K,V> t = root;
// 插入第一个节点
if (t == null) {
compare(key, key);
root >(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// 根据比较器找到插入节点的位置
Comparator<= comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp 0)
t = t.left;
else if (cmp 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<= (Comparable<) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp 0)
t = t.left;
else if (cmp 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
// 根据大小关系添加新的节点
Entry<K,V> e >(key, value, parent);
if (cmp 0)
parent.left = e;
else
parent.right = e;
// *插入之后修复平衡操作*
fixAfterInsertion(e);
size++;
modCount++;
return null;
}fixAfterDeletion 为删除后再平衡方法，需要大家关注其中的注释信息：
private void fixAfterInsertion(Entry<K,V> x) {
// 新插入的节点指定为红色
x.color = RED;
// 如果非空非根节点且有连续的红色节点出现，需要不断地修复平衡
while (x != root .parent.color 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 {
// 如下步骤对应插入3-节点的情况1
// 插入的是3-节点的右节点
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
// 左旋父节点
rotateLeft(x);
}
// 现在转换成了插入位置为3-节点的左节点，父节点染成黑色
setColor(parentOf(x), BLACK);
// 父节点的父节点为红色
setColor(parentOf(parentOf(x)), RED);
// 右旋父节点的父节点，转换成4-节点
rotateRight(parentOf(parentOf(x)));
}
} else {
// 插入节点后，出现连续红色的节点的位置在右侧
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
// 插入的是4-节点，对应插入4-节点的情况2
if (colorOf(y) == RED) {
// 反色处理
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
// 处理父节点的父节点（因为该节点为红色，可能会发生向上合并的操作）
x = parentOf(parentOf(x));
} else {
// 如下步骤对应插入3-节点的情况2
// 插入的是3-节点的左节点
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
// 右旋父节点
rotateRight(x);
}
// 转换成了插入位置为3-节点的右节点，父节点为黑色
setColor(parentOf(x), BLACK);
// 父节点的父节点为红色
setColor(parentOf(parentOf(x)), RED);
// 左旋父节点的父节点，转换成4-节点
rotateLeft(parentOf(parentOf(x)));
}
}
}
// 根节点始终为黑色
root.color = BLACK;
}红黑树执行删除方法的时间复杂度是多少呢？含有 n 个节点的红黑树的高度为 logn，不调用fixAfterDeletion 方法时，复杂度为 O(logn)，在 fixAfterDeletion 中，情况 1, 3, 4 在各执行常数次的颜色改变和至多 3 次旋转后便终止，只有在情况 2 中才可能重复修复平衡，指针也至多上升 O(logn) 次，且没有任何旋转操作，所以 fixAfterDeletion 复杂度为 O(logn)，最多旋转 3 次，因此红黑树删除方法的时间复杂度为 O(logn)。
巨人的肩膀
[*]《算法导论》：第 13 章 红黑树
[*]知乎 - 关于AVL树和红黑树的一点看法
[*]LeetCode - 红黑树从入门到看开
[*]博客园 - 红黑树的删除
[*]作者：京东物流 王奕龙
来源：京东云开发者社区 自猿其说 Tech 转载请注明来源
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]