查找 | igugyj's blog

查找

7.1 查找的基本概念

查找表：由同一类型的数据元素构成的集合。 关键字：数据元素中唯一标识该元素的某个数据项的值。 查找成功/失败：找到/未找到指定关键字。 平均查找长度（ASL）：所有查找过程中比较次数的平均值。

ASL = Σpᵢ × cᵢ

其中 pᵢ 是查找第 i 个元素的概率，cᵢ 是查找第 i 个元素需要的比较次数。通常假设等概率查找，pᵢ = 1/n。

7.2 顺序查找

无序表：从第一个元素开始逐个比较，直到找到或遍历完。

ASL_成功 = (n+1)/2，ASL_失败 = n+1

有序表：如果查找失败，不需要遍历完整个表，当遇到比关键字大的元素时就可以停止。

ASL_成功 = (n+1)/2，ASL_失败 ≈ n/2 + n/(n+1)（各个位置不等概率）

int SeqSearch(int a[], int n, int key) {
    a[0] = key;  // 哨兵
    int i = n;
    while (a[i] != key) i--;
    return i;  // 返回 0 表示查找失败
}

使用哨兵可以避免每次比较时判断是否越界。

7.3 折半查找（二分查找）

要求：查找表必须是有序的顺序表（数组）。

int BinarySearch(int a[], int n, int key) {
    int low = 1, high = n, mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (a[mid] == key) return mid;
        else if (a[mid] > key) high = mid - 1;
        else low = mid + 1;
    }
    return 0;
}

折半查找的过程可以用判定树表示，判定树是一棵平衡二叉树。

ASL分析：

ASL_成功 ≈ log₂(n+1) - 1（等概率时）
ASL_失败 ≈ ⌈log₂(n+1)⌉

时间复杂度：O(log n)

📌 408考点提示：折半查找的判定树是一棵平衡二叉树，其中结点数的计算公式和树高的计算常出选择题。手算判定树时，通常取 mid = ⌈(low+high)/2⌉ 或 mid = ⌊(low+high)/2⌋，注意不同取整方式会得到不同的判定树。

7.4 二叉排序树（BST）

BST 性质：

左子树所有结点值 < 根结点值 < 右子树所有结点值。
中序遍历 BST 得到递增有序序列。

查找操作：

BSTNode *BSTSearch(BSTNode *T, int key) {
    while (T && key != T->data) {
        if (key < T->data) T = T->lchild;
        else T = T->rchild;
    }
    return T;
}

插入操作：查找失败的位置就是插入位置。

删除操作：

删除叶子结点：直接删除。
删除仅有左/右子树的结点：用孩子替换。
删除有左右子树的结点：用前驱或后继替换。

ASL分析：

最好情况（平衡树）：O(log n)
最坏情况（单支树）：O(n)

⚠️ 易错点：删除 BST 结点时，如果同时有左右子树，通常用右子树的最小结点（中序后继）或左子树的最大结点（中序前驱）替换。

7.5 平衡二叉树（AVL）

定义：任意结点的左右子树高度差（平衡因子）不超过 1。

平衡因子 BF = 左子树高度 - 右子树高度。BF 的取值范围为 {-1, 0, 1}。

AVL 的插入与调整：

插入新结点后，从插入位置向上回溯找到第一个不平衡的结点，根据不平衡情况做旋转：

不平衡情况	操作	说明
LL	右单旋	结点在左孩子的左子树
RR	左单旋	结点在右孩子的右子树
LR	先左旋再右旋	结点在左孩子的右子树
RL	先右旋再左旋	结点在右孩子的左子树

LL 右单旋示例：A 的 BF=2，左孩子 B 的 BF=1。将 B 提升为根，A 成为 B 的右孩子，B 原来的右子树成为 A 的左子树。

LR 先左后右示例：A 的 BF=2，左孩子 B 的 BF=-1。先对 B 做左旋，再对 A 做右旋。

📌 408考点提示：AVL 的四种调整是必考内容。在做选择题时，往往需要手动画出调整后的树形。诀窍是找三个关键结点（祖孙三代）进行旋转操作。

7.6 红黑树

红黑树是一种近似平衡的二叉查找树，可以保证最长路径不超过最短路径的两倍。

红黑树的五个性质：

每个结点是红色或黑色。
根结点是黑色。
叶子结点（NIL）是黑色。
红色结点的两个子结点都是黑色（不能有连续红）。
从任一结点到其每个叶子的路径上黑结点数量相同（黑高相等）。

