Chap8 高级搜索树

返回：0300 数据结构总目录 · 上一章：0307 Chap7 二叉搜索树 · 下一章：0309 Chap9 词典

1、学习目标

高级搜索树解决普通 BST 的两个问题：一是访问局部性，二是外存或大规模数据下的高度控制。伸展树利用“刚访问过的还可能再访问”，B 树面向磁盘块，红黑树用较弱平衡换取较低维护成本。

结构	核心思想
伸展树	每次访问后把节点伸展到根
B 树	一个节点存多个关键码，降低树高
红黑树	用颜色约束实现适度平衡
KD 树	多维空间划分

2、资料范围

PDF 课件	内容
08.ABST.A1-A3	伸展树
08.ABST.B1-B5	B 树结构、查找、插入、删除
08.ABST.XA1-XA4	红黑树
08.ABST.XB1-XB2	KD 树
08.ABST.XC.More_Search_Trees.pdf	更多搜索树

3、伸展树

伸展树的操作原则：

每次访问节点 x 后，通过一系列旋转把 x 移到根。

伸展步骤：

情况	操作
zig	x 的父亲是根，单旋
zig-zig	x 和父亲同向，先旋父亲再旋 x
zig-zag	x 和父亲异向，连续两次旋 x

伸展树没有严格高度限制，单次操作可能很慢，但分摊复杂度为 O(log n)。它适合访问具有局部性的场景。

理解重点：

1. 不是每次都保持树很平衡。
2. 是把热点元素推到靠近根的位置。
3. 分摊分析比单次最坏复杂度更重要。

4、B 树

B 树是多路平衡搜索树，常用于外存索引。

一棵 m 阶 B 树大致满足：

1. 每个节点最多有 m 个孩子。
2. 除根外，每个内部节点至少有 ceil(m/2) 个孩子。
3. 所有叶子处于同一层。
4. 节点内关键码有序，孩子区间分隔关键码范围。

查找过程：

在节点内部二分或顺序查找关键码；
若命中则成功；
否则按区间进入对应孩子。

B 树高度很低，因为每个节点能容纳多个关键码。一次节点访问对应一次磁盘块读取时，B 树比二叉搜索树更适合外存。

4.1 插入

插入先定位到叶节点，把关键码插入节点。若节点溢出，则分裂：

中位关键码上升到父节点；
左半留在原节点；
右半形成新节点；
父节点可能继续溢出。

4.2 删除

删除时若关键码在内部节点，先找前驱或后继替换，再转化为叶节点删除。若节点下溢，则从兄弟借关键码或与兄弟合并，并可能向上继续修复。

5、红黑树

红黑树是二叉搜索树，增加颜色约束：

1. 每个节点为红或黑。
2. 根为黑。
3. 外部空节点视为黑。
4. 红节点不能有红孩子。
5. 从任一节点到所有外部节点的黑节点数相同。

这些约束保证最长路径不超过最短路径的两倍，因此高度为 O(log n)。

插入修复：

情况	处理
父黑	直接结束
父红且叔红	父叔变黑，祖父变红，向上继续
父红且叔黑	旋转加染色

删除修复更复杂，核心是处理“双黑”问题，通过兄弟颜色、兄弟孩子颜色决定旋转或染色。

6、KD 树

KD 树用于多维点集合。每一层按不同维度划分：

第 0 层按 x 划分；
第 1 层按 y 划分；
第 2 层再按 x 划分；
...

典型用途：

1. 二维/多维范围查询。
2. 最近邻查询。
3. 空间点集索引。

KD 树对数据分布敏感，工程上常配合重建或平衡策略。

7、结构对比

结构	查找	插入	删除	特点
AVL	O(log n)	O(log n)	O(log n)	平衡严格，查询快
伸展树	分摊 O(log n)	分摊 O(log n)	分摊 O(log n)	利用访问局部性
B 树	O(log_m n)	O(log_m n)	O(log_m n)	外存友好
红黑树	O(log n)	O(log n)	O(log n)	工程常用，维护成本适中
KD 树	平均较好	依实现	依实现	多维空间查询

8、易错点

易错点	修正
把伸展树理解成 AVL	伸展树不保持严格平衡，靠分摊效率
B 树和二叉树混淆	B 树节点内可有多个关键码和多个孩子
B 树插入忘记向上分裂	父节点也可能继续溢出
红黑树只背颜色	关键是黑高度约束带来的高度上界
KD 树当成普通 BST	每层比较维度不同

9、复盘清单

检查项	状态
能画出伸展树 zig、zig-zig、zig-zag	待复盘
能说明 B 树为什么适合外存	待复盘
能手动模拟 B 树插入分裂	待复盘
能背出红黑树五条性质并解释高度上界	待复盘
能说明 KD 树按维度轮换划分	待复盘