【干货分享】红黑树硬核讲解
1 引言
预防针：红黑树本来就是基本算法中的难点，所以看此文时建议先有点预备心理或知识铺垫，没接触过 RBT 而直接看此文的话，绝对懵逼。
为了数据的查询跟增删方便，系统引入了二叉查找树，它具有左节点 < 根节点 <右节点 的属性，
但是这种设定跟数据的插入顺序有很大关系，比如你插入的是 1234，二叉查找树会退化为链表。
为了避免链表结构的出现，研究者们又提出了平衡二叉树跟红黑树。平衡二叉树要求任意一个节点的左深度跟右深度差值绝对值不能大于 1，如果插入后超过了 1 会通过左右各种旋转来更改连接的变化，最终实现左右深度差不大于 1 的这个要求。
平衡二叉树的深度要求太过完美，当涉及大量增删时，可能会太多时间用在调节平衡上，为了平衡投入跟产出比，又设计了红黑树。
红黑树算是一个比较复杂的数据结构了，除非你面字节，可能让你手写红黑树。一般情况下你只要说出红黑树构造的五大背后逻辑，展现你对底层数据结构的深度跟广度即可。
本文不会着重说红黑树的增删过程，因为你百度看下权威教程或源码，然后跟着追踪就知道大致流程了，本文会说下红黑树为何如此设计，它跟 2-3 树有啥联系。
2 2-3 树
2.1 定义
为了保证查找树的平衡性，需要一些灵活性，因此我们允许树中的一个结点保存多个键。
2 结点：含有一个键和两条链接，左链接指向的 2-3 树中的键都小于该结点，右链接指向的 2-3 树中的键都大于该结点。
3 结点：含有两个键和三条链接，左链接指向的 2-3 树中的键都小于该结点，中链接指向的 2-3 树中的键都位于该结点的两个键之间，右链接指向的 2-3 树中的键都大于该结点。
4 节点：含有三个键和四条链接，大致的思路跟 3 节点类似。需注意在 2-3 树中，4 节点是短暂存在的，会被转化为 2 节点或 3 节点。
2.2 查找
要判断一个键是否在树中，我们先将它和根结点中的键比较。如果它和其中的任何一个相等，查找命中。否则我们就根据比较的结果找到指向相应区间的链接，并在其指向的子树中递归地继续查找。如果这是个空链接，查找未命中，可以发现跟简单的二叉树查找类似。
2.3 插入
要在 2-3 树中插入一个新结点，我们可以和二叉查找树一样先进行一次未命中的查找，然后把新结点挂在树的底部。但这样的话树无法保持完美平衡性。使用 2-3 树的主要原因就在于它能够在插入之后继续保持平衡。
如果未命中的查找结束于一个 2 结点：只要把这个 2 结点替换为一个 3 结点，将要插入的键保存在其中即可。
只有一个 3 结点的树，向其插入一个新数据：此时我们可以创建个临时 4 节点，然后将其转化为由 3 个 2 节点组成的 2-3 树
向一个父结点为 2 结点的 3 结点中插入新键：此时先将组成个临时 4 节点，然后将中间数提到上面跟父节点融合为一个 3 节点，这样树的高度没变。
向一个父结点为 3 结点的 3 结点中插入新键 4：跟上面套路类似，不断将中位数的数据往上提，直到遇到个 2 节点，或者到达了根节点然后进行拆分。
插入总结：
先找插入结点，若结点是 2 结点，则直接插入。如结点 3 结点，则插入使其临时容纳这个元素，然后分裂此结点，把中间元素移到其父结点中。对父结点亦如此处理。（中键一直往上移，直到找到空位，在此过程中没有空位就先搞个临时的，再分裂。）
2-3 树插入算法的根本在于这些变换都是局部的：除了相关的结点和链接之外不必修改或者检查树的其他部分。每次变换中，变更的链接数量不会超过一个很小的常数。所有局部变换都不会影响整棵树的有序性和平衡性。
【文章福利】另外小编还整理了一些 C++后端开发面试题，教学视频，后端学习路线图免费分享，需要的可以自行添加：学习交流群点击加入~ 群文件共享
小编强力推荐 C++后端开发免费学习地址：C/C++Linux服务器开发高级架构师/C++后台开发架构师
2.4 删除
2-3 树的删除分为两种情况。
如果待删除元素在 3 节点，那么可以直接将这个元素删除，删除这个元素不会引起高度的变化。
当待删除元素在 2 节点时，由于删除这个元素会导致 2 节点失去唯一的元素，引发树中某条路径的高度发生变化，为维持平衡，此时有两种方法。
先删除再对 2-3 树进行平衡调整。
想办法让这个被删除的元素不可能出现在 2 节点中。如果发现删除元素树 2 节点则会从兄弟节点或父节点借个元素，当前 2 节点变为 3 节点或临时 4 节点，然后再删除目标数据。
2.5 构造
和标准的二叉查找树由上向下生长不同，2-3 树的生长是由下向上的。
2.6 优点、缺点
优点：
2-3 树在最坏情况下仍有较好的性能。每个操作中处理每个结点的时间都不会超过一个很小的常数，且这两个操作都只会访问一条路径上的结点，所以任何查找或者插入的成本都肯定不会超过对数级别。
完美平衡的 2-3 树要平展的多。例如含有 10 亿个结点的一颗 2-3 树的高度仅在 19 到 30 之间。我们最多只需要访问 30 个结点就能在 10 亿个键中进行任意查找和插入操作。
缺点：
我们需要维护两种不同类型的结点，查找和插入操作的实现需要大量的代码，而且它们所产生的额外开销可能会使算法比标准的二叉查找树更慢。
平衡一棵树的初衷是为了消除最坏情况，但我们希望这种保障所需的代码能够越少越好，越简单越好，显然 2-3 树也不太适合。
既然已经懂了 2-3 树的实现，接下来我们对 2-3 树稍微变型下就是红黑树了，你可以认为红黑树的本质其实是对概念模型 2-3-4 树的一种实现。
3 红黑树
3.1 2-3 树跟红黑树关联
由于直接进行不同节点间的转化会造成较大的开销，所以选择以二叉树为基础，在二叉树的属性中加入一个颜色属性来表示 2-3 树中不同的节点。
2-3 树中的 2 节点对应着红黑树中的黑色节点。
2-3 树中的非 2 节点是以红节点 + 黑节点的方式存在，红节点的意义是与黑色父节点结合，表达着 2-3 树中的 3，4 节点。有的书上把红色说成了红色链接，也是一直理解方法。
先看 2-3 树到红黑树的节点转换。2 节点直接转化为黑色节点。3 节点这里可以有两种表现形式，左倾红节点或者右倾红节点。而 4 节点被强制要求转化为一个黑父带着左右两个红色儿子。
由于 3 节点转化到时候可以左倾也可以右倾，如果查看算法书籍，你会发现为了简单化，算法书籍中统一规定只用左倾红黑树。
红黑树跟 2-3 树转化到时候，可以认为将红色节点顺时针上升 45 度，来跟它到父节点保持平衡，再将红色到跟父节点看作一个整体。
可以发现黑色节点才会真正在 2-3 树中增加高度，所以红黑树的完美平衡其实等价 2-3 树的根节点到叶子节点到距离相等。所以说红黑树是 2-3 树或 2-3-4 树概念模型的一种实现。
在算法导论中红黑树树基于 2-3-4 树实现的。
在算法 4 中红黑树树基于 2-3 树实现的，并且要求 3 节点在红黑树中必须以左倾红色节点来表示。
2-3 树肯定比 2-3-4 树简单，所以接下来主要基于 2-3 树说。
3.2 红黑树基础定义跟旋转
3.2.1 五大法则
节点有黑色跟红色两种：至于为何有红色节点，在 2-3 树中已经说过了。
根节点必须是黑色：2-3 树中如果根节点树 2 节点那本来就是黑色，如果是 3 节点就用大的当黑根节点，小的当左倾红节点。
叶子节点为不存数据且都是黑色：主要是为了在插入跟删除时候方便操作。
任意节点到叶子节点经过的黑色节点数目相同：红黑树中的红节点是和黑色父节点绑定的，在 2-3 树中本来就是同一层的，只有黑色节点才会在 2-3 树中真正贡献高度，由于 2-3 树的任一节点到空链接距离相同，因此反应在红黑树中就是黑色完美平衡。
不会有连续的红色节点：2-3 树中本来就规定没有 4 节点，2-3-4 树中虽然有 4 节点，但是要求在红黑树中体现为一黑色节点带两红色儿子，分布左右，所以也不会有连续红节点。
3.2.2 左旋跟右旋
红黑树要求新插入数据颜色是红色，黑色是改变后的结果。红黑树的核心是左旋跟右旋。
3.3 左倾红黑树插入
左倾红黑树的插入一共有三种可能的情况。
待插入元素比黑父大，插在了黑父的右边，而黑父左边是红色儿子。这种情况会导致在红黑树中出现右倾红节点。或者黑父左边为空也会出现右倾。
待插入元素比红父小，且红父自身就是左倾，待插入数据比红父左节点还小，形成了连续的红节点。
对红父的父亲节点进行一次右旋转。
将数据变化为情况 1 的状态处理。
待插入元素比红父大，且红父自身就是左倾。待插入数据比红父左节点大，形成了右倾。通过左旋变成情况 2 处理。
整体来说左倾红黑树的插入就是这 3 种情况来回切换，最终达到平衡。
3.4 左倾红黑树删除
删除思路是不删除目标数据，而是找到目标数据的前驱节点或后继节点，然后把数据拷贝一份到目标数据进行覆盖。然后转而去删除前驱或后继。删除后再去修补平衡。
从宏观上来看从根节点开始查找，全程利用 2-3 树思维逐层对红黑树调整，每次保证当前节点树 2-3 树中非 2 节点，如果是非 2 节点则看下一层，如果是 2 节点则根据兄弟节点调整。
兄弟节点是 2 节点，从父节点借个数据跟当前节点及兄弟节点形成临时 4 节点。
兄弟节点是非 2 节点，兄弟节点上升一个数据，父节点下降一个数据。
删除后就涉及到数据平衡修复了，还是根据 2-3 树来修复平衡，路上可能会碰到红色右倾节点，遇到就进行一次左旋即可。
3.5 工业级红黑树增加
说下实际工程中红黑树的增删操作，增加主要有 3 种情况：
情况 1：关注节点是 a，它的叔叔节点 d 是红色：
将关注节点 a 的父节点 b、叔叔节点 d 的颜色都设置成黑色。
将关注节点 a 的祖父节点 c 的颜色设置成红色。
关注节点变成 a 的祖父节点 c，实现关注节点的迁移。
跳到情况 2 或情况 3。
情况 2：关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的右子节点：
关注节点变成节点 a 的父节点 b。
围绕新的关注节点 b 左旋。
跳到情况 3。
情况 3：如果关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的左子节点，我们就依次执行下面的操作：
围绕关注节点 a 的祖父节点 c 右旋。
将关注节点 a 的父节点 b、兄弟节点 c 的颜色互换，调整结束。
3.6 工业级红黑树删除
相比插入，删除就难多了！核心思想是找准关注点，根据关注点跟周围节点排布特征按照一定规则调整。主要俩步骤：
针对删除节点调整后仍要满足节点到叶子节点路径包含相同黑色节点。
针对关注节点二次调整，防止出现 2 个红色节点。
算法导论中说如果删除黑节点 X 带来黑色平衡破坏，让 X 的子节点变为黑-黑或红-黑。意思是既然删除了某个黑色节点，那么必然会破坏以这个黑色节点为路径上的黑色平衡，表现为路径中缺少一个黑，所以要想办法补充一个黑色节点(下面会用黑色圆圈表示)。同时如果一个节点既可以红又可以黑，就用红黑两个组成部分表示。
3.6.1 删除第一步
情况 1：要删除的节点是 a，它只有一个子节点 b：
删除节点 a，并且把节点 b 替换到节点 a 的位置，这一部分操作跟普通的二叉查找树的删除操作一样。
节点 a 只能是黑色，节点 b 也只能是红色，其他情况均不符合红黑树的定义。此时把节点 b 改为黑色。调整结束，不需要进行二次调整。
情况 2：要删除的节点 a 有两个非空子节点，并且它的后继节点就是节点 a 的右子节点 c：
如果节点 a 的后继节点就是右子节点 c，那 c 肯定没有左子树。将 c 的颜色变为 a 的颜色，并且用 c 来覆盖 a。
如果节点 c 是黑色，为了不违反红黑树的路径相同原则，给节点 c 的右子节点 d 多加一个黑色圆圈，这个时候节点 d 就成了红 - 黑或者黑 - 黑。
此时关注节点变成了节点 d，第二步的调整操作就会针对关注节点来做。
情况 3：要删除的是节点 a，它有两个非空子节点，并且节点 a 的后继节点不是 a 的右子节点：
找到后继节点 d，并将它删除，删除后继节点 d 的过程参照 CASE 1。
用 d 来替换 a，并且 d 的颜色设置的跟 a 颜色一样。
如果节点 d 是黑色，为了不违反红黑树路径相同原则，给节点 d 的右子节点 c 多加一个黑色，这个时候节点 c 就成了红 - 黑或者黑 - 黑。
此时关注节点变成了节点 c，第二步的调整操作就会针对关注节点来做。
3.6.2 删除第二步
经过初步调整之后，关注节点变成了红 - 黑或者黑 - 黑 节点。针对这个关注节点，再分四种情况来进行二次调整。二次调整是为了让红黑树中不存在相邻的红色节点。
情况 1：关注节点是 a，它的兄弟节点 c 是红色的，我们就依次进行下面的操作：
围绕关注节点 a 的父节点 b 左旋。
关注节点 a 的父节点 b 和祖父节点 c 交换颜色。
关注节点不变，继续从四种情况中选择适合的规则来调整。
情况 2：关注节点是 a，它的兄弟节点 c 是黑色，并且节点 c 的左右子节点 d、e 都是黑色：
将关注节点 a 的兄弟节点 c 的颜色变成红色，因为接下来黑圆圈会上移，那么 c 比 a 多个深色。
从关注节点 a 中去掉一个黑色，此时节点 a 就是单纯的红色或者黑色。
给关注节点 a 的父节点 b 添加一个黑色，这个时候节点 b 就变成红 - 黑或者黑 - 黑
关注节点从 a 变成其父节点 b，继续从四种情况中选择符合的规则来调整。
情况 3：关注节点是 a，它的兄弟节点 c 是黑色，c 的左子节点 d 是红色，c 的右子节点 e 是黑色：
围绕关注节点 a 的兄弟节点 c 右旋。
节点 c 和节点 d 交换颜色。
关注节点不变，跳转到情况 4，继续调整。
情况 4：关注节点 a 的兄弟节点 c 是黑色的，并且 c 的右子节点是红色的，我们就依次进行下面的操作：
围绕关注节点 a 的父节点 b 左旋。
将 b 的颜色复制给 c，因为 c 替代了 b 的位置。
将关注节点 a 的父节点 b 的颜色设置为黑色。
从关注节点 a 中去掉一个黑色，节点 a 就变成了单纯的红色或黑色。
将关注节点 a 的叔叔节点 e 设置为黑色，调整结束。
此时 a 跟 d 深度是一样的，因为无法判别 ad 是否为红，直接将 b 设置为黑的了，此时 e 提高了一度为保持平衡也设置为黑色的了。
3.6.3 删除理解
多画图，不画图单看代码一会儿就眩晕了。
插入跟删除算法都是用到了递推，比如插入情况 1，情况 1 的处理之后，关注节点从本身变成了它的祖父红色节点，这就是往根节点递推。不过情况 1 处理过一次之后，不一定会进入情况 2 或者情况 3，有可能还在情况 1。在情况 1 的情况下一直往根节点走，因为当前节点永远是红色，所以在最后要把根节点涂黑。同时只要进入到情况 2、情况 3 情况，操作就跟上面说过的类似了。
要记住，除了关注的节点所在的子树，其他的子树本身都是一颗红黑树，它们是满足红黑树的所有特征的。当关注节点往根节点递推时，这个时候关注节点的子树也已经满足了红黑树的定义，我们就不用再去特别关注子树的特征。只要注意关注节点往上的部分。这样就能把问题简化，思考的时候思路会清晰一些。
再说到删除算法，注意红-黑跟黑-黑存在的原因，为何最终都会走到从兄弟节点的地方做文章来实现最终的平衡。
删除情况 1 的目的只是为了能够进入接下来的三个情况中。
删除情况 2 的套路又是一个递推思路，关注节点往根节点递推，让其左右子树都满足红黑树的定义。因为往上推，右子树多了一个黑色节点，就把关注节点的兄弟节点变红。
删除情况 3 是为了进入删除情况 4，提前变色的原因和情况 2 是一样的，都是为了满足黑色深度相同。同样是归纳推理的思路。都要记住一点，各种情况下的其他子树节点都满足红黑树的定义，需要分类讨论的，都在这几种情况中了。
可能你看今天看了红黑树的删除你顿悟了，过了半个月又迷糊了。不要怕！因为怕也没用，再看呗。学习红黑树本身也不是为了面试字节去默写，而是去学习思想，锻炼思维，复杂问题简单化，当然了顺带也可以装的一手好 B。
参考资料
推荐一个零声教育 C/C++后台开发的免费公开课程，个人觉得老师讲得不错，分享给大家：C/C++后台开发高级架构师，内容包括Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习
原文：红黑树硬核讲解
还未添加个人签名 2022.05.06 加入
还未添加个人简介
评论