掌握二叉搜索树、AVL 树、红黑树、B 树与 B+ 树的查找性质、复杂度和结构差异,明确多路平衡树对外存索引的意义。
# 一、二叉搜索树
二叉搜索树(BST)满足:对任意结点,左子树所有关键字小于根关键字,右子树所有关键字大于根关键字,且左右子树也分别满足该条件。以下默认关键字互异;若允许重复值,需规定重复键放置或用结点计数。
查找从根开始:
- 目标等于当前关键字则成功。
- 目标较小则转向左子树,较大则转向右子树。
- 到达空指针仍未找到则失败。
1 | typedef struct BiTNode { |
查找、插入和删除都与树高 成正比。平衡时 ;若按递增序列插入,BST 会退化为单支树,最坏为 。删除结点时,若有两个孩子,可用其中序后继(右子树最小结点)或中序前驱替换,再删除该后继或前驱。
# 二、平衡二叉树
# 1. AVL 树
AVL 树是高度平衡的 BST。结点平衡因子为左子树高度减右子树高度,AVL 要求每个结点的平衡因子为 。插入或删除后若出现失衡,根据最先失衡祖先结点及其较高子树方向,分四种情况恢复:
| 类型 | 失衡路径 | 调整 |
|---|---|---|
| LL | 左孩子的左子树过高 | 对失衡结点右旋 |
| RR | 右孩子的右子树过高 | 对失衡结点左旋 |
| LR | 左孩子的右子树过高 | 先左旋左孩子,再右旋失衡结点 |
| RL | 右孩子的左子树过高 | 先右旋右孩子,再左旋失衡结点 |
AVL 树高度为 ,因此查找、插入和删除最坏为 。旋转只重组局部链接,仍需保持中序关键字次序。
# 2. 红黑树
红黑树用颜色约束控制树高。常见定义包括:根为黑色;叶子空结点视为黑色;红结点不能有红孩子;从任一结点到其后代空叶子的路径含有相同数量的黑结点。由此树高为 ,查找、插入和删除也为 。
红黑树的平衡程度弱于 AVL,但更新时通常通过变色和旋转维持性质。若题目要求具体插入或删除步骤,应按所用教材对 NIL 叶子和颜色调整的定义推演。
# 三、B 树
B 树(多路平衡查找树)一个结点可保存多个递增关键字和多个孩子指针,适合减少访问磁盘的次数。以下以 阶 B 树表示每个结点最多有 棵子树、 个关键字。
# 1. 阶为 的 B 树性质
- 每个结点的关键字递增,若有 个关键字则有 棵子树。
- 根结点若不是叶子,至少有 棵子树;根若是叶子,可只含一个或多个关键字。
- 除根外的结点至少有 个关键字、至多有 个关键字;非叶结点相应至少有 棵子树、至多有 棵子树。
- 所有叶子结点处于同一层。
查找时先在当前结点的有序关键字中查找或确定区间,再沿对应孩子指针下降。插入通常在叶子位置进行;结点溢出时分裂,并把分隔关键字提升到父结点,必要时向上继续分裂。删除导致结点关键字不足时,可向兄弟借关键字并调整父结点分隔值,或与兄弟合并。
# 四、B+ 树
B+ 树是为磁盘索引设计的多路平衡树。常见实现中,内部结点保存分隔关键字和孩子指针,所有记录或记录指针保存在叶结点;叶结点按关键字次序链接,便于范围查询和顺序扫描。不同教材对内部结点关键字代表 “分隔值” 还是 “子树最大 / 最小值” 有不同约定,做题时应依题目给出的结构规则。
| 对比项 | B 树 | B+ 树 |
|---|---|---|
| 记录所在位置 | 关键字和记录可在内部或叶结点 | 记录集中在叶结点 |
| 查找终点 | 可能在内部结点成功 | 通常继续到叶结点 |
| 叶结点链接 | 不要求链接 | 常按次序链接 |
| 范围查询 | 需多次树查找 | 定位首个叶结点后可顺链扫描 |
| 扇出与高度 | 结点可能同时存记录,扇出相对较小 | 内部结点主要存索引,扇出通常较大 |
flowchart TD
A[根结点:分隔关键字] --> B[内部结点:继续导航]
A --> C[内部结点:继续导航]
B --> D[叶结点:记录]
C --> E[叶结点:记录]
D --> E# 五、方法对比
| 结构 | 是否保证平衡 | 查找最坏复杂度 | 常见用途 |
|---|---|---|---|
| BST | 否 | 数据量较小或输入形态可控 | |
| AVL | 是,较严格 | 查找频繁、希望树高较小 | |
| 红黑树 | 是 | 更新操作较多的有序集合 | |
| B 树 / B+ 树 | 多路平衡 | 层访问 | 磁盘、数据库和文件系统索引 |
# 六、考场检查清单
- BST 的复杂度取决于树高;不平衡时不能直接写 。
- AVL 平衡因子定义要固定,四种失衡情况对应的单旋或双旋不能混淆。
- 阶 B 树表示最多 棵子树、最多 个关键字。
- B 树与 B+ 树的核心差异是记录存放位置和叶结点链接方式。
- 范围查找是 B+ 树的优势之一;单点查找仍需从根下降至叶结点。
