也是一个非常难的知识点。字节跳动面试官最喜欢问这个问题。很多人认为这个知识点太难了，不想花太多精力去理解。有人认为这种数据结构在日常开发中很少用到，没有必要去掌握。这里我对以上两个观点做一些修正：第一，红黑树的数据结构确实复杂，但是还没有到完全看不懂的地步。网上的大部分博客都不能清晰完整的描述红黑树的整个系统，也没有详细介绍红黑平衡调整的细节，给学习带来了很大的困难。其次，比如Java中HashMap的底层实现，在JDK1.8中为了解决hash冲突过多导致的长链表，会将链表转为红黑树；Linux底层CFS进程调度算法中，vruntime采用红黑方式存储；采用多路复用技术的epoll核心结构也是红黑树+双向链表。我们不会直接手写一个可用的红黑树，但是了解红黑树的结构有助于我们理解一些底层的实现。同时，红黑树也是树结构的高度综合应用，涉及到多叉树、树平衡调整、节点轮换等，这些都是对数据结构基本功的最好体验。其实面试官问这个问题的时候，如果不参考答案，很有可能无法给出明确的定义和操作。但是他希望从这道题开始，看你对一个数据结构的理解，考察你知识的广度和深度。能不能给出一个完整的定义，能不能介绍一下你对红黑树的理解，能不能在给定的场景中通过旋转、着色等操作调整一棵红黑树以满足定义...。这些是面试官希望从你的回答中得到的信息。问了身边大厂的面试官朋友，和我的说法没有太大区别。看完本文，你将能够从红黑树2-3-4树的概念模型出发，理解红黑树的5种定义背后的逻辑。也可以深入理解红黑节点颜色背后的含义，对插入和删除带来的动态变化有一定的了解，而不是死记硬背某个场景下的调平操作（比如：删除一个节点，当节点的叔叔节点为红色，且叔叔节点的左右子节点为黑色的情况下，我们应该...)。可以掌握节点旋转的具体操作，理解着色的目的。最后，如果你够认真，图中有清晰的插入删除步骤，你真的可以把红黑树变成自己的知识。先说平衡树。做开发的朋友一定知道接口：定义接口，给出实现。一个接口可以有很多不同的实现，但是这些实现都会满足接口中的声明。比如我们把手机定义为一种可以用来通讯的工具。作为其实现，三星、苹果、华为都推出了各种产品。红黑树的本质其实是概念模型的一种实现：2-3-4树，所以我们先关注2-3-4树。2-3-4树是阶数为4的B树，B-tree，全称BalanceTree，平衡树。该结构主要用于搜索。关于B-tree（平衡多路搜索树）的定义，网上已经有很多介绍，这里不再赘述。它最重要的特点是平衡性，它可以让我们在最坏情况下保持O(LogN)的时间复杂度来实现搜索（不平衡的搜索树可能会退化为单向链表，时间复杂度会达到O（N））。这里需要提醒大家，平衡的定义是指空链接到根节点的距离相等，这里一定要仔细理解。（也就是说，非叶子节点不会有空链接）由于2-3-4树是一棵阶数为4的B树，它会有以下节点：2个节点，3个节点，4个节点，2个节点存储了一个key[X]，两个指针，分别指向小于X的子节点和大于X的子节点；3个节点存储在两个key[X,Y]，三个指针中，分别指向小于X的子节点、X~Y之间的子节点和大于Y的子节点；可以推导出4个节点等等。节点介绍2-3-4树到红黑树的转换红黑树是概念模型2-3-4树的一种实现，因为不同节点之间的直接转换会造成很大的开销，所以选择以下Based在二叉树上，在二叉树的属性中加入颜色属性，代表2-3-4树中的不同节点。2-3-4树中的2个节点对应红黑树中的黑色节点，2-3-4树中的非2节点以红色节点+黑色节点的形式存在。红色节点的含义是，它和黑色节点一样父节点的组合表示2-3-4树中的3和4节点。（这里，可以理解为红色节点或者红色链接，看个人喜好。很多书上会说黑色节点指向的红色链接，链接指向的节点颜色为红色。）先看2-3-4Node从树到红黑树的转换。2个节点直接转化为黑色节点；3个节点在这里可以有两种表现形式，左倾红色节点或者右倾红色节点。并且4个节点被迫变身为黑色父亲，左右各有两个红色儿子。B-树到红黑树的变换是本文研究的主体是2-3树（后面会给出原因），是2-3树-left中的一种特殊变换-倾斜的红黑树。顾名思义，左倾红黑树限制，如果树中出现红色节点，那么这个节点一定是左儿子。下面是它的变换过程：从B树到红黑树的变换可能还不够明显，看不到单个节点的变换。我做了一个红黑树到2-3树的示意图，很清楚的描述了他们之间的关系。只要将左倾红黑树中的红色节点顺时针旋转45°，使其与黑色父节点平行，然后将它们作为一个整体来看，你会发现这不是一棵2-3树吗？B树从红黑树的改造到这里，想必大家已经明白了，红黑树其实就是概念模型2-3树（或2-3-4树）的一种实现。在算法介绍中，红黑树是基于2-3-4树实现的，其中4个节点需要平衡（即4个节点必须由左边的一个黑色父亲和两个红色儿子代表和对，红色的儿子不能出现在同一边）。算法4给出的红黑树是基于2-3树实现的，这种实现的红黑树很特殊，它要求概念模型中的3个节点必须用左倾的红色节点表示在红黑树中。这种限制可以大大降低红黑树调整过程的复杂度，我们将在后面的内容中体验。算法介绍和算法4中的红黑树我看了好几遍，最后选择了算法4中的红黑树作为演示的主体。首先，算法4中的红黑树是基于2-3树的概念模型，没有考虑2-3-4树中复杂的4节点分裂；第二，算法4中的红黑树是左倾红黑树，进一步减少了第三，算法介绍中对红黑树删除场景的描述不够具体，很多关键环节描述为“经过一定的旋转和颜色变化”，不利于新手的学习。（我花了很长时间才还原出具体过程）。考虑到部分读者有足够的精力去研究以2-3-4树为概念模型的红黑树，在介绍2-3树的同时，也会带来2-3-4的基础知识树帮助他们了解更多。读者可以在算法导论中了解红黑树。（所以如果没有必要，直接看2-3树部分）。在了解红黑树的插入和删除操作之前，我们需要先了解2-3树的插入和删除操作，这样才能理解红黑树中染色和旋转背后的含义。让我们看看2-3棵树的插入。我们的插入操作需要遵循一个原则：先尝试把这个元素放在已有的节点中，如果要存储的节点是2个节点，那么插入后就变成3个节点，如果要存储的节点是3个节点，那么插入后会变成4个节点（临时的）。然后，我们拆分可能产生的临时4节点，让临时4节点消失。如果需要向2-3-4树中的4个节点插入元素，会造成如下图所示的分裂过程。待插入的节点会被涂成红色，因为红色节点的意义是在概念模型2-3树中与父节点关联形成3个节点或临时4个节点。之所以插入后需要调整红黑树，正是因为概念模型中可能存在临时的4个节点（反映红黑树中双红的情况）。想象一下，如果要插入的节点是2-3树中的2-node，那么红黑树中的reaction对应的就是黑父节点。在黑色的父节点下增加一个红色的儿子，不会违反红黑树。任何规则，也对应于我们将一个元素插入2-3树中的2节点，只是将2节点变成3节点。接下来我们来看2-3棵树的删除。对于2-3树的删除，我们主要考虑要删除的元素在2节点的情况，因为如果要删除的元素在3节点，那么可以直接删除元素，不会破坏任何2-3树的属性（删除此元素不会导致高度发生变化）。当要删除的元素在节点2时，删除这个元素会导致节点2失去其唯一元素，从而导致节点2删除自己，从而导致树中某条路径的高度发生变化，树会变得不平衡。所以我们有两个方案来解决这个问题：第一个方案是先删除这2个节点，然后再调整树的平衡。在方案二中，我们想办法让被删除的元素不可能出现在2个节点中。在本文中，我们选择第二个选项。在到这个节点的路径中，我们不断判断当前节点是否是2-node。结点变成3-node或临时4-node（视具体情况而定，在红黑树后面的部分会详细介绍）。这个操作会产生一个结果：除非当前节点是根节点，否则当前节点的父节点一定是非2节点（因为搜索路径是从上到下，所以父节点已经执行过这个操作，所以不能是2个节点），那么我们就可以保证，当我们到达叶子节点的时候，我们也可以成功的从父节点或者兄弟节点借元素，让自己成为一个非2节点。这样就可以直接删除一个元素（现在这个元素不在2节点）。删除2-3树后，查看红黑树的节点，可以看到它的五种定义：1.节点颜色为红色和黑色【2-3树到红黑树的转换已经解释过了】2.根节点必须是黑色【如果根节点是2-3树中的2个节点，那么对应红黑树中的黑色节点；如果根节点是3个节点，也可以用黑色节点表示较大的元素，然后较小的元素作为左倾红色节点存在于红黑树中]3.所有叶子节点都是黑色的[theleaves这里提到的其实都是空链接，由于篇幅问题不便全部画出来]4.任意一个节点到叶子节点的路径黑色节点的个数相同【红黑树中的红色节点是绑定到黑色的父节点，这在2-3树中本来就是同一层，在2-3树中只有黑色节点才会真正贡献高度，因为2-3树的任何一个节点都是相同的与空链接的距离，所以在红黑树中反应是blackperfectbalance]5.不会有连续的红色节点[2-3树本来规定没有4个节点，2-3-虽然有是4树中的4个节点，要求在红黑树中体现为一个黑色节点有两个红色儿子，分布在左右，所以不会有连续的红色节点]我相信在你的视角里，红黑树已经不再是这五个死板的定义，背后正在出现一个2-3树的概念模型。虽然你已经有了这样的认识，但是红黑树才是真正的实现模型，我们还是要回到实现本身去探究它的一系列操作。在开始之前，我准备了两个基础知识，希望对你有所帮助。1.作为一棵二叉搜索树二叉搜索树的节点有一个元素X和两个指针字段，左指针指向小于X的元素，右指针指向大于X的元素。假设我们的插入顺序为1~10，那么这棵树会演变成只有右链接的形式，树高会增加到10层。这时候O(LogN)的查找时间复杂度已经不行了，因为这棵树退化成了链表。因此，调整二叉树的平衡非常重要。不管是AVL还是红黑树，本质上都是希望保证二叉搜索树中的元素尽可能均匀地分布在树的两边。当我们将一个元素Y插入到二叉搜索树中时，我们总是会将大小与树中的节点进行比较。如果Y小于当前元素，我们将向左移动。如果Y大于当前元素，我们将向右走，直到到达叶子节点，这时候我们就可以把Y插入到这棵二叉搜索树中了。由于这个插入动作，可能导致整棵树不平衡，所以我们需要在插入后进行平衡调整，使整棵树恢复到平衡状态（具体调整取决于树是AVL还是红黑树还是其他平衡树）。二叉搜索树的删除是一个非常有趣的问题。与插入不同，要删除的元素不能保证出现在树的叶子节点中。这会导致一个比较棘手的情况，就是我们需要从树的中间部分移除一个元素，移除之后需要对其进行调整，使整棵树满足平衡性。直接从树的中间部分去掉一个节点的场景太多了，涉及到的相关节点也太多了。这种操作很难实现。幸运的是，有人提出了一个观点，我们可以在不实际改变节点位置的情况下删除搜索树中的一个节点。由于搜索树的特殊性，删除一个元素节点后，它有两个最佳替代者，即有序序列中的前驱元素和后继元素。我们仍然以包含元素1~10的二叉搜索树为例。如果我们要删除5所在的节点，将其位置替换为4或6是可行的。4作为前驱元素，将存储在5所在节点的左子树的最右边；6作为后继元素，将存储在5所在节点右子树的最左边。这个结论稍微想一下就可以理解。现在我们把问题再简化一下，就是说删除一个节点时，先找到它的前驱元素或者后继元素（随便选一个），把它的前驱元素直接填入要删除的节点，然后删除它的前驱元素或后继元素。这时候问题就转化为删除二叉搜索树中没有左子树的节点（或者没有右子树的节点）。我们只需要删除这个节点，然后做相应的平衡调整即可（虽然还是需要拉平，但是比直接删除一个左右儿子都在树中间的节点要容易的多）。注意，这里不强调针对红黑树的操作，因为红黑树和AVL都是二叉查找树，都应用了这种方法。引入树的旋转。为了对一棵二叉树进行分级，使左右节点的个数均匀分布，通常会选择轮换的方法。您可以将二叉树中节点的左右子树视为要在天平上称重的项目。如果一侧较重，我们会从较重的一侧取一部分添加到较轻的一侧以保持相对平衡。平均的。这种调整在二叉树中的操作就是旋转。下面给出两个例子。希望大家仔细探究。旋转是二叉树平衡的本质。介绍树的旋转操作。理解了这些，再看红黑树的插入和删除，就可以理解旋转和着色背后的意义了。我们选择算法4中的左倾红黑树进行演示：首先看插入到左倾红黑树中，如图所示。左倾红黑树的插入有三种可能的情况。第一种，要插入的元素比黑色父元素大，插在黑色父元素的右侧，而红色子元素在黑色父元素的左侧。这种情况导致红黑树中有一个右倾的红色节点。注意，这种情况对应于2-3树中出现的临时4个节点。我们在2-3树中的处理是拆分临时的4个节点，左右元素各组成一个2节点，中间元素上升到上层和父节点绑定。所以，我们在红黑树中的动作就是把原来红色的左右儿子染成黑色（左右分裂），把黑色的父亲染成红色（等待上升合并）。插入左倾红黑树第二种情况，要插入的元素小于红色父节点，而红色父节点本身是左倾的。听起来有点绕口，但是看图就明白了。其实就是红色父节点和要插入的元素同时在左边，形成一个连续的红色节点。在这种情况下我们需要使用两个步骤来调整。由于我们插入的是红色节点，不会破坏完美的黑平衡，所以在旋转染色的过程中要注意保持这个完美的黑平衡。首先，对红爸爸的爸爸进行右旋。这次右旋不会破坏黑平衡，但不会解决持续红色的问题。接下来交换节点12和节点15的颜色，这样做的目的是消除连续的红色，这个操作仍然保持黑平衡。既然我们已经得到了case1的场景，那么我们就可以直接按照case1进行处理了。红色父母本身是左倾的。也就是说，插入的节点形成一个右倾的红色节点。右倾的处理很简单。将红色父节点向左转一次，可以使向右倾斜的红色节点变为向左倾斜。现在有连续的左倾红色节点。可以处理PressCase2。在插入左倾红黑树的时候，可以体验到左倾红黑树的左倾限制带来的好处，因为如果原树满足红黑树的定义，如果父树是红色的，那么它一定是左倾的，同时不需要考虑可能的右倾兄弟（如果有，说明原树不符合红黑树的定义）.此限制消除了许多需要考虑的场景，并使插入变得更加简单。左倾红黑树的删除左倾红黑树的删除需要借鉴上面提到的二叉搜索树的一般删除策略。当我们要删除一个节点时，选择它的前驱节点或后继节点元素来替换它。而是删除其前任/后继节点。在本例中，我选择用后继节点替换删除的节点。假设我们需要删除的节点的右子树如图所示，那么节点的删除其实就是转移到2的删除。我们从当前根节点开始，逐层调整红黑树支持2-3树中的预合并策略。具体做法是每次都保证当前节点是2-3树中的非2节点。如果当前节点已经是非2节点，则直接跳过；如果当前节点是2节点，则根据兄弟节点的状态进行调整：如果兄弟节点是2节点，则从父节点借一个元素给当前节点，然后组成一个临时的4节点与兄弟姐妹。如果兄弟节点是非2节点，则兄弟节点向父节点递增一个元素，父节点向当前节点递减一个元素，使当前节点成为3节点。这样的策略可以保证当最终到达要删除的节点时，它一定是非2节点，我们可以直接删除它的元素。左倾红黑树的删除接下来要考虑的是修复工作。由于红黑树定义的限制，我们在调整过程中有一些不应该存在的红色右倾节点（因为概念模型中的临时4是生成节点），所以我们沿着搜索方向。如果遇到当前节点右倾的红儿子，则对当前节点进行左旋。这时，原来的右儿子会来到当前节点的位置，然后右儿子通过和当前节点交换颜色，将右倾的红色节点固定为左倾的红色节点，我们不'打破黑节点的平衡。从右往左删除一棵左倾的红黑树是一个很基础的操作。我们以35和44为例。可以用35作为黑节点，44作为右倾的红子节点；您还可以使用44作为黑色节点，使用35作为左倾红色子节点。事实上，我们对正确倾斜的修复只是改变树的形状。一路回溯到当前根节点，直到路径中不再有任何红色右倾节点，修复工作全部完成。总结这篇文章的目的是从概念模型2-3树出发，介绍一棵红黑树的前世今生。希望大家能跳出枯燥的五个定义，更本质的了解红黑树中各种操作的来源。虽然本文只介绍了一个比较简单的左倾红黑树，但是如果你能把左倾红黑树理解清楚，那么普通的红黑树就差一点点了。对于还有精力看算法介绍的读者，我会给出一点自己的体会：插入阶段类似于左倾红黑树。删除黑节点X造成的黑平衡破坏，解释为给X的子节点增加了一层额外的黑色，使X的子节点变成[双黑]或[既黑又红]。我不太接受这个解释。想了想，我觉得这个表述可以更直白一点：既然删除了一个黑节点，那么必然会因为少了一个黑节点而破坏了与这个黑节点之间的路径上的黑平衡。如果仔细研究算法介绍中的四种删除场景，你会发现它们所做的其实是试图从兄弟节点的路径中移出一个黑节点。所以，如果实在看不懂【双黑】，【黑红皆宜】，那就直接按照“某条路欠黑，想办法加黑节点”的思路直接思考“！还是删除阶段，四次删除的场景应该怎么记住？我们假设被删除的节点是一个左倾节点。实际上，三个因素决定了场景的变化：本节点兄弟的颜色；兄弟左右儿子的颜色；此节点的父节点的颜色。这样粗略估计2x2x2x2一共有16种情况。其实会少很多，我们先从兄弟色开始。请注意，如果兄弟节点是红色的，那么当前节点的父亲和兄弟节点的儿子实际上都是黑色的。而当兄弟是黑的时候，我们只需要满足兄弟的右儿子是红的，通过一次调整就可以达到平衡（详见算法介绍）。另外一个提醒就是一定要考虑好内存的顺序。在算法介绍中的四种删除和拉平情况中，只有情况4是绝对最终状态，也就是说，达到这种状态后，只需要进行一次调整就可以确定达到平衡。所以，我们的出发点必须是从这个状态开始。对于其他的情况，我们要考虑的不是如何达到最终的平衡，而是如何一步一步的变成情况4。这样，你的思路就会清晰很多，记忆的压力也会减轻。如果细心的话，可以回忆一下本文介绍左倾红黑树插入的顺序。为什么是这个顺序？一个数据结构可视化网站，它的红黑树是基于2-3-4树的，和算法介绍的基本一样（删除时选择前继/后继节点除外），可以用作测试。https://www.cs.usfca.edu/~galles/visualization/Algorithms.html写在最后。如果你被问到红黑树，也许你可以试着问面试官一个问题：“你应该知道红黑树黑树的五个定义，如果我构造一个只有黑色节点的红黑树，是这可行吗？因为这并没有违反红黑树的任何规则。”如果他回答是可行的。继续追问：“那么，红黑树中的红色节点是做什么用的？红色节点的真正含义是什么？”你的故事开始了，我和你的算法的故事才刚刚开始。
