红黑树的实现原理和应用场景_红黑树的性质

一篇搞定红黑树：从原理到应用实战 　　前言：红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由鲁道夫·贝尔发明的，他称之为”对称二叉B树”，它现代的名字是在 Leo J.Guibas 和Robert Sedgewick于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(logn)时间内做查找，插入和删除，这里的n是树中素的数目。 　　精品文章推荐：C/C++发展方向（强烈推荐！！）Linux C/C++开发上线项目（后端、音视频、存储、QT）2023年Linux的知识技术合集（基础入门到高级进阶）2023年C/C++高性能技术知识大整理（进阶到大神级别）2023年音视频开发知识技术合集（基础入门到高级进阶） 　　一、红黑树的概念 　　红黑树，是一种二叉搜索树，但在每个节点上增加一个存储位表示节点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

　　红黑树的特性：(1)每个节点要么是黑色，要么是红色。(2)根节点为黑色(3)每个叶子节点(NIL)均为黑色。[注：这里的叶子节点指的是空(NIL或者NULL)的叶子节点！！！](4)如果一个节点是红色的，那么它的子节点必须是黑色的。(5)从一个节点到该节点的子孙节点NIL的所有路径上包含相同数目的黑节点。[注：这里指到叶子节点的路径] 　　特别说明：①特性(3)中的叶子节点，指的是只为空(NIL或NULL)的节点。②特性(5)，确保没有一条路径会比其他路径长出两倍。因为，红黑树是相对接近平衡二叉树。 　　所以红黑树中最短路径是全部都由黑色节点组成的路径，最长的路径是由红黑节点交替组成的路径。假设全部的黑色节点有N个，那么最短路径长度为logN ，整棵树的节点数量在N ~ 2N之间，所以最长路径长度为2logN 。 　　这些约束强制了红黑树的关键性质：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。 　　二、红黑树的操作 　　2.1红黑树的定义 　　红黑树节点的结构体中多了一个表示颜色的枚举。需要注意的是，在红黑树节点的拷贝构造中，对于颜色的默认值给的是RED。

　　这是因为如果新插入的节点是黑色的，那么一定会违反红黑树的性质4，即导致每条路径上的黑色节点不一致。而如果插入的节点是红色的，则不一定会使红黑树违反性质3，只有在新插入的红色节点的父亲也是红色节点时，才需要进行改动。 　　2.2红黑树的插入 　　红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：按照二叉搜索的树规则插入新节点检测新节点插入后，红黑树的性质是否造到破坏 　　因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整。但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论。约定：cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点 　　1）cur为红，p为红，g为黑，u存在且为红

　　cur和p均为红，违反了性质三。解决方式：将p、u改为黑，g改为红，然后把g当成cur，继续向上调整。 　　实现代码： 　　2）cur为红，p为红，g为黑，u不存在/u存在且为黑

　　情况2一定是由2.1的情况变换过来，并继续向上更新的，否则插入前的状态就不符合红黑树。其演变过程：

　　此时 c 子树一定包含一个黑节点，d、e子树只能是一个红节点。解决方式：p为g的左孩子，cur为p的左孩子，则进行右单旋转p为g的右孩子，cur为p的右孩子，则进行左单旋转p、g变色–p变黑，g变红 　　3）cur为红，p为红，g为黑，u不存在/u存在且为黑（变种）

　　解决方法：p为g的左孩子，cur为p的右孩子，则针对p做左单旋转p为g的右孩子，cur为p的左孩子，则针对p做右单旋转 　　此时，情况三变为了情况二，再使用 2.2 的方法就可以。 　　实现代码： 　　2.3红黑树的验证 　　红黑树的检测分为两步：检测其是否满足二叉搜索树(中序遍历是否为有序序列)检测其是否满足红黑树的性质 　　(1)检测一 编写测试代码：

　　观察到该树满足二叉搜索树。 　　(2)检测二根据红黑树的性质编写代码： 　　

　　观察到满足红黑树的性质。 　　2.4红黑树的性能 　　红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是 O(log N) ，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。 　　附完整代码： 　　三、红黑树的应用 　　红黑树的应用十分广泛，以至于我们多多少少了解一些总是有好处的。红黑树可以用来储存有序数据[1]，时间复杂度是O(logn)，效率非常高。 　　例如，Java集合中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树实现的。 　　3.1红黑树左旋和右旋 　　红黑树虽然特殊，但它也是一种树类型的数据结构，少不了增删查这类的操作。但在介绍添加、删除之前，我们需要先介绍一下旋转操作，这主要是出于对红黑树特性的考虑。毕竟在删除或者添加节点之后，很有可能会破坏原有的红黑树结构特性，这时候旋转操作就必不可少了，这和AVL树有一点点相像。总而言之，旋转的目的是让树保持红黑树的特性。 　　旋转包含两种：左旋和右旋。下面会分别进行介绍。 　　(1)左旋

