掌握二叉搜索树、AVL 树、红黑树、B 树与 B+ 树的查找性质、复杂度和结构差异,明确多路平衡树对外存索引的意义。

# 一、二叉搜索树

二叉搜索树(BST)满足:对任意结点,左子树所有关键字小于根关键字,右子树所有关键字大于根关键字,且左右子树也分别满足该条件。以下默认关键字互异;若允许重复值,需规定重复键放置或用结点计数。

查找从根开始:

  1. 目标等于当前关键字则成功。
  2. 目标较小则转向左子树,较大则转向右子树。
  3. 到达空指针仍未找到则失败。

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct BiTNode {
int data;
struct BiTNode *left;
struct BiTNode *right;
} BiTNode;

BiTNode *BSTSearch(BiTNode *root, int key) {
BiTNode *p = root;
while (p != NULL && p->data != key) {
p = key < p->data ? p->left : p->right;
}
return p;
}

查找、插入和删除都与树高 hh 成正比。平衡时 h=O(log⁡n)h=O(\log n);若按递增序列插入,BST 会退化为单支树,最坏为 O(n)O(n)。删除结点时,若有两个孩子,可用其中序后继(右子树最小结点)或中序前驱替换,再删除该后继或前驱。

# 二、平衡二叉树

# 1. AVL 树

AVL 树是高度平衡的 BST。结点平衡因子为左子树高度减右子树高度,AVL 要求每个结点的平衡因子为 −1,0,1-1,0,1。插入或删除后若出现失衡,根据最先失衡祖先结点及其较高子树方向,分四种情况恢复:

类型失衡路径调整
LL左孩子的左子树过高对失衡结点右旋
RR右孩子的右子树过高对失衡结点左旋
LR左孩子的右子树过高先左旋左孩子,再右旋失衡结点
RL右孩子的左子树过高先右旋右孩子,再左旋失衡结点

AVL 树高度为 O(log⁡n)O(\log n),因此查找、插入和删除最坏为 O(log⁡n)O(\log n)。旋转只重组局部链接,仍需保持中序关键字次序。

# 2. 红黑树

红黑树用颜色约束控制树高。常见定义包括:根为黑色;叶子空结点视为黑色;红结点不能有红孩子;从任一结点到其后代空叶子的路径含有相同数量的黑结点。由此树高为 O(log⁡n)O(\log n),查找、插入和删除也为 O(log⁡n)O(\log n)。

红黑树的平衡程度弱于 AVL,但更新时通常通过变色和旋转维持性质。若题目要求具体插入或删除步骤,应按所用教材对 NIL 叶子和颜色调整的定义推演。

# 三、B 树

B 树(多路平衡查找树)一个结点可保存多个递增关键字和多个孩子指针,适合减少访问磁盘的次数。以下以 mm 阶 B 树表示每个结点最多有 mm 棵子树、m−1m-1 个关键字。

# 1. 阶为 mm 的 B 树性质

  • 每个结点的关键字递增,若有 kk 个关键字则有 k+1k+1 棵子树。
  • 根结点若不是叶子,至少有 22 棵子树;根若是叶子,可只含一个或多个关键字。
  • 除根外的结点至少有 ⌈m/2⌉−1\lceil m/2\rceil-1 个关键字、至多有 m−1m-1 个关键字;非叶结点相应至少有 ⌈m/2⌉\lceil m/2\rceil 棵子树、至多有 mm 棵子树。
  • 所有叶子结点处于同一层。

查找时先在当前结点的有序关键字中查找或确定区间,再沿对应孩子指针下降。插入通常在叶子位置进行;结点溢出时分裂,并把分隔关键字提升到父结点,必要时向上继续分裂。删除导致结点关键字不足时,可向兄弟借关键字并调整父结点分隔值,或与兄弟合并。

# 四、B+ 树

B+ 树是为磁盘索引设计的多路平衡树。常见实现中,内部结点保存分隔关键字和孩子指针,所有记录或记录指针保存在叶结点;叶结点按关键字次序链接,便于范围查询和顺序扫描。不同教材对内部结点关键字代表 “分隔值” 还是 “子树最大 / 最小值” 有不同约定,做题时应依题目给出的结构规则。

对比项B 树B+ 树
记录所在位置关键字和记录可在内部或叶结点记录集中在叶结点
查找终点可能在内部结点成功通常继续到叶结点
叶结点链接不要求链接常按次序链接
范围查询需多次树查找定位首个叶结点后可顺链扫描
扇出与高度结点可能同时存记录,扇出相对较小内部结点主要存索引,扇出通常较大

flowchart TD
    A[根结点:分隔关键字] --> B[内部结点:继续导航]
    A --> C[内部结点:继续导航]
    B --> D[叶结点:记录]
    C --> E[叶结点:记录]
    D --> E

# 五、方法对比

结构是否保证平衡查找最坏复杂度常见用途
BST否O(n)O(n)数据量较小或输入形态可控
AVL是,较严格O(log⁡n)O(\log n)查找频繁、希望树高较小
红黑树是O(log⁡n)O(\log n)更新操作较多的有序集合
B 树 / B+ 树多路平衡O(log⁡mn)O(\log_m n) 层访问磁盘、数据库和文件系统索引

# 六、考场检查清单

  1. BST 的复杂度取决于树高;不平衡时不能直接写 O(log⁡n)O(\log n)。
  2. AVL 平衡因子定义要固定,四种失衡情况对应的单旋或双旋不能混淆。
  3. mm 阶 B 树表示最多 mm 棵子树、最多 m−1m-1 个关键字。
  4. B 树与 B+ 树的核心差异是记录存放位置和叶结点链接方式。
  5. 范围查找是 B+ 树的优势之一;单点查找仍需从根下降至叶结点。
更新于 阅读次数 次

请我喝[茶]~( ̄▽ ̄)~*

梦前辈 微信支付

微信支付

梦前辈 支付宝

支付宝