高薪程序员&面试题精讲系列55之你了解红黑树吗？说说它的底层结构吧
一. 面试题及剖析
1. 今日面试题
您是否熟悉红黑树的相关知识？
请问能否简要说明您对 HashMap 数据结构的理解？
当 HashMap 中的链表达到多高长度时会转换为红黑树？
当 HashMap 中的红黑树节点数量减少到一定程度时会恢复为链表结构？
2. 题目剖析
在过去的两篇推送中，《壹哥》为大家带来了关于二叉树系列的详细讲解。通过深入学习其概念与核心算法设计思想等关键知识点后发现，在各类数据结构中还存在一个更为复杂的分支——红黑树这一重要数据结构需要我们进一步深入研究与实践应用。因此《壹哥》将继续为大家分享这篇重要文章
在学习HashMap与ConcurrentHashMap的过程中, 我曾向大家介绍过, 这两种集合的数据结构都采用了红黑树作为基础. 当哈希冲突发生时, 为了有效地解决冲突问题, 会将同一键桶中的数据组织成一个链表. 当链表变得过长时, 则会采用红黑树来进行数据存储. 那么这棵红黑树究竟是什么样的存在? 它具备哪些特性以及能力, 才使得HashMap得以选用它作为底层存储结构的关键所在? 为何不选择B树或其他数据结构呢？
那么接下来请跟着 壹哥 ，来了解一下红黑树吧！
二. 红黑树详解
1. 概念
红黑树（Red Black Tree），也被简称为R-B树，在数据结构领域是一种经典的自平衡二叉查找树算法。它也是一种高度平衡的二叉搜索树结构，并且也可以被看作是一种特殊的二叉树类型。该数据结构中的每个节点都包含一个额外的位来标识节点的颜色信息：红色或黑色。
注：以上改写遵循以下原则：
- 每句话仅进行表达方式上的调整
- 使用了词汇替换、句式变换等方式进行改写
- 保持了原文的技术准确性
- 通过适当增减语序和修饰词使表达更加专业流畅
有些小伙伴可能会有疑问：为什么被称为“红黑树”而不是其他名称？这里所说的“红”与“黑”，仅仅是为了标识出二叉树中各个节点所具有的状态和特性。实际上，“黑色”是最常使用的颜色名称之一，在视觉效果上较为突出。而红色之所以被选用，则是因为其鲜艳度较高，在对比度上有较好的表现效果。因此得名“红黑树”。如果当初选择其他颜色的话，则可能会采用其他名称。
当执行插入或删除操作时, 红黑树会遵循特定的规则来维护其结构的平衡性, 并实现高效的查找操作. 具体结构通常可参考下图.
然而红黑树并非一棵 完美的 平衡二叉搜索树。从图中可见根节点右侧的高度明显高于左侧。然而左子与右子中的黑色节点层数相等即任何节点到所有叶子节点的路径均包含相同数量的黑色节点因此我们称红黑这种平衡特性为'黑色完美平衡'
2. 作用
红黑树主要用于存储有序数据；其查询操作的时间复杂度为O(log n)，具有较高的效率；因此其应用范围非常广泛。例如，在Java的集合类中使用了HashMap、ConcurrentHashMap、TreeSet和TreeMap；如C++标准容器库中的Set和Map也是基于红黑树实现的；此外Linux虚拟内存的管理也是利用红黑树来实现的一种重要技术。RedBlack Tree通过模拟磁盘空间管理的方式实现了高效的内存分配与回收；这一特性使其在需要高并发访问且对性能要求极高的场景中表现优异。
3. 特点(重点)
红黑树作为一种特殊的二叉树，有其自有的一些特征，如下：
该数据结构规定了每个节点的颜色属性：它们要么是黑色要么是红色。
根节点必须被指定为黑色。
所有叶节点必须被染成黑色（这有助于确保删除操作后红黑树的平衡）。
若某个节点是红色的，则其子节点必须均为黑色（这排除了连续出现两个红色节点的可能性）。
在从任一节点通向其所有子叶节点的过程中，所有路径上的黑色结点数量一致（这主要保证了红黑树的高度特性）。
若某节点具有黑色子节点，则该节点必然拥有两个子节点（这有助于维持红黑树的高度特性）。
左子树中的所有节点值均小于或等于父根值。
右子树中的所有节点值均大于或等于父根值。
包含n个结点的红黑树的最大高度不超过2log(n+1)（这体现了红黑树的高度平衡性）。
4. 红黑树与二叉树的关系
红黑树是一种独特类型的二叉树之一，在平衡二叉查找树领域具有重要的地位
每棵红黑树都属于一颗二叉排序树，在对红黑树进行查找的过程中都可以采用针对普通二叉排序树的标准查找算法，在该过程无需额外的颜色信息
5. 添加
进行红黑树插入操作时会涉及多个步骤；具体来说，则分为两个主要环节：首先需要确定新节点应放置的位置；其次，在完成位置确定后还需确保红黑树的自平衡特性得到维护。总结一下，则大致可以分为以下几步：
在处理过程中将红黑树视为一棵二叉查找树进行新节点的插入操作；
随后对该节点进行颜色设置使其变为红色状态；
最后通过调整旋转结构并重新配置颜色等手段对这棵结构进行修复以确保其符合红黑树的标准。
在处理插入操作时，在分析父节点状态的基础上，需对目标节点进行颜色标记，并将其准确地插入到二叉树结构中。针对不同场景进行分类处理。
①. 第一种情形：当被插入的节点位于树的根部时，请直接将该节点设为新根并将其标记为黑色。
②. 如果被插入节点的父亲已经是黑色，则无需采取任何措施。该子树在插入后仍然保持红黑树特性。
③. 第二种情形较为复杂：
* 情况1：假设当前节点的父亲是红色，并且其祖父节点中的另一子节点（叔叔节点）同样是红色。
* 情况2：若当前节点的父亲颜色为红色、其叔叔呈现黑色状态，并且当前处于其父之右方。
Case 3: 父节点为红色、叔节点为黑色，并且该节点为其父节点的左子节点。
这3种情况我们再分别考虑如下：
| 现象说明 | 处理策略 |
|---|
| Case 1 | 当前节点的父节点是红色，并且其祖父节点的另一个子节点（叔叔节点）也是红色 | (01) 我们将"父节点"染成黑色； (02) 我们将"叔叔节点"设定颜色为黑色； (03) 我们将"祖父节点"的颜色设置为"红色"； (04) 接下来我们将操作转移到"当前节点"(即原本是红父的红祖父)，并继续执行后续操作 |
| Case 2 | 当前节点的父是红边连接，并且其叔叔是黑边连接的同时, 当前是其父的右子树 | (01) 我们选择"父 nodes"作为新的中心进行操作； (02) 然后我们围绕这个新中心向左进行调整 |
| Case 3 | 当前 nodes 的父是红边连接, 并且其叔叔是黑边连接, 同时当它是其父亲的左子树时 | (01) 首先我们将该父 nodes 的颜色设定为空白； (02) 然后我们将该祖父 nodes 的颜色设置成红色； (03) 最后我们围绕该红祖父 nodes 向右进行调整 |
case1时示意图：
case2时示意图：
case3时示意图：
各位朋友请注意：本文并非专门针对红黑树的知识详述。它主要用于 interview 复习相关知识点回顾。关于 insert delete left rotate right rotate 等操作的具体实现细节不会展开讨论。如果您希望深入探讨这些操作的具体实现细节，请考虑查阅更详细的教程或书籍。
6. 删除
在红黑树中进行删除操作同样涉及复杂的步骤。从整体上看, 删除操作主要包含两个环节:首先需要定位目标节点,随后还需完成后续的平衡维护工作。
确定需要删除的目标节点自然可复用查找操作。若无目标节点则跳过此次操作；若有目标节点则需执行自平衡调整。删去该节点后需找到替代节点填充其位置；否则会导致子树与父辈节点脱节；除非被删节点本身无子节点则无需替代。
红黑树删除结点，查找删除结点时大致过程如下：
当被删除的节点没有子节点时，则可以直接移除该节点；
当被删节点仅有一个子节点时，则需移除该节点并将其子节点替代；
如果被删节点有两个子节点，则应将后续节点（即大于被删节点的最小节点）进行替换；
最终需通过调整颜色和结构等操作对整体树形进行优化处理以确保其仍为有效的红黑树。
7. 红黑树的自平衡
当向红黑树中添加或删除节点时，由于节点数量发生变化，可能导致剩余的节点不符合红黑树的基本特征。因此需要通过左旋和右旋以及颜色变换等方式进行平衡调整，以维持其特性。
7.1 左旋
以某个特定的顶点作为支撑中心（即为旋转轴），则该顶点原本位于右侧的部分将被移动到左侧的位置，并且右侧顶点对应的左侧分支将被重新配置到新的位置上；与此同时左侧结构保持原有的形态不变
左旋 只影响旋转结点和其右子树 的结构，把右子树的结点往左子树挪了。
7.2 右旋
选取某个节点作为支轴，在其左分支下执行重平衡操作：将左侧分支重新连接到原父节点上，并将左侧分支原来的右侧分支重新连接到左侧分支上；右侧分支则保持原有状态。
右旋 只影响旋转结点和其左子树 的结构，把左子树的结点往右子树挪了。
7.3 变色
结点的颜色由红变黑或由黑变红。
三. 结语
今天壹哥带领大家一起回顾了红黑树的相关知识。但请注意，本文并非专门介绍红黑树的教程文章。因此内容可能存在某些知识点的缺失之处。如果对于红黑树的基础知识还不是很熟悉，请务必继续深入学习相关的教材资源。
码字创作是一项繁重的任务。不知道 壹哥 这篇文章是否触动了您？点个关注、点赞、转发一下吧！