　　对节点F进行左旋，意味着将节点F变为其右孩子节点R的左孩子节点，并将节点R的左子树变为节点F的右子树。可参考下图进行理解(此处暂时忽略节点的颜色问题)：

　　对左旋稍微有点概念之后，可以结合伪代码进行理解“如何对节点x进行左旋”。 　　理解左旋之后，不妨进行一个小测验吧，如下图所示是红黑树操作过程的某个状态，现在我们要对节点0040进行左旋，自己动手尝试一下吧，答案点这里哟。

　　(2)右旋

　　对节点F进行右旋，意味着将节点F变为其左孩子节点L的右孩子节点，并将节点L的右子树变为节点F的左子树。 　　对右旋稍微有点概念之后，可以结合伪代码进行理解“如何对节点x进行右旋”。 　　理解右旋之后，同样进行一个小测验，如下图所示是红黑树操作过程的某个状态，现在我们要对节点0040进行左旋，自己动手尝试一下吧，答案点这里哟。

　　旋转总结： 　　⒈左旋和右旋是相对应的两个概念(比较一下就会发现)，理解了一个，另一个自然信手拈来。

　　⒉左旋示例图(以x为节点进行左旋)： 　　对x进行左旋，意味着将“x的右孩子”设为“x的父亲节点”；即，将 x变成了一个左节点(x成了为z的左孩子)。因此，左旋中的“左”，意味着“被旋转的节点将变成一个左节点”。 　　⒊右旋示例图(以x为节点进行右旋)： 　　对x进行右旋，意味着将“x的左孩子”设为“x的父亲节点”；即，将 x变成了一个右节点(x成了为z的右孩子)。因此，右旋中的“右”，意味着“被旋转的节点将变成一个右节点”。 　　3.2红黑树添加 　　将一个节点插入到红黑树中，需要执行哪些步骤呢？ ⑴首先，红黑树是一棵二叉查找树，节点插入规则是插入的数若小于当前节点，则往左子树深入，否则往右子树深入；⑵然后，将插入的节点着色为红色；⑶最后，通过旋转和重新着色操作来修正该树的红黑树特性。详细步骤如下： 　　第一步：将节点按照二叉查找树的插入规则进行节点插入。 　　红黑树本身就是一棵二叉查找树，将节点插入后，该树仍然是一颗二叉查找树。也就意味着，树的键值仍然是有序的。此外，无论是左旋还是右旋，若旋转之前这棵树是二叉查找树，旋转之后它一定还是二叉查找树。这也就意味着，任何的旋转和重新着色操作，都不会改变它仍然是一棵二叉查找树的事实。 　　好了，那接下来，我们就想方设法通过旋转以及重新着色，使这棵树重新成为红黑树即可。 　　第二步：将插入节点着色为红色。 　　为什么着色成红色，而不是黑色呢？在回答之前，我们需要重新温习一下红黑树的特性：(1)每个节点要么是黑色，要么是红色。(2)根节点为黑色(3)每个叶子节点(NIL)均为黑色。[注：这里的叶子节点指的是空(NIL或者NULL)的叶子节点！！！](4)如果一个节点是红色的，那么它的子节点必须是黑色的。(5)从一个节点到该节点的子孙节点NIL的所有路径上包含相同数目的黑节点。[注：这里指到叶子节点的路径] 　　将插入的节点着色为红色，不会违背“特性⑸”。少违背一条特性，就意味着我们需要处理的情况越少。接下来，只要努力让这棵树满足其它性质即可。都满足了的话，它就又是一棵红黑树了。 　　第三步：通过旋转和重新着色操作来修正该树的红黑树特性。 　　第二步中，将插入节点着色为“红色”之后，不会违背“特性⑸”。那它到底会违背哪些特性呢？对于“特性⑴”，显然不会违背，因为我们已经将它涂成红色了。对于“特性⑵”，显然也不会违背。在第一步中，我们是按二叉查找树的规则执行的插入操作，而根据二叉查找树的特点，插入操作不会改变根节点。所以，根节点仍然是黑色。对于“特性⑶”，显然不会违背。因为这里的叶子节点指的是空叶子节点，插入非空节点并不会对它们造成影响。对于“特性⑷”，是有可能违背的。这样分析下来，我们只要满足了“特性⑷”就可以将树重新构造成红黑树了。接下来我们一起来看一下伪代码，随后会对各种情况进行分析。 　　添加操作的伪代码： 　　结合伪代码及注释，先理解RB-INSERT节点插入过程。之后，我们对节点重新着色和旋转操作进行说明。 　　添加修正操作的伪代码 　　根据被插入节点的父节点的情况，可以将“节点z插入红黑树中并着色为红色”划分为三种情况来处理。 　　第一种情况说明: 被插入节点是根节点。 　　处理方法: 直接把该节点涂为黑色。 　　第二种情况说明: 被插入节点的父节点是黑色。 　　处理方法: 无需处理，节点插入后不影响红黑树特性。 　　第三种情况说明: 被插入节点的父节点是红色。 　　处理方法: 该情况与红黑树“特性⑸”冲突。该情况下，被插入节点必定存在非空祖父节点(原因: 被插入节点的父节点是红色,所以必定不是根节点,那么必定有一个黑色的祖父节点)。进一步说明，被插入节点也一定存在叔叔节点(即便叔叔节点是空叶子节点，我们也认为存在，因为空叶子节点本身就是黑色)。理解这点之后，我们又可以根据叔叔节点的情况进一步划分出三种情况(Case)。

