数据结构 —— 查找（Search）完整教程

面向考试 / 期末考试，涵盖数据结构查找章节全部核心知识点

目录

1. 基本概念
2. 顺序查找
3. 二分查找
4. 分块查找
5. 二叉排序树 BST
6. 平衡二叉树 AVL
7. 红黑树
8. B 树 / B+ 树
9. 哈希查找
10. 查找算法对比总结
11. 常见考题类型

1. 基本概念

1.1 查找的定义

查找（Search）：在数据集合中寻找满足某种条件的数据元素的过程。

1.2 基本术语

1.3 平均查找长度 ASL ★

ASL（Average Search Length）：在查找过程中，关键字比较次数的平均值。

ASL 成功： $$ASL_{成功} = \sum_{i=1}^{n} P_i \cdot C_i$$

• $P_i$：查找第 $i$ 个元素的概率
• $C_i$：找到第 $i$ 个元素需要的比较次数

ASL 失败： $$ASL_{失败} = \sum_{j=1}^{m} P_j \cdot C_j$$

• $P_j$：查找失败落在第 $j$ 个区间的概率
• $C_j$：在该区间判定失败需要的比较次数

1.4 查找表的分类

• 静态查找表：只做查询和检索（顺序查找、二分查找）
• 动态查找表：查询 + 插入 + 删除（二叉排序树、哈希表）

2. 顺序查找

2.1 基本思想

从表的一端开始，逐个比较关键字，直到找到目标或遍历完整个表。

2.2 算法实现

// 带哨兵的顺序查找
int SeqSearch(int a[], int n, int key) {
    a[0] = key;           // 设置哨兵
    int i = n;
    while (a[i] != key)   // 从后往前找
        i--;
    return i;             // i=0 表示查找失败
}

哨兵的作用：省略了每次循环判断 i >= 1 的边界条件，提高效率。

2.3 性能分析

2.4 适用场景

• 线性表（顺序存储或链式存储均可）
• 表元素无序
• 数据量较小

2.5 有序顺序表的顺序查找

如果顺序表有序，查找失败时不需要遍历到表尾：

• ASL 失败 = $\frac{n}{2} + \frac{n}{n+1}$ ≈ $\frac{n}{2}$

3. 二分查找

也称为：折半查找

3.1 前提条件 ★

• 仅适用于有序的顺序表
• 不适用于链表（链表无法随机访问中间元素）

3.2 基本思想

每次将查找区间折半，将目标值与中间元素比较：

• 相等 → 查找成功
• 目标 < 中间值 → 在左半区继续查找
• 目标 > 中间值 → 在右半区继续查找

3.3 算法实现

int BinarySearch(int a[], int n, int key) {
    int low = 0, high = n - 1, mid;
    while (low <= high) {
        mid = low + (high - low) / 2;  // 防止溢出
        if (a[mid] == key)
            return mid;                 // 查找成功
        else if (a[mid] > key)
            high = mid - 1;             // 左半区
        else
            low = mid + 1;              // 右半区
    }
    return -1;                          // 查找失败
}

3.4 判定树 ★★

二分查找的过程可以表示为一棵平衡二叉树，称为判定树。

判定树的性质：

• 是一棵平衡二叉树
• 有 $n$ 个结点的判定树高度为 $\lceil \log_2(n+1) \rceil$
• 查找成功时的比较次数 = 对应结点在判定树中的深度
• 查找失败时的比较次数 = 对应空指针的父结点深度

3.5 性能分析

3.6 ASL 计算示例

例：有序表为 [7, 14, 18, 21, 23, 29, 31, 35, 38]，求二分查找成功的 ASL。

构造判定树（结点中的数字为下标，不是值）：

              4(23)
           /       \
        1(14)      6(31)
       /    \      /    \
     0(7)  2(18) 5(29) 7(35)
       \     \           \
       1*    2*          8(38)
                          \
                          8*

• 查找 1 次成功：1 个结点 → $1 \times 1 = 1$
• 查找 2 次成功：2 个结点 → $2 \times 2 = 4$
• 查找 3 次成功：4 个结点 → $3 \times 4 = 12$
• 查找 4 次成功：2 个结点 → $4 \times 2 = 8$

$$ASL_{成功} = \frac{1+4+12+8}{9} = \frac{25}{9} \approx 2.78$$

4. 分块查找

也称为：索引顺序查找

4.1 基本思想

1. 将数据分成若干块，块内无序、块间有序
2. 建立索引表，索引表中记录每块的最大关键字和起始地址
3. 先查索引表确定块，再在块内顺序查找

4.2 性能分析

设有 $n$ 个记录，分为 $b$ 块，每块 $s$ 个记录（$n = b \times s$）：

$$ASL = L_{索引} + L_{块内}$$

