Chapter 2 | Red Black Tree & B+ Tree

Red Black Tree

概述

我们知道 AVL 树在每次操作都对原树进行平衡化操作，从而使得二叉搜索树保持一个相对平衡的状态，避免了链式结构造成的 O(n) 的复杂度。而同样的，红黑树也是一种平衡二叉搜索树，只不过与 AVL 树相比，它们对于“平衡”的定义以及为达到“平衡”采取的策略不同而已。

顾名思义，红黑树 (Red Black Tree) 就是一种节点分类为红黑两色的，比较平衡的二叉搜索树。只不过不同于 AVL 树，红黑树的“平衡”性质是通过黑高 (black height) 来定义的。接下来依次给出红黑树的定义和黑高的定义。

红黑树的定义

黑高的定义

特定节点的黑高，等于该节点到叶结点到简单路径中（不包括自身），黑色节点的数量。

推论

插入

红黑树本质是一种二叉平衡树，因此红黑树的插入按理和二叉搜索树类似，只不过红黑树引入了节点的红黑颜色，所以插入时可能会破坏原树的红黑颜色性质。 那么为了尽可能减少对颜色性质的破坏，我们默认插入的节点是红色节点 -- 因为红色节点的插入不可能破坏黑路同，只可能破坏不红红或根叶黑（事实上大多数情况若原树非空的话，连根叶黑都不会破坏）

如果插入新节点后，红黑树的性质并没有被破坏，那么我们不需要对红黑树进行维护；而如果破坏了红黑树的性质，我们就需要对红黑树做进一步维护。

我们可以将插入的情况分为：

1. 插入节点没有父亲（是根节点）-- 违反根叶黑
2. 插入节点父亲节点是红色节点 -- 违反不红红
3. 插入节点父亲节点是黑色节点 -- 不需要维护

很显然，对上述需要进行维护的 1、2 情况进一步分类，需要维护的情况只有三种：

1. 插入节点是根节点
2. 插入节点父亲红叔叔红
3. 插入节点父亲红叔叔黑

下面我们分别进行讨论

插入节点是根节点

插入节点父亲红叔叔红

插入节点父亲红叔叔黑

归纳总结如下图

*Top-Down 思路

在有了 Bottom-Up Insertion 思路的基础上，Top-Down Insertion 在维护上其实较为简单，这里简单进行说明

在与插入数作比较向下寻找的过程中，当我们发现一个节点 X 具有两个红色孩子，我们就将 X 变为红色，两个孩子变为黑色

而这样的维护可能会对红黑树造成破坏，当 X 的父亲也为红色时，就违反了“不红红”的性质，那么我们就只需要根据先前提到的 " 插入节点父亲红叔叔黑”的情况进行 Zig Rotation or Zig-zag Rotation（由于我们自顶向下的维护，不可能出现父亲红叔叔也红的情况，因为如果出现会在这次维护前先被维护）

这样的 Top-Down 的思路在算法实现上就只需要另外记下每次递归向下的 cur，father，grandfather 即可；就不需要在初始化时增加每个节点的 parent 指针，或是令设一个 log(n) 大小的栈来存储整条路的节点指针

构建

红黑树的构建其实就是节点的依次插入，可以作为插入操作的复习参考

下面的这个视频就比较生动地诠释了红黑树的构建过程

👉红黑树的构建（自视频 10:52 起）

删除

关于删除操作可以参考这个视频，下文也是依此归纳 👉红黑树 - 删除

要删除某个节点 x，我们首先要找到它，在 BST 中找到某个 x 的开销为 O(log⁡N)。接下来我们要删除这个任意位置的节点，由于红黑树的本质是一种二叉搜索树，所以对需要删除节点所做的“数”上的操作是相同的，只不过需要维护颜色上的性质

我们可以仿照二叉搜索树的删除将情况分类如下：

有两个非 NIL 子节点的情况总是会递归地转换成没有非 NIL 子节点和只有一个非 NIL 子节点的情况，因此我们实际上只需要对这两类情况做讨论

只有左孩子 / 右孩子

没有孩子

若删除节点没有孩子，我们需要根据该节点的红黑做进一步讨论

节点为红

这是一种平凡的情况，删除后无需做任何调整

节点为黑