　　注:此表仅考虑被插入节点的父节点为祖父节点的左孩子的情况，另一种情况与之对称。 　　以上三种情况处理问题的核心思想都是:将红色节点移到根节点；然后将根节点设为黑色。下面将进行详细介绍。 　　(Case 1)叔叔节点是红色 　　1.现象说明 　　当前节点的父节点是红色，且当前节点的祖父节点的另一个子节点(叔叔节点)也是红色 　　2.处理策略⑴将“父节点”设为黑色⑵将“叔叔节点”设为黑色⑶将“祖父节点”设为红色⑷将“祖父节点”设为“当前节点”(红色节点)；即，之后继续对“当前节点”进行操作 　　下面分析一下为什么要这样处理(建议结合示意图进行理解)： 　　“当前节点”和“父节点”都是红色，违背“特性⑷”。所以，将“父节点”染成“黑色”这点毋庸置疑。 　　但是，将“父节点”由“红色”染成“黑色”之后，违背了“特性⑸”：因为，包含“父节点”的这条分支的黑色节点总数增加了1。 解决这个问题的办法是：将“祖父节点”由“黑色”变成红色，同时，将“叔叔节点”由“红色”变成“黑色”。关于这里，说明几点：第一，为什么“祖父节点”之前是黑色？这个应该很容易想明白，因为在变换操作之前，该树是红黑树，“父节点”是红色，那么“祖父节点”一定是黑色； 第二，为什么将“祖父节点”由“黑色”变成“红色”，同时，将“叔叔节点”由“红色”变成“黑色”？因为这样能解决“包含‘父节点’的分支的黑色节点总数增加了1”的问题。这个道理也很简单。“包含‘父节点’的分支的黑色节点总数增加了1” 同时也意味着 “包含‘祖父节点’的分支的黑色节点的总数增加了1”，既然这样，我们通过将“祖父节点”由“黑色”变成“红色”以解决“包含‘祖父节点’的分支的黑色节点的总数增加了1”的问题； 但是，这样处理之后又会引起另一个问题“包含‘叔叔’节点的分支的黑色节点的总数减少了1”，现在我们已知“叔叔节点”是“红色”，将“叔叔节点”设为“黑色”就能解决这个问题。 所以，将“祖父节点”由“黑色”变成“红色”，同时，将“叔叔节点”由“红色”变成“黑色”，就解决了该问题。 　　按照上面的步骤处理之后：当前节点、父节点、叔叔节点之间都不会违背红黑树特性，但祖父节点却不一定。若此时，祖父节点是根节点，直接将祖父节点设为“黑色”，那就完全解决这个问题了；若祖父节点不是根节点，那我们需要将“祖父节点”设为“新的当前节点”，接着对“新的当前节点”进行分析。 　　3.示意图

　　过程模拟 　　第一步：

