红黑树硬核讲解

2022-09-20 16:30:58 浏览数 (1)

1 引言

预防针：红黑树本来就是基本算法中的难点，所以看此文时建议先有点预备心理或知识铺垫，没接触过RBT而直接看此文的话，绝对懵逼。

为了数据的查询跟增删方便，系统引入了二叉查找树，它具有左节点 < 根节点 <右节点 的属性，

二叉查找树(大于跟小于界线应为8，不是12) 但是这种设定跟数据的插入顺序有很大关系，比如你插入的是1234，二叉查找树会退化为链表。

链表 为了避免链表结构的出现，研究者们又提出了平衡二叉树跟红黑树。平衡二叉树要求任意一个节点的左深度跟右深度差值绝对值不能大于1，如果插入后超过了1会通过左右各种旋转来更改连接的变化，最终实现左右深度差不大于1的这个要求。

平衡二叉树的深度要求太过完美，当涉及大量增删时，可能会太多时间用在调节平衡上，为了平衡投入跟产出比，又设计了红黑树。

红黑树算是一个比较复杂的数据结构了，除非你面字节，可能让你手写红黑树。一般情况下你只要说出红黑树构造的五大背后逻辑，展现你对底层数据结构的深度跟广度即可。

本文不会着重说红黑树的增删过程，因为你百度看下权威教程或源码，然后跟着追踪就知道大致流程了，本文会说下红黑树为何如此设计，它跟2-3树有啥联系。

2 2-3 树

2.1 定义

为了保证查找树的平衡性，需要一些灵活性，因此我们允许树中的一个结点保存多个键。

  1. 2结点：含有一个键和两条链接，左链接指向的2-3树中的键都小于该结点，右链接指向的2-3树中的键都大于该结点。
  2. 3结点：含有两个键和三条链接，左链接指向的2-3树中的键都小于该结点，中链接指向的2-3树中的键都位于该结点的两个键之间，右链接指向的2-3树中的键都大于该结点。
  3. 4节点：含有三个键和四条链接，大致的思路跟3节点类似。需注意在2-3树中，4节点是短暂存在的，会被转化为2节点或3节点。

2-3-4节点

2.2 查找

要判断一个键是否在树中，我们先将它和根结点中的键比较。如果它和其中的任何一个相等，查找命中。否则我们就根据比较的结果找到指向相应区间的链接，并在其指向的子树中递归地继续查找。如果这是个空链接，查找未命中，可以发现跟简单的二叉树查找类似。

2.3 插入

要在2-3树中插入一个新结点，我们可以和二叉查找树一样先进行一次未命中的查找，然后把新结点挂在树的底部。但这样的话树无法保持完美平衡性。使用2-3树的主要原因就在于它能够在插入之后继续保持平衡。

  1. 如果未命中的查找结束于一个2结点：只要把这个2结点替换为一个3结点，将要插入的键保存在其中即可。
  2. 只有一个3结点的树，向其插入一个新数据：此时我们可以创建个临时4节点，然后将其转化为由3个2节点组成的2-3树

只有3节点树插入数据

  1. 向一个父结点为2结点的3结点中插入新键：此时先将组成个临时4节点，然后将中间数提到上面跟父节点融合为一个3节点，这样树的高度没变。

插入25

  1. 向一个父结点为3结点的3结点中插入新键4：跟上面套路类似，不断将中位数的数据往上提，直到遇到个2节点，或者到达了根节点然后进行拆分。

插入4

插入总结：

  1. 先找插入结点，若结点是2结点，则直接插入。如结点3结点，则插入使其临时容纳这个元素，然后分裂此结点，把中间元素移到其父结点中。对父结点亦如此处理。（中键一直往上移，直到找到空位，在此过程中没有空位就先搞个临时的，再分裂。）
  2. 2-3树插入算法的根本在于这些变换都是局部的：除了相关的结点和链接之外不必修改或者检查树的其他部分。每次变换中，变更的链接数量不会超过一个很小的常数。所有局部变换都不会影响整棵树的有序性和平衡性。

2.4 删除

2-3树的删除分为两种情况。

  1. 如果待删除元素在3节点，那么可以直接将这个元素删除，删除这个元素不会引起高度的变化。

删除3节点中数据

  1. 当待删除元素在2节点时，由于删除这个元素会导致2节点失去唯一的元素，引发树中某条路径的高度发生变化，为维持平衡，此时有两种方法。

  1. 先删除再对2-3树进行平衡调整。
  2. 想办法让这个被删除的元素不可能出现在2节点中。如果发现删除元素树2节点则会从兄弟节点或父节点借个元素，当前2节点变为3节点或临时4节点，然后再删除目标数据。