与 AVL 的对比：

AVL 更平衡，查找更快；红黑树插入/删除时调整更少。
408 对红黑树要求不高，了解概念和性质即可，重点是理解"黑高"概念。

7.7 B树和B+树（重点）

B树

B 树是一棵多路平衡查找树。一棵 m 阶 B 树满足：

每个结点最多有 m 棵子树（m-1 个关键字）。
根结点至少 2 棵子树（若根不是叶子），至少 1 个关键字。
除根外，每个非叶子结点至少有 ⌈m/2⌉ 棵子树。
所有叶子结点在同一层（空指针层）。
非叶子结点的关键字从左到右递增。

B树的查找：类似 BST，在结点内顺序查找或折半查找，然后进入对应子树。

B树的插入：

插入后若结点关键字数 ≤ m-1，则插入完成。
若关键字数 = m（溢出），则从中间位置 ⌈m/2⌉ 分裂，中间关键字上升到父结点，左右两部分分裂为两个结点。
分裂可能导致父结点也溢出，需要继续向上分裂，直到根结点。若根结点分裂，树的高度加 1。

B树插入示例（5阶B树）：依次插入 1, 2, 3, 4, 5：

插入1~4：根结点 [1,2,3,4]
插入5：溢出→分裂→ [3] 为根，[1,2] 和 [4,5] 为孩子
继续插入6,7：适当位置插入：
  [3]
 /   \
[1,2] [4,5,6,7]
插入8：右孩子溢出→分裂→ [5] 上升到根
  [3,5]
 /  |  \
[1,2] [4] [6,7,8]

B树的删除：

删除叶子结点关键字后，若关键字数 ≥ ⌈m/2⌉-1，则完成。
若不足，先看左右兄弟能否借（兄弟关键字数 > ⌈m/2⌉-1），能借则通过父结点旋转。
若兄弟也不足，则与兄弟合并（父结点关键字下移）。
合并可能导致父结点关键字不足，需要继续向上合并。

B树删除示例（5阶B树，⌈5/2⌉=3，最少关键字数=2）：删除关键字后若结点关键字数 < 2，则需要借或合并。

向兄弟借：父结点关键字下移，兄弟关键字上移。
与兄弟合并：父结点关键字下移后与兄弟合并。

📌 408考点提示：B树的插入和删除过程是高频综合题。需要能手动模拟 3 阶或 4 阶 B 树的插入分裂过程。考试通常要求画出每一操作后的树形。注意 m 阶 B 树每个结点最多 m-1 个关键字，最少 ⌈m/2⌉-1 个关键字（根除外）。

💡 记忆技巧：B 树的根最少有 2 个分支，其他内部结点最少有 ⌈m/2⌉ 个分支，最多有 m 个分支。"少则借，多则裂"——这是 B 树插入删除的核心思想。

B+树

B+树是 B 树的变体，常用于数据库索引。

B+树与 B 树的区别：

特性	B树	B+树
关键字位置	所有结点中	仅叶子结点
分支数量	与关键字数同	= 关键字数
叶子结点	存储数据	存储数据+链表连接
非叶子结点	存储数据	仅作索引，存储最大关键字

7.8 散列表（哈希表）

散列函数构造

常用散列函数：

直接定址法：H(key) = a×key + b。适合关键字分布基本连续的情况。
除留余数法：H(key) = key % p。p 取不大于表长 m 的最大质数。
数字分析法：取关键字中分布均匀的若干位。
平方取中法：取关键字平方的中间几位。

冲突处理

开放地址法：

线性探测法：Hᵢ = (H(key) + dᵢ) % m，dᵢ = 0, 1, 2, ...
- 优点：简单，不易聚集。
- 缺点：容易产生"堆积"现象。
平方探测法：dᵢ = 0², 1², -1², 2², -2², ...
- 优点：不易堆积。
- 缺点：不一定能探测到所有位置（需满足 m 为 4k+3 的质数）。
再散列法：Hᵢ = (H(key) + i×H₂(key)) % m。

链地址法：将同义词用链表连接起来。查找时先在哈希函数定位的链表中顺序查找。

装填因子与ASL

装填因子 α = 表中元素个数 / 表长。α 越大，冲突概率越高，查找效率越低。

线性探测法的 ASL：

ASL_成功 ≈ 1/2 × (1 + 1/(1-α))
ASL_失败 ≈ 1/2 × (1 + 1/(1-α)²)

链地址法的 ASL：

ASL_成功 ≈ 1 + α/2
ASL_失败 ≈ α + e^(-α)

📌 408考点提示：散列表的 ASL 计算是必考题型，需要能够手动构造散列表，计算等概率下的查找成功与失败的 ASL。注意"查找失败"在开放地址法中是探测到空位置为止。

7.9 题型示例

例题1：对有序表 {1, 3, 5, 7, 9, 11, 13, 15, 17} 进行折半查找，计算 ASL_成功和 ASL_失败。

解：画出判定树，树高 h = ⌈log₂(9+1)⌉ = 4。

             7
           /   \
          3     11
         / \   /  \
        1   5 9   13
                   \
                    15
                      \
                       17

ASL_成功 = (1×1 + 2×2 + 4×3 + 2×4) / 9 = (1+4+12+8)/9 = 25/9 ≈ 2.78 ASL_失败 = (3×3 + 6×4) / 10 = (9+24)/10 = 33/10 = 3.3 （10 个失败区间，3 个在高度 3 层，6 个在高度 4 层）

例题2：关键字序列 {7, 8, 30, 11, 18, 9, 14}，散列表长 11，H(key)=key%7，用线性探测法处理冲突，求 ASL_成功和 ASL_失败。

解：

key:  7  8  30  11  18  9  14
H:    0  1   2   4   4  2   0
位置:
7→0, 8→1, 30→2, 11→4
18→4冲突→5, 9→2冲突→3, 14→0冲突→6
最终位置:
key:  7  8  30  9  11  18  14
pos:  0  1   2  3   4   5   6

ASL_成功 = (1+1+1+2+1+2+2) / 7 = 10/7 ≈ 1.43 ASL_失败 = (9+8+7+6+5+4+3+2+1+1+1) / 11 = 47/11 ≈ 4.27 （从每个哈希值开始探测直到空位的距离）

例题3：在 5 阶 B 树中，依次插入 1, 2, 3, 4, 5，画出插入过程。

解：

插入 1, 2, 3, 4：根结点有 4 个关键字，正常。
插入 5：结点关键字数 = 5 = m，溢出。从 ⌈5/2⌉ = 3 处分裂，关键字 3 上升到新根，1,2 和 4,5 分成两个结点。

        [3]
       /   \
    [1,2]  [4,5]

例题4：给定关键字序列 {15, 7, 22, 8, 14, 29, 18, 6, 26}，构造 AVL 树，若需要旋转请说明旋转类型。

解：依次插入：

插入 15：AVL = {15}
插入 7：{7, 15}，平衡
插入 22：{7, 15, 22}，平衡
插入 8：

    15          15
   /  \   →    /  \
  7   22      8   22
   \         /
    8       7

BF(15)=1-1=0，BF(7)=0-1=-1，平衡。

插入 14：

BF(15)=2-1=1，BF(8)=1-1=0，BF(7)=0，BF(14)=0 均正常。

插入 29：

BF(15)=2-2=0，平衡。

插入 18：插入到 22 的左子树

    15
   /  \
  8   22
 / \  / \
7  14 18 29

BF(22)=1-1=0，BF(15)=2-2=0，平衡。

插入 6：插入到 7 的左子树

      15
     /  \
    8   22
   / \  / \
  7  14 18 29
 /
6

BF(8)=2-1=1，BF(15)=3-2=1，均 ≤1，无需旋转，平衡。

插入 26：插入到 22 的右子树→29 的左子树

      15
     /  \
    8   22
   / \  / \
  7  14 18 29
 /        /
6       26

BF(29)=1-0=1，BF(22)=1-2=-1，BF(15)=2-3=-1，均 ≤1。检查结点 22 的平衡因子 BF=-1，其右孩子 29 的 BF=1 → RL 型不平衡。先右旋：以 29 为支点右旋 → 26 成为 29 的父结点再左旋：以 22 为支点左旋 → 26 成为新根

      15
     /  \
    8   26
   / \  / \
  7  14 22 29
 /       \  /
6        18 26

最终得到平衡的 AVL 树。

        [3]
       /   \
    [1,2]  [4,5]

本章总结

查找是 408 中占比很大的一部分，其中折半查找的判定树、AVL 树的旋转调整、B 树的分裂合并、散列表的 ASL 计算是高频考点。查找算法的核心评价指标是 ASL，需要能够熟练计算各种查找结构在成功和失败两种情况下的 ASL。

查找

查找