深入理解经典红黑树 | 京东物流技术团队

本篇我们讲红黑树的经典实现，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 源码来讲解红黑树的插入和删除节点操作：
节点定义

1.     static final class Entry<K,V> implements Map.Entry<K,V> {
2.         K key;
3.         V value;
4.         Entry<K,V> left;
5.         Entry<K,V> right;
6.         Entry<K,V> parent;
7.         boolean color = BLACK;
9.         Entry(K key, V value, Entry<K,V> parent) {
10.             this.key = key;
11.             this.value = value;
12.             this.parent = parent;
13.         }
14.         // ...
15.     }

复制代码

我们可以发现节点定义除了有表示颜色信息和左右子节点的引用外，还增加了 parent 针对父节点的引用。
插入节点

插入2-节点
直接将节点插入2-节点的情况非常简单，如下图所示的两种情况，2-节点转换成3-节点：

插入3-节点
插入3-节点我们需要分左斜3-节点和右斜3-节点两种情况讨论：

• 插入左斜的3-节点的左节点或右节点，需要将其转换成4-节点，如下图所示：
  

• 插入右斜的3-节点的左节点或右节点，需要将其转换成4-节点，如下图所示：
  

插入4-节点
以上两种情况都是不会发生“向上合并”，如果插入的4-节点，需要将其分解成3个2-节点，之后将2-节点的“根节点”合并到它的父节点中（如果有的话），我们同样需要分情况讨论：

• 插入4-节点的左侧红色节点：
  

• 插入4-节点的右侧红色节点：
  

目前插入新节点的所有情况已经讨论完了，下面我们看一下 TreeMap 中的源码，大家注意其中的注释即可：

1.     public V put(K key, V value) {
2.         Entry<K,V> t = root;
3.         // 插入第一个节点
4.         if (t == null) {
5.             compare(key, key);
7.             root >(key, value, null);
8.             size = 1;
9.             modCount++;
10.             return null;
11.         }
12.         int cmp;
13.         Entry<K,V> parent;
14.         // 根据比较器找到插入节点的位置
15.         Comparator<= comparator;
16.         if (cpr != null) {
17.             do {
18.                 parent = t;
19.                 cmp = cpr.compare(key, t.key);
20.                 if (cmp 0)
21.                     t = t.left;
22.                 else if (cmp 0)
23.                     t = t.right;
24.                 else
25.                     return t.setValue(value);
26.             } while (t != null);
27.         }
28.         else {
29.             if (key == null)
30.                 throw new NullPointerException();
31.             @SuppressWarnings("unchecked")
32.                 Comparable<= (Comparable<) key;
33.             do {
34.                 parent = t;
35.                 cmp = k.compareTo(t.key);
36.                 if (cmp 0)
37.                     t = t.left;
38.                 else if (cmp 0)
39.                     t = t.right;
40.                 else
41.                     return t.setValue(value);
42.             } while (t != null);
43.         }
44.         // 根据大小关系添加新的节点
45.         Entry<K,V> e >(key, value, parent);
46.         if (cmp 0)
47.             parent.left = e;
48.         else
49.             parent.right = e;
50.         // *插入之后修复平衡操作*
51.         fixAfterInsertion(e);
52.         size++;
53.         modCount++;
54.         return null;
55.     }

复制代码

fixAfterDeletion 为删除后再平衡方法，需要大家关注其中的注释信息：

1.     private void fixAfterInsertion(Entry<K,V> x) {
2.         // 新插入的节点指定为红色
3.         x.color = RED;
5.         // 如果非空非根节点且有连续的红色节点出现，需要不断地修复平衡
6.         while (x != root .parent.color K,V> y = rightOf(parentOf(parentOf(x)));
7.                 if (colorOf(y) == RED) {
8.                     // 反色处理
9.                     setColor(parentOf(x), BLACK);
10.                     setColor(y, BLACK);
11.                     setColor(parentOf(parentOf(x)), RED);
12.                     // 处理父节点的父节点（因为该节点为红色，可能会发生向上合并的操作）
13.                     x = parentOf(parentOf(x));
14.                 } else {
15.                     // 如下步骤对应插入3-节点的情况1
16.                     // 插入的是3-节点的右节点
17.                     if (x == rightOf(parentOf(x))) {
18.                         x = parentOf(x);
19.                         // 左旋父节点
20.                         rotateLeft(x);
21.                     }
22.                     // 现在转换成了插入位置为3-节点的左节点，父节点染成黑色
23.                     setColor(parentOf(x), BLACK);
24.                     // 父节点的父节点为红色
25.                     setColor(parentOf(parentOf(x)), RED);
26.                     // 右旋父节点的父节点，转换成4-节点
27.                     rotateRight(parentOf(parentOf(x)));
28.                 }
29.             } else {
30.                 // 插入节点后，出现连续红色的节点的位置在右侧
31.                 Entry<K,V> y = leftOf(parentOf(parentOf(x)));
32.                 // 插入的是4-节点，对应插入4-节点的情况2
33.                 if (colorOf(y) == RED) {
34.                     // 反色处理
35.                     setColor(parentOf(x), BLACK);
36.                     setColor(y, BLACK);
37.                     setColor(parentOf(parentOf(x)), RED);
38.                     // 处理父节点的父节点（因为该节点为红色，可能会发生向上合并的操作）
39.                     x = parentOf(parentOf(x));
40.                 } else {
41.                     // 如下步骤对应插入3-节点的情况2
42.                     // 插入的是3-节点的左节点
43.                     if (x == leftOf(parentOf(x))) {
44.                         x = parentOf(x);
45.                         // 右旋父节点
46.                         rotateRight(x);
47.                     }
48.                     // 转换成了插入位置为3-节点的右节点，父节点为黑色
49.                     setColor(parentOf(x), BLACK);
50.                     // 父节点的父节点为红色
51.                     setColor(parentOf(parentOf(x)), RED);
52.                     // 左旋父节点的父节点，转换成4-节点
53.                     rotateLeft(parentOf(parentOf(x)));
54.                 }
55.             }
56.         }
57.         // 根节点始终为黑色
58.         root.color = BLACK;
59.     }

复制代码

红黑树执行删除方法的时间复杂度是多少呢？含有 n 个节点的红黑树的高度为 logn，不调用fixAfterDeletion 方法时，复杂度为 O(logn)，在 fixAfterDeletion 中，情况 1, 3, 4 在各执行常数次的颜色改变和至多 3 次旋转后便终止，只有在情况 2 中才可能重复修复平衡，指针也至多上升 O(logn) 次，且没有任何旋转操作，所以 fixAfterDeletion 复杂度为 O(logn)，最多旋转 3 次，因此红黑树删除方法的时间复杂度为 O(logn)。
巨人的肩膀

• 《算法导论》：第 13 章 红黑树
  
• 知乎 - 关于AVL树和红黑树的一点看法
  
• LeetCode - 红黑树从入门到看开
  
• 博客园 - 红黑树的删除
  
• 作者：京东物流 王奕龙
  来源：京东云开发者社区 自猿其说 Tech 转载请注明来源
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！