　　第二步：修复操作(当前节点是20，用cur表示)

　　第三步：继续对新的当前节点进行修复操作 　　这里因为到达了根节点，所以停止了修复，如果当前节点不是根节点，或者当前节点的父节点不是黑色节点，那么就需要继续向上修复。 　　第四步：继续插入新节点

　　第五步：插入新节点–再接再厉

　　这时候面临的是叔叔节点不是红色，不再满足case1的情况，继续分析。 　　(Case 2)叔叔节点是黑色，且当前节点是右孩子 　　1.现象说明 　　当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子 　　2.处理策略⑴将“父节点”作为“新的当前节点”⑵以“新的当前节点”为支点进行左旋 　　下面分析一下为什么要这样处理(建议结合示意图进行理解)： 　　首先，将“父节点”作为“新的当前节点”；接着，以“新的当前节点”为支点进行左旋。 为了便于理解，我们先说明第⑵步，再说明第⑴步；为了便于说明，我们设置“父节点”的代号为F(Father)，“当前节点”的代号为S(Son)。 　　为什么要“以F为支点进行左旋”呢？其实这里是为case 3这种情况做的准备(可以结合case 3一起理解 or 先理解case 3的策略)，我们修复红黑树秉持着能少处理就少处理的原则，但是此处单纯依靠重新染色操作无法避免与“特性⑷”和“特性⑸”相违背，迫于无奈只能采取变动稍大的旋转操作。而此处的左旋是和case 3的右旋相对应的，假设我们没有进行左旋，而是对祖父节点直接进行右旋，那么只是将“违背特性⑷”的问题换了一个分支，但问题依然存在。如下图，当前节点是60，父节点是40，叔叔节点是90，祖父节点是80，若我们不对父亲节点左旋，而是直接采取case 3的操作，就会发现，问题并没有解决，只是把皮球抛给了对方。综上，这也就是这里为什么要“以F为支点进行左旋”的原因。

　　按照上面的步骤(以F为支点进行左旋)处理之后：若S变成了根节点，那么直接将其设为“黑色”，就完全解决问题了；若S不是根节点，那我们需要执行步骤⑴，即“将F设为‘新的当前节点’”。那为什么不继续以S为新的当前节点继续处理，而需要以F为新的当前节点来进行处理呢？这是因为“左旋”之后，F变成了S的“子节点”，即S变成了F的父节点；而我们处理问题的时候，需要从下至上(由叶到根)方向进行处理；也就是说，必须先解决“孩子”的问题，再解决“父亲”的问题；所以，我们执行步骤⑴：将“父节点”作为“新的当前节点”。 　　3.示意图 　　动图演示

　　过程模拟

　　该过程提前剧透了case 3的处理策略，可以先看看。 　　(Case 3)叔叔节点是黑色，且当前节点是左孩子 　　1.现象说明 　　当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子 　　2.处理策略⑴将“父节点”设为黑色⑵将“祖父节点”设为红色⑶以“祖父节点”为支点进行右旋 　　下面分析一下为什么要这样处理(建议结合示意图进行理解)： 　　为了便于说明，我们设置“当前节点”为S(Son)，“叔叔节点”为U(Uncle)，“父节点”为F(Father)，祖父节点为G(Grand-Father)。 　　目前，所有分支的黑色节点个数是一致的，现在出现两个连续红色节点S和F，那么简单点，将其中一个改成黑色节点，将父节点F变成黑色，那么以父节点F的局部子树是平衡的，但是 父节点的兄弟节点U可能是不平衡的，因为父节点F路径多了一个黑色，那么这个黑色节点放在哪里？ 只能往根节点移，将祖父G变红，这样祖父G的另一个分支将少一个黑色节点，再把祖父G右旋，这样父节点F代替了原来的祖父G，也就相当于把多的黑色节点，放在了公共的祖父位置上。 　　示意图

　　过程模拟