我们对被删除节点的 sibling 兄弟节点继续分类

兄弟为黑且有红孩

兄弟为黑且无红孩

兄弟为红

总结

可以参照这个删除案例的动画做复习巩固 👉红黑树删除 - 案例 自视频 20:41

*B Tree

概述

所以简单来说就是通过降低树高来减少硬盘读取次数，从而提高访问效率

性质

在 B 树中，有两种节点：

1. 内部节点：存储了数据以及指向其子节点的指针。
2. 外部节点 / 失败节点：与内部节点不同的是，外部节点不存储数据，只是为了查找时方便表示查找失败，在通常情况下省略

一棵 m 阶 B 树满足的性质如下：

• 平衡性：所有的叶子节点都在同一层
• 有序性：节点内部有序，任一元素的左子树都大于它，右子树都小于它
• 多路性: 对于 m 阶 B 树的节点
  • 分支数 = 元素数 +1
  • 最多 \(m\) 个分支，\(m-1\) 个元素
  • 普通节点最少 \(\lceil{\frac{m}{2}}\rceil\) 个分支，\(\lceil{\frac{m}{2}}\rceil-1\) 个元素；根节点最少 2 个分支，1 个元素

一个简单的 5 阶 B 树的图例如下 :

插入

针对 m 阶高度 h 的 B 树，插入一个元素时，首先判断在 B 树中是否存在，如果不存在，即在叶子结点处结束，然后在叶子结点中插入该新的元素。

1. 若该节点元素个数小于 m-1，直接插入；
2. 若该节点元素个数等于 m-1，插入后该节点元素个数变为 m，引起节点上溢出；进行分裂操作：以该节点中间元素为分界，取中间元素（即第 \(\lceil{\frac{m}{2}}\rceil\) 个元素），插入到父节点中（此时父节点也可能上溢出）；
3. 重复上面动作，直到所有节点符合 B 树的规则；最坏的情况一直分裂到根节点，生成新的根节点，高度增加 1；

详细过程可以参照这个视频 👉B 树 (B- 树 ) - 来由 , 定义 , 插入 , 构建

删除

删除非叶节点元素类似于二叉搜索树，找到它的直接前驱或直接后继替代它，再删除直接前驱或直接后驱

因此删除非叶节点元素最终都转换成删除叶节点元素

删除叶结点元素的大致流程如下：具体可以参照👉B 树 (B- 树 ) - 删除

graph LR
    A("叶结点元素")
    B("没有下溢出：**无需调整**")
    C("下溢出")
    D("兄弟够借：**向左或右借**")
    E("兄弟不够借：**合并**")
    F("**父下来 兄上去**")
    G("**父下移到左，右并过来**
    or
    **父下移到右，左并过来**")
    H("**父亲是否下溢出？**")
    A-->B
    A-->C
    C-->D
    C-->E
    D-->F
    E-->G
    G-->H
    H-->C

B Tree & Red Black Tree

B 树有很多特殊形式，比如 3 阶 B 树（又称 2-3 树），比如 4 阶 B 树（又称 2-3-4 树 or 2-4 树）。与一般的 B 树一样，它们都可以实现在 \(O(\log n)\) 时间内进行搜索、插入和删除操作。

而其中 ,2-3-4 树和红黑树是同构，任意一棵红黑树都唯一对应一棵 2-3-4 树。在 2-3-4 树上的插入和删除操作导致节点的扩展、分裂和合并，相当于红黑树中的变色和旋转。下图是 2-3-4 树的 2 节点、3 节点和 4 节点对应的红黑树节点。注意到 2-3-4 树的 3 节点对应红黑树中红色节点左偏和右偏两种情况，所以一棵红黑树可能对应多棵 2-3-4 树。

下图是一棵红黑树和与之对应的 2-3-4 树。将红黑树中的红色节点上移到父节点的左右两侧，形成一个 B 树节点，就可以得到与之对应的 2-3-4 树。可以发现，红黑树的节点数等于 2-3-4 树的节点个数

B+ Tree

概述

前面将得到的 B 树可以像二叉搜索树那样快速的查找到一个元素，这种查找过程又叫做随机查找，当我们要按照顺序去遍历所有元素时，就要采取中序遍历的方法，在节点之间来回移动，效率较低，而 B+ 树正是解决了这个问题而诞生，被广泛作为数据库的索引结构

叶结点包含了所有的关键字，若要顺序查找所有关键字对应的记录，可以像遍历链表一样逐一查找；非叶子结点可以帮助我们快速的定位到叶子节点层上的关键字，相当于为叶子结点层建立了索引，以 log(n) 级别的复杂度查找到关键字

事实上，整套 B+ 树是一个多级索引结构，叶结点层是对它指向记录的索引，中间层非叶节点是对叶结点层关键字的索引，再上一层是对下一层这些索引项的索引 ... 直到 root；而先前的 B 树若作为索引结构，相当于每个节点的关键字都对应了一条记录

将 B 树和 B+ 树做对比我们发现：

B 树所有结点的关键字都有直接指向对应记录的指针；B+ 树叶结点包含全部关键字及指向相应记录的指针，非叶节点只作索引

B 树顺序查找或范围查找只能中序遍历，效率低；B+ 树兼顾顺序查找和随机查找，还可以方便地进行范围查找

性质

从名字上来看，B+ 树和 B 树非常相似，而一般地来说，B+ 树满足如下性质：( 实际就是上面提到的 B 树的 " 多路性 "-- 稍有不同 )

例如下图就是一棵 M = 4 的 B+ 树

所有真实的数据都被存储在叶子结点中，形成一个有序的数列。而非叶子结点中第 i 个键值等于其第 i+1 棵子树的最小值（在上图中表现为颜色相同的一对上下结点），因此非叶结点最多存 M−1 个值。

查找

类似于二叉搜索树的查找，比较简单，不赘述

插入

B+ 树的插入算法与 B 树的相近：

• 若为空树，创建一个叶子节点，然后将记录插入其中，此时这个叶子节点也是根节点，插入操作结束。

• 针对叶子类型节点：根据关键字找到叶子节点，向这个叶子节点插入记录。插入后，若当前节点关键字的个数小于等于 m ，则插入结束。否则发生了上溢出，执行分裂操作：将这个叶子节点分裂成左右两个叶子节点，左叶子节点包含（\(\lceil \frac {m+1} 2 \rceil\)）个记录，右节点包含剩下的记录，将第（\(\lceil \frac {m+1} 2 \rceil + 1\)）个记录的关键字进位到父节点中（父节点一定是索引类型节点），进位到父节点的关键字左孩子指针向左节点，右孩子指针向右节点。将当前节点的指针指向父节点，然后执行第 3 步。

• 针对索引类型节点（内部节点）：若当前节点关键字的个数小于等于 m-1 ，则插入结束。否则发生了上溢出，执行分裂操作：将这个索引类型节点分裂成两个索引节点，左索引节点包含 \(\lceil \frac {m} 2 \rceil\)key，右节点包含除中间位置（\(\lceil \frac {m} 2 \rceil + 1\)）外剩下的 key，将中间位置的关键字进位到父节点中，进位到父节点的关键字左孩子指向左节点，进位到父节点的关键字右孩子指向右节点。将当前节点的指针指向父节点，然后重复这一步。

可以参考下面的案例加深理解

* 删除

B+ 树的删除也仅在叶子节点中进行，当叶子节点中的最大关键字被删除时，其在非叶子节点中的值可以作为一个分界关键字存在。若因删除而使节点中关键字的个数少于 \(\lceil \dfrac{m}{2} \rceil\) 时，其和兄弟节点的合并过程亦和 B 树类似。

具体步骤如下：

首先查询到键值所在的叶子节点，删除该叶子节点的数据。

如果删除叶子节点之后的数据数量，满足 B+ 树的平衡条件，则不做平衡操作。但是如果删除的叶子节点数据是最小数，则要更新父节点中对应的值。

否则，就需要做平衡操作：如果该叶子节点的左右兄弟节点的数据量可以借用，就借用过来满足平衡条件。否则，就与相邻的兄弟节点合并成一个新的子节点了。

在上面平衡操作中，如果是进行了合并操作，就需要向上修正父节点的指针：删除被合并节点的键值以及指针。

由于做了删除操作，可能父节点也会不平衡，那么就按照前面的步骤也对父节点进行重新平衡操作，这样一直到某个节点平衡为止。

结合具体案例说明会更清晰一些