1 引言预防针红黑树本来就是基本算法中的难点所以看此文时建议先有点预备心理或知识铺垫没接触过RBT而直接看此文的话绝对懵逼。为了数据的查询跟增删方便系统引入了二叉查找树它具有左节点 根节点 右节点的属性二叉查找树(大于跟小于界线应为8不是12)但是这种设定跟数据的插入顺序有很大关系比如你插入的是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-3-4节点2.2 查找要判断一个键是否在树中我们先将它和根结点中的键比较。如果它和其中的任何一个相等查找命中。否则我们就根据比较的结果找到指向相应区间的链接并在其指向的子树中递归地继续查找。如果这是个空链接查找未命中可以发现跟简单的二叉树查找类似。2.3 插入要在2-3树中插入一个新结点我们可以和二叉查找树一样先进行一次未命中的查找然后把新结点挂在树的底部。但这样的话树无法保持完美平衡性。使用2-3树的主要原因就在于它能够在插入之后继续保持平衡。如果未命中的查找结束于一个2结点只要把这个2结点替换为一个3结点将要插入的键保存在其中即可。只有一个3结点的树向其插入一个新数据此时我们可以创建个临时4节点然后将其转化为由3个2节点组成的2-3树只有3节点树插入数据向一个父结点为2结点的3结点中插入新键此时先将组成个临时4节点然后将中间数提到上面跟父节点融合为一个3节点这样树的高度没变。插入25向一个父结点为3结点的3结点中插入新键4跟上面套路类似不断将中位数的数据往上提直到遇到个2节点或者到达了根节点然后进行拆分。插入4插入总结先找插入结点若结点是2结点则直接插入。如结点3结点则插入使其临时容纳这个元素然后分裂此结点把中间元素移到其父结点中。对父结点亦如此处理。中键一直往上移直到找到空位在此过程中没有空位就先搞个临时的再分裂。2-3树插入算法的根本在于这些变换都是局部的除了相关的结点和链接之外不必修改或者检查树的其他部分。每次变换中变更的链接数量不会超过一个很小的常数。所有局部变换都不会影响整棵树的有序性和平衡性。2.4 删除2-3树的删除分为两种情况。如果待删除元素在3节点那么可以直接将这个元素删除删除这个元素不会引起高度的变化。删除3节点中数据当待删除元素在2节点时由于删除这个元素会导致2节点失去唯一的元素引发树中某条路径的高度发生变化为维持平衡此时有两种方法。先删除再对2-3树进行平衡调整。想办法让这个被删除的元素不可能出现在2节点中。如果发现删除元素树2节点则会从兄弟节点或父节点借个元素当前2节点变为3节点或临时4节点然后再删除目标数据。2节点情况下删除目标数据22.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树中的34节点。有的书上把红色说成了红色链接也是一直理解方法。先看2-3树到红黑树的节点转换。2节点直接转化为黑色节点。3节点这里可以有两种表现形式左倾红节点或者右倾红节点。而4节点被强制要求转化为一个黑父带着左右两个红色儿子。23树到红黑树转变由于3节点转化到时候可以左倾也可以右倾如果查看算法书籍你会发现为了简单化算法书籍中统一规定只用左倾红黑树。红黑树跟2-3树转化到时候可以认为将红色节点顺时针上升45度来跟它到父节点保持平衡再将红色到跟父节点看作一个整体。红黑树转2-3树可以发现黑色节点才会真正在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 左倾红黑树插入左倾红黑树的插入一共有三种可能的情况。待插入元素比黑父大插在了黑父的右边而黑父左边是红色儿子。这种情况会导致在红黑树中出现右倾红节点。或者黑父左边为空也会出现右倾。插入20待插入元素比红父小且红父自身就是左倾待插入数据比红父左节点还小形成了连续的红节点。对红父的父亲节点进行一次右旋转。将数据变化为情况1的状态处理。插入14待插入元素比红父大且红父自身就是左倾。待插入数据比红父左节点大形成了右倾。通过左旋变成情况2处理。插入17整体来说左倾红黑树的插入就是这3种情况来回切换最终达到平衡。3.4 左倾红黑树删除删除思路是不删除目标数据而是找到目标数据的前驱节点或后继节点然后把数据拷贝一份到目标数据进行覆盖。然后转而去删除前驱或后继。删除后再去修补平衡。从宏观上来看从根节点开始查找全程利用2-3树思维逐层对红黑树调整每次保证当前节点树2-3树中非2节点如果是非2节点则看下一层如果是2节点则根据兄弟节点调整。兄弟节点是2节点从父节点借个数据跟当前节点及兄弟节点形成临时4节点。兄弟节点是非2节点兄弟节点上升一个数据父节点下降一个数据。删除目标1删除后就涉及到数据平衡修复了还是根据2-3树来修复平衡路上可能会碰到红色右倾节点遇到就进行一次左旋即可。2-3树修补工作3.5 工业级红黑树增加这里其实主要参考极客时间小争哥的文章说下实际工程中红黑树的增删操作增加主要有3种情况情况1情况1关注节点是 a它的叔叔节点 d 是红色将关注节点 a 的父节点 b、叔叔节点 d 的颜色都设置成黑色。将关注节点 a 的祖父节点 c 的颜色设置成红色。关注节点变成 a 的祖父节点 c实现关注节点的迁移。跳到情况2或情况3。情况2情况2关注节点是 a它的叔叔节点 d 是黑色关注节点 a 是其父节点 b 的右子节点关注节点变成节点 a 的父节点 b。围绕新的关注节点 b 左旋。跳到情况3。情况3情况3如果关注节点是 a它的叔叔节点 d 是黑色关注节点 a 是其父节点 b 的左子节点我们就依次执行下面的操作围绕关注节点 a 的祖父节点 c 右旋。将关注节点 a 的父节点 b、兄弟节点 c 的颜色互换调整结束。3.6 工业级红黑树删除相比插入删除就难多了核心思想是找准关注点根据关注点跟周围节点排布特征按照一定规则调整。主要俩步骤针对删除节点调整后仍要满足节点到叶子节点路径包含相同黑色节点。针对关注节点二次调整防止出现2个红色节点。算法导论中说如果删除黑节点X带来黑色平衡破坏让X的子节点变为黑-黑或红-黑。意思是既然删除了某个黑色节点那么必然会破坏以这个黑色节点为路径上的黑色平衡表现为路径中缺少一个黑所以要想办法补充一个黑色节点(下面会用黑色圆圈表示)。同时如果一个节点既可以红又可以黑就用红黑两个组成部分表示。3.6.1 删除第一步情况1情况1要删除的节点是 a它只有一个子节点 b删除节点 a并且把节点 b 替换到节点 a 的位置这一部分操作跟普通的二叉查找树的删除操作一样。节点 a 只能是黑色节点 b 也只能是红色其他情况均不符合红黑树的定义。此时把节点 b 改为黑色。调整结束不需要进行二次调整。情况2情况2要删除的节点 a 有两个非空子节点并且它的后继节点就是节点 a 的右子节点 c如果节点 a 的后继节点就是右子节点 c那 c 肯定没有左子树。将c的颜色变为a的颜色并且用c来覆盖a。如果节点 c 是黑色为了不违反红黑树的路径相同原则给节点 c 的右子节点 d 多加一个黑色圆圈这个时候节点 d 就成了红 - 黑或者黑 - 黑。此时关注节点变成了节点 d第二步的调整操作就会针对关注节点来做。情况3情况3要删除的是节点 a它有两个非空子节点并且节点 a 的后继节点不是a的右子节点找到后继节点 d并将它删除删除后继节点 d 的过程参照 CASE 1。用d来替换a并且d的颜色设置的跟a颜色一样。如果节点 d 是黑色为了不违反红黑树路径相同原则给节点 d 的右子节点 c 多加一个黑色这个时候节点 c 就成了红 - 黑或者黑 - 黑。此时关注节点变成了节点 c第二步的调整操作就会针对关注节点来做。3.6.2 删除第二步经过初步调整之后关注节点变成了红 - 黑或者黑 - 黑节点。针对这个关注节点再分四种情况来进行二次调整。二次调整是为了让红黑树中不存在相邻的红色节点。情况1情况1关注节点是 a它的兄弟节点 c 是红色的我们就依次进行下面的操作围绕关注节点 a 的父节点 b 左旋。关注节点 a 的父节点 b 和祖父节点 c 交换颜色。关注节点不变继续从四种情况中选择适合的规则来调整。情况2情况2关注节点是 a它的兄弟节点 c 是黑色并且节点 c 的左右子节点 d、e 都是黑色将关注节点 a 的兄弟节点 c 的颜色变成红色因为接下来黑圆圈会上移那么c比a多个深色。从关注节点 a 中去掉一个黑色此时节点 a 就是单纯的红色或者黑色。给关注节点 a 的父节点 b 添加一个黑色这个时候节点 b 就变成红 - 黑或者黑 - 黑关注节点从 a 变成其父节点 b继续从四种情况中选择符合的规则来调整。情况3情况3关注节点是 a它的兄弟节点 c 是黑色c 的左子节点 d 是红色c 的右子节点 e 是黑色围绕关注节点 a 的兄弟节点 c 右旋。节点 c 和节点 d 交换颜色。关注节点不变跳转到情况4继续调整。情况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。4 总结本文的重点不在于讲解工业化红黑树的删除跟插入全部过程只是希望通过2-3树跟左倾红黑树的增删让大家从本质上理解下红黑树的操作来源。其中工业化删除部分已征得小争哥同意如果理解了上面的内容那么你再去看工业化红黑树的操作就手到擒来了。