2节点情况下删除目标数据2

2.5 构造

和标准的二叉查找树由上向下生长不同，2-3树的生长是由下向上的。

插入

2.6 优点、缺点

优点：

  1. 2-3树在最坏情况下仍有较好的性能。每个操作中处理每个结点的时间都不会超过一个很小的常数，且这两个操作都只会访问一条路径上的结点，所以任何查找或者插入的成本都肯定不会超过对数级别。
  2. 完美平衡的2-3树要平展的多。例如含有10亿个结点的一颗2-3树的高度仅在19到30之间。我们最多只需要访问30个结点就能在10亿个键中进行任意查找和插入操作。

缺点：

  1. 我们需要维护两种不同类型的结点，查找和插入操作的实现需要大量的代码，而且它们所产生的额外开销可能会使算法比标准的二叉查找树更慢。
  2. 平衡一棵树的初衷是为了消除最坏情况，但我们希望这种保障所需的代码能够越少越好，越简单越好，显然2-3树也不太适合。

既然已经懂了2-3树的实现，接下来我们对2-3树稍微变型下就是红黑树了，你可以认为红黑树的本质其实是对概念模型2-3-4树的一种实现。

3 红黑树

3.1 2-3树跟红黑树关联

由于直接进行不同节点间的转化会造成较大的开销，所以选择以二叉树为基础，在二叉树的属性中加入一个颜色属性来表示2-3树中不同的节点。

  1. 2-3树中的2节点对应着红黑树中的黑色节点。
  2. 2-3树中的非2节点是以红节点 黑节点的方式存在，红节点的意义是与黑色父节点结合，表达着2-3树中的3，4节点。有的书上把红色说成了红色链接，也是一直理解方法。

先看2-3树到红黑树的节点转换。2节点直接转化为黑色节点。3节点这里可以有两种表现形式，左倾红节点或者右倾红节点。而4节点被强制要求转化为一个黑父带着左右两个红色儿子。

23树到红黑树转变 由于3节点转化到时候可以左倾也可以右倾，如果查看算法书籍，你会发现为了简单化，算法书籍中统一规定只用左倾红黑树。

红黑树跟2-3树转化到时候，可以认为将红色节点顺时针上升45度，来跟它到父节点保持平衡，再将红色到跟父节点看作一个整体。

红黑树转2-3树 可以发现黑色节点才会真正在2-3树中增加高度，所以红黑树的完美平衡其实等价2-3树的根节点到叶子节点到距离相等。所以说红黑树是2-3树或2-3-4树概念模型的一种实现。

  1. 在算法导论中红黑树树基于2-3-4树实现的。
  2. 在算法4中红黑树树基于2-3树实现的，并且要求3节点在红黑树中必须以左倾红色节点来表示。
  3. 2-3树肯定比2-3-4树简单，所以接下来主要基于2-3树说。

3.2 红黑树基础定义跟旋转

3.2.1 五大法则
  1. 节点有黑色跟红色两种：至于为何有红色节点，在2-3树中已经说过了。
  2. 根节点必须是黑色：2-3树中如果根节点树2节点那本来就是黑色，如果是3节点就用大的当黑根节点，小的当左倾红节点。
  3. 叶子节点为不存数据且都是黑色：主要是为了在插入跟删除时候方便操作。
  4. 任意节点到叶子节点经过的黑色节点数目相同：红黑树中的红节点是和黑色父节点绑定的，在2-3树中本来就是同一层的，只有黑色节点才会在2-3树中真正贡献高度，由于2-3树的任一节点到空链接距离相同，因此反应在红黑树中就是黑色完美平衡。
  5. 不会有连续的红色节点：2-3树中本来就规定没有4节点，2-3-4树中虽然有4节点，但是要求在红黑树中体现为一黑色节点带两红色儿子，分布左右，所以也不会有连续红节点。
3.2.2 左旋跟右旋

红黑树要求新插入数据颜色是红色，黑色是改变后的结果。红黑树的核心是左旋跟右旋。

左旋跟右旋

3.3 左倾红黑树插入

左倾红黑树的插入一共有三种可能的情况。

  1. 待插入元素比黑父大，插在了黑父的右边，而黑父左边是红色儿子。这种情况会导致在红黑树中出现右倾红节点。或者黑父左边为空也会出现右倾。

插入20

  1. 待插入元素比红父小，且红父自身就是左倾，待插入数据比红父左节点还小，形成了连续的红节点。

  1. 对红父的父亲节点进行一次右旋转。
  2. 将数据变化为情况1的状态处理。

插入14

  1. 待插入元素比红父大，且红父自身就是左倾。待插入数据比红父左节点大，形成了右倾。通过左旋变成情况2处理。