　　至此，红黑树的添加操作终于完成了。 　　3.3红黑树删除 　　将红黑树内的某一个节点删除，需要执行哪些步骤呢？ ⑴首先，红黑树是一棵二叉查找树，按照二叉查找树的节点删除规则删除该节点；⑵然后，通过旋转和重新着色操作来修正该树的红黑树特性。详细步骤如下： 　　第一步：将节点按照二叉查找树的删除规则进行节点删除。 　　这和“删除常规二叉查找树中的节点方法是一样的”。分3种情况： 　　Ⅰ.被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就OK了。 　　Ⅱ.被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。 　　Ⅲ.被删除节点有两个儿子。那么，先找出它的[前驱节点/后继节点]；然后把“它的[前驱节点/后继节点]的内容”复制给“该节点”；之后，删除“它的[前驱节点/后继节点]”。在这里，[前驱节点/后继节点]相当于替身，在将[前驱节点/后继节点]的内容复制给”被删除节点”之后，再将[前驱节点/后继节点]删除。这样就巧妙的将问题转换为“删除[前驱节点/后继节点]”的情况了，下面就考虑[前驱节点/后继节点]。在”被删除节点”有两个非空子节点的情况下，它的[前驱节点/后继节点]不可能是双子非空。既然”[前驱节点/后继节点]”不可能双子都非空，就意味着”该节点的[前驱节点/后继节点]”要么没有儿子，要么只有一个儿子。若没有儿子，则按”情况Ⅰ”进行处理；若只有一个儿子，则按”情况Ⅱ”进行处理。 　　第二步：通过旋转和重新着色操作来修正该树的红黑树特性。 　　因为”第一步”中删除节点之后，可能会违背红黑树的特性。所以需要通过”旋转和重新着色”来修正该树，使之重新成为一棵红黑树。 　　接下来我们一起来看一下伪代码，随后会对各种情况进行分析。 　　删除操作的伪代码 　　结合伪代码及注释，先理解RB-DELETE节点删除过程。之后，我们对节点重新着色和旋转操作进行说明。 　　删除修正操作的伪代码 　　在对删除函数进行分析之前，我们再来温习一遍红黑树的几个特性：(1)每个节点要么是黑色，要么是红色。(2)根节点为黑色(3)每个叶子节点(NIL)均为黑色。[注：这里的叶子节点指的是空(NIL或者NULL)的叶子节点！！！](4)如果一个节点是红色的，那么它的子节点必须是黑色的。(5)从一个节点到该节点的子孙节点NIL的所有路径上包含相同数目的黑节点。[注：这里指到叶子节点的路径] 　　前面我们将”删除红黑树中的某个节点”大致分为两步，在第一步中”按照二叉查找树的节点删除规则删除该节点”后，可能违反”特性⑵、⑷、⑸”三个特性。第二步需要解决上面的三个问题，进而保持红黑树的全部特性。 　　通过RB-DELETE算法，我们知道：删除节点y之后，x占据了原来节点y的位置。那么，我们面临几种形态： 　　a)节点y为红色；这时我们无需做任何处理，因为并未违反任何一条特性 　　b)节点y为黑色，x为红色；此时，在删除节点y之后，我们违背了特性⑸，y所在的子树少了一个黑色节点，那我们只需要将x染为黑色补上缺掉的这个黑色节点即可 　　c)节点y为黑色，x为黑色，但x是根节点；这意味着原来的y就是根节点，这样相当于是所有路径共同减少一个黑色节点，依旧满足红黑树特性，故无需处理 　　d)节点y为黑色，x为黑色，x不是根节点；这种形态还需要细分四种子情况进行分析：

　　(Case 1)兄弟节点是红色 　　1.现象说明 　　当前节点x是黑色，当前节点的兄弟节点是红色(此时x的父节点和x的兄弟节点的子节点都是黑色) 　　2.处理策略⑴将“兄弟节点”设为黑色⑵将“父亲节点”设为红色⑶以“父亲节点”为支点进行左旋⑷左旋后，重新设置x的“兄弟节点” 　　面分析一下为什么要这样处理(建议结合示意图进行理解)： 　　这么做的目的是将“Case 1”转换为“Case 2”、“Case 3”或“Case 4”，从而进行进一步的处理。对x的父节点进行左旋；左旋后，为了保持红黑树特性，就需要在左旋前“将x的兄弟节点设为黑色”，同时“将x的父节点设为红色”；左旋后，由于x的兄弟节点发生了变化，需要更新x的兄弟节点，从而进行后续处理。 　　或者可以这么理解，由于兄弟节点是红色节点的时候，无处借调黑节点，所以需要将兄弟节点提升到父节点，由于兄弟节点是红色的，那么兄弟节点的子节点必定是黑色的，旋转之后就可以从它的子节点借调了。 　　3.示意图

　　4.过程模拟