• 索引顺序查找：$ASL = \frac{b+1}{2} + \frac{s+1}{2}$
• 索引二分查找：$ASL = \log_2(b+1) - 1 + \frac{s+1}{2}$

最佳分块：$s = \sqrt{n}$ 时，$ASL_{min} = \sqrt{n} + 1$

5. 二叉排序树 BST

也称为：二叉查找树、二叉搜索树

5.1 定义 ★

二叉排序树是空树或满足以下性质的二叉树：

1. 若左子树非空，则左子树上所有结点的值均小于根结点的值
2. 若右子树非空，则右子树上所有结点的值均大于根结点的值
3. 左、右子树也各是一棵二叉排序树

考试重点：中序遍历 BST 得到递增有序序列

5.2 查找操作

BSTNode* BSTSearch(BSTNode* root, int key) {
    if (root == NULL || root->key == key)
        return root;
    if (key < root->key)
        return BSTSearch(root->left, key);
    else
        return BSTSearch(root->right, key);
}

查找过程：从根开始，若等于根则成功；小于根则走左子；大于根则走右子。

5.3 插入操作

插入的新结点一定是叶子结点。

BSTNode* BSTInsert(BSTNode* root, int key) {
    if (root == NULL) {
        BSTNode* node = (BSTNode*)malloc(sizeof(BSTNode));
        node->key = key;
        node->left = node->right = NULL;
        return node;
    }
    if (key < root->key)
        root->left = BSTInsert(root->left, key);
    else if (key > root->key)
        root->right = BSTInsert(root->right, key);
    return root;  // key 已存在则不插入
}

5.4 删除操作

情况分析（设要删除结点为 p）：

中序前驱：左子树中最右下的结点
中序后继：右子树中最左下的结点

5.5 ASL 分析

• 最好情况（平衡）：$ASL = O(\log n)$
• 最坏情况（单边斜树）：$ASL = O(n)$

插入次序影响 BST 的形状 → 由此引出平衡二叉树的需求。

6. 平衡二叉树 AVL

6.1 定义 ★

平衡二叉树：任意结点的左子树与右子树高度差的绝对值不超过 1。

平衡因子 = 左子树高度 - 右子树高度，取值：-1、0、1

6.2 最小不平衡子树

在插入过程中，以离插入结点最近的平衡因子绝对值 > 1 的结点为根的子树。

6.3 四种调整类型 ★★★

6.4 旋转示意图

LL 型（右单旋）：

      A               B
     / \             / \
    B   Ar   =>    C     A
   / \            / \   / \
  C   Br        Cl  Cr Br  Ar
 / \
Cl  Cr

RR 型（左单旋）：

    A                 B
   / \               / \
  Al  B     =>      A   C
     / \           / \  / \
    Bl  C        Al Bl Cl Cr
       / \
      Cl  Cr

LR 型（先左后右）：

      A                 A               C
     / \               / \             / \
    B   Ar   左旋B    C   Ar  右旋A   B     A
   / \        =>    / \        =>    / \   / \
  Bl  C            B   Cr          Bl  Cl Cr  Ar
     / \          / \
    Cl  Cr       Bl  Cl

RL 型（先右后左）：与 LR 对称。

6.5 AVL 性能

AVL 查找效率最优，但插入/删除维护代价较高 → 引出红黑树（折中方案）。

7. 红黑树

7.1 定义 ★

红黑树是一棵满足以下性质的二叉排序树：

1. 每个结点是红色或黑色
2. 根结点是黑色
3. **叶子结点（NIL）**是黑色
4. 不能有连续两个红色结点（红结点的父子和子结点必为黑）
5. 从任一结点到其每个叶子结点的路径上，黑色结点数相同（黑高相同）

7.2 红黑树 vs AVL 树

7.3 性质推导 ★

1. 从根到叶子的最长路径 ≤ 最短路径的 2 倍
2. 红黑树的高度 $h \leq 2\log_2(n+1)$
3. 查找时间复杂度为 $O(\log n)$

8. B 树 / B+ 树

B 树 = 多路平衡查找树，常用于文件系统和数据库索引

8.1 B 树的定义（$m$ 阶）★

1. 每个结点至多 $m$ 棵子树
2. 根结点至少 2 棵子树（非叶子时）
3. 非根非叶结点至少 $\lceil m/2 \rceil$ 棵子树
4. 所有叶子结点在同一层
5. 每个结点包含 $n$ 个关键字，$n+1$ 棵子树，关键字有序
6. 每个非根结点关键字数：$\lceil m/2 \rceil - 1 \le n \le m - 1$

8.2 5 阶 B 树示例

              [20, 40]
            /    |     \
    [5,10,15]  [25,30,35]  [45,50,55,60]
    / | |  \   / |  |  \   / |  |  |  \
   ...叶子都在同一层...

