Lec 2: Red-Black Trees and B+ Trees⚓︎

Red-Black Trees⚓︎

Definition⚓︎

红黑树(red-black trees) 本质上也是一棵二叉查找树，它的目标同 AVL 树一样，也是尽可能地维护二叉查找树的平衡。下图表示的是红黑树的一个节点：

• 节点除了有指向左右孩子的指针外，还额外多了一个指向父节点的指针
• 同时又多了一个存储颜色的字段，占 1 bit 空间（红色 / 黑色）
• 红黑树里的空指针NULL有时会被称为NIL，它被认为是一个外部节点，并且是黑色的

于是有了以下定义：

定义

红黑树是一棵二叉查找树，它满足下面几条性质：

• 每个节点的颜色非黑即红
• 根节点是黑色的

根据维基百科上的内容，第二条性质并不是必需的。

• 每个叶子节点是黑色的

注意

这里的「叶子结点」并不是一般树上的叶子节点，它特指空节点NIL。

• 如果一个节点是红色的，那么它的孩子都是黑色的（也就是说，不会出现相邻两层节点都是红色的情况）
• 对于每个节点，从该节点出发，到它后代叶子节点的所有简单路径上，应包含相同数量的黑色节点（显然是实现树的平衡的关键所在）

注意

红色节点要么没有孩子，要么有两个黑色的孩子，否则无法满足第五条性质。

在红黑树中，实际存在的节点被称为内部节点(internal node)，而空节点NIL被称为外部节点(external node)

此外，还要为节点 x 定义一个「黑高」(black height) \(\mathrm{bh}(x)\)：它表示从节点 x 出发到叶子节点的简单路径上黑色节点的个数（不包括节点 x），而整棵树的黑高等于根节点的黑高。「黑高」用于衡量整棵红黑树平衡程度的重要指标。

引理：一棵有 \(N\) 个内部节点的红黑树，它的高度至多为 \(2\ln (N+1)\)。

从该引理中我们可以发现，尽管红黑树相比 AVL 树看起来不是那么平衡，但是它能够确保树高是 \(O(\log N)\) 的，所以红黑树也是一棵相当平衡的树。

Operations⚓︎

Insertion⚓︎

与 AVL 树类似，我们希望插入的节点尽可能不影响红黑树的平衡程度，换言之就是尽可能地不改变红黑树的黑高，因此新插入节点的颜色应该是红色的。

• 如果运气好的话，即新插入节点的父节点是黑色的，我们无需作任何调整
• 但很可能会遇到父节点也是红色的情况，这样需要我们做一定的调整，下面根据课件给出的例子，分情况讨论调整的方法

分析

注

「调整」一栏的图中，黑色三角形表示以黑色节点为根节点的子树。

初始状态 Case 1 Case 2 Case 3

新插入节点的父节点，以及父节点的兄弟节点都是红色的。

例子调整

先插入 5——OK！再插入 4——No！4 和 5 是相邻的红色节点，没有满足定义的要求，所以我们要开始调整这棵树了。

相当简单，只需要交换父亲节点、父亲的兄弟节点与祖父的颜色即可。

但正因为太简单了，所以在调整后还会出现四种情况：

• 最理想的情况是祖父节点是根节点的时候，让根节点变黑即可
• 但更常见的是调整完一次后，仍然在我们要讨论的三种情况内——所以慢慢来吧 ~

注：Case 1 应该还有 3 种对称情况（新插入节点在 LR、RL 和 RR 位置上），但由于比较简单，所以就不再赘述。

新插入节点是其祖父节点（黑色）的 LR 或 RL 孙子节点。

例子调整

在 Case 1 交换颜色后，虽然节点 4 那一部分合法了，但是它的祖父和曾祖父却都是红色的，所以还得继续调整。

类似 AVL 树的旋转，转一下就行。然而这个调整并没有使这棵树变得合法，而只是将它调整至 Case 3 的形状（LR -> LL），最终的解决方案还得见 Case 3。

注：Case 2 还有一种对称情况（RL -> RR），调整方法类似。

新插入节点是其祖父节点（黑色）的 LL 或 RR 孙子节点。

例子调整

一次旋转 + 一次换色即可（可以看到，两次操作的顺序并不重要）。这样一转换后，终于使这棵红黑树变回合法的了！

如果将 Case 2 和 Case 3 一起看的话，可以发现我们进行了一次类似 AVL 树的 LR 旋转操作。

注：Case 3 也有一种对称情况（RR）

---

根据前面的分类讨论，我们可以画一个（不是特别标准的）状态图，从全局角度观察整个插入流程（想法来自修佬的笔记）

可以看到，在整个调整的过程中，最多只需要两次旋转，就可以使新的树继续维持红黑树的特性，因此插入的效率和 AVL 树差不多。

注：迭代实现比递归实现速度上略快一点，但不多。

Deletion⚓︎

我们通过「两步走」的方法实现整个删除操作：维护红黑树的平衡 -> 删除树中节点

先来看删除节点（共 4 种情况）：

• 删除树中的唯一节点 -> 直接删
• 被删除节点有两个孩子 -> 用左子树最大节点或右子树最小节点替代被删除的节点，并保持颜色不变（具体删除细节见 FDS 相关部分），然后将其从原来的位置中删除（根据二叉查找树的性质知，它至多只有一个孩子，因此问题转换为后面两种情况）
• 被删除节点没有孩子
  • 若为红色 -> 直接删
  • 若为黑色 -> 删除后由于打破最后一条性质，需要重新维护
• 被删除节点有一个孩子 -> 孩子一定是红色的（否则的话不满足最后一条性质）-> 该节点一定是黑色的 -> 用孩子替代自己并染黑

再来看最重要（也是最麻烦）的平衡维护（X 表示当前正在维护的节点，初始情况为即将被删除的节点）：

分析

Case 1Case 2Case 3Case 4Case 5

X 的兄弟节点 S 是红色的（则 S 的两个孩子、父节点 P 一定都是黑色的），这时无法通过简单的旋转或染色使其满足所有性质，我们先让部分区域先满足所有性质，之后再维护剩余部分。

初始状态旋转后染色后

若 X 是 P 的左孩子，则左旋 P；否则右旋 P（对称情况）

将兄弟节点 S 染红，父节点 P 染黑

大功告成！现在我们保证了在忽视 X 的子树（我用蓝色虚线矩形方框圈出来的部分）的情况下，满足红黑树的所有性质。至于剩下的部分，继续按情况讨论。

兄弟节点 S 及其两个孩子 L 和 R 都是黑色的，父节点 P 是红色的

初始状态染色后

交换 P 和 S 的颜色即可

所有节点（P、S、L 和 R）都是黑色的。此时也没有一步到位的操作，只能让部分区域暂时满足红黑树的性质；再根据节点 P 上面的结构来递归维护它。

但如果P 是根节点的话，那么经过下面的调整后就完成维护了。

初始状态染色后

仅需给兄弟节点 S 染红即可

兄弟节点 S 是黑色的；兄弟节点靠近内侧的孩子（LR、RL）是红色的，靠近外侧的孩子（LL、RR）是黑色的；父节点的颜色可红可黑。

初始状态旋转后染色后

若 X 为左孩子，右旋 S；否则左旋 S

将 S 染红，L 染黑

此时这棵树满足 Case 5 的条件，进一步的调整就请看下面的 Case 5 了

兄弟节点 S 是黑色的；兄弟节点靠近内侧的孩子（LR、RL）可红可黑，靠近外侧的孩子（LL、RR）是红色的；父节点的颜色可红可黑。

注意

图片里面的子树 B 表示以靠近内侧孩子为根节点的树，它的根节点被我画成黑色了，实际上红色也是可以的！

初始状态旋转后染色后

若 X 为左孩子，则左旋 P；否则右旋 P

交换 P 和 S 的颜色，并且将 R 染黑（如果 X 是右孩子的话应该是将 L 染黑）

---

再次献上不是很标准的状态图（基本照着修佬的图画的，但又稍微调整了一下）：

状态图里未提到的地方：

• 在 Case 3 中，如果 P 是根节点，那么经过调整后就大功告成了，直接进入 "Finish!"