　　上图删除节点42之后，若是看着不习惯，可以把空叶子节点画出来便于理解。 　　(Case 2)兄弟节点是黑色，兄弟节点的两个孩子节点都是黑色 　　1.现象说明 　　当前节点x是黑色，当前节点的兄弟节点也是黑色，且兄弟节点的两个孩子节点也都是黑色 　　2.处理策略⑴将“兄弟节点”设为红色⑵将“父节点”作为“新的当前节点”” 　　下面分析一下为什么要这样处理(建议结合示意图进行理解)： 　　之所以要将兄弟节点变红，是因为如果把兄弟节点直接借调过来，两边的黑色节点数依旧不一致，这样的情况下只能是将兄弟节点也变成红色来达到颜色的平衡。当将兄弟节点也变红之后，虽达到了局部的平衡，但是对于父节点来说，如果父节点是黑色，不符合特性⑸；若父节点是红色，则不符合特性⑷。这样就需要回溯到父节点，接着进行修复操作。 　　3.示意图 　　类型一：父节点是红色

　　类型二：父节点是黑色

　　4.过程模拟

　　兄弟节点45的左右孩子为空，可以看做是黑色的（特性⑶）。 　　(Case 3)兄弟节点是黑色，兄弟节点的右孩子是黑色，左孩子是红色 　　1.现象说明 　　当前节点x是黑色，当前节点的兄弟节点也是黑色，但兄弟节点的左孩子是红色，右孩子是黑色 　　2.处理策略⑴将“兄弟节点的左孩子”设为黑色⑵将“兄弟节点”设为红色⑶以“兄弟节点”为支点进行右旋⑷右旋后，重新设置x的“兄弟节点” 　　下面分析一下为什么要这样处理(建议结合示意图进行理解)： 　　我们处理“Case 3”的目的是为了将“Case 3”进行转换，转换成“Case 4”,从而进行进一步的处理。考虑到当前分支缺少一个黑色节点，势必要从兄弟节点借调黑色，但借走黑色之后，兄弟节点的右子树会缺少一个黑色节点，如果兄弟节点的右孩子是红色还好说，可以直接染成黑色，但如果本身就是黑色，这样就无法补充缺少的黑色，故先通过case 3转换成case 4，使兄弟节点的右孩子变红。 　　3.示意图

　　当前节点0040（黑色），兄弟节点0100（黑色），兄弟节点的左孩子0080（红色），兄弟节点的右孩子0120（黑色）。 　　(Case 4)兄弟节点是黑色，兄弟节点的右孩子是红色，左孩子颜色任意 　　1.现象说明 　　当前节点x是黑色，当前节点的兄弟节点也是黑色，兄弟节点的右孩子是红色，兄弟节点的左孩子颜色任意 　　2.处理策略⑴将“父亲节点”的颜色赋值给“兄弟节点”⑵将“父亲节点”设为黑色⑶将“兄弟节点的右孩子”设为黑色⑷以“父节点”为支点进行左旋⑸设置“x”为根节点 　　下面分析一下为什么要这样处理(建议结合示意图进行理解)： 　　为了便于说明，我们设置“当前节点”为S(Son)，“兄弟节点”为B(Brother)，“兄弟节点的左孩子”为BLS(Brother’s Left Son)，“兄弟节点的右孩子”为BRS(Brother’s Right Son)，“父节点”为F(Father)。 　　我们要对F进行左旋。但在左旋前，我们需要调换F和B的颜色，并设置BRS为黑色。为什么需要这样处理呢？我们可以这样理解，左旋的实际意义是将兄弟一路的黑色节点调到当前节点一路，但还不能影响兄弟一路本身的黑色节点数。 　　策略⑴⑵⑷的实际效果是将右路（兄弟一路）拿取一个黑色节点到左路（当前节点一路），此时，左路黑色节点数恢复原样，但右路因为拿走了一个黑色节点导致黑色节点数-1，故策略⑶就是右路恢复黑色节点数的操作。 　　3.示意图

　　当前节点0040（黑色），兄弟节点0080（黑色），兄弟节点的左孩子0070（黑色），兄弟节点的右孩子0100（红色）。 　　四、红黑树的C++实现 　　下面附上C++代码及测试代码： 　　4.1红黑树的实现文件(RBTree.h) 　　4.2红黑树的测试文件(main.cpp) 　　4.3C++程序运行结果 　　红黑树是一种特殊的二叉查找树，故而数据在其内部是有序的。 ↩︎左旋小测验答案:

　　3.右旋小测验答案: