【数据结构】考研408 | 红黑树收官与B树启航：删除策略与多路平衡解析

导读

大家好，很高兴又和大家见面啦！！！ 在上一篇内容中，我们深入探讨了 红黑树（RBT）的插入操作，理解了它如何通过颜色调整与旋转操作维护“适度平衡”。现在，我们站在两个关键问题的交汇点：

• 红黑树的删除操作将如何延续其平衡智慧？
• 当数据规模超越内存限制时，什么样的结构能更高效地管理磁盘上的海量数据？

今天，我们将带着对红黑树的理解，自然过渡到 多路平衡查找树（B树）​ 的世界。从二叉到多叉，从内存到磁盘，让我们一同探索数据结构如何为不同场景量身定制解决方案！

一、红黑树

经过前面的学习，我们以及对红黑树及其插入操作有了一定的认知。对于红黑树而言，其删除操作相比于插入操作会更加的复杂，不过现阶段我们并不需要对其进行深入的探讨，仅作简单的了解即可。

1.1 红黑树的删除

红黑树的删除操作我们需要了解以下内容：

1. 红黑树删除操作的时间复杂度S=O(\log_2N)
2. 在红黑树中删除结点的处理方式和“BST的删除”一样
3. 按2.删除结点后，可能破坏“红黑树特性”，此时需要调整结点颜色、位置，使其再次满足“红黑树特性”。

简单的说就是红黑树在进行删除操作时，若该删除操作破坏了 RBT 的特性，则需要进行相应的调整使其恢复为一棵 RBT ； 删除操作的具体内容，我们会在今后的学习中再进行详细的介绍，这里就不再展开；

1.2 红黑树的性能分析

RBT 的时间复杂度与 AVL 的时间复杂度一致，均为 O(\log_2 N) 既然二者的时间复杂度一致，那为什么还要有 RBT 这种数据结构呢？ 在前面我们也有过介绍，这是因为 AVL 的 高度平衡 的严格规定，这就导致了 插入 与 删除 操作十分容易破坏 AVL 的 平衡特性 ，进而导致了在执行这些操作时，需要频繁的进行 平衡调整 操作； 而 RBT 的 适度平衡 的相对松弛规定，就保证了这些操作不会那么容易破坏 RBT 的 红黑特性 ，从而大幅度的降低了 平衡调整 操作的频率； 因此在需要频繁进行查找操作的情况下，使用 AVL 会更加的合适，而对于频繁进行 插入、删除 的动态查找中，使用 RBT 会更加合适；

二、多路查找树

尽管 RBT 通过其独特的着色规则和适度的平衡性，在内存中的动态数据管理上表现出色，但当我们面对海量数据、需要依赖磁盘等外部存储时，它的二叉树形态可能导致树高较大，进而引发频繁的I/O操作，成为性能瓶颈。 为了解决这类问题，我们引入了 多路查找树 的概念。与二叉查找树每个节点最多只有两个分支不同，多路查找树的一个节点可以拥有多个子节点，从而显著降低树的高度。 B树正是为了磁盘等存储设备而设计的一种高效、平衡的多路查找树。接下来，我们将从多路查找树的基本思想出发，逐步展开对B树核心概念的学习。

2.1 基本定义

多路查找树（Multiway Search Tree）是一种重要的树形数据结构，它突破了二叉查找树每个节点只能有一个关键字和最多两个子节点的限制，专为需要高效管理大规模数据，特别是涉及外部存储（如磁盘）的场景而设计。

这里我们需要注意，多路查找树 不能够缩写为 MST ，这是因为我们在学习 图 时，有介绍过一种 MST ，其全称是 Minimum Spanning Tree （最小生成树），这里为了避免歧义，因此我们不会将其称为 MST

一棵 m叉查找树 可以是一棵空树，也可以时满足以下特性的 m叉树：

1. m叉查找树 每个节点包含关键字数量有限，最多为 m-1个关键字。
2. 每个节点有最多 m 个子树，子树的数量取决于节点中关键字的数量。
3. 节点中的关键字有序，可以是递增或递减。
4. 失败节点指向不存在的关键字范围，用于查找失败时的处理。

flowchart TB
	subgraph PS[说明]
		word[关键字<br>可以递增:key1 < key2 < ... < keym - 1<br>可以递减: key1 > key2 > ... > keym - 1<br>数量最多为m - 1]
		sub[子树<br>数量取决于结点中关键字数量<br>m - 1 个关键字可以有 m 棵子树]
		fail[失败结点<br>表示查找失败, 为树中不存在的空结点]
	end
	subgraph Tree[m叉查找树]
		direction TB
		a[key1, key2, ..., keym-1]
		b[子树1]
		c[子树2]
		d[...]
		e[子树m]
		a--->b--->b1[NULL<br>失败结点]
		a--->c--->c1[NULL<br>失败结点]
		a--->d--->d1[NULL<br>失败结点]
		a--->e--->e1[NULL<br>失败结点]
	end
	Tree--->PS

在这之前，我们学习的 二叉查找树 （Binary Search Tree, BST）多路查找树 是两种重要的树形搜索结构。 当数据量巨大且涉及磁盘存取时，多路查找树（如B树）通过允许每个节点拥有多个子节点，能够有效降低树高，从而显著减少I/O操作次数，克服了 二叉查找树 在这种场景下的局限性。

2.2 BST 的特点

在 BST 中，各结点的值满足 左子树 <<

• 左子树：(-\infty , key)
• 根结点：key
• 右子树：(key, +\infty)

因此我们每一次的查找操作都是在符合条件的范围内查找目标关键字；

flowchart TB
a[key1]
b[key2]
c[key3]
a--->b
a--->c
b--->b1[负无穷, key2]
b--->b2[key2, key1]
c--->c1[key1, key3]
c--->c2[key3, 正无穷]

2.3 从 BST 到 m叉查找树

当我们将 BST 中每个结点存储的关键字数量由一个扩展到 m 个时，二叉查找树 就被拓展到了 m叉查找树；

flowchart TB
a[key1, key2, ..., keym-1]
a--->a1[负无穷, key1]
a--->a2[key1, key2]
a--->a4[...]
a--->a5[keym-2, keym - 1]
a--->a6[keym - 1, 正无穷]

可以看到，在 m叉查找树 中，每个结点可以含有多个 关键字 以及多个 子结点

2.4 m叉查找树的退化

当 m叉查找树 的每个结点都只存储一个关键字时，此时的 m叉查找树 就会退化为一棵 BST； 在这种情况下，若关键字的总数不变，此时的 BST 就会变的细长，进而导致查找效率降低； 如一棵 5叉查找树 中总共有16个关键字：

flowchart TB
a[5, 11, 22, 36]
b[1, 3]
c[6, 8, 9]
d[13, 15]
e[30, 35]
f[40, 42, 45]
a--->b
a--->c
a--->d
a--->e
a--->f

当其在关键字的总数不变的情况下，5叉查找树 退化为了一棵 BST：

flowchart TB

a1[3]
b1[1]
a1--->b1
b2[5]
a1--->b2

a2[11]
c2[8]
a2--->c2
c1[6]
c2--->c1

c1--->a1
c1--->c1_[NULL]
c3[9]
c2--->c3
d1[13]
a2--->d1
d1--->d1_[NULL]
d2[15]
d1--->d2


a3[22]
a3--->a2

a4[36]
e1[30]
a4--->e1
e2[35]
a4--->e2
f1[40]
a3--->f1
f1--->a4
f2[42]
f1--->f2
f2--->f2_[NULL]
f3[45]
f2--->f3

可以看到，此时我们以 22 作为 BST 的根结点时，树高从 5叉查找树 的 h_5 = 2 变成了 h_2 = 6 当然这只是其中一种情况还算是比较好的退化，若是以 5 作为根，那么我们得到的 BST 的高度还会继续增加； 在介绍 BST 时，我们就有提到过这一问题：

• 若插入的序列接近有序时，如递增序列或者递减序列，那么此时的 BST 会退化成 链表 ，从而查找效率会从 O(\log_2 N) 降低到 O(N)

同理，当 5叉查找树 在退化过程中，关键字序列接近有序时，5叉查找树 同样也会退化为链表，从而大大降低查找的效率； 因此为了保证查找的效率，m叉查找树 规定：

• 除了 根结点 外，任何结点 至少有 \lceil\frac{m}{2}\rceil 个分叉，即至少含有 \lceil \frac{m}{2} \rceil - 1 个关键字

如 5叉查找树 除了根结点外，其他结点至少含有 \lceil \frac{5}{2} \rceil = \lceil 2.5 \rceil = 3 个分支，至少含有 2 个关键字

flowchart TB
root[key,_,_,_<br>最多4个关键字<br>最少1个关键字]
lchild[key1, key2,_,_<br>最多4个关键字<br>最少2个关键字]
rchild[key1, key2,_,_<br>最多4个关键字<br>最少2个关键字]
root--->lchild
root--->rchild
l1[key1, key2,_,_<br>最多4个关键字<br>最少2个关键字]
l2[key1, key2,_,_<br>最多4个关键字<br>最少2个关键字]
l3[key1, key2,_,_<br>最多4个关键字<br>最少2个关键字]
lchild--->l1
lchild--->l2
lchild--->l3
r1[key1, key2,_,_<br>最多4个关键字<br>最少2个关键字]
r2[key1, key2,_,_<br>最多4个关键字<br>最少2个关键字]
r3[key1, key2,_,_<br>最多4个关键字<br>最少2个关键字]
rchild--->r1
rchild--->r2
rchild--->r3

2.5 m叉查找树的不平衡问题

在树形结构中，其查找效率与树的高度之间成正比：

• 树的高度越低，查找效率越高
• 树的高度越高，查找效率越低

二者之间可以用关系式：S = O(h) 表示，而对于一棵平衡树，其树高与结点之间则是成对数关系：h = O(\log N) ； 这也就是说，对于一棵平衡树，其查找效率与结点之间的关系可以表示为：S = O(\log N) ； 这个结论在 m叉查找树 中也同样适用，因此当 m叉查找树 的某一结点的个子树之间的高度相差太大，从而导致该子树失衡时，m叉查找树 的查找效率同样也会降低； 因此为了保证 m叉查找树 的查找效率，我们在创建一棵 m叉查找树 时，应尽可能的保持树的平衡状态；

三、多路平衡查找树

多路平衡查找树是一种重要的数据结构，它允许每个节点拥有多于两个子节点，并通过自平衡机制维持高效查找性能。 多路平衡查找树（特别是B树）的设计主要是为了高效管理无法全部装入内存的大规模数据集，尤其是涉及磁盘等外部存储的设备。

3.1 平衡机制

多路平衡查找树通过一套严格的规则在插入和删除操作时维持其平衡特性：

• 插入操作：当向一个已满的节点插入新关键字导致其超出容量时，会进行节点分裂。
  • 该节点会从中间位置分成两部分，中间的关键字被提升到父节点中。
  • 如果父节点也因此变满，分裂操作可能会向上递归进行，甚至可能导致树的高度增加。
• 删除操作：当从节点中删除一个关键字导致其关键字数量低于下限时，会通过兄弟节点借用关键字或与兄弟节点合并等操作来重新满足约束条件。这些操作同样可能向上传递

3.2 分类

多路平衡查找树是一个概念家族，其中包括5类平衡查找树：

• 2-3树/2-3-4树：B树思想的先驱。
  • 2-3树的节点可以是2-节点（1个关键字，2个子节点）或3-节点（2个关键字，3个子节点）。
  • 2-3-4树则增加了4-节点。
  • 它们直观地展示了多路平衡的特性。
• B树：平衡多路查找树的经典实现。 一棵m阶B树每个节点最多有 m 个子节点和 m-1 个关键字。 所有叶子节点位于同一层，通过节点分裂和合并维持平衡。
• B+ 树：B树的优化变种，现代数据库的基石。与B树的关键区别：
  • 非叶子节点仅起索引作用，只包含关键字，不保存数据指针。
  • 所有数据记录都存储在叶子节点，且叶子节点间通过指针顺序链接。
• B* 树：B+树的进一步优化。主要通过提升节点的空间利用率来减少分裂次数： 非叶子节点之间增加了指向兄弟节点的指针； 规定非叶子节点的关键字最少为 (\frac{2}{3})*M，而非B+树的 \frac{1}{2}。
• Trie 树（字典树）：一种专精于字符串处理的多路查找树。
  • 其键值由节点在树中的路径决定，每个节点代表一个字符，非常适合前缀匹配和字典检索。

3.3 B树

B树 是一种 绝对平衡 的 自平衡多路查找树，所谓的 m阶B树 指所有结点的 平衡因子均等于 0 的 m路平衡查找树。

3.3.1 定义

一棵 m阶B树 可以是一棵空树，也可以是一棵满足以下特性的 m叉树：

• 树中每个结点至多有 m 棵子树，即至多有 m - 1 个关键字
• 若根结点不是叶结点，则至少有 2 棵子树，即至少有 1 个关键字
• 除根结点外的所有非叶结点至少有 \lceil \frac{m}{2} \rceil 棵子树，即至少有 \lceil \frac{m}{2} \rceil - 1 个关键字
• 所有非叶结点的结构如下：

flowchart TB
a[n]
b[P0]
c[K1]
d[P1]
e[K2]
f[...]
g[Kn]
h[Pn]

其中，n（\lceil \frac{m}{2} \rceil - 1 \leq n \leq m - 1） 为结点中关键字的个数；K_i（i= 1, 2, \cdots, n) 为结点的 关键字，且满足 K_1 < K_2 < \cdots < k_nP_i（i= 0, 1, \cdots, n） 为指向子树根结点的指针，且指针 P_{i - 1} 所指子树中所有结点的关键字均小于 K_i，P_i 所指子树中所有结点的关键字均大于 K_i；

• 所有的叶结点都出现在同一层次上，并且不带信息（可以视为 外部结点 或类似与折半查找判定树的失败结点，实际上这些结点并不存在，指向这些结点的指针为空）

3.3.2 实例理解

这里我们以一棵 5 阶 B树 为例，进一步理解上述性质：

flowchart TB
	subgraph R[根结点]
		direction TB
		n[n = 1]
		p0[P0]
		key[key1 = 22]
		p1[P1]
	end

	
	subgraph r[子树2]
		direction TB
		nr[n = 2]
		pr0[P0]
		keyr1[key1 = 36]
		pr1[P1]
		keyr2[key2 = 45]
		pr2[P2]
		keyr3[key3 = 50]
		pr3[P3]
		keyr4[key4 = 56]
		pr4[P4]
	end
	p1--->r
	pr0--->n4[NULL]
	pr1--->n5[NULL]
	pr2--->n6[NULL]
	pr3 ---> n7[NULL]
	pr4 ---> n8[NULL]
	subgraph l[子树1]
		direction TB
		nl[n = 2]
		pl0[P0]
		keyl1[key1 = 5]
		pl1[P1]
		keyl2[key2 = 11]
		pl2[P2]
	end
	p0--->l
	pl0 ---> n1[NULL]
	pl1 ---> n2[NULL]
	pl2 ---> n3[NULL]

在这棵 5阶B树 中，各结点的子树、关键字分别满足以下内容：

• 根结点中： 当关键字数量为 0 时，表示该树为一棵 空树 关键字可以只有 1 个，其对应有 2 棵子树 关键字最多有 5 - 1 = 4 个，其对应有 5 棵子树
• 除了根节点外，其余 非叶结点 中： 关键字的数量至少为 \lceil \frac{5}{2} \rceil - 1 = \lceil 2.5 \rceil - 1 = 3 - 1 = 2 个，最多为 5 - 1 = 4 个 子树的数量至少为 \lceil \frac{5}{2} \rceil = \lceil 2.5 \rceil = 3 棵，最多为 5 棵；
• 叶子结点 也称为 外部结点 ，均位于第 3 层，代表查找失败时的位置。通常在计算 B树高度时不会计算叶子结点；
• 所有的非叶子结点中，关键字是按照递增的顺序从左到右进行排列；

结语

通过本篇的学习，我们系统性地探索了从红黑树的删除操作到B树基本概念的完整知识路径。以下是本次内容的核心要点回顾： 📚 核心知识总结

💡 学习路径价值 从红黑树到B树的学习路径，展现了数据结构设计如何针对不同应用场景（内存计算vs.磁盘存储）进行优化。

• 红黑树通过“适度平衡”在内存操作中取得了良好性能
• B树则通过“多路平衡”专门解决了外部存储中海量数据的管理效率问题。

这两类结构各有其最佳适用场景，理解它们的设计哲学与优缺点，将为我们在实际工程中选择合适的数据结构提供坚实依据。 互动与分享

• 点赞👍 - 您的认可是我持续创作的最大动力
• 收藏⭐ - 方便随时回顾这些重要的基础概念
• 转发↗️ - 分享给更多可能需要的朋友
• 评论💬 - 欢迎留下您的宝贵意见或想讨论的话题

感谢您的耐心阅读！ 关注博主，不错过更多技术干货。我们下一篇再见！