8.3 B 树的高度

设 $m$ 阶 B 树有 $n$ 个关键字： $$h \leq \log_{\lceil m/2 \rceil}\left(\frac{n+1}{2}\right) + 1$$

8.4 B+ 树的特点 ★★

B+ 树是 B 树的变体，主要区别：

8.5 B+ 树结构图

            [20, 40]           ← 非叶（仅索引）
           /    |    \
    [5,10]  [25,30]  [45,60]   ← 非叶（仅索引）
    /  |  \  /  |  \  /  |  \
   ○ ↔ ○ ↔ ○ ↔ ○ ↔ ○ ↔ ○ ↔ ○   ← 叶子（全记录 + 链表）
   ↓   ↓   ↓   ↓   ↓   ↓   ↓
  记录 记录 记录 记录 记录 记录 记录

9. 哈希查找

也称为：散列查找

9.1 基本概念

9.2 哈希函数的构造方法

重点：除留余数法中 $p$ 应取不大于表长的最大素数，可减少冲突。

9.3 冲突处理方法 ★★★

一、开放定址法

当冲突发生时，探测下一个空闲地址。

数学公式：$H_i = (H(key) + d_i) \bmod m$

(1) 线性探测法：$d_i = 0, 1, 2, …, m-1$

• 优点：实现简单
• 缺点：聚集现象（同义词和非同义词争用同一地址）

(2) 平方探测法：$d_i = 0, 1^2, -1^2, 2^2, -2^2, …$

• 可避免聚集现象
• 要求表长 $m$ 是形如 $4k+3$ 的素数

(3) 双散列法：$d_i = i \times H_2(key)$

• 使用第二个哈希函数计算增量

(4) 伪随机序列法

二、链地址法（拉链法）★

将所有同义词存储在同一链表中。

哈希表：
[0] → K0 → K10 → K20 → NULL
[1] → K1 → NULL
[2] → K2 → K12 → NULL
[3] → NULL
[4] → K4 → NULL
...

9.4 散列表查找 ASL

平均查找长度与装填因子 $\alpha$ 直接相关： $$\alpha = \frac{\text{表中已有记录数}}{\text{表长度}}$$

$\alpha$ 越小，冲突越少，ASL 越小，但空间浪费越大。

9.5 哈希查找 ASL 计算示例 ★

例：关键字序列 {19, 14, 23, 01, 68, 20, 84, 27, 55, 11, 10, 79}，哈希函数 $H(key) = key \bmod 13$，表长 $m=13$。

用线性探测法处理冲突，构造哈希表并计算 ASL。

哈希表最终状态：

[0] 79  [1] 14  [2] 01  [3] 68  [4] 27  [5] 55
[6] 19  [7] 20  [8] 84  [9] —   [10] 23 [11] 11  [12] 10

ASL 成功：

$$ASL_{成功} = \frac{1+1+1+2+1+1+3+4+3+1+3+9}{12} = \frac{30}{12} = 2.5$$

10. 查找算法对比总结

11. 常见考题类型

题型一：构造判定树，计算 ASL

给定有序表，画出二分查找的判定树（圆描结点 + 方描失败），计算 ASL。

题型二：BST 的插入与删除

给定关键字序列，一步步构造 BST，画出每一步后的树形。

题型三：AVL 平衡调整

给定插入序列，构造 AVL 树，指出每次调整的类型（LL/RR/LR/RL）。

题型四：B 树的插入与删除

给定 $m$ 阶 B 树，依次插入/删除关键字，画出最终树形。

题型五：哈希表构造 + ASL 计算

给定关键字 + 哈希函数 + 冲突处理方法，构造哈希表并计算 ASL。

题型六：哈希函数设计 + ASL 计算

链地址法下的哈希表构造和 ASL 分析。

附录：核心公式速记

1. 顺序查找：$ASL_{成功} = \frac{n+1}{2}$

2. 二分查找判定树高度：$\lceil \log_2(n+1) \rceil$

3. 二分查找 ASL：$\frac{n+1}{n}\log_2(n+1) - 1$

4. 分块查找最优：$s = \sqrt{n}$，$ASL_{min} = \sqrt{n} + 1$

5. AVL 平衡因子：左高 - 右高，只能取 -1, 0, +1

6. $m$ 阶 B 树关键字数：$\lceil m/2 \rceil - 1 \le n \le m - 1$

7. 装填因子：$\alpha = \frac{记录数}{表长}$

8. 哈希 ASL（链地址法成功）：$1 + \frac{\alpha}{2}$

💡 备考建议：重点掌握二分查找（判定树 + ASL）、AVL 树的四种调整、B/B+ 树的区别、哈希表的构造和冲突处理，这四部分是考试高频考点。