红黑树从入门到看开 agile Posted on Jul 14 2023 数据结构与算法 yukiyama --- title: 红黑树从入门到看开 tags: - 红黑树 - 树 - 平衡二叉树 - 算法与数据结构 categories: 算法与数据结构 description: >- 红黑树，向来被认为是最难理解和掌握的常见高级数据结构之一。在耗费巨量时间与无数次长考后，终于总结出一点小小的心得，为了不负已然磨损殆尽的智商和时光，惶恐写就本文。对于有志于全面掌握红黑树的读者朋友，希望本文能够帮助你更快更平滑以至更彻底地理解红黑树。 cover: >- https://raw.githubusercontent.com/iyukiyama/pics/master/hexo-iyukiyama/site_img/posts/algorithms/rbt-bg.png katex: true abbrlink: red-black-tree keywords: top_img: comments: --- # 红黑树从入门到看开 > - 可在作者的 [github仓库](https://github.com/iyukiyama/leetcode-posts) 中获取本文和其他文章的 markdown 源文件及相关代码。 > > - 欢迎评论或仓库 PR 指出文章错漏或与我讨论相关问题，我将长期维护所有文章。 > - 所有文章均用 Typora 完成写作，可使用 Typora 打开文章 md 文件，以获得最佳阅读体验。 ⚠️ ⚠️ ⚠️ **谨以此三万字文章献给有志于彻底掌握红黑树一切细节的朋友。** ❗️ **【NEW】** ❗️ - 9-15: [红黑树从入门到看开](https://leetcode.cn/circle/discuss/SwgIJV/) 这是小白 yuki 推出的「树ADT」系列文章的第 6 篇 (6/13) 。 *** > $keywords$ : > > 2-3树 / 2-3-4树 / 完美平衡 / 完美黑平衡 / 结点变换 / 旋转 / 反色 / 红黑树 / 红与黑的本质 / 红黑树五大性质 / 2-3-4树与红黑树同构 / 插入结点 / 删除结点 / 情形归约 / JDK TreeMap 源码解析 / 左倾红黑树 / 2-3树与左倾红黑树同构 / 左倾红黑树三大性质 红黑树，向来被认为是最难理解和掌握的常见高级数据结构之一，yuki 在学习过程中也的确深感其难度之大。在耗费巨量时间与无数次长考后，终于总结出一点小小的心得，为了不负已然磨损殆尽的智商和时光，惶恐写就本文。对于 **有志于全面掌握红黑树的读者朋友** ，希望本文能够帮助你更快更平滑以至更彻底地理解红黑树。 阅读本文前，读者需要掌握 BST ([二叉查找树](https://leetcode.cn/circle/discuss/wPzlSb/)) 以及至少一种基于旋转操作的平衡 BST ([AVL树](https://leetcode.cn/circle/discuss/zbwD3p/), [splay树](https://leetcode.cn/circle/discuss/BCK17f/)) 。文章主要内容如下。 - 本文将依次讲解 **「2-3树与2-3-4树」** 、 **「红黑树」** 以及 **「左倾红黑树」** 。 - 在「2-3树与2-3-4树」章节中指出该平衡 BST 相比之前介绍过过其他平衡 BST ([AVL树](https://leetcode.cn/circle/discuss/zbwD3p/), [splay树](https://leetcode.cn/circle/discuss/BCK17f/)) 的优点。 - 指出「2-3树与2-3-4树」情形多样，编程复杂的缺点，并以保持其优点规避其缺点为目标，引入「红黑树」。 - 在「红黑树」章节中指出红黑树是保持 BST 形态的2-3-4树的「同构」，而 **保证「同构」的根本是 BST 结点的红黑颜色信息** 。 - 深入讨论了 **红黑颜色的本质** ，以及从该颜色信息出发如何得到 **红黑树的五大性质** 。 - 详细讲解了 **红黑树的结点插入与结点删除操作** ，尤其是后者。在「删除结点」操作中列出了 42 种2-3-4树上的结点删除情形，并通过一系列细心的对比分析，归约出 4 种独立情形。该方法于他处未曾见， **应当是 yuki 的一小创新** 。逐情形对比2-3-4树与红黑树以及归约大量情形的做法，相比单纯基于红黑树性质的分析 (算法导论的做法) 要更具象，使我们能够清晰地了解删除结点每一步动作的目的，并确信 4 种独立情形即可覆盖所有可能的情况。 - 指出 JDK 源码的一处疑似有瑕疵的写法，并给出逻辑更恰当的改进写法。 - 给出了「红黑树」的较为完整的类实现代码。 - 在「左倾红黑树 (LLRBT)」章节中指出 Sedgewick 是如何通过一条简单的规则 ( **3-结点左倾约束** ) 完成对经典红黑树天才般的改造。 - 详细讲解了 **LLRBT 的结点插入与结点删除操作** ，尤其是后者。在3-结点左倾约束的指导下，反色及旋转的奇妙配合使 LLRBT 插入结点和删除结点的操作相比经典红黑树要轻盈许多。 - 给出了「LLRBT」的较为完整的类实现代码。 说实话红黑树的难度本来并不是小白 yuki 能够驾驭的，但奈何人菜瘾大，为此着实苦苦求索了一段时间，因此文章中有所错漏几乎是不可避免的，欢迎读者朋友们批评指正！ 另外，本文原题 「红黑树 (树ADT连载 6/13)」，十分干瘪，不太符合作者沉稳中又略带一点玩世不恭的气质，遂改为现标题。**「看开」表示作者的一种态度**，即看完本文，若仍不能掌握红黑树，那就算了，就像钱钟书说的，大不了一棵红黑树，实在不值得如此殚精竭虑。 *** yuki的其他文章如下，欢迎阅读指正！ > 如下所有文章同时也在我的 github [仓库](https://github.com/iyukiyama/leetcode-posts) 中维护。 | 文章 | [发布时间] 字数/览/藏/赞 (~2022-10-20) | | ------------------------------------------------------------ | ---------------------------------------- | | [十大排序从入门到入赘](https://leetcode.cn/circle/discuss/eBo9UB/) 🔥🔥🔥 | [20220516] 2.5万字/64.8k览/3.7k藏/937赞 | | [二分查找从入门到入睡](https://leetcode.cn/circle/discuss/ooxfo8/) 🔥🔥🔥 | [20220509] 2.3万字/38.4k览/2.1k藏/503赞 | | [并查集从入门到出门](https://leetcode.cn/circle/discuss/qmjuMW/) 🔥🔥 | [20220514] 1.2万字/17.9k览/1.0k藏/321赞 | | [图论算法从入门到放下](https://leetcode.cn/circle/discuss/FyPTTM/) 🔥🔥 | [20220617] 5.6万字/19.9k览/1.3k藏/365赞 | | 树ADT系列 (预计13篇) | 系列文章，连载中 | | 3. [二叉查找树](https://leetcode.cn/circle/discuss/wPzlSb/) | [20220801] 5千字 | | 4. [AVL树](https://leetcode.cn/circle/discuss/zbwD3p/) | [20220817] 5千字 | | 5. [splay树](https://leetcode.cn/circle/discuss/BCK17f/) | [20220817] 5千字 | | 6. [红黑树从入门到看开](https://leetcode.cn/circle/discuss/SwgIJV/) 🔥🤯🤯🤯 | [20220915] 3万字/5.3k览/269藏/72赞 | | 10. [树状数组从入门到下车](https://leetcode.cn/circle/discuss/qGREiN/) 🔥🤯 | [20220722] 1.4万字/5.8k览/196藏/72赞 | | 11. [线段树从入门到急停](https://leetcode.cn/circle/discuss/H4aMOn/) 🔥🤯 | [20220726] 2.5万字/8.7k览/481藏/138赞 | | [图论相关证明系列](https://leetcode.cn/circle/discuss/GV0JrV/) | 系列文章 | | 1. [Dijkstra正确性证明](https://leetcode.cn/circle/discuss/jJQn7V/) 🤯 | [20220531] | | 2. [Prim正确性证明](https://leetcode.cn/circle/discuss/VVEc8f/) 🤯 | [20220919] | | 3. [Bellman-Ford及SPFA正确性证明](https://leetcode.cn/circle/discuss/xeEwYl/) | [20220602] | | 4. [Floyd正确性证明](https://leetcode.cn/circle/discuss/Nbzix4/) | [20220602] | | 5. [最大流最小割定理证明](https://leetcode.cn/circle/discuss/tMIy36/) 🤯🤯 | [20220719] | | 6. [Edmonds-Karp复杂度证明](https://leetcode.cn/circle/discuss/tN3sZc/) 🤯🤯 | [20220515] | | 7. [Dinic复杂度证明](https://leetcode.cn/circle/discuss/T9Xa1R/) 🤯🤯 | [20220531] | *** [TOC] *** ## 2-3树与2-3-4树 > 一切妄图脱离2-3-4树来理解「红黑树」的努力都是徒劳的。–– *yukiyama* 在 [AVL树](https://leetcode.cn/circle/discuss/zbwD3p/) 和 [splay树](https://leetcode.cn/circle/discuss/BCK17f/) 两篇文章中，我们介绍了两种平衡二叉树的实现，其中AVL树通过跟踪并动态维护树的高度信息在每次操作后 **严格保持树平衡** ，而伸展树无需维护树的高度信息，而是通过 **「展开」** 降低多次操作的摊还时间复杂度。这两种平衡树的基础均为 **「旋转」** 操作，通过旋转来调整局部树高使树保持平衡或趋向平衡。本节我们介绍的2-3树和2-3-4树也是平衡树，但它不基于「旋转」操作，而是通过 **动态地调整结点容量** 来实现平衡。 在二叉树中，每一个结点最多只有两个子结点，当某结点拥有两个子结点时，称其为 **2-结点** ，其持有一个数据项以及两个子结点。2-3树和2-3-4树不是二叉树，因为前者除了2-结点外，还可以有 **3-结点** (3-结点持有两个数据项以及三个子结点) ， 后者除了2-结点和3-结点外，还有 **4-结点** (4-结点持有三个数据项以及四个子结点) 。后续我们将看到2-3树和2-3-4树如何通过结点之间的动态变换来保持平衡。  > 「算法导论」称 [ John Hopcroft](https://en.wikipedia.org/wiki/John_Hopcroft) 于1970 发明2-3树 (未发表)。 > > 本节部分内容为 Robert Sedgewick & Kevin Wayne 所著「算法: 第4版」相关章节的整理和总结。 <br /> ### 2-3树 一棵2-3树的结点分为 **内部结点** (*internal nodes*) 和 **叶子结点** (*leaf nodes*) ，定义如下。 ```text 内部结点: 2-结点: 拥有1个数据项x，2个子结点。 -左子树中任意结点数据项均小于x。 -右子树中任意结点数据项均大于x。 3-结点: 拥有2个数据项x,y，3个子结点。 -左子树中任意结点数据项均小于x。 -中间子树中任意结点数据项均介于x与y之间。 -右子树中任意结点数据项均大于y。 叶子结点: 无子结点，数据项为 1 项或 2 项。 ``` 后续我们会看到，在2-3树的操作过程中，可能会「临时」产生一些4-结点。如下是一棵典型的2-3树。  <br /> #### 结点变换 2-3树实现平衡的基础在于 **「结点变换」** ，不同情形的「插入」很好地体现了不同的变换，下面我们通过插入操作来了解2-3树结点变换的过程。 执行插入方法之前首先要执行 $find$ 方法，当待插入结点不存在时执行插入操作。查找操作与基本 BST 的不同在于3-结点存在 2 个数据项，因此需要比较两次来确定下一步要去往该结点的左、中、还是右子树。与 BST 类似， **插入总是在树的底部执行** ，略有不同的是， BST 中待插入对象总是作为叶子结点插入，而在2-3树中，若作为叶子结点插入会破坏2-3树的 **完美平衡** ，所谓完美平衡指 **2-3树的所有叶子结点到根结点的路径长度相同** 。实际上该数据结构3-结点的设计就是为了容纳待插入对象，使树能够保持完美平衡，因此待插入对象总是被插入到一个叶子结点中，但这又带来下面2中的问题。 1. 若该叶子结点为2-结点，可直接插入，此结点变为3-结点。 2. 若该叶子结点为3-结点，插入后变为4-结点，不符合2-3树的定义。 因此对于2，需要进行「结点变换」以使得插入后的树仍是一棵完美平衡的2-3树，我们通过下表和示意图分析不同插入情形所对应的结点变换过程。 | 情形 | 具体过程 | | --------------------------------------- | ------------------------------------------------------------ | | 1. 插入至2-结点中 | 插入后变为3-结点 | | 2. 插入至3-结点中<br />(该结点为根结点) | 插入后变为4-结点，然后分解为3个2-结点。(树高+1) | | 3. 插入至3-结点中<br />(父结点为2-结点) | 插入后变为4-结点，然后分解为3个2-结点，但其中一个与父结点合并，使得父结点变为3-结点 | | 4. 插入至3-结点中<br />(父结点为3-结点) | 与上一条类似，但父结点变为4-结点，继续向上 (送入一个结点后) 分解直到：<br />1. 遇到2-结点，转变为情形1。<br />2. 到根处仍为3-结点，最终为情形2。 | 下图展示了从左至右依次为情形1,2,3,4。  我们看到，2-3树的插入过程十分简单，并且从中容易看出2-3树保持平衡的关键所在。在插入的过程中，若插入3-结点，则通过向上变换有机会找到一个2-结点，2-结点膨胀为3-结点将插入对象「消化」在其中，树高不变，只有向上变换到根结点处仍不能消化时，通过分解变换，树高才会增长 1，而这个增长使得 **所有叶子结点** 到根结点的路径长度 **同时增加 1** ，因此2-3树能够保持平衡，并且是 **完美平衡** 的。我们还能感到树高的增长是缓慢的，因为在插入过程中的4-结点裂变为3个2-结点时，提高了之后的「消化能力」，使得向上变换不容易到达当前根结点使树长高。在稍后的「小结」中，我们会具体计算树高 $h$ 与结点数 $n$ 的关系。 <br /> ### 2-3-4树 #### 结点变换 在理解了2-3树的基础上，2-3-4树的学习是简单的，因为后者只不过比前者多了一种4-结点。2-3-4树保持平衡的关键也是「结点变换」，过程类似，如下表。 | 情形 | 具体过程 | | --------------------------------------- | ------------------------------------------------------------ | | 1. 插入至2-结点或3-结点中 | 插入后变为3-结点或4结点 | | 2. 插入至4-结点中<br />(该结点为根结点) | 4-结点先分解为3个2-结点后 (树高+1) 再插入。 | | 3. 插入至4-结点中<br />(父结点为2-结点) | 4-结点先分解为3个2-结点，其中一个与父结点合并，使得父结点变为3-结点，然后再插入。 | | 4. 插入至4-结点中<br />(父结点为3-结点) | 4-结点先分解为3个2-结点，其中一个与父结点合并，使得父结点变为4-结点，然后再插入。 | | 5. 插入至4-结点中<br />(父结点为4-结点) | 与上一条类似，但父结点变为5-结点，继续向上 (送入一个结点后) 分解直到：<br />1. 遇到2-结点或3-结点，转变为情形1。<br />2. 遇到4-结点，继续上送。<br />3. 到根处仍为4-结点，转变为情形2。 | 插入4-结点可以统一描述为：该4-结点分解为3个2-结点，将其中一个上送后 (与该4-结点的父结点结合为3-结点或4-结点或5-结点)，待插入结点插入到分解后的左子结点或右子结点中。 如下示意图中，$x$ 表示插入的键，为了方便表示，其他键都用「口」表示，但它们是不同的，且符合大小顺序的要求。从这个示意图中可直观地看到插入至2-结点/3-结点/4-结点后的变化。插入4-结点时，分解后的父结点用虚线框表示上送的结点可能插入2-结点/3-结点/4-结点。通过这个示意图我们发现2-3-4树的插入是非常简单的，读者需要准确地理解各个情形的过程，因为后续的「红黑树」的插入过程，将完全以这张图为基础对照说明。 ※ 在「插入4-结点」情形中，我们无需仔细讨论虚线框中的 「..口..」具体是3-结点/4-结点/5-结点的哪种情形，当对应到红黑树后我们将看到无论是哪种情形，都只需要简单反色后继续上溯考察重复同样的过程即可。若读者不放心，可以列出分解后由于上送一个结点使得「..口..」分别为3-结点/4-结点/5-结点的情形加以分析。其中若为3-结点/4-结点，则上送一次即结束，若为5-结点，则继续上送结点并重复同样的考察。  <br /> ### 小结 现在我们来考虑2-3树中结点数 $n$ 与树高 $h$ 的关系。当一棵具有 $n$ 个结点的2-3树的所有结点均为2-结点时，树高最高，所有结点均为3-结点时，树高最低。因此有： $$ 2^{h+1}-1 \leq n \leq \frac{3^{h+1}-1}{2} $$ $$ log _{3}(2n+1)-1\leq h \leq \log _{2}(n+1)-1 $$ 即树高 $h$ 为 $O(logn)$ ，从这个角度也可以看出2-3树是平衡的，且之前我们分析过，它是完美平衡的，主要操作的最坏时间复杂度均为 $O(logn)$ 。2-3-4树的分析类似，略。 相比 AVL 树，2-3树/2-3-4树在无需通过树高信息跟踪树的平衡状态的情况下就保持了完美平衡，相比伸展树，2-3树/2-3-4树总是能 **稳定地保持平衡** ，因此它们应当是十分理想的平衡树方案，但在本节中我们未给出具体实现，这是因为需要处理的情况较多，代码编写复杂，对不同情况的判断和处理会产生许多额外的开销，因此虽然理论上很理想，在实践中却几乎不被使用。但理解这两者是异常重要的，因为一种被广泛应用的称作「红黑树」的平衡 BST 正是以其思想为基础，更确切地，我们指出 –– **经典红黑树与2-3-4树同构 (isomorphic)，左倾红黑树与2-3树同构** 。在后续的「红黑树」与「左倾红黑树」章节中，我们将分析如何根据一些简单的规则将2-3-4树构造成经典红黑树，将2-3树构造成左倾红黑树，并给出它们的具体实现，同时我们将会看到红黑树/左倾红黑树如何兼顾2-3-4树/2-3树和 BST 两者的优点。 <br /> ## 经典红黑树 有了2-3树/2-3-4树的知识铺垫后，本节我们学习在实践中被广为应用的 **「红黑树 (*red-black tree)*」** 。区别于主要基于2-3树的「左倾红黑树」，本节讲解的是基于2-3-4树的 **「经典红黑树」** 。 在前文中我们提到过红黑树是2-3-4树的同构，本节我们将看到如何通过两条简单的规则将2-3-4树转变为红黑树。首先，红黑树是一棵 BST ，相比基本 BST，它通过附加的 **1bit 信息 (颜色) 和旋转操作**，实现在保持 BST 结构的基础上始终与2-3-4树同构，因此它既能沿用基本 BST 的许多操作，同时也能够保持 2-3-4树「完美平衡」(在红黑树中为 **「完美黑平衡」** ) 的优点。 > 注意：虽然2-3树和2-3-4树无旋转操作，但基于它们的经典红黑树和左倾红黑树涉及旋转操作，因此读者要确保完全理解旋转操作后再继续阅读后文。 > > > > 红黑树由 [Rudolf Bayer](https://en.wikipedia.org/wiki/Rudolf_Bayer) 发明于 1972 年的[此篇论文](https://link.springer.com/article/10.1007/BF00289509) 中，并称此数据结构为「对称二叉B树 (*symmetric binary B-tree*)」。「红黑树」这一称呼则由 [Leonidas J. Guibas](https://en.wikipedia.org/wiki/Leonidas_J._Guibas) 和 [Robert Sedgewick](https://en.wikipedia.org/wiki/Robert_Sedgewick_(computer_scientist)) 在[此论文](https://ieeexplore.ieee.org/document/4567957/)中提出。 <br /> ### 从2-3-4树到红黑树 #### 两条规则 (定义) 只需按照如下规则 (也可视作红黑树的定义) 即可将2-3-4树转换为红黑树。显然红黑树与2-3-4树严格对应，因此说它们是 **同构** 的。 1. 所有3-结点转换为由红链链接的两个结点 (左斜或右斜均可)，该链的父结点为黑色，子结点为红色。 2. 所有4-结点转换为两条构成「^」形状的红链，两个子结点为红色，父结点为黑色。 下图展示了2-3-4树及其对应的红黑树 (红黑树结点未标数字，对照原2-3-4树即可知道每一个结点的数字)，中间的红黑树将红链横放，虚线框住的单条红链即为一个3-结点，两条相邻红链即为一个4-结点后， **红黑树与2-3-4树严格对应** 的关系清晰可见。 ※ 关于「链的颜色」: 除根结点外，树上的每个结点都有一条来自父结点的链指向它，因此我们可以把链也涂上颜色，链的颜色与它唯一指向的结点的颜色相同。  <br /> #### 红与黑 通过上述定义和对应关系，我们指出红黑树颜色的本质： > 红与黑的本质是在原 BST 结点的基础上附加的 1bit 信息，该比特位使得2-3-4树在展成 BST 的情况下仍能保持与原2-3-4树同构，也就是通过查询结点的红与黑标记即能还原这些结点在原2-3-4树中所对应的结点 (2-结点/3-结点/4-结点)。 可见红与黑只不过是这 1bit 信息的具体化，实际上在程序中通常用布尔值来表达，并且规定 $BLACK = true, RED = false$，或相反，还可以用数字 1 和 0 来表达，只要体现出这 1bit 信息即可。红与黑也只不过是命名人的一种选择，在 wiki 词条中介绍了当年 Guibas 和 Sedgewick 将该2-3-4树的同构命名为红黑树的原因。不得不说「红黑」的表达确实令人印象深刻。 > In a 1978 paper, "A Dichromatic Framework for Balanced Trees", [Leonidas J. Guibas](https://en.wikipedia.org/wiki/Leonidas_J._Guibas) and [Robert Sedgewick](https://en.wikipedia.org/wiki/Robert_Sedgewick_(computer_scientist)) derived the red–black tree from the symmetric binary B-tree. The color "red" was chosen because it was the best-looking color produced by the color laser printer available to the authors while working at [Xerox PARC](https://en.wikipedia.org/wiki/Xerox_PARC). Another response from Guibas states that it was because of the red and black pens available to them to draw the trees. 现在我们再回到前述两条规则。 - 对于规则1，其本质是用两个颜色相异的结点表达2-3-4树中的3-结点，若颜色相同，则等同于失去该信息 (「信息」的本质，单纯相同无信息，单纯相异也无信息，可相同可相异，有了变化和对比才有信息)，也就无法表达3-结点 (只能表达2-结点)。子结点为红，父结点为黑只是一种规定，完全可以规定子为黑父为红 (只要相异即可)，只不过如上面引用的 wiki 中的文字所说，红色醒目，用以提示多键结点 (3-结点/4结点) 是更自然的选择。 - 对于规则2，我们指出，4-结点转换为 BST 中的「 `^` 」形结构是一种 **更恰当的人为选择** ，因为我们完全可以把4-结点转换成3个在一条直线上的结点，而不破坏 BST 的结点有序性质。如下图，我们把前面2-3-4树例子中两处 4-结点分别展成「`/`」形和「`\`」形，如下，不难看出该 (与规则2不符的) 「红黑树」仍然满足 BST 的性质 (可填入数字验证)，并且也是完美黑平衡的，只不过相比「 `^` 」形更不平衡 (针对 BST 形态而言)，且用「 `^` 」表达4-结点只需这一种形态，而「`/`」和「`\`」却是两种形态。你可能看到过 **「红黑树中不允许出现两个连续红结点」** 、**「红黑树红结点的子结点必为黑结点」** 、**「红黑树红结点的父结点必为黑结点」** 之类的描述，原因就在于我们选择了更恰当的「`^`」形来表达4-结点，从而使得红黑树中不存在两个连续红结点的情况。  总之，在红黑树中，一对 **父黑子红** 的结点就对应着2-3-4树中的3-结点，除非这个父结点的另一个孩子结点也是红，那么这三个父子子结点就对应着2-3-4树中的4-结点。更一般的描述是，红黑树通过 **子结点和父结点的颜色关系** 来将具体的红黑结点与2-3-4树中的2-结点/3-结点/4-结点相对应，具体如下。 - 2-结点：当一个黑结点不存在红子结点时，它就是2-3-4树中的一个2-结点。 - 3-结点：当一个黑结点只有一个红子结点时 (可以有两个子结点，但有且只有一个红子结点)，这对父黑子红结点构成2-3-4树中的一个3-结点。 - 4-结点：当一个黑结点存在两个红子结点时，这三个结点构成2-3-4树中的一个4-结点。 **除上述情形外，不存在其他情形。** 下图三行示意图分别是红黑树对应2-3-4树中的2-结点/3-结点/4-结点的不同情形。  <br /> #### 五大性质 在理解红黑树定义及红黑颜色的本质后，我们指出红黑树具有以下性质。 | 五大性质 | 描述 | | ------------- | ------------------------------------------------------------ | | 1. 颜色 | 红黑树的结点或者为黑色或者为红色。 | | 2. 根结点 | 根结点为黑色。 | | 3. null结点 | 叶子结点的null子结点(上图未画出，通常都不会画出)为黑色。 | | 4. 不可连续红 | 红色结点的子结点为黑色。 | | 5. 完美黑平衡 | 红黑树是「完美黑平衡」的，即任意叶子结点到根结点所经过的黑链数相同。 | ※ 注意，「算法导论」中「红黑树」一章的「叶子结点」指的是我们通常所理解的叶子结点 (有实际意义值的末端结点) 的 null 子结点。从该书的图13-1(a)可看出。 对于这五大性质，我们进一步有如下解释。 - 对于1，红黑颜色即前述 1bit 信息，使得2-3-4树转换为 BST 后仍能严格表达原2-3-4树，即这是红黑树与2-3-4树同构所要求的。 - 对于2，假设在原2-3-4树中根结点是一个3-结点或4-结点，按照定义 (规则1和2)，根结点必须为黑色，否则形成两个相邻的红色结点。又或红黑树只有根结点，若为红，则单个红色结点无意义，而单个黑结点有意义。 - 对于3，当叶子结点为红色时，若其 null 子结点为红色，则形成两个相邻的红色结点，违反定义，所以 null 子结点必须为黑色。 - 对于4，两个相邻红结点违反定义。 - 对于5，因为2-3-4树是完美平衡的，转换成红黑树后，不考虑红链 (本质为3-结点或4-结点) 的情况下 (即只考虑黑链，回想一下红链横放的图示) 是完美平衡的，于是对整棵红黑树，我们称其 **完美黑平衡** 。 如果把红黑树的性质看作某种理论系统，那么这个系统完全是从一条公理出发得到的，我们姑且称之为 1bit 公理，前面已叙述过，此处再次概括如下。 > 1bit 红黑信息使 BST 形态的红黑树与2-3-4树同构。 本节开头的规则1和规则2都是这一公理的具体体现 (规则2中人为选择了更恰当的「^」形) 。而前述所谓红黑树的五大性质都是遵从两条规则得到的，因此也可以说这五大性质是从这个 1bit 公理出发得到的 (第5条是对2-3-4树固有性质的继承，但也是因为 1bit 公理使得红黑树与2-3-4树同构所具有的)。换言之，1bit 公理对红黑树系统来说是完备的。 我们不厌其烦地强调2-3-4树与红黑树的对应关系，并且深入理解红黑的本质，目的都是为了在之后的红黑树实现中，能够更清晰地看出红黑树的各种操作，本质上都是为了保持与2-3-4树同构。若能在脑海中自如地切换红黑树与2-3-4树，理解红黑树将不再困难。 <br /> ### 结点变换 现在，我们深刻地理解了红黑树与2-3-4树的严格对应关系，因此我们也可以确定其保持平衡的操作必然 **与2-3-4树严格对应** ，我们已经知道，2-3-4树是通过「结点变换」来保持平衡的，之前我们通过考察2-3-4树结点插入过程分析过其结点变换过程，在本节中我们采用对照的方式，首先考察红黑树插入结点过程中的结点变换 (保持与2-3-4树同构的操作，即变色及旋转)，然后考察在2-3-4树中未涉及的删除结点过程的结点变换，后者相比前者要复杂得多。 <br /> #### 插入结点 ##### 插入操作 在「红黑树保持平衡的操作与2-3-4树严格对应」这一结论的指导下，我们很容易按照2-3-4树插入情形，一边对照着画出两种树的插入过程 (后续三张图)，一边写下如下红黑树与之对应的变换过程。 | 情形 | 2-3-4树 | 红黑树 | | --------------------------------------- | ------------------------------------------------------------ | ------------------------------------------------------------ | | 1. 插入至2-结点 | 变为 **3-结点** | 变为 **红链** (左斜或右斜) | | 2. 插入至3-结点 | 变为 **4-结点** | 变为两条相邻的 **红链**，<br />若原3-结点左斜，则可能构成 `^, /, <` 三种形态之一<br />若原3-结点右斜，则可能构成 `^, \, >` 三种形态之一<br />非「^」形要调整为「 ^ 」形 | | 3. 插入至4-结点中<br />(该结点为根结点) | 4-结点先 **分解** 为3个2-结点后 (树高+1) 再插入。 | 4-结点 (2-3-4树) 中的3个结点 (红黑树) 各自反色即完成分解，然后插入 | | 4. 插入至4-结点中<br />(父结点为2-结点) | 4-结点先分解为3个2-结点，其中一个与父结点合并，使得父结点变为3-结点，然后再插入。 | 同上 | | 5. 插入至4-结点中<br />(父结点为3-结点) | 4-结点先分解为3个2-结点，其中一个与父结点合并，使得父结点变为4-结点，然后再插入。 | 同上 | | 6. 插入至4-结点中<br />(父结点为4-结点) | 与上一条类似，但父结点变为5-结点，继续向上 (送入一个结点后) 分解直到：<br />1. 遇到2-结点或3-结点，转变为情形1或情形2。<br />2. 遇到4-结点，继续上送。<br />3. 到根处仍为4-结点，转变为情形3。 | 同上 | 这里有必要强调待插入结点的颜色，对应到2-3-4树中，结点一定会被插入到2-结点/3-结点/4-结点其中之一，从后续「插入调整」中的三张图中容易看出，无论哪种情形，插入后 $x$ 必须为红结点才符合定义，因此总是 **将待插入结点其作为红结点插入** 。 ※ 除非当前树为空，此时插入结点将作为新的根结点，其为黑色，为统一操作，在程序实现上仍然将其作为红色结点插入，最后 $root$ 会执行置黑的操作。 <br /> ##### 插入调整 现在我们具体分析插入结点后的调整操作。 **■ 插入2-结点 (2变3)** 如下，**若在一黑结点下插入，且该黑结点没有红子结点时**，那么这个黑结点就代表了2-结点，也就是此时我们会将 $x$ 插入一个2-结点，因此 $x$ 可直接插入。根据 $x$ 与该2-结点数据项大小关系，有左斜或右斜两种可能。  **■ 插入3-结点 (3变4)** 如下图。 - **若在一红色结点下插入，且该红结点不存在红色兄弟结点时**，那么这个红结点就代表了3-结点 (与它的黑父结点构成3-结点)，因此 $x$ 可直接插入此3-结点。 - **若在一黑色结点下插入**，则为左下和右上两种「^」情形，也属于插入3-结点情形。 如我们在上一张表格中所述，插入3-结点将产生两条相邻的红链，若原红链左斜，则可能构成 「`^,<,/` 」形态之一，若原红链右斜，则可能构成「`^,>,\`」 形态之一，共有 6 种情形 (下图表现红黑树的 6 个格子)，5种形态。其中，「^」形态的两种情形无需调整，其他情形需要经过如图的旋转和反色操作调整为符合 **规则2** 要求的「 ^ 」形态。可以看到，在左斜3-结点下插入与在右斜3-结点下插入是完全对称的，在代码分析中我们会看到镜像情形的代码只需简单修改即可。 对于两种无需处理的「^」情形，结合「插入2-结点」的情形，有此结论：**当待插入结点在一黑色结点下插入时，直接插入而无需其他处理**。  **■ 插入4-结点 (4分解为三个2-结点后其中一个2变3)** 如下，**若在一红色结点下插入，且该红结点有一红色兄弟结点时**，那么这个红结点就代表了4-结点 (与它的黑父结点以及红色兄弟结点构成4-结点)，也就是此时我们会将 $x$ 插入一个4-结点，通过下图，**与2-3-4树对照** ，我们发现，插入4-结点只需将原4-结点的3个结点各自反色即可，简单得令人惊讶。由于上送结点可能需要上溯调整，因此反色后要置 $x = x.parent.parent$ 并继续考察 $x$ ，后续请读者结合伪代码和相应的代码理解。  从上述对照分析中我们发现红黑树的插入确实完美地与2-3-4树一一对应，观察这样的对应甚至可以说是赏心悦目的。除了插入3-结点需要对其中的 4 种情况稍作处理外 (其余两种「^」直接插入) ，插入2-结点和插入4-结点都十分简单。前面三张图片是按插入2-3-4树中哪一种结点分类分析的，实际编写代码时，我们要 **按照插入 BST 形式的红黑树** 来编写，因此还需稍作整理如下。 > 下表中的case1/2/3即为「算法导论」第13章 RB-INSERT-FIXUP(T, z) 伪代码中的 case1/2/3。 【插入结点的父结点为一左子结点】 | 情形 | 2-3-4树情形 | 红黑树情形 | | ----- | ------------------------------------------- | ------------------------------------------------------------ | | case0 | 插入2-结点 & 插入3-结点的黑父结点之下的情形 | 在黑结点下插入: 直接插入 | | case1 | 插入4-结点 | 在红结点下插入，且该结点有红色兄弟结点 (插入结点的叔结点) <br />原4-结点的3个结点反色 | | case2 | 插入3结点，「<」形 | 在红结点下插入，且该结点无红色兄弟结点 (插入结点的叔结点)<br />插入结点为右子结点: <br />下段左旋>反色>上段右旋 | | case3 | 插入3结点，「/」形 | 在红结点下插入，且该结点无红色兄弟结点 (插入结点的叔结点)<br />插入结点为左子结点: <br />反色>上段右旋 | 【插入结点的父结点为一右子结点】 | 情形 | 2-3-4树情形 | 红黑树情形 | | ----- | ------------------------------------------- | ------------------------------------------------------------ | | case0 | 插入2-结点 & 插入3-结点的黑父结点之下的情形 | 在黑结点下插入: 直接插入 | | case1 | 插入4-结点 | 在红结点下插入，且该结点有红色兄弟结点 (插入结点的叔结点):<br />原4-结点的3个结点反色 | | case2 | 插入3结点，「`>`」形 | 在红结点下插入，且该结点无红色兄弟结点 (插入结点的叔结点):<br />插入结点插入后为左子结点: <br />下段右旋>反色>上段左旋 | | case3 | 插入3结点，「`\`」形 | 在红结点下插入，且该结点无红色兄弟结点 (插入结点的叔结点):<br />插入结点插入后为右子结点: <br />反色>上段左旋 | 这两个表格是两种对称的情形，表格中「红黑树情形」对应的伪代码如下 (「算法导论」第13章 RB-INSERT-FIXUP(T, z) )。 ```java RB-INSERT-FIXUP (T, z) 1 while z.p.color == RED // 不满足则为 case0 2 if z.p == z.p.p.left // 插入结点的父结点为一左子结点 3 y = z.p.p.right // 插入结点的叔结点 4 if y.color == RED // case1 叔结点为红色 (插入4-结点) 5 z.p.color = BLACK // case1 反色 6 y.color = BLACK // case1 反色 7 z.p.p.color = RED // case1 反色 8 z = z.p.p // case1 继续上溯调整 9 else if z == z.p.right // case2 叔结点为黑色且插入结点作为右儿子 (插入3-结点，「<」形) 10 z = z.p // case2 准备下段左旋 11 LEFT-ROTATE(T, z);// case2 下段左旋 12 z.p.color = BLACK // case3 反色 13 z.p.p.color = RED // case3 反色 14 RIGHT-ROTATE(T, z.p.p) // case3 「/」形，上段右旋 15 else (same as then clause // 插入结点的父结点为一右子结点 with “right” and “left” exchanged) 16 T.root.color = BLACK ``` <br /> ##### 代码实现 将上述伪代码翻译成代码。插入方法 `put(Node h, K key, V val)` 最后一行调用的 `fixAfterInsertion(newNode)` 方法即上述伪代码的直白翻译。方法中调用的 `flipColors`, `flipColor`, `setColor`, `rotateLeft`, `rotateRight` 实现十分简单，其中旋转操作与我们在AVL树中看过的旋转操作一样，这些方法的具体实现请参考「类的实现代码」。 ```java public void put(K key, V val) { // 插入key-val结点 if (key == null) throw new IllegalArgumentException("first argument to put() is null"); if (val == null) { // 表示删除该key delete(key); return; } put(root, key, val); // 调用实际插入方法 } private void put(Node h, K key, V val) { int compareRes; Node<K, V> cur = h, p = null; // cur: 当前结点，p: cur的父结点 while (cur != null) { p = cur; compareRes = key.compareTo(cur.key); if (compareRes < 0) cur = cur.left; // 往左 else if(compareRes > 0) cur = cur.right; // 往右 else { // 存在key，修改其值后返回 cur.val = val; return; } } // while正常结束，后续执行插入 Node<K, V> newNode = new Node<K, V>(RED, key, val, null, null, null); // 插入的结点总是红色的 newNode.parent = p; if (p != null) { // 非空树，插入到 p 下 compareRes = newNode.key.compareTo(p.key); if (compareRes < 0) p.left = newNode; // 作为左子结点插入 else p.right = newNode; // 作为右子结点插入 } else this.root = newNode; // p == null 说明未进入while，树空，newNode作为根结点插入 fixAfterInsertion(newNode); // 向上调整，恢复红黑树平衡 } public void fixAfterInsertion(Node<K, V> k) { Node<K, V> p, g; // parent, grandParent while (((p = parentOf(k)) != null) && isRed(p)) { g = parentOf(p); if (p == g.left) { // k的父结点是一个左儿子 Node<K, V> u = g.right; // uncle: p的兄弟结点，k的叔结点 if (isRed(u)) { // case1: k的叔结点为红，则k插入到一个4-结点中 flipColors(g); k = g; // 插入4-结点只需反色，此时要上溯到变红的g } else { // k的叔结点为黑，则k插入到一个3-结点中 if (k == p.right) { // case2: k 是一个右儿子 k = p; rotateLeft(p); // 左旋，之后k在底部 } flipColor(p); // case3: 反色 setColor(p, BLACK); flipColor(g); // case3: 反色 setColor(g, RED); rotateRight(g); // case3: 右旋 } } else { // k的父结点是一个右儿子 Node<K, V> u = g.left; if (isRed(u)) { flipColors(g); k = g; } else { if (k == p.left) { k = p; rotateRight(p); } flipColor(p); flipColor(g); rotateLeft(g); } } } if (k == root) setColor(k, BLACK); } ``` <br /> #### 删除结点 与「插入结点」操作一样，我们仍旧遵循「红黑树保持平衡的操作与2-3-4树严格对应」这一结论，来分析「删除结点」的过程。红黑树结点删除的操作向来被看作 **高级数据结构中最为复杂和难以理解的操作之一**，以至于一些久负盛名的算法书，例如 Sedgewick 的「算法第4版」(该树的红黑树为左倾红黑树)、Weiss的「数算」对删除结点的操作都只有只言片语，后者的红黑树代码实现中甚至略去了删除结点的部分。「算法导论」给出的过程较为详细，但缺少实现代码，且只基于恢复红黑性质而未能联系2-3-4树来解释，不但难以理解，且未对照2-3-4树的删除过程，让人对其正确性信心不足。 我们指出红黑树删除操作难以理解的一个关键在于，操作是针对 BST 形态的红黑树，但本质却要求删除后保持仍为一棵符合定义的完美平衡的2-3-4树 (同构)，在多种情形下建立二者之间的联系极大地增加了我们的思考负担。但读者朋友不必担心，本小节我将配以大量图示详细叙述，通过严格对比2-3-4树和红黑树，确保读者能够比较轻松地理解红黑树删除操作的每一处细节，并确信归约出的4种情形确实能够覆盖所有删除情形。本小节内容较多，预先列出后续行文顺序如下。 1. 删除操作: 说明红黑树对应的2-3-4树中删除结点的操作。指出删除3-结点或4-结点中的键是容易的， **只有删除2-结点才需要向上调整** 。 2. 情形归约: 列出 42 种删除2-结点的情形，从中归约出 4 种情形， **并指出其中需要向上调整的情形** 。 3. 删除调整: 通过对比2-3-4树删除2-结点的过程，分析出红黑树删除2-结点的过程 (如何旋转及变色)，并给出伪代码。 4. 代码实现: 给出红黑树删除结点的 Java 实现代码。 <br /> ##### 删除操作 如同 BST 的删除操作那样，删除结点的方法中，首先要找到该结点，若存在，则根据目标结点的位置及其左右子树是否存在，执行具体的删除动作，无论删除的结点在何处，最终都会 **删除一个对应于2-3-4树上的叶子结点** (这一点是关键，后面详细说明) 。与「插入结点」中的考虑一样，删除结点后要保证红黑树仍与2-3-4树同构。当要删除的结点 (红黑树) 对应为2-3-4树中3-结点或4-结点中的键时，可以直接删除该键而不破坏平衡 (叶子结点仍在，只是少了一个键)，若待删除结点对应2-3-4树中的2-结点时，删除该结点将导致其父结点的子结点数少一个，不满足2-3-4树结点的结构 (2-3-4树语境)。类似「插入结点」后的操作， **关键在于删除2-结点后恢复同构** ，这是本节重点，在进入该内容讲解之前，我们先分析2-3-4树的结点删除操作。有了 BST 删除操作的经验，我们很容易将在2-3-4树中要删除的键 ($key$) 分为如下两种情形 (见下表情形1和情形2)。 1. 情形1: $key$ 的后继键一定在叶子结点中，且如果该叶子结点为3-结点或4-结点，一定是结点中最左侧 (最小) 的那个键。例如删除图中的30，其后继为32，若删除34，其后继为35，若删除45，其后继为48。 2. 情形2: 可直接删除目标 $key$ (键值) ，若该键在3-结点或4-结点中，例如删除32或53，可直接删除。若该键在2-结点中，如删除40，则其父结点失去2-3-4树结构性质。  2-3-4树删除 $key$ 情形 (以 $key$ 是否在叶子结点中划分)。 | 2-3-4树删除 $key$ 情形 | 删除操作 | | --------------------------- | ------------------------------------------------------------ | | 情形1: $key$ 不在叶子结点中 | 用 $key$ 的后继键值替换 $key$，然后删除后继键值<br />※ 后继键必为某叶子结点中的最小键 | | 情形2: $key$ 在叶子结点中 | 直接删除目标键值<br />※ 若目标键在2-结点中，删除后失去2-3-4树结构性质，要调整 | 红黑树删除结点情形 (以删除结点的子结点情形划分)。 | 红黑树删除结点 $x$ 情形 | 删除操作 | | ----------------------- | ------------------------------------------------------------ | | 情形a: $x$ 有左右子结点 | 用后继结点 (的键值) 替换 $x$ (的键值)，然后删除后继结点<br />※ 删除后继结点必为情形b或情形c | | 情形b: $x$ 有一个子结点 | 建立子结点与 $x.parent$ 的链接，然后删除 $x$<br />※ $x$ 及其子结点构成3-结点，删除后不影响同构 | | 情形c: $x$ 无子结点 | 删除 $x$ <br />※ $x$ 对应2-3-4树中的多种情形，可能为红或黑，若为2-3-4树中的2-结点，则删除后失同构，需调整 | 对于上述两表，对比说明如下。 1. 情形a包括了情形1以及情形2中删除4-结点的中间 $key$ 的情况，这一情形需要找到 $x$ 的后继结点，然后转为情形b或情形c。 2. 情形b除了从情形a中转移过来的情况外，还包括情形2中删除右斜3-结点左键和删除左斜3-结点右键这两种情况。它们都表现为删除3-结点中黑色的那个结点。 3. 情形c除了从情形a中转移过来的情况外，还包括情形2中删除2-结点 (1)、删除右斜3-结点右键 (2)、删除左斜3-结点的左键 (3)、删除4-结点的左键 (4)、删除4-结点的右键 (5) 这5种情况。如果是(1)，那么删除了一个2-结点，失同构，需要调整，如果是 (2), (3), (4), (5)，可直接删除。而且我们发现这5种情况中只有 (1) 满足 $x$ 为黑色。 - 对于情形a，当我们判断 $x$ 存在左右孩子后，令 `x = x.successor` ，即可转为b, c情形。 - 对于情形b，当判断 $x$ 只有一个孩子时，我们建立 $x.parent$ 与 $x.child$ 的链接关系，然后删除 $x$ 。需要注意的是，情形b保证了 $x$ 一定是黑色的，$x.child$ 一定是红色的，删除 $x$ 后原3-结点变为2-结点，因此 $x.child$ 要置为黑色，仍与2-3-4树同构，无需调整，删除结束。 - 对于情形c，直接删除 $x$ ，但若 $x$ 为黑，失同构，需要调整。 通过上述分析，我们发现仅有 $x$ **无孩子结点且为黑** 时才需要恢复同构。在理解了红黑树的删除操作后，我们给出下面的代码。删除结点的操作由公有的 $delete$ 驱动方法和私有的具体方法构成。在驱动方法中先执行 $get$ 查找是否存在键为 $key$ 的结点，存在则执行具体删除方法。代码中的注释与前述分析是完全一致的，请读者对照阅读，应当不难理解。 ```java public void delete(K key) { // 删除key对应的结点 Node<K, V> x = get(this.root, key); // 找到key对应的结点x if (x != null) delete(x); } private void delete(Node<K, V> x) { // 删除结点x if (x.left != null && x.right != null) { // x有左右孩子 Node<K,V> s = successor(x); // 找到x的后继s x.key = s.key; // s取代x x.val = s.val; // s取代x x = s; // x此时是实际要删除的s } // 经过此if后，x为实际要删除的结点，x要么是无孩子的叶子结点，要么只有一个孩子结点 Node<K,V> r = x.left != null ? x.left : x.right; // r: replacement，即x.child，用来取代x if (r != null) { // 情形b: x只有左孩子或右孩子 // 以下四句链接x.p与r r.parent = x.parent; if (x.parent == null) root = r; // 原x为root else if (x == x.parent.left) x.parent.left = r; // 原x不为root且为一个左孩子 else x.parent.right = r; // 原x不为root且为一个右孩子 x.left = x.right = x.parent = null; // 删除x (x脱离树，置其左右子结点和父结点为 null) setColor(r, BLACK); // #1 r一定为红，置黑 // if (x.color == BLACK) fixAfterDeletion(r); // #2 调整 } else if (x.parent == null) { // case2 x无孩子且无父结点，x为根结点，且该树只有此结点 root = null; } else { // 情形c: x无孩子 (r为null) if (x.color == BLACK) fixAfterDeletion(x); // x为2结点，调整 if (x.parent != null) { // 删除x if (x == x.parent.left) x.parent.left = null; // x为一左子结点 else if (x == x.parent.right) x.parent.right = null; // x为一右子结点 x.parent = null; } } } ``` 实际上上面给出的代码基本上就是 JDK 的 TreeMap 中的 $deleteEntry$ [方法](https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/TreeMap.java)。说「基本上」是因为，在源码中有 #2 行而无 #1 行，而我们给出的方法中有 #1 行而无 #2 行。若读者理解了前述分析，相信很容易接受我们给出的写法。反而 JDK 源码的写法似乎不佳，关于这一点，需要读者先理解接下来要讲解的 $fixAfterDeletion$ 方法后才能讨论，如果确如作者分析的那样，我们应该向 Oracle 提交该方法的改进请求。详细探讨请见「补充」。 ```java setColor(r, BLACK); // #1 r一定为红，置黑 // if (x.color == BLACK) fixAfterDeletion(r); // #2 调平 ``` <br /> ##### 情形归约 删除2-结点 ($x$) 后要恢复与2-3-4树同构，可令 $x$ 的父结点向下补充缺失的2-结点。可以这么考虑，删除 $x$ 之前，我们先利用父结点的键将该处填充为一个3-结点或4-结点，于是 $x$ 可直接删除，父结点出借了一个键，根据其键数变化，还需要一些调整。以下列出删除2-结点的不同情形，只有情形3-2需要向上调整，其他情形在常数次操作后恢复同构。 - 情形1: 若 $x$ 的兄弟结点为3-结点。$x$ 从其父结点中取一个键到 $x$ 中组成3-结点，但父结点的键数要保持不变，否者链的数量也会减1，因此父结点从 $x$ 的兄弟结点中取一个键。删除 $x$ ，平衡恢复。 - 情形2: 若 $x$ 的兄弟结点为4-结点。$x$ 、$x$ 的父结点中的一个键、$x$ 兄弟结点中的一个键组成一个4-结点。但父结点的键数要保持不变，否者链的数量也会减1，因此父结点从 $x$ 的兄弟结点中取一个键。删除 $x$ ，平衡恢复。 - 情形3: 若 $x$ 的兄弟结点为2-结点。由于 $x$ 的兄弟结点只有一个键，不能向上述两种情形那样通过 $x$ 兄弟结点来「间接取键」，但我们可以把 $x$ 、$x$ 父结点中的一个键、$x$ 兄弟结点合并为一个4-结点。$x$ 的父结点少了一个键，但链也少了一条，结构仍是正确的。删除 $x$。 - 情形3-1: 若父结点为3-结点或4-结点，父结点借出一个结点，缩小为2-结点或3-结点。平衡恢复。 - 情形3-2: 若父结点为2-结点，则在合并后父结点「缺失」。如同「插入结点」最后的向上调整，此情形的结点删除也需要继续 **向上调整** 。 情形3-2向上调整的过程中，若遇到一个3-结点或4-结点，它被亏空处「借键」后变为2-结点或3-结点)，调整结束。否则一直调整到根处，若根为2-结点，补充亏空后整棵2-3-4树高度减1，所有叶子结点到根的路径长度同时减1，调整结束。  ※ 此图并未画出所有情形的所有子情形 (例如 $x$ 的父结点可以为2-结点/3-结点/4-结点，又如 $x$ 的位置不一定在最左边等)，但对解释删除2-结点的操作来说已经完备，读者若不放心，可依据此图过程画出其他情形。 经过上述分析，我们发现 **删除后的调整过程是关键** 。当我们试图对照2-3-4树中删除2-结点的各种情形画出红黑树删除过程中结点变换的过程时，我们很快发现 **该情形实在太多** ，逐个讨论耗时甚巨，很容易迷失在旋转与变色中，因此需要减少讨论情形。如同算法导论，我们也会指出删除结点的 **4 种情形** ，但与算法导论直接从抽象的红黑性质入手不同，本小节避免谈及红黑树的5条性质，而是将2-3-4树与红黑树对照分析，从众多具体的2-3-4树情形归约到 4 种情形。 虽然该方法前期工作较繁琐， **需要极大的耐心和细心** ，但我们能够清楚地看到每一种情形的2-3-4树和红黑树的对应关系，归约得到的4种情形是很容易理解和接受的。之后对4种情形的删除操作的分析，将会坚定而轻松。 下图全面分析删除2-结点 (结点 $x$) 的不同情形，建议读者预先验证下每个情形的2-3-4树是否与红黑树对应。$x$ 为一个 **左子结点** 的情形已用绿色框框住，可以看到，当它是一个右子结点时，有同样多的 **镜像情形** ，根据「插入结点」的经验，实际编程时，只需将 $x$ 为左子结点的代码中的 $left$ 和 $right$ 交换即得到镜像情形的代码。于是对于整张图的42种情形 (红黑树)，只需看绿色框中的21种。  如下，我们列出这21种情形的标号，实际上仍未列完，图中红黑树未接结点的黑色链条，可以接2-结点、3-结点或4-结点，其中3-结点又分为左斜或右斜。不过我们 **保证已经覆盖了所有删除情形** ，因为只有与 $x$ 相邻的黑色链条才可能影响变换的结果，而在2-3-4树示意图中与 $x$ 相邻的「..□..」（即红黑树中的黑色链条所链接的2-结点/3-结点/4-结点），总能够在已经给出的某种情形中找到对应 (例如 1-4 对应2-3-4树中 $x$ 右侧的 「..□..」，可以为2-结点，3-结点或4-结点，分别由1-5，2-5，3-5对应的2-3-4树所对应)。 | $x$ 的兄弟结点 | $x$ 的父结点 | 情形 | | -------------- | ------------ | ------------------ | | 2-结点 | 2-结点 | 1-1 | | | 3-结点 | 1-2, 1-3, 1-4, 1-5 | | | 4-结点 | 1-6, 1-7 | | 3-结点 | 2-结点 | 2-1 | | | 3-结点 | 2-2, 2-3, 2-4, 2-5 | | | 4-结点 | 2-6, 2-7 | | 4-结点 | 2-结点 | 3-1 | | | 3-结点 | 3-2, 3-3, 3-4, 3-5 | | | 4-结点 | 3-6, 3-7 | 现在，我们观察所列情形的2-3-4树和对应的红黑树的形态，归约其中的等价情形。再次强调，以下讨论中 $x$ 是一个左子结点 (绿色框)，其对称情形是 $x$ 为一个右子结点。 1. 我们首先看到 $x.p$ 为4-结点的情形，例如 1-6 ，一个红色结点连着两个黑色子结点的部分，在 1-2 中也有相同的部分。通过与它们对应的2-3-4树容易观察到，**相同部分才会参与变换**，不同的部分不参与变换，所以它们可以看作一种情形。同理，1-7, 2-6, 2-7, 3-6, 3-7 都不必重复讨论，这样就去掉了 6 种情形。 2. 利用同样的方法 (对照2-3-4树)，我们观察到 1-1, 1-2, 1-5 参与变换的部分也是一样的，同理 2-1, 2-2, 2-5 情况等价， 3-1, 3-2, 3-5 情况等价，于是再去掉 6 种情形。 3. 对于1-4，其 $x$ (在红黑树中) 的兄弟结点只能是黑色结点 (即黑链下挂的未画出的结点)，若为2-结点，则 1-1 与该部分对应，若为3-结点，则 2-1 与该部分对应，若为4-结点，则3-1与该部分对应，因此1-4可以不用重复讨论。同理，2-4，3-4也可以去掉。注意，虽然「^」形结构父结点在 1-1 中为黑，在 1-4 中为红，但通过对2-3-4树的观察可知，变换所涉及的结点只有「^」结构的三个结点，因此它们是等价的 (颜色变化后续说明)。 4. 现在只剩下1-1, 2-1, 3-1, 1-3, 2-3, 3-3 六种情形。更进一步，我们分析1-3, 2-3, 3-3 这三种情形。它们的共同特点是 $x$ (在红黑树中的) 的兄弟结点为红色，实际上意味着在2-3-4树中 $x$ 的父结点为 (右斜的) 3-结点。因为1-3, 2-3, 3-3 分别与1-2, 2-2, 3-2 对应同一种2-3-4树，只是前三个的 $x.p$ (3-结点) 为左斜，后三个为右斜，所以我们尝试左旋 $x.p$ 使后者与前者相同， **左旋后发现确实转换成了 1-2, 2-2, 3-2 情形** 。于是，我们遇到 $x$ 的兄弟结点为红色结点时，左旋 $x.p$ (及相应变色) 即可得到之前讨论过的情形，而 1-2, 2-2, 3-2 在上述第2条的讨论中，已经被我们去掉了，1-1, 2-1, 3-1 是它们的等价。  最终我们从众多情形中归约出4种情形，包括三种基本情形 1-1, 2-1, 3-1，以及情形 x-3 (表示 1-3 & 2-3 & 3-3，共同点是 $x$ 的兄弟结点为红色，左旋 $x.p$ 后转换为基本情形)。 ※ 情形2-1有两种，但只需要将左侧结构的 $w$ ($x$ 的兄弟结点) 右旋即可得到右侧结构，我们从2-3-4树的角度将此二者看作一种情形，后续实际编程时的4种情形与此处略有不同。 接下来分析这四种情形的结点删除过程，以及删除后的调整。 <br /> ##### 删除调整 为方便叙述，我们将前述归约出的4种情形与「算法导论」给出的 case1~4 对照如下。 | 算法导论4情形 | 对应前述4情形 | | --------------------------------------------- | ------------------------------------------------------------ | | case1: $w$ 为红色 | 情形x-3<br />只需对 $x.p$ 置红及 $w$ 反色并左旋 $x.p$ 后转为后续情形 | | case2: $w$ 为黑色，且其孩子左黑右黑 | 情形1-1 | | case3: $w$ 为黑色，且其孩子左红右黑 | 情形2-1左侧<br />只需对 $w$ 及 $w.left$ 反色并右旋 $w$ 即为 case4 | | case4: $w$ 为黑色，且其孩子左黑右红或左红右红 | 情形2-1右侧 & 情形3-1 | ※ $w$ 是待删除结点 $x$ 的兄弟结点。 现在我们画出 case1~4 删除结点 $x$ 前后的2-3-4树和红黑树。左侧的「删除前后 (2-3-4树)」是简单的，我们根据左侧2-3-4树删除 $x$ 后的结果，考虑并尝试对删除前的红黑树做旋转和颜色调整操作，不难得到右侧「删除前后 (红黑树)」中的过程。  为了便于读者观察，黑色虚线椭圆框住的 $x.p$ 结点只考察了2-结点的情形，只有此情形才可能在 case2 时，需要继续向上尝试调整。如果 $x.p$ 为3-结点或4-结点，如我们在前面「删除操作」小节中讨论的那样，在本次调平后必然能够恢复平衡。而且 $x.p$ 必然为红色 (3-结点或4-结点的子结点必为红色，请看情形1-2和情形1-6的2-3-4树) ，调整后这个结点是原3-结点或4-结点出借的结点，如果还保持红色，将无法脱离原3-结点或4-结点 (2-3-4树)，因此必须置黑。这是 RB-DELETE-FIXUP(T, x) 伪代码最后一行的作用。 至此，我们已经完成了红黑树删除结点操作中最为困难的「删除后调整」的分析，并写下了在红黑树中四种删除2-结点情形的调整动作。现在只需将上图「删除前后 (红黑树)」中具体动作写成代码即可。下面是「算法导论」给出的 RB-DELETE-FIXUP(T, x) 伪代码，与我们在图中写下的过程是一样的，以下逐行给出注释。 ```java RB-DELETE-FIXUP(T, x) // 从被删除的结点x开始调整 1 while x ≠ T.root and x.color == BLACK // x未上溯到根，且x为黑 (删除2-结点) 2 if x == x.p.left // x是一个左孩子 3 w = x.p.right // w是x的叔结点 4 if w.color == RED // case1 w为红 (则x.p为3-结点，其子结点必为黑) 5 w.color = BLACK // case1 w置黑(反色) 6 x.p.color = RED // case1 x.p置红(反色) 7 LEFT-ROTATE(T, x.p) // case1 左旋x.p (前两行反色是为了左旋后变为case2) 8 w = x.p.right // case1 有了第3行，此行可省略(因为旋转时x.p.right引用会相应调整) 9 if w.left.color == BLACK and w.right.color == BLACK // case2 w的孩子结点左黑右黑 10 w.color = RED // case2 w置红(反色，进入该分支时w一定是黑色，反色目的是让它作为一个3-结点中的红色结点) 11 x = x.p // case2 继续向上调整，此情况的x.p可能为黑，表示上一行注释中 // 所说的3-结点是通过3个2-结点合并而来的(合并为4-结点后删去x)，因此x.p(2-结点)亏空 12 else if w.right.color == BLACK // case3 w的孩子结点左红右黑，此情形结束后必平衡 13 w.left.color = BLACK // case3 w左孩子置黑(反色) 14 w.color = RED // case3 w置红(反色, 进入该分支时w一定是黑色) 15 RIGHT-ROTATE(T, w) // case3 右旋w (前两行反色是为了右旋后变为case4) 16 w = x.p.right // case3 有了第3行，此行可省略(因为旋转时x.p.right引用会相应调整) // 从下一行开始是w孩子结点为左黑右红或左红右红的情形，此情形结束后必平衡 17 w.color = x.p.color // case4 继承x.p的颜色，后续左旋x.p后w会取代x.p的位置 18 x.p.color = BLACK // case4 x.p置黑，目的是为了让它作为调整后原x位置新形成的3-结点中的黑色结点 19 w.right.color = BLACK // case4 w右孩子置黑(反色，目的是为了让它成为一个2-结点) 20 LEFT-ROTATE(T, x.p) // case4 左旋x.p，令左侧挂上一个3-结点(原x被删除的位置) 21 x = T.root // case4 此句用于退出while，因为case3和case4调整后必平衡 22 else (same as then clause with "right" and "left" exchanged) // x是右孩子，为镜像情形，将前面代码中的left与right交换即可得到本处代码 23 x.color = BLACK // while结束要么是case3/case4调整后已平衡 x被被置为root后主动退出， // 要么是case1/case2 x为红。若为前者无需此句(此时的root一定是黑的) // 若为后者，说明此时的x结点是原3-结点或4-结点出借的结点，如果还保持红色， // 将无法脱离原3-结点或4-结点 (2-3-4树)，因此必须置黑。 // 此句也可以写成这样: if(x != root) x.color = BLACK ``` <br /> ##### 代码实现 下面给出删除结点的完整代码。`delete` 驱动方法和具体方法前面已给出。 ```java public void delete(K key) {} // 前面已给出，此处省略 private void delete(Node<K, V> x) {} // 前面已给出，此处省略 public void fixAfterDeletion(Node<K, V> x) { Node<K, V> parent = parentOf(x); while (isBlack(x) && x != root) { if (x == leftOf(parent)) { // x是一个左子结点 Node<K, V> sib = rightOf(parent); // case1：sib为红，转换为后续case if (isRed(sib)) { setColor(parent, RED); setColor(sib,BLACK); rotateLeft(parent); // sib = parent.right; //「算法导论」伪代码有此句，可以省略 } // case2:左黑右黑，这种情形可能需要继续向上调平 if (isBlack(leftOf(sib)) && isBlack(rightOf(sib))) { setColor(sib, RED); x = parent; // 向上调平 parent = parentOf(x); // 更新parent } else { // case3 & case4 一定能够调平 // case3: 右黑，其实就是左红右黑，转换为case4 if (isBlack(rightOf(sib))) { setColor(sib.left, BLACK); setColor(sib, RED); rotateRight(sib); // sib = parent.right; //「算法导论」伪代码有此句，可以省略 } // 以下是case4: 右红，其实就是左红右红或左黑右红，这种情形一定会调平 setColor(sib, colorOf(parent)); setColor(parent, BLACK); setColor(rightOf(sib), BLACK); rotateLeft(parent); x = root; //此句用于退出while，因为case3和case4调整后必平衡 } } else { Node<K, V> sib = leftOf(parent); if (isRed(sib)) { setColor(parent, RED); setColor(sib, BLACK); rotateRight(parent); } if (isBlack(leftOf(sib)) && isBlack(rightOf(sib))) { setColor(sib, RED); x = parent; parent = parentOf(x); } else { if (isBlack(leftOf(sib))) { setColor(sib.right, BLACK); setColor(sib, RED); rotateLeft(sib); } setColor(sib, colorOf(parent)); setColor(parent, BLACK); setColor(leftOf(sib), BLACK); rotateRight(parent); x = root; } } } // while结束要么是case3/case4调整后已平衡 x被被置为root后主动退出， // 要么是case1/case2 x为红。若为前者无需此句(此时的root一定是黑的) // 若为后者，说明此时的x结点是原3-结点或4-结点出借的结点，如果还保持红色， // 将无法脱离原3-结点或4-结点 (2-3-4树)，因此必须置黑。 setColor(x, BLACK); // 也可以写成这样 if(x != root) setColor(x, BLACK); } ``` <br /> ##### 补充 【补充1: JDK TreeMap类源码中的deleteEntry方法】 在「删除操作」小节中，我们指出 JDK 的 TreeMap 类的 $deleteEntry$ [方法](https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/TreeMap.java)，源码的实现略有不妥，即该方法中有如下 #2 行而无 #1 行，由于 $x.color$ 一定是黑，因此总是会执行调整方法，进入 $fixAfterDeletion$ 方法后，又因为 $r$ 的兄弟结点是黑色的 $null$ ，因此会进入 case2 分支，执行 $x = x.p$ (即原 $r.p$ ) 语句后，满足 $x.color == BLACK$，继续调整。到这里我们可以这么理解，源码的写法使得原 $r.p$ 被看作亏空的2-结点 (确实被删除了，$r$ 取代之)，通过 $fixAfterDeletion$ 方法一定能够补上此亏空 (即向上调平)，而 $r$ 仍是红色，将与补上的2-结点 (见case2的2-3-4树) 或3-结点 (见case3或case4的2-3-4树) 组成3-结点或4-结点，因此原来补亏后亏空处变为2-结点或3-结点，现在变成了3-结点或4-结点，一方面红黑性质不变，一方面平衡也能得到保证，因此源码是正确的。但原本该处并不需要调整 (该分支删除3-结点的键，删除后并不导致失衡)，执行这样的调整显然是多余的。目前作者正尝试向 Oracle 报告该见解，若读者有不同看法也欢迎与作者交流 (hainanlxs AT yahoo.co.jp)。 ```java setColor(r, BLACK); // #1 r一定为红，置黑 // if (x.color == BLACK) fixAfterDeletion(r); // #2 调整 ``` 【补充2: 算法导论两处伪代码及注释】 我们给出的删除结点的方法基本上应用的是 JDK TreeMap的 `remove/deleteEntry` 方法，不过下面也给出如下「算法导论」中的相关伪代码，供读者对照学习。 ```java RB-TRANSPLANT (T, u, v) // v取代u (链接u.p和v) 1 if u.p == T.nil // 若u为根 2 T.root = v // 则新根为v 3 else if u == u.p.left // 否则若u为一左儿子 4 u.p.left = v // 其父的左儿子更新为v 5 else u.p.right == v // 否则若u为一右儿子，其父的右儿子更新为v 6 v.p = u.p // v父置为u父 ``` ```java RB-DELETE(T, z) // 待删除结点z 1 y = z 2 y-original-color = y.color // 记录待删除结点的颜色 3 if z.left == T.nil // z无左孩子 4 x = z.right // x为z的右孩子 5 RB-TRANSPLANT(T, z, z.right) // 链接z.p和x 6 else if z.right == T.nil // z无右孩子 7 x = z.left // x为z的左孩子 8 RB-TRANSPLANT(T, z, z.left) // 链接z.p和x 9 else y = TREE-MINIMUM(z.right) // z具有两个孩子，令y为z的后继，y将用于替换z，随后删除y 10 y-original-color = y.color // 记录y的颜色 11 x = y.right // x是y的右儿子（y必无左儿子） 12 if y.p == z // 若y的父亲为z 13 x.p = z // 令x的父亲为z (删除y) // 这一行CLRS写错了 14 else RB-TRANSPLANT(T, y, y.right) // 否则链接y.p和x (删除y) 15 y.right = z.right // 将z右子树挂到y右侧 (此时y已经是x了) 16 y.right.p = y // 令z的右子树指向y (与上一行一起链接y和z.right) 17 RB-TRANSPLANT(T, z, y) // 链接z.p和y 18 y.left = z.left // 将z左子树挂到y左侧 19 y.left.p = y // 令z的左子树指向y (与上一行一起链接y和z.left) 20 y.color = z.color // y继承z的颜色 21 if y-original-color == BLACK // 说明删除了一个2-结点，要调平 22 RB-DELETE-FIXUP(T, x) // 上溯调平 ``` <br /> ### 红黑树类架构 以下是红黑树类 (MyRBTree) 架构。 | 类成员/方法 | 描述 | | --------------------------------------------------------- | --------------------------------------- | | `private Node<K, V> root;` | 字段，红黑树的根结点 | | `private static final Boolean RED = false, BLACK = true;` | 常量字段，红与黑 | | `public MyRBTree()` | 无参构造器，$root$ 初始为 $null$ | | `public void makeEmpty()` | 树置空 | | `public boolean isEmpty()` | 判断树是否为空 | | `public boolean contains(K key)` | 判断是否有键为 $key$ 的结点 | | `public V get(K key)` | 获取对应 $key$ 的 $val$ | | `public K min()` | 返回最小 $key$ | | `public K max()` | 返回最大 $key$ | | `public Node<K, V> successor(Node<K, V> node)` | 返回 $node$ 的后继结点 | | `public void put(K key, V val)` | 插入结点驱动方法 | | `public void rotateLeft(Node<K, V> h)` | 左旋 | | `public void rotateRight(Node<K, V> h)` | 右旋 | | `public void delete(K key)` | 删除 $key$ | | `public void printTree()` | 中序遍历打印红黑树 | | `private Node<K, V> get(Node<K, V> x, K key)` | 在以 $x$ 为根结点的树中寻找目标键 $key$ | | `private void fixAfterInsertion(Node<K, V> x)` | 插入 $x$ 结点后的调整 | | `private void fixAfterDeletion(Node<K, V> x)` | 删除 $x$ 结点后的调整 | | `private Node<K,V> leftOf(Node<K,V> p)` | 返回 $p$ 结点的左子结点 | | `private Node<K,V> rightOf(Node<K,V> p)` | 返回 $p$ 结点的右子结点 | | `private Node<K, V> parentOf(Node<K, V> node)` | 返回 $node$ 结点的父结点 | | `private boolean colorOf(Node<K, V> node)` | 返回 $node$ 结点的颜色 | | `private boolean isRed(Node<K, V> node)` | 判断 $node$ 结点是否为红 | | `private boolean isBlack(Node<K, V> node)` | 判断 $node$ 结点是否为黑 | | `private void setColor(Node<K,V> node, boolean color)` | 设置结点 $node$ 颜色为 $color$ | | `private void put(Node<K, V> h, K key, V val)` | 插入结点 | | `private void delete(Node<K, V> x)` | 删除结点 | | `private void flipColor(Node<K, V> h)` | 结点 $h$ 反色 | | `private void flipColors(Node<K, V> h)` | 结点 $h$ 及其左右子结点反色 | | `private void printTree(Node t)` | 红序遍历打印红黑树 (以 $t$ 为根结点) | 以下为红黑树结点嵌套类 $Node$ 的架构。 | 类成员/方法 | 描述 | | ------------------------------------------------------------ | ------------------------------------------ | | `public boolean color` | 字段，本结点颜色 | | `public K key` | 字段，本结点 $key$ | | `public V val` | 字段，本结点 $value$ | | `public Node<K, V> parent, left, right` | 三个字段，本结点的父结点/左子结点/右子结点 | | `public Node(Boolean color, K key, V val, Node parent, Node left, Node right)` | 构造器 | <br /> ### 主要方法 重难点方法已在前面章节中详细介绍，完整的类代码请参考「类的实现代码」。 <br /> ### 类的实现代码 ```java class MyRBTree<K extends Comparable<K>, V> { private Node<K, V> root; private static final Boolean RED = false, BLACK = true; public MyRBTree() {} public void makeEmpty() { // 树置空 root = null; } public boolean isEmpty() { // 树判空 return root == null; } public boolean contains(K key) { // 判断是否存在key if (key == null) throw new IllegalArgumentException("argument to contains() is null"); return get(root, key) != null; } public V get(K key) { // 获取对应key的val if (key == null) throw new IllegalArgumentException("argument to get() is null"); return get(root, key).val; } private Node<K, V> get(Node<K, V> x, K key) { // 在以 x 为根结点的树中寻找目标键 key while (x != null) { int compareRes = key.compareTo(x.key); if (compareRes < 0) x = x.left; // 在左子树中寻找 else if (compareRes > 0) x = x.right; // 在右子树中寻找 else return x; // 找到返回该目标 key 的 val } return null; } // private Node<K, V> get(Node<K, V> x, K key) { // 递归版本get // if (x == null) return null; // int cmp = key.compareTo(x.key); // if (cmp < 0) return get(x.left, key); // 在左子树中寻找 // else if (cmp > 0) return get(x.right, key); // 在右子树中寻找 // else return x; // 找到 // } public K min() { // 返回最小键值 if (isEmpty()) throw new NoSuchElementException("calls min() with empty symbol table"); return min(root).key; } private Node<K, V> min(Node<K, V> x) { // 返回最小结点 if (x.left == null) return x; else return min(x.left); } // public Node<K, V> min(Node<K, V> node) { // 迭代版 // if (node.left == null) return node; // while (node.left != null) node = node.left; // return node; // } public K max() { // 返回最大键值 if (isEmpty()) throw new NoSuchElementException("calls max() with empty symbol table"); return max(root).key; } private Node<K, V> max(Node<K, V> x) { // 返回最大键 if (x.right == null) return x; else return max(x.right); } public Node<K, V> successor(Node<K, V> node) { // 返回结点 node 的后继结点 if (node.right != null) return min(node.right); //下面这里是不会进入的，因为只有node的两个孩子都不为null时才会进入这个方法 Node<K, V> y = node.parent; while ((y != null) && (y.right == node)) { node = y; y = y.parent; } return y; } public void put(K key, V val) { // 插入key-val结点 if (key == null) throw new IllegalArgumentException("first argument to put() is null"); if (val == null) { // 表示删除该key delete(key); return; } put(root, key, val); // 调用实际插入方法 } private void put(Node<K, V> h, K key, V val) { // 从结点 h 开始插入 key-val 结点 int compareRes; Node<K, V> cur = h, p = null; // cur: 当前结点，p: cur的父结点 while (cur != null) { p = cur; compareRes = key.compareTo(cur.key); if (compareRes < 0) cur = cur.left; // 往左 else if(compareRes > 0) cur = cur.right; // 往右 else { // 存在key，修改其值后返回 cur.val = val; return; } } // while正常结束，后续执行插入 Node<K, V> newNode = new Node<>(RED, key, val, null, null, null); // 插入的结点总是红色的 newNode.parent = p; if (p != null) { // 非空树，插入到 p 下 compareRes = newNode.key.compareTo(p.key); if (compareRes < 0) p.left = newNode; // 作为左子结点插入 else p.right = newNode; // 作为右子结点插入 } else this.root = newNode; // p == null 说明未进入while，树空，newNode作为根结点插入 fixAfterInsertion(newNode); // 向上调整，保持与2-3树同构 } public void rotateLeft(Node<K, V> h) { // 左旋 Node<K, V> x = h.right; // h左上x右下 h.right = x.left; // x左子树挂到h右侧 if (x.left != null) x.left.parent = h; // x左子树不空，x左子树的父节点更新为h x.parent = h.parent; // x转到h位置上，x的父节点为h的父节点 if (h.parent == null) this.root = x; // 若h为根结点 则x取代h后x为根结点 else { // 若h不为根结点 if (h == h.parent.left) h.parent.left = x; // h是左儿子，h的父节点更新其左儿子为x else h.parent.right = x; // h是右儿子，h的父节点更新其右儿子为x } x.left = h; // x左儿子更新为h h.parent = x; // h父节点更新为x } public void rotateRight(Node<K, V> h) { // 右旋 Node<K, V> x = h.left; h.left = x.right; if (x.right != null) x.right.parent = h; x.parent = h.parent; if (h.parent == null) this.root = x; else { if (h == h.parent.right) h.parent.right = x; else h.parent.left = x; } x.right = h; h.parent = x; } private void fixAfterInsertion(Node<K, V> x) { // 插入结点 x 后向上调整 Node<K, V> p, g; // parent, grandParent while (((p = parentOf(x)) != null) && isRed(p)) { g = parentOf(p); if (p == g.left) { // x的父节点是一个左儿子 Node<K, V> u = g.right; // uncle: p的兄弟结点，k的叔结点 if (isRed(u)) { // case1: x的叔结点为红，则x插入到一个4-结点中 flipColors(g); x = g; // 插入4-结点只需反色，此时要上溯到变红的g } else { // x的叔结点为黑，则x插入到一个3-结点中 if (x == p.right) { // case2: x是一个右儿子 x = p; rotateLeft(p); // 左旋，之后x在底部 } flipColor(p); // case3: 反色 setColor(p, BLACK); flipColor(g); // case3: 反色 setColor(g, RED); rotateRight(g); // case3: 右旋 } } else { // x的父节点是一个右儿子 Node<K, V> u = g.left; if (isRed(u)) { flipColors(g); x = g; } else { if (x == p.left) { x = p; rotateRight(p); } flipColor(p); flipColor(g); rotateLeft(g); } } } if (x == root) setColor(x, BLACK); } public void delete(K key) { // 删除key对应的结点 Node<K, V> x = get(this.root, key); // 找到key对应的结点x if (x != null) delete(x); } private void delete(Node<K, V> x) { // 删除结点 x if (x.left != null && x.right != null) { // x 有左右孩子 Node<K,V> s = successor(x); // 找到x的后继 x.key = s.key; // s 取代 x x.val = s.val; // s 取代 x x = s; // x 此时是实际要删除的 s } // 经过此 if 后，x 为实际要删除的结点，x 要么为无孩子的叶子结点，要么只有一个孩子结点 // case1:x只有左孩子或右孩子 // case2:若x无孩子，r为null Node<K,V> r = x.left != null ? x.left : x.right; // r: replacement用来取代x if (r != null) { // case1 // if(colorOf(r) != RED) System.out.println("xx"); // 测试，r一定为红 // if(colorOf(x) != BLACK) System.out.println("xx"); // 测试，x一定为黑 // Node<K, V> uncle = r == x.left ? x.right : x.left; // // if(uncle != null) System.out.println("xx"); // 测试，uncle一定为null // if(colorOf(uncle) != BLACK) System.out.println("xx"); // 测试，uncle一定为黑（null） // 以下四句链接x.p与r r.parent = x.parent; if (x.parent == null) root = r; // 原x为root else if (x == x.parent.left) x.parent.left = r; // 原x不为root且为一个左孩子 else x.parent.right = r; // 原x不为root且为一个右孩子 x.left = x.right = x.parent = null; // 删除x (x脱离树，置其左右子结点和父结点为 null) setColor(r, BLACK); // r一定为红，置黑 // if (x.color == BLACK) fixAfterDeletion(r); // 调整 } else if (x.parent == null) { // case2 x无孩子且无父结点，x为根结点，且该树只有此结点 root = null; } else { // case2 x无孩子但有父节点，则x为一叶子结点 if (x.color == BLACK) fixAfterDeletion(x); // x为2结点，调整 if (x.parent != null) { // 删除x if (x == x.parent.left) x.parent.left = null; // x为一左子结点 else if (x == x.parent.right) x.parent.right = null; // x为一右子结点 x.parent = null; } } } private void fixAfterDeletion(Node<K, V> x) { // 删除结点 x 后向上调整 Node<K, V> parent = parentOf(x); while (isBlack(x) && x != root) { if (x == leftOf(parent)) { // x是一个左子结点 Node<K, V> sib = rightOf(parent); // case1：sib为红，转换为后续case if (isRed(sib)) { setColor(parent, RED); setColor(sib,BLACK); rotateLeft(parent); // sib = parent.right; //「算法导论」伪代码有此句，可以省略 } // case2:左黑右黑，这种情形可能需要继续向上调平 if (isBlack(leftOf(sib)) && isBlack(rightOf(sib))) { setColor(sib, RED); x = parent; // 向上调平 parent = parentOf(x); // 更新parent } else { // case3 & case4 一定能够恢复同构 // case3: 右黑，其实就是左红右黑，转换为case4 if (isBlack(rightOf(sib))) { setColor(sib.left, BLACK); setColor(sib, RED); rotateRight(sib); // sib = parent.right; //「算法导论」伪代码有此句，可以省略 } // 以下是case4: 右红，其实就是左红右红或左黑右红，这种情形一定恢复同构 setColor(sib, colorOf(parent)); setColor(parent, BLACK); setColor(rightOf(sib), BLACK); rotateLeft(parent); x = root; //此句用于退出while，因为case3和case4调整后必恢复同构 } } else { Node<K, V> sib = leftOf(parent); if (isRed(sib)) { setColor(parent, RED); setColor(sib, BLACK); rotateRight(parent); } if (isBlack(leftOf(sib)) && isBlack(rightOf(sib))) { setColor(sib, RED); x = parent; parent = parentOf(x); } else { if (isBlack(leftOf(sib))) { setColor(sib.right, BLACK); setColor(sib, RED); rotateLeft(sib); } setColor(sib, colorOf(parent)); setColor(parent, BLACK); setColor(leftOf(sib), BLACK); rotateRight(parent); x = root; } } } // while结束要么是case3/case4调整后已平衡 x被被置为root后主动退出， // 要么是case1/case2 x为红。若为前者无需此句(此时的root一定是黑的) // 若为后者，说明此时的x结点是原3-结点或4-结点出借的结点，如果还保持红色， // 将无法脱离原3-结点或4-结点 (2-3-4树)，因此必须置黑。 setColor(x, BLACK); // 也可以写成这样 if(x != root) setColor(x, BLACK); } private Node<K,V> leftOf(Node<K,V> p) { // 返回 p 的左子结点 return (p == null) ? null: p.left; } private Node<K,V> rightOf(Node<K,V> p) { // 返回 p 的右子结点 return (p == null) ? null: p.right; } private Node<K, V> parentOf(Node<K, V> node) { // 返回 p 的父结点 return node != null ? node.parent : null; } private boolean colorOf(Node<K, V> node) { // 返回 node 的颜色 if (node != null) return node.color; return BLACK; } // public void setParent(Node<K, V> node, Node<K, V> parent) { // if (node != null) node.parent = parent; // } private boolean isRed(Node<K, V> node) { // 判断 node 是否为红 return (node != null && node.color == RED) ? true : false; } private boolean isBlack(Node<K, V> node) { // 判断 node 是否为黑 return !isRed(node); } private void setColor(Node<K,V> node, boolean color) { // 设置 node 的颜色为 color if (node != null) node.color = color; } private void flipColor(Node<K, V> h) { // 结点 h 反色 h.color = !h.color; } private void flipColors(Node<K, V> h) { // 「^」形反色 (h为「^」形的父结点) h.color = !h.color; h.left.color = !h.left.color; h.right.color = !h.right.color; } public void printTree(){ // 中序遍历打印红黑树 printTree(root); } private void printTree(Node t) { // 中序遍历打印红黑树 if(t != null) { printTree(t.left); System.out.print(t.key + " "); printTree(t.right); } } /** * 红黑树结点嵌套类 */ public class Node<K extends Comparable<K>, V> { public boolean color; public K key; public V val; public Node<K, V> parent, left, right; public Node(Boolean color, K key, V val, Node parent, Node left, Node right) { this.color = color; this.key = key; this.val = val; this.parent = parent; this.left = left; this.right = right; } } } ``` <br /> ### 测试代码 ```java public static void main( String [ ] args ) { MyRBTree<Integer, Integer> t = new MyRBTree<>(); int NUMS = 1_000_000, GAP = 307; System.out.println( "Checking... (no bad output means success)" ); // 插入测试 for(int key = GAP; key != 0; key = (key + GAP) % NUMS) t.put( key , key + 1); System.out.println("Inserts complete"); // 删除测试 for(int key = 1; key < NUMS; key += 2) t.delete(key); System.out.println( "Removes complete" ); for(int key = 2; key < NUMS; key += 2) { if(!t.contains(key)) System.out.println( "Error: find fails for " + key ); } for(int key = 1; key < NUMS; key += 2){ if(t.contains(key)) System.out.println( "Error: Found deleted item " + key ); } NUMS = 5_000_000; for(int key = GAP; key != 0; key = (key + GAP) % NUMS) t.put( key , key + 1); System.out.println("Inserts complete"); for(int key = 1; key < NUMS; key += 2) t.delete(key); System.out.println( "Removes complete" ); for(int key = 2; key < NUMS; key += 2) { if(!t.contains(key)) System.out.println( "Error: find fails for " + key ); } for(int key = 1; key < NUMS; key += 2){ if(t.contains(key)) System.out.println( "Error: Found deleted item " + key ); } } ``` 输出如下说明测试通过。 ```java Checking... (no bad output means success) Inserts complete Removes complete Inserts complete Removes complete ``` <br /> ### 小结 - 指出了红黑颜色本质上是 BST 附带的1bit信息，该信息的存在使得红黑树在保持 BST 形态的同时始终与2-3-4树同构。 - 详细解释了红黑树五大性质的根本。 - 深入分析并展示了红黑树的插入结点和删除结点操作。 - 在「删除结点」小节中，仔细对比了各情形下的2-3-4树与红黑树形态，从数十种形态中成功归约出 4 种独立情形。 - 提出 JDK 中代码中的疑似存在的逻辑瑕疵 (充分验证后将向 Oracle 报告该问题)。 - 给出了较为完整的红黑树类的代码。 <br /> ## 左倾红黑树 这一节我们学习前述经典红黑树的一种变体，即著名的 *Algorithms 4th* 一书中介绍的 **左倾红黑树 ( *Left-Leaning Red-black Tree, LLRBT* )** ，LLRBT 的提出者以及「红黑树」的命名者正是该书作者 Sedgewick。 我们已经知道，经典红黑树与2-3-4树同构，本节中我们将看到 **LLRBT 与2-3树同构** ，它也是 BST ，因此在保持2-3树的「完美平衡」优点的基础上 (在 *LLRBT* 中体现为完美黑平衡)，也能够直接继承基本 BST 操作的写法，这一点与经典红黑树是一样的。在 LLRBT 中，尤其是在其删除操作中，我们将领略技巧十分高超的代码实现。 > 「左倾红黑树」由 Sedgewick 在 [这篇论文](https://sedgewick.io/wp-content/themes/sedgewick/papers/2008LLRB.pdf) 中提出。 > > [Eddie Kohler](http://read.seas.harvard.edu/~kohler/) 的文章 [Left-Leaning Red-Black Trees Considered Harmful](https://read.seas.harvard.edu/~kohler/notes/llrb.html) 指出了 LLRBT 的一些缺点，文章中对经典红黑树和 LLRBT 做了许多比较，推荐阅读。 <br /> ### 从2-3树到LLRBT 从2-3树转换为 LLRBT 比2-3-4树到红黑树的转换更为简单，只需将2-3树的所有3-结点转变为一条 **左斜的红链** (这就是 LLRBT 名称的由来) 即可。子结点 (左下结点) 为红色，父结点 (右上结点) 为黑色。显然 LLRBT 可与一棵2-3树严格对应。下图将红黑树中的红链横放，将红链看作一个3-结点后，能够很清楚地看出 LLRBT 与2-3树严格对应。 ※ LLRBT 规定红链左斜是为了使红黑树更易于实现。本节图片多为 *Algorithms 4th* 的原图。  有了这样的定义和对应关系后，我们指出 LLRBT 具有以下性质。 | LLRBT 性质 | 描述 | | ------------- | ------------------------------------------------------------ | | 1. 红链左斜 | 所有红链都是左斜的 | | 2. 红链不相邻 | 不存在与同一个结点相连的两条红链 | | 3. 完美黑平衡 | LLRBT 是「完美黑平衡」的，即任意叶子结点到根结点所经过的黑链数相同。 | - 1由定义决定。 - 对于2，在「红黑树」一节中我们已经知道，两条相邻的红链是4-结点。 - 对于3，因为2-3树是完美平衡的，转换成 LLRBT 后，不考虑红链 (本质为一个3-结点) 的情况下 (即只考虑黑链) 是完美平衡的，于是对整棵 LLRBT ，我们就说它完美黑平衡。 <br /> #### 结点变换 LLRBT 与2-3树严格对应，因此其保持平衡的操作也应当 **与2-3树相对应** ，我们已经知道，2-3树是通过「结点变换」来保持平衡的，之前我们通过考察2-3树结点插入过程分析过其结点变换过程，同样地，在本节中我们采用对照的方式，首先考察 LLRBT 插入结点过程中的结点变换，然后考察在2-3树中未涉及的删除结点过程中的结点变换，后者相比前者要更为复杂。 <br /> #### 插入结点 我们直接对比2-3树的插入情形，写出 LLRBT 与之对应的变换过程。 1. 情形1。在2-3树中插入目标键 ($x$) 后2-结点变为3-结点，对应到 LLRBT 即按照基本 BST 方式插入后，插入结点与其父结点的链为 **红链** (红链才能对应到2-3树中的3-结点)，实际表现为该插入结点为红色。如果红链为右链，那么根据性质1，需左旋该链，实际操作为左旋其父结点 (左旋方法参数传入父结点)。 2. 情形2。对于2-3树插入目标键 ($x$) 后3-结点 (两个键分别为 $y,z$ ) 变为4-结点，然后分解为3个2-结点。这个分解实际上包含了三种细分情形，$x < y < z$， $y < x < z$，$y < z < x$ ，使得分解后 $x,y,z$ 的相对位置有所不同，但形态上是一样的。但对应到 LLRBT 中，这三种情形的形态各不相同，分别为 **「/」形、「<」形及「^」形** ，如后图。这三种形态都表现为 **「两条相邻的红链」** ，我们知道这代表了4-结点，所以也要像2-3树那样分解为3个2-结点，具体操作如下。 1. 首先考虑「^」形，此形态 **本身已经是三个2-结点** ，因此直接将「^」上的三个结点反色即可，即将左右子结点的颜色置黑，父结点置红。 2. 对于「/」形，只需将上段红链右旋后 (对右上顶点执行右旋) 即可转变为「^」形，随后反色。 3. 对于「<」形，只需将下段红链左旋后 (对中间顶点执行左旋) 即可转变为「/」形，然后将上段红链右旋变为「^」形，最后反色。 3. 情形3。在2-3树中也是4-结点分解为3个2结点，但父结点会变为3-结点，对应到 LLRBT 中，根据情形2的分析，变换为3个2结点最终都对应着「^」形结构，父结点变为3-结点对应着 「^」 形结构的 **中结点要被置为红色** ，相当于向父结点中放入一个结点。这一对应使得该情形的 「^」 形反色时，左右两个结点被置为黑色的同时，中结点要被置为红色。 4. 情形4。如下图，三种情形最终都会变成右侧形态，即对应2-3树中父结点变为4-结点 (两条相邻红链)，此后继续向上按规则变换即可 (在实现中在递归的回溯过程中执行)。  ※ 在情形2中，由于 LLBRT 在操作后只有左红链，所以插入结点后一定不会出现「`\`」形或「`>`」形。 | 情形 | 2-3树 | LLRBT | | --------------------------------------- | ------------------------------------------------------------ | ------------------------------------------------------------ | | 1. 插入至2-结点中 | 变为 **3-结点** | 变为 **红链** ，若为右红链，则左旋 | | 2. 插入至3-结点中<br />(该结点为根结点) | 变为4-结点，分解为3个2-结点 | 根据新键与原3-结点(红链连接的两个结点)中两键的大小关系，有三种情形。<br />1. 「^」形，反色<br />2. 「/」形，上段右旋为「^」后反色<br />3. 「<」形，下段左旋为「/」后上段右旋为「^」后反色 | | 3. 插入至3-结点中<br />(父结点为2-结点) | 变为4-结点，分解为3个2-结点，其中一个与父结点合并，使得父结点变为3-结点 | 同上 | | 4. 插入至3-结点中<br />(父结点为3-结点) | 与上一条类似，其中一个与父结点合并，使得父结点变为4-结点，继续向上(插入一个结点后)分解直到：<br />1. 遇到2-结点，转变为情形1。<br />2. 到根处仍为3-结点，转变为情形2。 | 「^」「/」「<」最终都使得其上侧变为两条相邻的红链，此后再继续向上变换。 | 下图展示了在 LLRBT 的2-结点和3-结点中插入结点的过程。  通过上述对照分析，我们看到通过颜色调整和旋转 LLRBT 的实现确实与2-3树一一对应，这也解释了一些一开始不太好理解的操作细节，例如令插入结点为「红色」、三种「相邻红链」情形的变换过程，以及「^」形时的反色动作 (两个子结点变黑，父结点变红)， 这些都是 LLRBT 与2-3树同构所要求的。 ```java public void put(K key, V val) { // 插入key-val结点 if (key == null) throw new IllegalArgumentException("first argument to put() is null"); if (val == null) { // 表示删除该key delete(key); return; } root = put(root, key, val); // 调用实际插入方法 root.color = BLACK; // 每次插入结点后根结点都要描黑 } private Node put(Node h, K key, V val) { // 在以h为根的树中插入结点key-val if (h == null) return new Node(key, val, RED, 1); // 插入 (与父结点用红链连接) int compareRes = key.compareTo(h.key); if (compareRes < 0) h.left = put(h.left, key, val); // 在左子树中寻找插入位置 else if (compareRes > 0) h.right = put(h.right, key, val); // 在右子树中寻找插入位置 else h.val = val; // key相等，更新键 return balance(h); // 回溯过程中向上调整 } private Node balance(Node h) { // 恢复结点h处的LLRBT性质 if (!isRed(h.left) && isRed(h.right)) h = rotateLeft(h); // 左黑右红（包含「<」形），左旋 if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h); // 「/」形，上段右旋 if (isRed(h.left) && isRed(h.right)) flipColors(h); // 「^」型，反色 h.size = size(h.left) + size(h.right) + 1; return h; } ``` <br /> ##### 旋转 现在我们来看 LLRBT 中的旋转操作。下图分别展示了左旋和右旋过程以及相应的代码，我们之前说过，2-3树/2-3-4树不是通过旋转，而是通过结点变换来保持平衡，但是，当我们用红黑树/LLRBT 来表示2-3-4树/2-3树时，为了能够在保持与2-3-4树/2-3树的对应，是需要旋转操作的，这一点我们已经在前面分析过了。从下图可以看到，LLRBT 的旋转操作与以前我们学习过的旋转操作基本一样，只是因为要保持链的颜色不变，因此多了 **结点颜色调整** 的步骤 (以及子树结点数的更新)。  <br /> #### 删除结点 如同 BST 的删除操作那样，删除结点的方法中，首先要找到该结点，然后用该结点右子结点为根结点的子树中的最小结点 (键值) 来替换删除目标结点，再执行删除最小结点方法删掉被替换的最小结点，因此需要 **先实现删除最小结点方法** 。 我们先考虑2-3树的删除过程，首先把「删除结点」的表述替换成「删除键」(在2-3树中，只有最小键在2-结点中才会「删除结点」，否则只是删除键)。最小键一定在叶子结点中，当该叶子结点为3-结点时 (最小键为该3-结点的两个键中较小的那个)，直接删除该最小键即可。若最小键对应的叶子结点是2-结点，直接删除会导致不满足2-3树的结构要求。为了保持仍为一棵2-3树，一个简单的想法是，通过某种 **「膨胀调整」** ，使得删除最小键时，它所在的叶子结点的容量比2-结点大，这时候就可以直接删除它 (此时它是结点中最左边的键)，结点仍在 (只是缩小了)，也就能够保持完美平衡。 因为我们不知道什么时候会到达最小键所在的叶子结点，为了能够让最小键所在结点最终调整成比2-结点大的结点，我们需要从根开始这一调整，在从根到目标结点的路径上，考察途径的当前结点，当此结点为2-结点时，将其膨胀。在「插入结点」过程中，对临时出现的4-结点，我们采取了分解操作，相对应地，膨胀可以看作 **分解的逆过程** 。 「结点膨胀」的实现稍后讲解，先假设已经实现，那么经过上述操作，我们 **一定能够保证** 到达最小键所在结点时，该结点比2-结点大，从而能够删除最小键而不破坏2-3树的完美平衡性质。此外，如下事实也是易知的。 1. 过程中可能会出现4-结点 (但不会出现更大的结点) ，也可以说删除操作使得这棵树的 **中间态为一棵2-3-4树** 。 2. 如果是根结点及其左右儿子结点均为2-结点的情况，这三个2-结点将膨胀为一个4-结点，树高将减 1 (对2-3-4树而言减1，对 LLRBT 而言则不变) 。 3. 最小键对应到 BST 中，一定是一个 **左斜红链下的红色叶子结点** 。 对于第 3 点，我们也可以说删除最小键所做的膨胀操作，就是为了保证我们最终删除的最小键，是一个左斜链下的红色叶子结点。  完成删除后，程序开始回溯，在回溯的过程中分解删除路径上临时产生的4-结点，这一过程与「插入结点」的回溯过程完全相同。回溯到根结点时，若删除开始之前根结点及其左右儿子结点均为2-结点的情况，它们会合成为一个4-结点，那么此时会被分解为三个2-结点，树高加 1 (对2-3-4树而言加1，对 LLRBT 而言则不变) 。 <br /> ##### 膨胀 现在我们来分析「结点膨胀」，这一部分是整个 LLRBT 最难的内容，请读者将如下文字描述与示意图和代码结合起来理解。示意图中 LLRBT 以常规的 BST 形式呈现，为了集中精力理解膨胀过程，不再表现键值，一些不重要的分支也不画出。注意，描述时我们必须同时将 LLBRT 看作2-3-4树 (虽然 LLBRT 对应的是2-3树，但删除的过程的中间态是2-3-4树) ，必要时我会在「结点」一词后用括号 (BST) 或 (2-3-4树) 来强调此时说的结点是哪种形态语境下的结点。这样做的原因是为了保持 LLRBT 始终与2-3树同构，因此当行文强调2-3树/2-3-4树时，读者不妨在脑海中将 LLRBT 中的红链放平，将水平的结点看作一个结点 (2-3树/2-3-4树的结点)。以下，我们将当前结点为根结点的情况记作case1，不为根结点的情况记作case2。 **首先处理case1** 。当前结点 (BST) 是根结点 (BST) ，为黑色，我们要考察它是2-结点还是3-结点。先列出我们的目标： 1. 如果根结点是3-结点，无需处理，继续前往左子树。 2. 如果根结点是2-结点。 1. 且两个子结点都是2-结点，将这三个2-结点膨胀为一个4-结点。 2. 若左子结点为2-结点，右子结点不是2-结点，就通过右子结点借一个键到左子结点中 (通过旋转，实际借的是根结点的键)。 现在来实现上述目标。在删除最小键驱动方法中，若不满足 `if (!isRed(root.left) && !isRed(root.right))` ，则说明根结点为3-结点，记作case1-1，否则根结点为2-结点，记作case1-2 (注意，根据 LLRBT 的性质，根结点及其左右子结点的形态只能是case1-1或case1-2)。对于case1-2，先将根结点 (BST) 翻红，这么操作的原因稍后解释。接着调用删除最小键具体方法，执行 `root = deleteMin(root)` 。 - case1-1: 根结点为3-结点，无需膨胀，但不直接去往左子树，而是与case1-2一样，先执行 `root = deleteMin(root)` 。 - case1-2: 根结点为2-结点，继续考察，执行 `root = deleteMin(root)` 。 - case1-2-1: 通过 `if (!isRed(h.left) && !isRed(h.left.left))` 考察根结点的左子结点 (2-3-4树)，若不满足 $if$ 条件，则根结点的左子结点为3-结点或case1-1，无需膨胀，执行下一句 `h.left = deleteMin(h.left)` ，去往左子树递归删除。 - case1-2-2: 若满足上述 $if$ 条件，则根结点的左子结点为2-结点，需膨胀，但还不知道是「三个2-结点膨胀为一个4-结点」，还是从根结点的右子结点 (间接地) 「借键膨胀」，这取决于根结点的右子结点是否为2-结点，于是执行 `h = moveRedLeft(h)` 进一步处理。进入该方法后首先执行反色语句 `flipColors(h)` ，这么做的原因我们马上会知道。 - case1-2-2-1: 反色后通过 `if (isRed(h.right.left))` 考察根结点的右子结点是否为2-结点，若不满足，则为2-结点，需要将根结点及其左右子结点膨胀为一个4-结点， **而刚才的反色操作已经完成了这一膨胀** ，这就是进入 `moveRedLeft(h)` 方法后先执行反色操作的原因。 - case1-2-2-2: 若满足，则根结点的右子结点为一个3-结点，于是通过 **两次旋转** 将左子结点膨胀为一个3-结点 (借用了原根结点的键，根结点则借来了其右子结点的键，因此可以说左子结点借了原根的键，也可以说左子结点「间接地」借了右子结点的键)。两次旋转完成后还需 **一次反色** 恢复 LLRBT 性质。另外，这一次的反色操作让我们看清了 case1-2 先将根结点翻红的原因，详细解释请看【补充QA】。 通过上述操作，当前结点为根结点的情况 (case1) 处理完成，我们保证了接下来要去往的 **根结点的左子结点** 为3-结点 (case1-1, case1-2-1, case1-2-2-2) 或4-结点 (case 1-2-2-1) 。  **接着处理case2。** 不妨假设当前结点是根结点的左子结点，根据前述分析，当前结点是一个3-结点或4-结点的最小键所在的结点 (BST) ，且为红色。我们要考察它的左子结点 (2-3-4树) 是否需要膨胀。由于当前结点不是根结点，因此在程序中此时位于删除最小键的具体方法 `deleteMin(Node h)` 中，如果当前结点的左子结点为 $null$ ，那么当前结点就是最小键，返回 $null$ 即意味着将其删除，即此句 `if (h.left == null) return null`。如果不是 $null$ ，那么有如下情况。 - case2-1: 通过 `if (!isRed(h.left) && !isRed(h.left.left))` 考察当前结点的左子结点 (2-3-4树)，若不满足 $if$ 条件，则根结点的左子结点为3-结点，无需膨胀，执行下一句 `h.left = deleteMin(h.left)` ，去往左子树递归删除。 - case2-2: 若满足上述 $if$ 条件，则当前结点的左子结点为2-结点，需膨胀，但还不知道是「三个2-结点膨胀为一个4-结点」，还是从根结点的右子结点 (间接地) 「借键膨胀」，这取决于根结点的右子结点是否为2-结点，于是执行 `h = moveRedLeft(h)` 进一步处理。进入该方法后首先执行反色语句 `flipColors(h)` ，这么做的原因我们在case1中已经见过了。 - case2-2-1: 反色后通过 `if (isRed(h.right.left))` 考察当前结点的右子结点是否为2-结点，若不满足，则为2-结点，需要将当前结点 (BST) 及其左右子结点膨胀为一个4-结点， **而刚才的反色操作已经完成了这一膨胀** 。 - case2-2-2: 若满足，则当前结点的右子结点为一个3-结点，于是通过 **两次旋转** 将左子结点膨胀为一个3-结点 (借用了当前结点 (2-3-4树) 中的最小键，当前结点则借来了其右子结点的键，因此可以说左子结点借了原根的键，也可以说左子结点「间接地」借了右子结点的键)。两次旋转完成后还需 **一次反色** 恢复 LLRBT 性质。  通过上面的分析，可以感受到这部分代码极具技巧性，case2 在代码上就是 case1-2 的复用 (实际意义上只有极细微的差别)，返回前的 `balance(h)` 也与插入结点时的回溯一样，反色后旋转在一定规则的指导下竟然能配合得如此奇妙，实在是令人拍案叫绝。 ```java public void deleteMin() { // 删除最小键驱动方法 if (isEmpty()) throw new NoSuchElementException("BST underflow"); if (!isRed(root.left) && !isRed(root.right)) root.color = RED; // 根结点为2-结点 root = deleteMin(root); // 调用删除最小键具体方法 if (!isEmpty()) root.color = BLACK; // 恢复根结点颜色为黑色 } private Node deleteMin(Node h) { // 删除以h为根结点的最小键 if (h.left == null) return null; // 找到最小键，删除(即返回null，使得这个最小键的父结点.left=null) if (!isRed(h.left) && !isRed(h.left.left)) h = moveRedLeft(h); // 借键 h.left = deleteMin(h.left); // 向左子树递归删除 return balance(h); // 回溯过程中恢复路径上结点的LLRBT性质(分解4-结点) } private Node moveRedLeft(Node h) { flipColors(h); if (isRed(h.right.left)) { // h.left 的兄弟结点是3-结点 h.right = rotateRight(h.right); h = rotateLeft(h); flipColors(h); } // 若不满足，说明 return h; } ``` 【补充QA】 - 在删除最小键驱动方法 $deleteMin$ 中，case1-2 时的 `root.color = RED` 的意义？ - 我们已经知道，一个「^」形所代表的4-结点 (父黑左右子结点红，以下简称黑红红) 分解为三个2-结点时，形态不变，只需将三个结点的颜色翻转 (翻转为父红左右子结点黑，以下简称红黑黑)。膨胀是其逆过程，因此也只需将三个结点的颜色翻转，但是不要忘了，初始时，根结点的颜色总是黑色的，因此需要先将根结点颜色翻红。通过后续动作很容易验证这一操作的必要性及正确性，根结点翻红后三个结点为红黑黑，而后的三种情况如下，均符合 LLRBT (含中间态) 的性质。 - 不反色为case1-2-1，红黑黑。 - 经过一次反色变为case1-2-2-1，黑红红。 - 经过两次反色变为case1-2-2-2，红黑黑。 - $moveRedLeft$ 方法实现「借键」，这个方法名应该怎么理解？ - (仅为作者的个人看法) 这个方法的命名大概是想表达 move red to left。整个过程看起来像是从兄弟结点借键，但实际上借的是父结点的键，只不过父结点能够借出给左子结点，是因为右子结点把其较小键借给了父结点，这是通过两次旋转实现的传递。总之代码作者可能是想表达该方法最终让 $left$ 变 $red$ 了，但不关心是从谁那 $move$ 来的。 - $deleteMax / moveRedRight$ 的分析分别与 $deleteMin/moveRedLeft$ 类似，但各自都有一条语句的区别。 - 在删除最大键的具体方法 $deleteMax$ 中，第一行的 `if (isRed(h.left)) h = rotateRight(h)` 是删除最小键具体方法所没有的。这是因为对于删除最小键，膨胀变换保证了这个最小键对应左斜链下的红色叶子结点，因此可直接删除。而最大键如果在左斜红链父结点中，就不能直接删除，需要右旋将最大键置于右链子结点后才可以直接删除。如果最大键在4-结点中，可直接删除，不过前述语句对这两种情况都统一做了右旋，使得最终可以直接删除最大键所在的右下末端结点。示意图如下。  最后来分析删除指定键的方法 $delete$ (包括驱动方法和具体方法) 。与 $deleteMin$ 一样，首先考虑目标键在叶子结点中 (2-3树)，且该叶子结点为2-结点中，直接删除会导致失去2-3树结构。因此也要像 $deleteMin$ 那样自顶向下「膨胀」，在删除指定键的路径上，总是使当前结点不为2-结点。找到目标后在以其右子结点为根结点的子树中寻找最小键，用其键值替换掉删除目标的键值，而后执行 $deleteMin$ 删除这个最小键。具体请看如下代码注释。 ```java public void delete(K 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; // 根结点为2-结点 root = delete(root, key); // 调用具体删除指定键的方法 if (!isEmpty()) root.color = BLACK; // 恢复根结点颜色为黑色 } private Node delete(Node h, K key) { // 在以h为根结点的树中删除指定键 if (key.compareTo(h.key) < 0) { // 目标在当前h的左子树中 if (!isRed(h.left) && !isRed(h.left.left)) h = moveRedLeft(h); // h.left是一个2-结点，借键膨胀 h.left = delete(h.left, key); // 递归删除 } else { // 目标可能等于h.key也可能在h的右子树中 if (isRed(h.left)) h = rotateRight(h); // 避免目标结点无右子树 (若无右子树则无法用min(h.right)来完成替换) if (key.compareTo(h.key) == 0 && (h.right == null)) return null; // h为目标结点且无右子树，说明目标结点为叶子结点，可直接删除 if (!isRed(h.right) && !isRed(h.right.left)) h = moveRedRight(h); // h.right是一个2-结点，借键膨胀 if (key.compareTo(h.key) == 0) { // h为目标结点且有右子树 Node x = min(h.right); // 找到h的后继x h.key = x.key; // x取代h h.val = x.val; // x取代h h.right = deleteMin(h.right); // 删除x } else h.right = delete(h.right, key); // 递归删除 } return balance(h); // 回溯过程中恢复路径上结点的LLRBT性质(分解4-结点) } ``` <br /> ### LLRBT类架构 以下是LLRBT类 (LeftLeaningRedBlackTree) 架构。 | 类成员/方法 | 描述 | | --------------------------------------------------------- | -------------------------------------------- | | `private Node<K, V> root;` | 字段，LLRBT 的根结点 | | `private static final Boolean RED = false, BLACK = true;` | 常量字段，红与黑 | | `public LeftLeaningRedBlackTree()` | 无参构造器，$root$ 初始为 $null$ | | `public int size()` | 返回当前树的大小驱动方法 | | `public void makeEmpty()` | 树置空 | | `public boolean isEmpty()` | 判断树是否为空 | | `public boolean contains(K key)` | 判断是否有键为 $key$ 的结点 | | `public V get(K key)` | 获取对应 $key$ 的 $val$ | | `public K min()` | 返回最小 $key$ | | `public K max()` | 返回最大 $key$ | | `public void put(K key, V val)` | 插入结点驱动方法 | | `public void deleteMin()` | 删除最小键驱动方法 | | `public void deleteMax()` | 删除最大键驱动方法 | | `public int height()` | 返回当前树高 | | `public void rotateLeft(Node<K, V> h)` | 左旋 | | `public void rotateRight(Node<K, V> h)` | 右旋 | | `public void delete(K key)` | 删除 $key$ | | `public void printTree()` | 中序遍历打印红黑树 | | `public K floor(K key)` | 返回小于等于 key 的键 | | `public K ceiling(K key)` | 返回大于等于 key 的键 | | `private int size(Node<K, V> x)` | 返回以结点 x 为根结点的树的大小 | | `private Node<K, V> get(Node<K, V> x, K key)` | 在以 $x$ 为根结点的树中寻找目标键 $key$ | | `private Node<K, V> min(Node<K, V> x)` | 返回最小结点 | | `private Node<K, V> max(Node<K, V> x)` | 返回最大结点 | | `private boolean isRed(Node<K, V> node)` | 判断 $node$ 结点是否为红 | | `private Node put(Node<K, V> h, K key, V val)` | 插入结点 | | `private Node deleteMin(Node h)` | 删除以h为根结点的最小键 | | `private Node<K, V> delete(Node<K, V> h, K key)` | 在以 h 为根结点的树中删除指定键 | | `private void flipColors(Node<K, V> h)` | 结点 $h$ 及其左右子结点反色 | | `private Node moveRedLeft(Node h)` | 借键到左侧 | | `private Node moveRedRight(Node h)` | 借键到右侧 | | `private Node balance(Node h)` | 恢复结点 h 处的 LLRBT 性质 | | `private int height(Node x)` | 返回以结点 x 为根结点的树的树高 | | `private Node<K, V> floor(Node<K, V> x, K key)` | 在以 x 为根结点的树中返回小于等于 key 的结点 | | `private Node<K, V> ceiling(Node<K, V> x, K key)` | 在以 x 为根结点的树中返回大于等于 key 的结点 | | `private void printTree(Node t)` | 红序遍历打印红黑树 (以 $t$ 为根结点) | 以下为 LLRBT 结点嵌套类 $Node$ 的架构。 | 类成员/方法 | 描述 | | ---------------------------------------------------- | ----------------------------------- | | `public boolean color` | 字段，本结点颜色 | | `public K key` | 字段，本结点 $key$ | | `public V val` | 字段，本结点 $value$ | | `public Node<K, V> left, right` | 两个字段，本结点的左子结点/右子结点 | | `private int size` | 以本结点为根结点的树的大小 | | `public Node(K key, V val, boolean color, int size)` | 构造器 | <br /> ### 主要方法 重难点方法已在前面章节中详细介绍，完整的类代码请参考「类的实现代码」。 <br /> ### 类的实现代码 ```java class LeftLeaningRedBlackTree<K extends Comparable<K>, V> { private static final boolean RED = false, BLACK = true; private Node<K, V> root; public LeftLeaningRedBlackTree() {} public int size() { // 当前树的大小 return size(root); } private int size(Node<K, V> x) { // 返回以结点 x 为根结点的树的大小 if (x == null) return 0; return x.size; } public void makeEmpty() { // 树置空 root = null; } public boolean isEmpty() { // 树判空 return root == null; } public boolean contains(K key) { // 判断树中是否存在键为 key 的结点 return get(key) != null; } public V get(K key) { // 获取对应key的val if (key == null) throw new IllegalArgumentException("argument to get() is null"); return get(root, key).val; } private Node<K, V> get(Node<K, V> x, K key) { // 在以 x 为根结点的树中寻找目标键 key while (x != null) { int compareRes = key.compareTo(x.key); if (compareRes < 0) x = x.left; // 在左子树中寻找 else if (compareRes > 0) x = x.right; // 在右子树中寻找 else return x; // 找到返回目标结点 } return null; } // private V get(Node x, K key) { // 递归版本get // if (x == null) return null; // int cmp = key.compareTo(x.key); // if (cmp < 0) return get(x.left, key); // else if (cmp > 0) return get(x.right, key); // else return x.val; // } private boolean isRed(Node x) { // 判断结点是否为红色 if (x == null) return false; // 空结点为黑色 return x.color == RED; } public void put(K key, V val) { // 插入 key-val 结点 if (key == null) throw new IllegalArgumentException("first argument to put() is null"); if (val == null) { // 表示删除该key delete(key); return; } root = put(root, key, val); // 调用实际插入方法 root.color = BLACK; // 每次插入结点后根结点都要描黑 } private Node put(Node<K, V> h, K key, V val) { // 在以 h 为根的树中插入结点 key-val if (h == null) return new Node(key, val, RED, 1); // 插入 (与父节点用红链连接) int compareRes = key.compareTo(h.key); if (compareRes < 0) h.left = put(h.left, key, val); // 在左子树中寻找插入位置 else if (compareRes > 0) h.right = put(h.right, key, val); // 在右子树中寻找插入位置 else h.val = val; // key相等，更新键 // 回溯过程中向上调整 return balance(h); } public void deleteMin() { // 删除最小键驱动方法 if (isEmpty()) throw new NoSuchElementException("BST underflow"); if (!isRed(root.left) && !isRed(root.right)) root.color = RED; // 根结点为2-结点 root = deleteMin(root); // 调用删除最小键具体方法 if (!isEmpty()) root.color = BLACK; // 恢复根结点颜色为黑色 } private Node deleteMin(Node h) { // 删除以h为根结点的最小键 if (h.left == null) return null; // 找到最小键，删除(即返回null，使得这个最小键的父节点.left=null) if (!isRed(h.left) && !isRed(h.left.left)) h = moveRedLeft(h); // 借键 h.left = deleteMin(h.left); // 向左子树递归删除 return balance(h); // 回溯过程中恢复路径上结点的LLRBT性质(分解4-结点) } public void deleteMax() { // 删除最大键驱动方法 if (isEmpty()) throw new NoSuchElementException("BST underflow"); if (!isRed(root.left) && !isRed(root.right)) root.color = RED; root = deleteMax(root); if (!isEmpty()) root.color = BLACK; } private Node deleteMax(Node h) { // 删除最大键具体方法 if (isRed(h.left)) h = rotateRight(h); // 避免最大键为左红链父结点的情况，将其右旋至右下末端 if (h.right == null) return null; if (!isRed(h.right) && !isRed(h.right.left)) h = moveRedRight(h); h.right = deleteMax(h.right); return balance(h); } public void delete(K 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; // 根结点为2-结点 root = delete(root, key); // 调用具体删除指定键的方法 if (!isEmpty()) root.color = BLACK; // 恢复根结点颜色为黑色 } private Node<K, V> delete(Node<K, V> h, K key) { // 在以 h 为根结点的树中删除指定键 if (key.compareTo(h.key) < 0) { // 目标在当前h的左子树中 if (!isRed(h.left) && !isRed(h.left.left)) h = moveRedLeft(h); // h.left是一个2-结点，借键膨胀 h.left = delete(h.left, key); // 递归删除 } else { // 目标可能等于h.key也可能在h的右子树中 if (isRed(h.left)) h = rotateRight(h); // 避免目标结点无右子树 (若无右子树则无法用min(h.right)来完成替换) if (key.compareTo(h.key) == 0 && (h.right == null)) return null; // h为目标结点且无右子树，说明目标结点为叶子结点，可直接删除 if (!isRed(h.right) && !isRed(h.right.left)) h = moveRedRight(h); // h.right是一个2-结点，借键膨胀 if (key.compareTo(h.key) == 0) { // h为目标结点且有右子树 Node<K, V> x = min(h.right); // 找到h的后继x h.key = x.key; // x取代h h.val = x.val; // x取代h h.right = deleteMin(h.right); // 删除x } else h.right = delete(h.right, key); // 递归删除 } return balance(h); // 回溯过程中恢复路径上结点的LLRBT性质(分解4-结点) } private Node<K, V> rotateRight(Node<K, V> h) { // 右旋 Node<K, V> x = h.left; h.left = x.right; x.right = h; x.color = h.color; h.color = RED; x.size = h.size; h.size = size(h.left) + size(h.right) + 1; return x; } private Node<K, V> rotateLeft(Node<K, V> h) { // 左旋 Node<K, V> x = h.right; h.right = x.left; x.left = h; x.color = h.color; h.color = RED; x.size = h.size; h.size = size(h.left) + size(h.right) + 1; return x; } private void flipColors(Node h) { // 反色 h.color = !h.color; h.left.color = !h.left.color; h.right.color = !h.right.color; } private Node moveRedLeft(Node h) { // 借键 flipColors(h); if (isRed(h.right.left)) { // h.left 的兄弟结点是3-结点 h.right = rotateRight(h.right); h = rotateLeft(h); flipColors(h); } return h; } private Node moveRedRight(Node h) { flipColors(h); if (isRed(h.left.left)) { h = rotateRight(h); // 从「/」形右旋即可完成借键，无需像moveRedLeft那样先从「>」形右旋为「\」形再左旋完成借键 flipColors(h); } return h; } private Node balance(Node h) { // 恢复结点 h 处的 LLRBT 性质 if (!isRed(h.left) && isRed(h.right)) h = rotateLeft(h); // 左黑右红（包含「<」形），左旋 if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h); // 「/」形，上段右旋 if (isRed(h.left) && isRed(h.right)) flipColors(h); // 「^」型，反色 h.size = size(h.left) + size(h.right) + 1; // 更新 h.size return h; } public int height() { // 返回当前树高 return height(root); } private int height(Node x) { // 返回以结点 x 为根结点的树的树高 if (x == null) return -1; return 1 + Math.max(height(x.left), height(x.right)); } public K min() { // 返回最小键 if (isEmpty()) throw new NoSuchElementException("calls min() with empty symbol table"); return min(root).key; } private Node<K, V> min(Node<K, V> x) { // 返回最小结点 if (x.left == null) return x; else return min(x.left); } public K max() { // 返回最大键 if (isEmpty()) throw new NoSuchElementException("calls max() with empty symbol table"); return max(root).key; } private Node<K, V> max(Node<K, V> x) { // 返回最大结点 if (x.right == null) return x; else return max(x.right); } public void printTree() { // 按中序遍历打印树的驱动方法 if (isEmpty()) System.out.println("Empty tree"); else printTree(root); } private void printTree(Node t) { // 中序遍历打印树 (以 t 结点为根结点的树) if (t != null) { printTree(t.left); System.out.println(t.key); printTree(t.right); } } public K floor(K key) { // 返回小于等于 key 的键 if (key == null) throw new IllegalArgumentException("argument to floor() is null"); if (isEmpty()) throw new NoSuchElementException("calls floor() with empty symbol table"); Node<K, V> x = floor(root, key); if (x == null) throw new NoSuchElementException("argument to floor() is too small"); else return x.key; } private Node<K, V> floor(Node<K, V> x, K key) { // 在以 x 为根结点的树中返回小于等于 key 的结点 if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp == 0) return x; if (cmp < 0) return floor(x.left, key); Node t = floor(x.right, key); if (t != null) return t; else return x; } public K ceiling(K key) { // 返回大于等于 key 的键 if (key == null) throw new IllegalArgumentException("argument to ceiling() is null"); if (isEmpty()) throw new NoSuchElementException("calls ceiling() with empty symbol table"); Node<K, V> x = ceiling(root, key); if (x == null) throw new NoSuchElementException("argument to ceiling() is too large"); else return x.key; } private Node<K, V> ceiling(Node<K, V> x, K key) { // 在以 x 为根结点的树中返回大于等于 key 的结点 if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp == 0) return x; if (cmp > 0) return ceiling(x.right, key); Node t = ceiling(x.left, key); if (t != null) return t; else return x; } /** * LLRBT结点类 */ private class Node<K extends Comparable<K>, V> { private K key; private V val; private Node<K, V> left, right; private boolean color; private int size; public Node(K key, V val, boolean color, int size) { this.key = key; this.val = val; this.color = color; this.size = size; } } } ``` <br /> ### 测试代码 ```java public static void main( String [ ] args ) { LeftLeaningRedBlackTree<Integer, Integer> t = new LeftLeaningRedBlackTree<>(); int NUMS = 1_000_000, GAP = 307; System.out.println( "Checking... (no bad output means success)" ); // 插入测试 for(int key = GAP; key != 0; key = (key + GAP) % NUMS) t.put( key , key + 1); System.out.println("Inserts complete"); // 删除测试 for(int key = 1; key < NUMS; key += 2) t.delete(key); System.out.println( "Removes complete" ); for(int key = 2; key < NUMS; key += 2) { if(!t.contains(key)) System.out.println( "Error: find fails for " + key ); } for(int key = 1; key < NUMS; key += 2){ if(t.contains(key)) System.out.println( "Error: Found deleted item " + key ); } NUMS = 5_000_000; for(int key = GAP; key != 0; key = (key + GAP) % NUMS) t.put( key , key + 1); System.out.println("Inserts complete"); for(int key = 1; key < NUMS; key += 2) t.delete(key); System.out.println( "Removes complete" ); for(int key = 2; key < NUMS; key += 2) { if(!t.contains(key)) System.out.println( "Error: find fails for " + key ); } for(int key = 1; key < NUMS; key += 2){ if(t.contains(key)) System.out.println( "Error: Found deleted item " + key ); } } ``` 输出如下说明测试通过。 ```java Checking... (no bad output means success) Inserts complete Removes complete Inserts complete Removes complete ``` <br /> ### 小结 - 介绍了 LLRBT 相比传统红黑树的改进之处，即总是使3-结点左斜，从而保证 LLRBT 与2-3树而非2-3-4树同构。 - 详细解释了 LLRBT 的三个性质。 - 深入分析并展示了 LLRBT 的插入结点和删除结点操作。 - 给出了较为完整的 LLRBT 类的代码。 <br /> 十大排序从入门到入赘 二分查找从入门到入睡