从状态图中，我们可以发现在删除一个节点并维护平衡的过程中，至多需要 3 次旋转操作，显然在绝大多数情况下比 AVL 树的 \(O(\log N)\) 要快，因此红黑树的使用更加广泛些。

例子

看了前面的理论分析，（如果你是像我一样第一次学红黑树的话）你应该处于一种似懂非懂的状态。现在尝试阅读下面的例子，看你是否真的理解红黑树的删除过程。

这是一棵红黑树，我们要从中删除若干个节点：

删除节点 3 删除节点 17 删除节点 8

参考图片答案

这里的 Case 2.1 指的是我这边的 Case 2

参考图片答案

• 这里的 Case 2.2 指的是我这边的 Case 3
• 可以看到，在经过一次 Case 3 的转变后，我们需要维护的点 X 向上移了一层（17 -> 15），但删除的节点是 17 不是 15

参考图片答案

这里的 Case 3 和 Case 4 分别指的是我这边的 Case 4 和 Case 5

通过表格比较 AVL 树和红黑树的效率：

B+ Trees⚓︎

B+ 树是 B 树的改良版，广泛应用于关系型数据库和操作系统的文件系统中。

计算机内的大量数据往往是存在磁盘内而非内存里，但磁盘的访问速度比内存慢很多。因此为了加快磁盘的访问速度，可以让数据存储于一段连续的块内，这便是 B+ 树和普通的二叉查找树之间的区别。而且，相比二叉查找树，B+ 树的插入与修改拥有较稳定的对数时间复杂度，因而能够保持数据稳定有序。

例子

这是一棵四阶 B+ 树（或者也可以称为 2-3-4 树，因为一个节点可以有 2/3/4 个孩子）

• 黑色方块表示空指针
• 标红的数字表示当前子树中的最小值，它会被存储于父节点中

Operations⚓︎

再来看一个例子，从中学习 B+ 树的创建、查找、插入等操作

例子

这是原始数据，由 5 个存储块构成，每个存储块存有 2-3 个数据（不得超过这个范围），存储块内的数据按升序排列：

我们先根据这些存储块，自底向上创建一棵三阶 B+ 树：

查找 52 插入 18 插入 1 插入 19 插入 28

查找过程类似二叉查找树，也是自顶向下寻找，找的数偏大往右找，偏小往左找

先看下面的存储块有没有空余的地方——在该情况中是有的，那就直接插入存储块内（还得检查一下要不要修改父节点的元素，当然这里不需要）

通过查找发现，我们要插入的数据块（蓝色）的数据已满，不能再插入了，那么就看能不能将这个数据块一分为二（每个数据块放 2 个数据），也就是看父节点还能不能再多一个孩子——这里是 OK 的（打钩的位置），那就分出来吧，然后不要忘记修改父节点的数据！

这次比前一种情况更麻烦一些：数据块和它的父节点都满了，所以要向祖父节点寻找空位，再多给一个叔叔节点，将一分为二后的数据块放在叔叔节点上。最后不要忘记修改父节点和祖父节点的数据！

更加糟糕，这下数据块和它的所有祖先都满了，那就只能产生一个新的根节点（添加新的一层）存放多出来的节点。

在插入操作中我们运用的是简单的分裂法，这会产生很多的叶子节点（一个个存储块），从而导致树的增高。

删除操作与插入类似，但要注意：如果一个根节点失去两个孩子时，要移除这个根节点。

Btree Insert(ElementType X, Btree T) {
    Search from root to leaves for X and find the the proper leaf node;
    Insert X;
    while (this node has M+1 keys) {
        split it into 2 nodes with RoundUp((M+1) / 2) and RoundDown((M+1) / 2) keys respectively;
        if (this node is the root)
            create a new root with two children;
        check its parent;
    } 
}

对于一棵有 \(N\) 个数据的 \(M\) 阶 B+ 树：

• 深度 \(\mathrm{Depth}(M, N) = O(\lceil \log_{\lceil \frac{M}{2} \rceil} N \rceil)\)
• 插入时间 \(T(M, N) = O(\dfrac{M \cdot \log N}{\log M})\)
  • 所以阶数 \(M\) 不是越大越好，最合适的取值为 3 或 4
• 查找时间 \(T_{Find}(M, N) = O(\log N)\)

评论区