插入17 整体来说左倾红黑树的插入就是这3种情况来回切换，最终达到平衡。

3.4 左倾红黑树删除

删除思路是不删除目标数据，而是找到目标数据的前驱节点或后继节点，然后把数据拷贝一份到目标数据进行覆盖。然后转而去删除前驱或后继。删除后再去修补平衡。

从宏观上来看从根节点开始查找，全程利用2-3树思维逐层对红黑树调整，每次保证当前节点树2-3树中非2节点，如果是非2节点则看下一层，如果是2节点则根据兄弟节点调整。

  1. 兄弟节点是2节点，从父节点借个数据跟当前节点及兄弟节点形成临时4节点。
  2. 兄弟节点是非2节点，兄弟节点上升一个数据，父节点下降一个数据。

删除目标1

删除后就涉及到数据平衡修复了，还是根据2-3树来修复平衡，路上可能会碰到红色右倾节点，遇到就进行一次左旋即可。

2-3树修补工作

3.5 工业级红黑树增加

这里其实主要参考极客时间小争哥的文章，说下实际工程中红黑树的增删操作，增加主要有3种情况：

情况1

情况1：关注节点是 a，它的叔叔节点 d 是红色：

  1. 将关注节点 a 的父节点 b、叔叔节点 d 的颜色都设置成黑色。
  2. 将关注节点 a 的祖父节点 c 的颜色设置成红色。
  3. 关注节点变成 a 的祖父节点 c，实现关注节点的迁移。
  4. 跳到情况2或情况3。

情况2 情况2：关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的右子节点：

  1. 关注节点变成节点 a 的父节点 b。
  2. 围绕新的关注节点 b 左旋。
  3. 跳到情况3。

情况3

情况3：如果关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的左子节点，我们就依次执行下面的操作：

  1. 围绕关注节点 a 的祖父节点 c 右旋。
  2. 将关注节点 a 的父节点 b、兄弟节点 c 的颜色互换，调整结束。

3.6 工业级红黑树删除

相比插入，删除就难多了！核心思想是找准关注点，根据关注点跟周围节点排布特征按照一定规则调整。主要俩步骤：

  1. 针对删除节点调整后仍要满足节点到叶子节点路径包含相同黑色节点。
  2. 针对关注节点二次调整，防止出现2个红色节点。

算法导论中说如果删除黑节点X带来黑色平衡破坏，让X的子节点变为黑-黑或红-黑。意思是既然删除了某个黑色节点，那么必然会破坏以这个黑色节点为路径上的黑色平衡，表现为路径中缺少一个黑，所以要想办法补充一个黑色节点(下面会用黑色圆圈表示)。同时如果一个节点既可以红又可以黑，就用红黑两个组成部分表示。

3.6.1 删除第一步

情况1 情况1：要删除的节点是 a，它只有一个子节点 b：

  1. 删除节点 a，并且把节点 b 替换到节点 a 的位置，这一部分操作跟普通的二叉查找树的删除操作一样。
  2. 节点 a 只能是黑色，节点 b 也只能是红色，其他情况均不符合红黑树的定义。此时把节点 b 改为黑色。调整结束，不需要进行二次调整。

情况2 情况2：要删除的节点 a 有两个非空子节点，并且它的后继节点就是节点 a 的右子节点 c：

  1. 如果节点 a 的后继节点就是右子节点 c，那 c 肯定没有左子树。将c的颜色变为a的颜色，并且用c来覆盖a。
  2. 如果节点 c 是黑色，为了不违反红黑树的路径相同原则，给节点 c 的右子节点 d 多加一个黑色圆圈，这个时候节点 d 就成了红 - 黑或者黑 - 黑。
  3. 此时关注节点变成了节点 d，第二步的调整操作就会针对关注节点来做。

情况3 情况3：要删除的是节点 a，它有两个非空子节点，并且节点 a 的后继节点不是a的右子节点：

  1. 找到后继节点 d，并将它删除，删除后继节点 d 的过程参照 CASE 1。
  2. 用d来替换a，并且d的颜色设置的跟a颜色一样。
  3. 如果节点 d 是黑色，为了不违反红黑树路径相同原则，给节点 d 的右子节点 c 多加一个黑色，这个时候节点 c 就成了红 - 黑或者黑 - 黑。
  4. 此时关注节点变成了节点 c，第二步的调整操作就会针对关注节点来做。
3.6.2 删除第二步

经过初步调整之后，关注节点变成了红 - 黑或者黑 - 黑 节点。针对这个关注节点，再分四种情况来进行二次调整。二次调整是为了让红黑树中不存在相邻的红色节点。

情况1 情况1：关注节点是 a，它的兄弟节点 c 是红色的，我们就依次进行下面的操作：

  1. 围绕关注节点 a 的父节点 b 左旋。
  2. 关注节点 a 的父节点 b 和祖父节点 c 交换颜色。
  3. 关注节点不变，继续从四种情况中选择适合的规则来调整。

情况2 情况2：关注节点是 a，它的兄弟节点 c 是黑色，并且节点 c 的左右子节点 d、e 都是黑色：

  1. 将关注节点 a 的兄弟节点 c 的颜色变成红色，因为接下来黑圆圈会上移，那么c比a多个深色。
  2. 从关注节点 a 中去掉一个黑色，此时节点 a 就是单纯的红色或者黑色。
  3. 给关注节点 a 的父节点 b 添加一个黑色，这个时候节点 b 就变成红 - 黑或者黑 - 黑
  4. 关注节点从 a 变成其父节点 b，继续从四种情况中选择符合的规则来调整。

情况3

情况3：关注节点是 a，它的兄弟节点 c 是黑色，c 的左子节点 d 是红色，c 的右子节点 e 是黑色：

  1. 围绕关注节点 a 的兄弟节点 c 右旋。
  2. 节点 c 和节点 d 交换颜色。
  3. 关注节点不变，跳转到情况4，继续调整。

情况4

情况4：关注节点 a 的兄弟节点 c 是黑色的，并且 c 的右子节点是红色的，我们就依次进行下面的操作：

  1. 围绕关注节点 a 的父节点 b 左旋。
  2. 将b的颜色复制给c，因为c替代了b的位置。
  3. 将关注节点 a 的父节点 b 的颜色设置为黑色。
  4. 从关注节点 a 中去掉一个黑色，节点 a 就变成了单纯的红色或黑色。
  5. 将关注节点 a 的叔叔节点 e 设置为黑色，调整结束。
  6. 此时a跟d深度是一样的，因为无法判别ad是否为红，直接将b设置为黑的了，此时e提高了一度为保持平衡也设置为黑色的了。
3.6.3 删除理解
  1. 多画图，不画图单看代码一会儿就眩晕了。
  2. 插入跟删除算法都是用到了递推，比如插入情况1，情况1的处理之后，关注节点从本身变成了它的祖父红色节点，这就是往根节点递推。不过情况1处理过一次之后，不一定会进入情况2或者情况3，有可能还在情况1。在情况1的情况下一直往根节点走，因为当前节点永远是红色，所以在最后要把根节点涂黑。同时只要进入到情况2、情况3情况，操作就跟上面说过的类似了。
  3. 要记住，除了关注的节点所在的子树，其他的子树本身都是一颗红黑树，它们是满足红黑树的所有特征的。当关注节点往根节点递推时，这个时候关注节点的子树也已经满足了红黑树的定义，我们就不用再去特别关注子树的特征。只要注意关注节点往上的部分。这样就能把问题简化，思考的时候思路会清晰一些。
  4. 再说到删除算法，注意红-黑跟黑-黑存在的原因，为何最终都会走到从兄弟节点的地方做文章来实现最终的平衡。
  5. 删除情况1的目的只是为了能够进入接下来的三个情况中。
  6. 删除情况2的套路又是一个递推思路，关注节点往根节点递推，让其左右子树都满足红黑树的定义。因为往上推，右子树多了一个黑色节点，就把关注节点的兄弟节点变红。
  7. 删除情况3是为了进入删除情况4，提前变色的原因和情况2是一样的，都是为了满足黑色深度相同。同样是归纳推理的思路。都要记住一点，各种情况下的其他子树节点都满足红黑树的定义，需要分类讨论的，都在这几种情况中了。
  8. 可能你看今天看了红黑树的删除你顿悟了，过了半个月又迷糊了。不要怕！因为怕也没用，再看呗。学习红黑树本身也不是为了面试字节去默写，而是去学习思想，锻炼思维，复杂问题简单化，当然了顺带也可以装的一手好B。

4 总结

本文的重点不在于讲解工业化红黑树的删除跟插入全部过程，只是希望通过2-3树跟左倾红黑树的增删，让大家从本质上理解下红黑树的操作来源。其中工业化删除部分已征得小争哥同意，如果理解了上面的内容，那么你再去看工业化红黑树的操作就手到擒来了。

参考

  1. 红黑树在线演示：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
  2. 2-3树到红黑树讲解：https://blog.csdn.net/qq_35190492/article/details/109503539
  3. 小争哥极客时间红黑树：https://time.geekbang.org/column/article/68976
编程算法 二叉树

0 人点赞