当你在10亿数据中只经过十几次对比就能找到目标时，不禁感叹编程的魅力！人类多么伟大！了解了黑树之后，我想和大家分享一下我的所学所想所感。红黑树是一个比较难的数据结构。要完全理解它是非常费时费力的。红黑树是如何自平衡的？什么时候需要左撇子或右撇子？插入删除破坏树的平衡后如何处理？等一系列的问题来烦我再研究。如果你在学习过程中也有我的疑惑，那么这篇文章一定会对你有所帮助。本文将帮助你全面深入的了解红黑树！本文将通过图文并茂的方式对红黑树的知识点进行讲解，不会涉及任何代码。相信我，在不了解红黑树实现原理之前，看代码的时候一定会一头雾水。明白了原理，代码就会一步步写出来，一点难度都没有。阅读本文需要具备的知识点：二叉搜索树是完美平衡的。它是一个自平衡的二叉搜索树。当执行插入、删除等可能破坏树的平衡的操作时，需要重新自处理以达到平衡状态。现在想想在你的脑海里是如何实现的？是否有太多场景需要考虑？啧啧，别着急，看完这篇文章，你会觉得其实也不过如此。好吧，我们先来看看红黑树的定义和一些基本性质。红黑树的定义和性质红黑树是一种包含红黑节点的二叉搜索树，可以自平衡。它必须满足以下属性：每个节点都是黑色或红色。根节点是黑色的。每个叶节点(Nil)都是黑色的。每个红色节点的两个孩子都必须是黑色的。从任何节点到每个叶节点的路径包含相同数量的黑色节点。从性质5可以推导出，如果一个节点有太阳黑子节点，那么该节点必须有两个子节点。图1：一棵简单的红黑树上图是一棵简单的红黑树。其中Nil是叶节点，它是黑色的。（值得提醒的是，在Java中，叶子节点是一个空节点。）红黑树并不是一个完美平衡的二叉搜索树。从图1可以看出，根节点P的左子树明显高于右子树。但是，左子树和右子树中黑色节点的层数是相等的，即从任意节点到每个叶节点的路径包含相同数量的黑色节点（性质5）。所以我们称这种红黑树的平衡为完美黑平衡。此时，为了不混淆后面的解释，我们还需要对红黑树的一些节点的名称进行约定，如图2所示：图2：节点命名约定我们将正在处理的节点称为处理（遍历）的节点称为当前节点，如图2中的D，其父亲称为父节点，其父亲的另一个子节点称为兄弟节点，父亲的父亲称为祖父节点。前面说过，红黑树是可以自平衡的。它依赖什么？有如下三种操作：左旋转：以某个节点为支点（旋转节点），其右子节点成为旋转节点的父节点，右子节点的左子节点成为右子节点旋转节点的节点，左子节点保持不变。图3右旋转：以某个节点为支点（旋转节点），其左子节点成为旋转节点的父节点，左子节点的右子节点成为旋转节点的左子节点，右孩子保持不变。图4.颜色变化：节点的颜色从红色变为黑色或从黑色变为红色。图3：左旋转图4：右旋转上面提到的旋转节点也是旋转的支点，图4和图5中的P节点。我们先忽略颜色，可以看到旋转操作不会影响旋转节点的父节点，父节点上方的结构保持不变。左旋转只影响旋转节点及其右子树的结构，将右子树的节点移动到左子树；右旋转只影响旋转节点及其左子树的结构，将左子树的节点移动到右子树。所以旋转操作是局部的。另外，可以看出旋转可以保持红黑树的平衡：当一个子树中的节点较少时，则从另一个子树中“借”一些节点；当一个子树中有更多节点时，则将一些节点“租”到??子树的另一侧。但要保持红黑树的性质，节点不能随意移动，必须改变颜色。如何改变？具体场景有不同的方法，后面会详细讲。现在，只要记住红黑树总是通过旋转和颜色变化来实现自我平衡。balabala学了这么多，相信大家对红黑树都有一定的印象，下面就来测试一下吧。思考题1：一个黑色节点是否可以同时包含一个红色子节点和一个黑色子节点？（答案见文末）接下来讲解一下红黑树的搜索预热。红黑树搜索因为红黑树是二叉平衡树，搜索不会破坏树的平衡，所以搜索和二叉平衡树的搜索没有区别：从根节点开始，设当前节点的根节点。如果当前节点为空，则返回null。如果当前节点不为空，则将当前节点的关键字与搜索关键字进行比较。如果当前节点key等于搜索key，则key为搜索目标，返回当前节点。如果当前节点key大于搜索key，则设置当前节点的左子节点为当前节点，重复步骤2。如果当前节点key小于搜索key，则设置当前节点的右子节点currentnode为当前节点，重复步骤2。如图5所示：图5：二叉树搜索流程图非常简单，但简单并不代表效率不高。由于红黑树始终保持黑与黑的完美平衡，其查找的最差时间复杂度为O(2lgN)，即整棵树刚好被红与黑隔开时。这么好的查找效率得益于红黑树的自平衡特性，而这背后的功夫则是得益于红黑树的插入操作。红黑树插入插入操作包括两部分工作：一是寻找插入的位置；另一种是插入后自平衡。查找插入的父节点非常简单，与查找操作没有太大区别：从根节点开始查找。如果根节点为空，则将该节点作为根节点插入并结束。如果根节点不为空，则将根节点作为当前节点。如果当前节点为null，则返回当前节点的父节点并结束。如果当前节点key等于查找key，则key所在节点为插入节点，更新该节点的值，结束。如果当前节点key大于搜索key，则设置当前节点的左子节点为当前节点，重复步骤4。如果当前节点key小于搜索key，则设置当前节点的右子节点currentnode为当前节点，重复步骤4。如图6：图6：红黑树插入位置搜索OK，插入位置已经找到，插入节点位置正确，但是插入节点应该是什么颜色？答案是红色的。原因很简单，当红色父节点（如果存在）为黑色节点时，红黑树的黑色平衡没有被破坏，不需要进行自平衡操作。但是如果插入节点是黑色的，那么插入位置所在子树的黑色节点总是多1，必须做自平衡。所有插入场景如图7所示：图7：红黑树插入场景嗯，插入场景很多，8种插入场景！但是场景1、2、3的处理很简单，而场景4.2和4.3正好相反。只是转身。了解一种情况可以导致另一种情况，所以总体来说并不复杂。我们将在未来查看每个场景以充分理解它。另外，根据二叉树的性质，除了场景2，所有的插入操作都在叶子节点进行。这个应该不难理解，因为在寻找插入位置的时候，我们是在寻找子节点为空的父节点。在开始各个场景的讲解之前，我们先做个约定，如图8所示：图8：插入操作节点的命名约定图8中的字母并不代表节点Key的大小。I代表插入节点，P代表插入节点的父节点，S代表插入节点的叔叔节点，PP代表插入节点的祖父母节点。好吧，下面对每个插入的场景和处理一一进行分析。场景一：最简单的场景是红黑树是一棵空树。把插入的节点作为根节点即可，但是注意根据红黑树2的性质：根节点是黑色的。您还需要将插入节点设置为黑色。解决方法：将插入的节点作为根节点，将该节点设置为黑色。场景二：插入节点的Key已经存在插入节点的Key已经存在。由于红黑树总是平衡的，红黑树在插入之前就已经平衡了，所以将插入的节点设置为待替换节点的颜色，然后更新节点的值，完成插入。解决方法：设置I为当前节点的颜色，将当前节点的值更新为插入节点的值。场景三：插入节点的父节点是黑节点。由于插入的节点是红色的，当插入的节点是黑色的时候，不会影响红黑树的平衡。无需自平衡即可直接插入。处理：直接插入。场景四：插入节点的父节点是红色节点。回想一下红黑树2的性质：根节点是黑色的。如果插入的父节点是红节点，那么父节点不可能是根节点，所以插入的节点总有祖父节点。这一点很重要，因为后续的轮换操作肯定需要祖父母节点的参与。场景4分为多个子场景，下面将进入重点部分，请各位评委注意。插入场景4.1：叔节点存在，是红节点。从红黑树的性质4可知，祖父节点一定是黑色节点，因为两个相连的红色节点不能同时存在。那么此时应该插入到子树中的红黑层的情况是：blackredred。显然最简单的处理方式就是改成：红黑红。如图9、图10所示。解决方法：将P、S设置为黑色，将PP设置为红色，将PP设置为当前插入节点。图9：插入场景4.1_1图10：插入场景4.1_2可以看到，我们将PP节点设置为红色，如果PP的父节点为黑色，则无需进一步处理。但是如果PP的父节点是红色的，根据性质4，此时红黑树是不平衡的，所以需要把PP当作一个新的插入节点，继续进行插入操作自平衡，直到是平衡的。试想一下，当PP恰好是根节点时，那么根据性质2，我们必须将PP重置为黑色，那么树的红黑结构就变成了：黑黑红。换句话说，在从根节点到叶节点的路径上添加了黑色节点。这也是红黑树中唯一增加黑色节点层数的插入场景。我们还可以总结出另外一个经验：红黑树的生长是自下而上的。这不同于普通的二叉搜索树，它是从上到下生长的。插入场景4.2：叔节点不存在或为黑节点，插入节点的父节点为祖父节点的左子节点。从插入前来看，不算场景4.1中自下而上处理的情况，叔节点要么是红色，要么是叶子节点（Nil）。因为如果叔节点是黑节点，父节点是红节点，那么叔节点所在的子树中的黑节点比父节点所在的子树多，不满足要求红黑树。Nature5.后续场景同理，不再赘述。前面说到，当需要进行轮换操作时，子树的一侧的节点肯定多了或者少了，需要租或借给另一侧。很明显是多次插入的情况，所以租用更多的节点到子树的另一边就可以了。插入场景4.2.1：插入的节点是其父节点的左子节点。处理：使P变黑，PP变红，右旋PP。图11：插入场景4.2.1从图11可以得到，左边有两个红色的节点，右边没有，所以另一边的一个刚好，因为是红色的，肯定不会破坏树的平衡。嘿，你能不能把PP调成红色，把I和P调成黑色？答案是肯定的！看过《算法：第 4 版》的同学可能知道，书上解释的是设置PP为红色，I和P为黑色。但如果把PP设置为红色，显然又会出现场景4.1的情况，需要自下而上处理，不必要的操作太多。既然自己能消化，就别麻烦爷爷奶奶了。插入场景4.2.2：插入的节点是其父节点的右孩子。这个场景显然可以转化为场景4.2.1，如图12所示，不再赘述。图12：插入场景4.2.2的处理：将P向左旋转，将P设为插入节点，得到场景4.2.1，继续场景4.2.1的处理。插入场景4.3：叔节点不存在或为黑节点，插入节点的父节点为祖父节点的右子节点。这个场景对应场景4.2，只是方向相反。不多解释，直接看图。插入场景4.3.1：插入的节点是其父节点的右孩子。图13：插入场景4.3.1处理：设P为黑，PP为红，PP为左。插入场景4.3.2：插入的节点是其父节点的右子节点。图14插入场景处理4.3.2：右旋P，将P设为插入节点，得到场景4.3.1，继续场景4.3.1的处理。好了，插入的所有场景都说完了。可能有同学会想：以上场景都是第一次插入的例子，不包括自下而上的处理，那么上述场景是否适用于自下而上的情况呢？答案是肯定的。道理很简单，只要每个子树都自平衡，最终整棵树都会平衡。那么，这里有一个练习，请拿出你的笔和纸，试着画一下（请一定要用手画，以加深印象）。Exercise1：请画出图15的插入自平衡过程。（答案见文末）图15：Exercise1红黑树删除红黑树插入已经够复杂了，删除更复杂，也是红黑树最复杂的操作。但是坚持住，胜利的曙光就在前方！红黑树的删除操作也包括两部分工作：一是寻找目标节点；另一种是删除后自我平衡。显然，可以重复使用搜索操作来找到目标节点。当目标节点不存在时，忽略该操作；当目标节点存在时，删除后必须进行自平衡处理。删除一个节点后，我们还需要找一个节点来替换被删除节点的位置，否则子树与父节点断开连接，除非被删除的节点刚好没有子节点，那么就不需要替换了.二叉树中删除一个节点并寻找替换节点有三种情况：如果被删除的节点没有子节点，则直接删除。如果被删除的节点只有一个子节点，则用该子节点替换被删除的节点。如果删除的节点有两个子节点，则将删除的节点替换为后继节点（比删除的节点大的最小节点）。补充说明，场景3的后继节点是比删除节点大的最小节点，也是删除节点右子树中最右边的节点。那么能否用前驱节点（删除节点左子树的最左边节点）代替呢？是的。但是习惯上用后继节点代替，后面的解释也用后继节点代替。另外，告诉大家一个直观的求前继后继节点的方法（不知道为什么没人提，大家知道吗？）：将二叉树的所有节点投影到X轴上，将所有的节点是从左到右排序后，所有目标节点的前后节点都是对应的前驱节点和后继节点。如图16所示：图16：x轴投影后的二叉树排序接下来说一个重要的思想：被删除的节点被替换后，不考虑节点的key值，对于树，可以认为删除的节点是替换节点！话说的很苍白，我们来看图17。图17：不看键值对，删除节点转置的思路。图17中红黑树的最终结果是删除了Q!位置的节点。这个思路很重要，大大简化了红黑树删除的场景的解释！基于此，以上三种二叉树删除场景可以相互转换，最终转换为场景一。场景二：删除的节点被其唯一的子节点替换。子节点被删除的节点替换后，可以认为删除的节点是子节点。如果子节点有两个子节点，相当于转换为场景3。总是从上到下转换，总是转换为场景1。（对于红黑树，根据性质5.1，一个节点只有一个childnodemustbeattheendofthetree)场景三：删除一个有后继节点的节点（必须没有左节点），如果后继节点有右子节点，那么相当于切换到场景二，否则切换到场景1，图18为二叉树删除节点场景关系图：图18：二叉树删除场景转换综上所述，删除操作删除的节点可以看做是替换节点的删除，替换节点总是在树的末尾。有了这个结论，我们讨论的删除红黑树的场景就少了很多，因为我们只考虑删除树尾节点的场景。同样的，我们来大致看一下删除操作的所有场景，如图19所示：图19：红黑树删除场景哈哈，是的，就算简化了，还是有9个场景！但是和插入操作一样，有左右对称的场景，只是方向变了，没有本质区别。同样，我们约定一下，如图20所示：图20：删除操作节点的命名约定图20中的字母不代表节点Key的大小。R代表替换节点，P代表替换节点的父节点，S代表替换节点的兄弟节点，SL代表兄弟节点的左子节点，SR代表兄弟节点的右子节点。灰色节点意味着它可以是红色或黑色。值得提醒的是，R是替换节点，会替换到被删除节点的位置。删除完成。一切就绪后，我们将继续进行最后也是最困难的演示。删除场景一：替换节点为红色节点。当我们将替换节点换到被删除节点的位置时，由于替换节点是红色的，所以删除不会影响红黑树的平衡，只要将替换节点的颜色设置为删除的节点。重新平衡。处理：颜色变为删除节点的颜色。删除场景二：替换节点为黑节点。当替换节点为黑色时，我们要做自平衡。我们还必须考虑替换节点是其父节点的左子节点还是右子节点，以执行不同的旋转操作以重新平衡树。删除场景2.1：替换节点是其父节点的左子节点。删除场景2.1.1：替换节点的兄弟节点是红节点。图21：删除场景2.1.1如果兄弟节点是红色节点，那么根据性质4，兄弟节点的父节点和子节点一定是黑色的，不会有其他子场景。我们按照图21进行处理，得到Delete场景2.1.2.3（后续解释，这里记住此时R还是一个替代节点，它的新兄弟节点SL和它的子节点都是黑色的）。处理：S置黑，P置红，P向左转，得到场景2.1.2.3，继续场景2.1.2.3。删除场景2.1.2：替换节点的兄弟节点为黑节点。当兄弟节点为黑色时，无法确定其父节点和子节点的具体颜色（如果不考虑自下而上的情况，子节点不为红色，则为叶子节点Nil，Nil节点为黑色节点），此时就要考虑多种子场景。删除场景2.1.2.1：替换节点的兄弟节点的右子节点为红色节点，左子节点为任意颜色。图22：在场景2.1.2.1中删除左子树中待删除的黑色节点。很明显，左子树中的黑节点少了1，但是右子树中多了一个红节点，那我们直接去右子树“借一个红节点来补充黑节点就好了。这时候，一定进行旋转处理，如图22所示。处理：将S的颜色设置为P的颜色，将P设置为黑色，将SR设置为黑色，将P向左旋转。为什么平衡图不满足红黑树的本质是什么？上面说到R要被替换，它也参与了树的自平衡，平衡后会替换到被删除节点的位置，所以R可以最后视为删除节点。的。另外，图2.1.2.1考虑了第一次替换和自下而上的处理。如果只考虑第一次替换，根据红黑树的性质，SL必须为red或者Nil，所以最终的结果树是balancedof。如果是bottom-up处理的情况，同理，每个子树remains处于平衡状态，最终整棵树一定是平衡的。后续场景同上，不再过多解释。删除场景2.1.2.2：被替换节点的兄弟节点右子节点为黑节点，左子节点为红节点。兄弟节点所在的子树有一个红色节点，我们总可以从兄弟子树上借用一个红色节点，显然这个场景可以转化为场景2.1.2.1。如图23所示：图23：删除场景2.1.2.2处理：S置红色，SL置黑色，S向右旋转，得到场景2.1.2.1，继续场景2.1.2.1。删除场景2.1.2.3：替换节点的兄弟节点的子节点都是黑节点。嗯，这次兄弟子树没有红色节点可以“借”了。兄弟帮不上忙，还是问父母吧。在这种情况下，我们将兄弟节点设置为红色，然后将父节点作为替代节点，自下而上进行处理，去父节点的兄弟节点“借”。但是为什么需要将兄弟节点设置为红色呢？很明显，就是保证P所在子树中的平衡（R即将被删除，黑节点少一个，子树需要少一个），后续的平衡工作交给父We考虑到，还是那句话，当每棵子树都平衡的时候，最后整棵树总是平衡的。图24：场景2.1.2.3处理：设置S为红色，P作为新的替换节点，重新删除节点场景处理。删除场景2.2：替换节点是其父节点的右孩子。嗯，右边的操作也是反方向的。我不需要解释太多。相信理解了删除场景2.1，肯定能理解2.2。删除场景2.2.1：替换节点的兄弟节点是红节点。图25：删除场景2.2.1处理：设置S为黑色，P为红色，右旋P得到场景2.2.2.3，进行场景2.2.2.3处理。删除场景2.2.2：替换节点的兄弟节点为黑节点。删除场景2.2.2.1：替换节点的兄弟节点的左子节点为红色节点，右子节点为任意颜色。图26：删除场景2.2.2.1处理：将S的颜色设置为P的颜色，将P设置为黑色，将SL设置为黑色，将P向右旋转。删除场景2.2.2.2：替换节点的兄弟节点的左子节点为黑节点，右子节点为红节点。图27：删除场景2.2.2.2处理：设置S为红色，SR为黑色，S向左旋转，得到场景2.2.2.1，继续场景2.2.2.1处理。删除场景2.2.2.3：替换节点的兄弟节点的子节点都是黑节点。图28：删除场景2.2.2.3处理：设置S为红色，P作为新的替换节点，重新删除节点场景处理。综上所述，删除红黑树后的自平衡处理可以概括为：能处理的自己消化（场景1），处理不了的请兄弟帮忙（场景除外）1、场景2.1.2.3和场景2.2.2.3)。如果帮不上忙，可以通过父母找远房亲戚（场景2.1.2.3和2.2.2.3）。连兄弟姐妹都帮不了，那就去找远房亲戚吧。这样记忆应该会比较好记吧~最后做个练习加深理解（不熟悉的同学一定要手写）。习题2：请画出图29的删除自平衡过程，习题2写在后面。相信看完这篇文章，阅读Java、HashMap和TreeMap的源码绝对不难！最后，让我们看看思考题和练习题的答案。问题一：黑色节点是否可以同时包含红色子节点和黑色子节点？答：是的。下图节点F：习题1：请画出图15的插入自平衡过程，答案如下图所示：习题2：请画出图29的删除自平衡过程，答案如下如下：
