红黑树的红黑有什么意义_硬核图解--字节面试必问的红黑树
注：本文比较硬核但是很值得大家花心思看完，看完你一定会有所收获的
红黑树是一种在面试中常考且极具挑战性的核心知识点。据说很多字节跳动的面试官都喜欢将这个问题作为考察重点。很多人认为这个知识点非常棘手；也有人认为该数据结构在日常开发中的应用较为有限；因此掌握起来并非易事。
该数据结构虽抽象但并非难以掌握；然而其平衡调整机制涉及诸多细节，在多数网络博客中往往缺乏系统性；因此这给理解和掌握带来了诸多障碍
其次，在Java语言环境中（如JDK 1.8版本），为了应对过度哈希冲突导致的长链表问题，在Map数据结构的具体实现阶段（如HashMap），会将常规线性链表转换为基于红黑树的数据结构以优化性能；此外，在Linux操作系统底层操作系统任务调度系统（如CFS进程调度算法）中，默认情况下采用了基于红黑树进行存储的方式以提高资源利用率；最后，在多路复用技术下的Epoll通信框架（如网络输入/输出模型）核心机制同样采用了结合了红黑树与双向链表的设计方案以增强系统的吞吐量与稳定性。
我们不建议直接手动实现一个功能完善的红黑树数据结构；但掌握其基本架构将有助于深入理解底层的具体实现细节。此外, 红黑树作为一种高效的数据存储方式, 实现了对树形组织形式的高度综合应用, 包括多层节点结构、动态平衡机制以及旋转操作等核心组件, 这些特性共同构成了数据结构中的高级知识体系。
其实当面试官提出这个问题时, 通常情况下他会希望不依赖标准答案就清晰地阐述该数据结构的基本定义与操作流程. 他的主要意图是从这个问题出发了解候选人对于数据结构的理解深度以及知识广度. 他希望看到候选人能够: (1) 完整地阐述该数据结构的基本定义;(2) 分享你对红黑树这一数据结构的理解与认识;(3) 并能通过旋转、染色等操作对特定场景下的红黑树进行相应的调整以满足其定义要求.
通过阅读这篇文章, 你可以深入掌握红黑树的基本原理, 包括其五大核心定义所蕴含的核心逻辑. 此外, 你可以进一步明确红色节点所代表的意义, 并对因插入和删除操作而导致的数据结构动态变化有清晰的认识, 而不再依赖于死记硬背特定情况下的平衡调整策略（例如: 当删除某节点后, 其叔父结点呈红色状态时, 应该如何进行相应的调整）. 同时, 你可以熟练掌握各种旋转操作及其应用条件, 并明确染色规则的作用.
最终，在你的全神贯注下，在配图中清晰地展示了所有增删操作的具体步骤后，则能真正地将红黑树转化为属于你的专业知识
先谈平衡树
对于开发人员来说，了解接口是一个基本技能：首先需要创建一个界面（interface），然后为该界面提供具体的实现（implementation）。任何一个接口都可以有多个不同的实现方式，并且这些不同的实现都会满足该接口的声明要求。
例如，在界定手机时可将其称为通讯工具；其具体化体现为三星、苹果、华为等品牌推出了各自系列的产品。
红黑树的本质其实也是对概念模型：2-3-4树 的一种实现，因此我们先来关注2-3-4树。
2–3–4 树是阶数为4的B树全称BalanceTree亦称作平衡二叉搜索树其主要用途是实现高效的查找操作
对于平衡多路查找树这一数据结构的概念进行阐述。由于已有大量相关资料对此进行了详尽阐述，在此不做进一步详细说明。其关键特征在于高度的平衡性，从而保证了在最坏情况下依然维持O(LogN)的时间复杂度用于查找操作。需要注意的是，若不满足平衡条件，则可能导致查找效率降至线性时间复杂度O(N)。
建议提醒各位，在平衡性的定义中指出空指针与根节点之间的距离相等这一特性；必须深入理解其含义。（换句话说，在非叶子节点中不可能出现空指针）
由于2-3-4树是一颗阶数为4的B树，所以它会存在以下节点：
- 2节点
- 3节点
- 4节点
2个键值对中包含一个键值对[X]以及两个指针分别连接到小于X和大于X的子树；而3个键值对则存储了两个键值对[X,Y]以及三个指针分别连接到小于X、介于X至Y之间的中间区域以及大于Y的部分；按照此规律，则4个键值对将会有更多的指针以供引用。
节点介绍
2-3-4树到红黑树的转化
红黑树是基于二叉树实现的一种变种。为了避免在不同节点之间进行转换所带来的高昂计算成本，则采用将颜色作为附加属性的方式来区分原本属于不同层级的节点。因此，在二叉树的基础上引入颜色属性能够有效地区分原本属于不同层级的节点。
在2-3-4树中（原意：在二阶、三阶、四阶树中），2号位点（原意：代表二阶的位置）与之对应的则是红黑树中的黑色点（原意：黑色的点）。此外，在这些位置上（原意：除开上述位置之外），这些点表现为红点与黑点结合的形式（原意：以红色点加黑色点的方式存在）。其作用在于将这些位置上的点与其对应的黑色父点连接起来（原意：其意义在于将这些点与相应的黑色父结组合在一起）。
可以理解为红节点或者红色链接（取决于个人偏好）。在许多教材中常表述为由黑色节点引出的红色链接。所指的节点通常呈红色。
我们首先考察从2-3-4树过渡至红黑树时的结点转换过程。具体而言：
- 2号结点将直接转换为黑色结点
- 3号结点可采用不同的方式呈现——左倾或右倾红结点
- 4号结点必须被严格设置为带有两个红色子结点的黑色父结点
B树到红黑树的转化
本文的核心研究对象是2-3树，并其具体原因将在后续内容中详细阐述，在众多2-3树变形形式中具有显著特征--左倾红黑树。基于名称提示，在这种变形形式中具有显著特征--左倾红黑树的特点是在结构上进行了特定约束：即对于任何一个红色节点而言，该节点仅允许作为左子节点存在。
以下是它的转化过程：
B树到红黑树的转化
仅凭单个节点的转化难以直观看出其变化规律。为了更好地理解这种转换关系并避免遗漏关键细节，在此我对该过程进行了深入分析，并精心制作了一张红黑树转2-3树 的示意图，并直观地展示了两者的内在联系。
通过将左倾红黑树中的红色节点以45度角并绕顺时针方向转动的方式使其与黑色父节点保持平行，并将其视为一个整体结构后你会发现这实际上是一种2-3树
B树到红黑树的转化
此时我认为大家现在已经理解了红黑树本质上就是其中一种基于2-3或2-3-4树的概念模型
算法导论对红黑树的实现基于2-3-4树模型，在这种结构中，每个4阶节点必须严格满足平衡条件（即每个4阶节点必须由一个黑色父节点和两个红色子节点构成），其两个红色子节点不能同时位于同一侧。
算法4所描述的红黑树结构基于2-3树实现方案，并且这种特定实现方式下的红黑树具有显著特点。具体而言，在概念模型中定义的三元组在被映射至红黑树时必须以带有左倾标记的形式采用带有红色标签的方式呈现。这样的限制条件能够有效地降低对红黑树进行结构调整时所面临的复杂度问题，在后续章节我们将深入探讨这一特性带来的实际应用价值。
我深入学习了《算法导论》以及第4版的《算法》中关于红黑树的内容，并对这两种教材中的红黑树实现进行了系统梳理。最终，在比较两者的优劣后，我选择了第4版《算法》中的红黑树作为演示的核心内容。
- 首先，在算法4中采用的是以2-3树为框架构建的红黑树结构，在设计时无需处理2-3-4树中复杂的"四节点分裂"问题；
- 其次，在算法设计中采用的是左倾红黑树这一特定实现方式，在平衡操作上相对简化了难度；
- 算法导论在阐述红黑树删除操作时描述较为简略，并未对关键步骤进行详细展开说明，
这使得初次学习该部分内容的读者可能会感到理解不够深入。因此，
考虑到部分读者具备较强的数据结构基础（如对2-3-4树有一定了解），在介绍完基于2-3树的知识后，
可以适当补充相关背景信息以便更好地理解算法导论中的内容。
（不过对于不需要深入研究的情况，
这部分内容可以暂时略过）
为了深入理解红黑树这种自平衡二叉查找树的工作原理及其核心操作——染色与旋转——我们需要先打下坚实的基础。具体来说，在学习红黑树之前必须先掌握其基础模型——2-3树的相关知识及其插入删除操作的基本规律
以上改写仅改变了表达方式，并未改变原意
如果需要在2-3-4树中向4节点内插入元素，那么会引发如下图所示 的分裂过程
2-3-4树的插入
实际上，在执行插入操作时，算法必然将待插入的点标记为红色。其意义在于与其父点建立联系，并形成概念模型2-3树中的三元点或者临时四元点。
而红黑树之所以需要在插入后进行调整步骤，则是为了确保可能出现的概念模型中的临时四节点（即体现在红黑树中表现为两个红色指针指向同一个父节点）的存在得到妥善处理
考虑将2-3树中的一个2节点作为待插入节点时，在红黑树中这会对应于黑色父节点的情形。此时，在该黑色父节点下添加一个红色子节点并不会违反红黑树的任何规定。同样地，在我们的操作中将该2-3树中的2节点转化为3节点就可以实现这一过程。
在探讨...的时候，在多数情况下我们需要特别关注的是当被删元素位于二节点的情境。这是因为若被删元素位于三节点，则可以直接进行该操作而不破坏原有结构。这不会影响到该数据结构的基本特性，并且也不会导致整体高度发生改变。
当待删除元素位于2节点时，在删除该元素后会导致2节点丧失其仅有的一个元素 ，从而引起自身被删除。这将导致树中某条路径的高度发生变动，并使整个树失去平衡。
因此我们有两种方案去解决这个问题：
- 第一种方案是先删除该2节点,并对树进行平衡处理。
- 第二种方案则是采取措施确保被删除的元素无法存在于2节点中。
我们选择了第二种方案，在经过该节点的路径上持续判断当前节点是否为2阶（2-node）。如果满足条件，则会从其兄弟节点或父节点获取一个元素以实现平衡操作。从而将该2阶（2-node）升级为3阶（3-node）或临时标记为4阶（4-node, 具体情况视后续红黑树章节而定）。后续章节会对相关操作进行详细讲解。
这种操作会导致某种结果：只有当当前字符不是根字符时才会有这样的情况发生（由于搜索路径是从上至下进行的，在此之前已经对该字符进行了处理），因此不可能出现该字符为2的情况。然而，在完成这些处理之后，并且考虑到了可能存在的子树结构之后，则可以得出结论：在到达叶子结点时...
2-3树的删除
再看红黑树
红黑树的节点
来看它的五条定义：
1.节点颜色有红色和黑色
【2-3树到红黑树的转化已经解释过】
2.根节点必为黑色
2-3树中如果根节点为2节点，那么它本来就对应红黑树中黑节点；如果根节点为3节点，也可以用黑色节点表示较大的那个元素，然后较小的元素作为左倾红节点存在于红黑树中
在2-3树中，当根节点是2型节点时（即双键结点），它直接映射至对应的黑色结点（即黑键结点）；当根结点是3型时（三键结点），较大者将被标记为黑色，并以此为基础构建相应的红色子结构。这些红色子结构将根据具体情况分为左倾和右倾两种类型，并最终整合到完整的红黑树体系中。
3.所有叶子节点都是黑色
【此处提到的叶子其实是空链接，因篇幅问题不便全部画出】
####4.任意节点到叶子节点经过的黑色节点数目相同
红黑树中的红节点是和黑色父节点绑定的，在2-3树中本来就是同一层的，只有黑色节点才会在2-3树中真正贡献高度 ，由于2-3树的任一节点到空链接距离相同，因此反应在红黑树中就是黑色完美平衡
在红黑树结构中，红色节点总是与其对应的黑色父节点紧密相连，在二叉查找树扩展结构中这些红色和黑色结点共同构成了更为复杂的层级关系。其中仅通过黑色节点才能实现二叉查找树的高度优化，在这种情况下整个数据结构才得以维持其高度平衡特性
5.不会有连续的红色节点
2-3树中本来就有规定没有4节点，2-3-4树中虽然有4节点，但是要求在红黑树中体现为一黑色节点带两红色儿子，分布左右，所以也不会有连续红节点
2-3树中原本就规定没有4节点 虽然在2-3-4树中存在4节点 但在红黑树中则通过特定结构来表示这些情况 具体表现为黑色节点带有两个红色子节点 并且这些红色子节点分别位于左右两侧 从而确保不会出现连续红色边
2-3树中原本就规定没有4个子节点 虽然在2-3-4树中可能存在一个具有四个子节点的情况 但在红黑树这种数据结构中 则会将这种情况表示为一个黑色父结点带有两个红色子结点 并且这些红色子结点分别位于父结点的左右两侧 这种结构设计使得不会出现相邻结点均为红色的情况
从你的角度来看，在对红黑树的认识上早已超出了传统的单一定义范围。它背后所呈现的是一颗2-3树的概念模型。尽管你在认识上已有了一定的理解基础，但红黑树作为真正意义上的实现方案，并非仅仅依赖于这些理论上的框架；为了更好地理解它的各种操作机制，在深入研究之前...
1.作为二叉查找树
每个节点包含一个数据元素X，并有两个子链表字段：左子链表字段存储所有小于X的数据项；右子链表字段存储所有大于X的数据项。
当我们依次向树中插入数值1至10时
因此，在二叉树中实施平衡优化是一个关键步骤。包括AVL和红黑树在内的各种自平衡二叉搜索树都旨在尽可能地将这棵二叉查找树中的元素均匀地分布在两边。
当我们向一棵二叉搜索树中添加一个元素Y时，在每个节点上都会进行大小比较：若Y小于当前节点值，则向左移动；若Y大于当前节点值，则向右移动；持续此过程直至抵达叶子节点后，我们便可在该二叉搜索树中添加元素Y。
由于本次插入操作可能导致整棵树出现一定程度的失衡状态，在完成插入操作后需执行一次平衡化处理以恢复正常状态（具体实施方式取决于树类型是否为AVL、红黑树或其他类型）。
二叉查找树的删除操作具有一定的挑战性。与插入不同的是，在进行删除操作时需要考虑待删除的关键字未必总是位于树中的终端节点位置。这一操作往往会导致难以解决的情况：即需要从树结构中移除一个非终端节点，并且在完成该操作后还需通过相应的调整来确保整个数据结构维持其平衡特性。在实际应用中经常遇到需要从中间位置移除节点的情形：由于这涉及大量相关联的数据项处理起来相对繁琐因而难以高效实现
有人提出了一个观点：我们不需要真正移动该节点的位置来完成删除操作。基于查找树的特性，在删除某特定元素节点后，该位置将由其有序序列中的前驱替代表示者和后继替代表示者来填补。
考虑一个包含元素1至10的二叉查找树作为示例。当我们需要删除位于该树中值为5的那个节点时，请注意可以选择将4或6替代其位置均为合理的选择。其中前驱元素为4，则需存放在该节点左子树中最右侧的位置；而后继元素为6，则需存放在该节点右子树中最左侧的位置。
关于这个结论，大家只需稍加思索便可以明白。
在处理过程中，我们实现了对问题的简化。具体来说，在删除某个节点时，在确定该节点的所有前后继元之后（选择其中一个作为替代），我们将该节点的前后继元按照一定的规则进行替换操作，并将其对应的替代元从系统中移除。
这个时候问题就转换为在二叉查找树中删掉一个无左孩子的节点（或是一个无右孩子的节点），具体操作如下：先删掉该目标节点再执行相应的平衡处理；虽然仍需进行平衡处理但相较于一次性处理既有左孩子又有右孩子的情况而言要简单得多。
注意，在这里并没有特别指出这是关于红黑树的操作；因为红黑树和AVL都属于二叉查找树家族，并且它们都可以采用这种方法。
注意，在这里并没有特别指出这是关于红黑树的操作；由于红黑树和AVL都属于二叉查找树家族，并且它们都可以采用这种方法。
介绍一下树的旋转
为了平衡一颗二叉树以使左右子节点数量均衡，通常采用旋转的方法。我们可以将一棵二叉树中某个节点的左右子树类比于天平上的待测物品，在某一侧较重时，则从重的一侧转移部分资源到轻的一侧以达到相对均衡的效果。
在二叉树中对结构进行优化的一种操作即为旋转，在这里有两个例子可以供参考。希望各位能够深入研究这一技术细节，并真正理解其重要性。
介绍一下树的旋转
树的旋转操作
在掌握了这些基本概念之后，在研究数据结构时就应当去深入理解其内在原理和应用逻辑的基础上
左倾红黑树的插入
如图所示，对于左倾红黑树的插入一共有三种可能的情况。
- 第一种情形下,待插入元素位于黑父右侧,而黑父左侧为红色儿子元素.这种配置将导致红黑树中出现右倾红色节点.观察可知,这种情况在2-3树中对应生成了一个临时4节点.在2-3树的操作中,我们需要将此临时4节点进行分裂,使其左右子项各自形成新的2节点,并将中间元素上移至上层与父节点重新结合.据此推断,在红黑树中相应的操作应为:将原本红色的左右子项被染成黑色(完成分裂),并将黑父标记为红色(等待上层结合).
- 第二种情形涉及待插入元素小于红父且红父自身呈左倾状态.这种配置看似复杂,但实际上意味着待插入元素与红父共同位于同一侧边.此时我们需要采取两步调整策略:首先对红父的父亲执行一次右旋操作,这虽然不会破坏黑色平衡特性但未能解决连续红色的问题.随后将12所在节点与15所在节点的颜色进行交换以消除连续红色现象.在此基础上我们即可进入第一种情形下的处理流程.
- 第三种情形下,待插入元素大于红父且红父本身呈左倾状态.此时插入操作会导致一个右倾红色节点的形成.对于这种情况我们只需对其进行一次左旋操作即可将其转变为左倾状态从而触发第二种情形下的处理流程.
在插入操作中能感受到左倾斜红黑树对于左倾斜限制带来的优势，在假设原始树满足红黑树标准的情况下：若父节点为红色，则该节点必定满足左倾斜条件；此外，在这种情况下无需考虑可能存在的右倾斜兄弟（如果有右倾斜情况出现，则表明原始结构不符合标准）。
这种限制消除了很多需要考虑的场景，让插入变得更加简单。
左倾红黑树的删除
左倾红黑树的删除操作需要参考之前的内容中提到的二叉查找树通用的删除策略。在进行节点删除时，我们选择其前驱或后继元素来替代该节点，并代替当前节点的位置进行删除。
在这个例子中，我选择用后继节点来替代被删除节点。
在需要删除的节点的情况下，其右子树如图所示，则对该节点进行处理相当于处理2
以当前根节点为起点，在采用预先合并策略的基础上对红黑树进行逐层处理。具体而言，在每次操作中需要确保该节点不是2-3树中的双键结点；如果该节点已经是双键结点，则无需进一步操作；而如果是单键结点，则需要根据其兄弟结点的状态进行处理：
- 如果其兄弟是2节点，则从父节点获取一个元素至当前节点，并进而与之共同构成临时4度单体。
- 如果其兄弟为非2度单体，则需先使其提升一个单位至父层，并使父层降级至本层以便当前单体升至3度单体。
此方案能够确保当处理到待删除节点时，该节点必定不是二度节点从而使得该节点的元素得以顺利移除
左倾红黑树的删除
修复工作是需要重点考虑的。受限于红黑树本身的定义，在进行调整时可能出现了一些不应该存在的红色右倾节点（因为生成了概念模型中的临时4节点），于是我们顺着搜索的方向向上回溯检查。如果遇到当前节点有一个右子节点且该子节点颜色为红色，则对该子操作进行一次左旋操作：此时原本位于右侧的儿子会移动到当前位置并修改其颜色状态（原本为红色变为黑色），随后我们将父节点的颜色状态与其交换（将父节点从红色变为黑色）。经过这一步操作后原本存在的右倾红节点已经被修正为左倾红节点的状态，并且这一步操作不会影响到黑色节点的高度。
左倾红黑树的删除
右倾转左倾是一种基础操作。以数值35和 为例：你可以将数值35设为黑色父节点并将其右边设置为红子节点（值为 ）；或者反过来设置数值为父-子关系（值为 和值为 ）。实际上，在修复过程中我们只是更换了树形结构——即从该路径上的每个红色右偏移子结点依次删除它们直到路径中不再包含任何红色右偏移子结点为止。
总结
本文的目的在于从概念模型2-3树的角度展开介绍红黑树的发展历程与演变过程。希望读者能够摆脱单一知识点重复枯燥的学习模式，在深入理解红黑树核心操作的基础上掌握其实质。
虽然本文仅作为初步介绍讨论了较为简单的左倾红黑树模型，若能透彻理解这一数据结构的核心机制，则普通红黑树通常仅需额外处理几种特殊情形。
对于还有精力阅读算法导论的读者，我给出一点自己的经验：
双重黑色
写在最后
最后，在遇到关于红黑树的问题时，请你尝试反问面试官一个问题：“您是否了解红黑树的基本定义？例如，如果我尝试只使用黑色节点构建一棵红黑树的话，这会不会违反任何一条规则？”
如果他回答可行。
进一步探讨：‘那么也就是说，在红黑树中为什么要引入红色节点呢？红色节点的实际作用又是什么？’
你们的故事就开始了，而我和你的算法故事也才刚开始。
絮叨
敖丙把自己的面试文章整理成了一本电子书，共 1630页！
干货满满的信息量极大，并且每一个细节都值得细细品味。清单如下：包括我在复习过程中整理过的面试题和简历模板等 complimentary copies ，现正免费分享给诸位。
我自称是敖丙。
随着你知道的东西越来越多,你的无知面也随之扩大。
衷心感谢每一位支持我的朋友:在评论区留下您的见解,在分享页面点赞以显示关注,在文章末尾收藏以方便查阅。
我们下期见！
回复【资料】有我准备的一线大厂面试资料和简历模板