引言

第七章“查找”是数据结构里和“工程实现”最贴近的一章。前面学线性表、树、图，更多是结构本身；这一章关心的是：

给你一个关键字，怎么最快找到它。

这章可以分成五条主线：

1. 静态查找：顺序查找、折半查找、分块查找
2. 动态查找树：二叉排序树、AVL、红黑树
3. 多路平衡查找：B树、B+树
4. 散列查找：散列函数、冲突处理、性能分析
5. 全章对比：复杂度、适用场景、常见坑

本篇把 E:\PPT 下第七章全部课件合并，并补齐 PPT 中一笔带过但考试会考、实战会踩坑的部分。

图像化理解（Mermaid）

  mindmap
  root((第七章查找体系))
    静态查找
      顺序查找
      折半查找
      分块查找
    动态查找树
      BST
      AVL
      红黑树
    多路查找
      B树
      B+树
    散列查找
      散列函数
      冲突处理（拉链/开放定址）
  

一句话：查找问题本质是“时间、更新代价、空间”三者取平衡。

一、查找的基本概念

1. 基础术语

• 查找：在数据集合中寻找满足条件的数据元素。
• 查找表（查找结构）：用于查找的数据集合。
• 关键字：能标识记录的数据项。

按是否需要维护插入/删除，可分为：

• 静态查找表：只查找，不改动。
• 动态查找表：查找 + 插入 + 删除。

2. 查找长度与 ASL

• 查找长度：一次查找中比较关键字的次数。
• 平均查找长度（ASL）：所有查找情况查找长度的期望。

统一表达式：

1

ASL = Σ(Pi * Ci)

• Pi：第 i 种查找情况发生概率
• Ci：该情况下比较次数

评价查找算法时，一般分开讨论：查找成功 ASL 与查找失败 ASL。

二、顺序查找（线性查找）

1. 思想

从头到尾依次比较，直到找到目标或越界。

2. 代码（普通版）

1
2
3
4
5
6
7
8

int SeqSearch(const int a[], int n, int key) {
    for (int i = 0; i < n; ++i) {
        if (a[i] == key) {
            return i;
        }
    }
    return -1;
}

3. 代码（哨兵版，1-based）

1
2
3
4
5
6
7
8
9

int SeqSearchSentinel(int a[], int n, int key) {
    // 约定 a[1..n] 存数据，a[0] 作为哨兵
    a[0] = key;
    int i = n;
    while (a[i] != key) {
        --i;
    }
    return i; // i==0 表示失败
}

4. 复杂度与 ASL

• 时间复杂度：O(n)
• 空间复杂度：O(1)

等概率查找成功：

1

ASL成功 = (1 + 2 + ... + n) / n = (n + 1) / 2

等概率查找失败（普通版）：

1

ASL失败 = n

等概率查找失败（哨兵版，计比较次数常取 n+1 或 n，看课程口径）。

5. 有序表顺序查找优化

若表递增有序，比较到 a[i] > key 可提前失败。

6. 易错点

1. 哨兵版返回 0 代表失败，不是 -1。
2. 有序顺序查找提前失败仅在“有序表”成立。
3. “被查概率不等”时应将高频元素尽量前置。

三、折半查找（二分查找）

1. 适用条件

1. 顺序存储（可随机访问）
2. 关键字有序

链表不适合折半查找。

2. 代码（迭代版）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int BinarySearch(const int a[], int n, int key) {
    int low = 0;
    int high = n - 1;

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

3. 代码（递归版）

1
2
3
4
5
6
7
8
9
10
11
12
13

int BinarySearchRec(const int a[], int low, int high, int key) {
    if (low > high) {
        return -1;
    }
    int mid = low + (high - low) / 2;
    if (a[mid] == key) {
        return mid;
    }
    if (a[mid] < key) {
        return BinarySearchRec(a, mid + 1, high, key);
    }
    return BinarySearchRec(a, low, mid - 1, key);
}

4. 复杂度

• 时间复杂度：O(log2 n)
• 空间复杂度：
  • 迭代：O(1)
  • 递归：O(log2 n)（递归栈）

5. 判定树性质

按 mid = floor((low+high)/2) 构造时：

• 判定树近似完全二叉树
• 任意结点左右子树高度差不超过 1

6. 易错点

1. while (low <= high) 不能写成 <。
2. mid 建议写成 low + (high - low) / 2 防溢出。
3. 失败条件是 low > high。
4. 若题目改成 ceil((low+high)/2)，判定树形态会变，别套错模板。

四、分块查找（索引顺序查找）

1. 思想

把表分成若干块：

• 块间有序（按每块最大关键字排序）
• 块内无序（通常顺序查）

先查索引表定位块，再在块内查找。

2. 索引结构

每个索引项一般含：

• maxKey：本块最大关键字
• start/end：本块区间

3. 查找流程

1. 在索引表中找目标所属块（可顺序，可折半）。
2. 进入块内顺序查找。

4. 关键细节（折半查索引）

若索引中找不到 key，最后会 low > high，应去 low 对应块尝试（前提 low 未越界）；若 low 越界则失败。

5. ASL（等分块，n=bs）

• 索引顺序查：

1

ASL = (b+1)/2 + (s+1)/2

• 索引折半查：

1

ASL ≈ log2(b+1) + (s+1)/2

6. 易错点

1. 分块查找不是“全局有序”，块内可无序。
2. 索引折半失败时不是立刻失败，要看 low 是否可用。
3. b 与 s 的取值影响 ASL，应平衡索引成本与块内成本。

五、二叉排序树 BST

1. 定义

对任一结点：

• 左子树关键字 < 根
• 右子树关键字 > 根

中序遍历得到递增序列。

2. 结点定义

1
2
3
4
5
6

struct BSTNode {
    int key;
    BSTNode* left;
    BSTNode* right;
    BSTNode(int k) : key(k), left(nullptr), right(nullptr) {}
};

3. 查找

1
2
3
4
5
6
7
8
9
10

BSTNode* BSTSearch(BSTNode* root, int key) {
    BSTNode* cur = root;
    while (cur != nullptr) {
        if (key == cur->key) {
            return cur;
        }
        cur = (key < cur->key) ? cur->left : cur->right;
    }
    return nullptr;
}

4. 插入

1
2
3
4
5
6
7
8
9
10
11

BSTNode* BSTInsert(BSTNode* root, int key) {
    if (root == nullptr) {
        return new BSTNode(key);
    }
    if (key < root->key) {
        root->left = BSTInsert(root->left, key);
    } else if (key > root->key) {
        root->right = BSTInsert(root->right, key);
    }
    return root; // 相等则忽略
}

5. 删除（完整三种情况）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

BSTNode* FindMin(BSTNode* root) {
    BSTNode* cur = root;
    while (cur && cur->left) {
        cur = cur->left;
    }
    return cur;
}

BSTNode* BSTDelete(BSTNode* root, int key) {
    if (root == nullptr) {
        return nullptr;
    }
    if (key < root->key) {
        root->left = BSTDelete(root->left, key);
        return root;
    }
    if (key > root->key) {
        root->right = BSTDelete(root->right, key);
        return root;
    }

    if (root->left == nullptr && root->right == nullptr) {
        delete root;
        return nullptr;
    }
    if (root->left == nullptr || root->right == nullptr) {
        BSTNode* child = (root->left != nullptr) ? root->left : root->right;
        delete root;
        return child;
    }

    BSTNode* succ = FindMin(root->right);
    root->key = succ->key;
    root->right = BSTDelete(root->right, succ->key);
    return root;
}

6. 复杂度

设树高 h：查找/插入/删除均为 O(h)。

• 最好：O(log n)
• 最坏退化链：O(n)

7. 易错点

1. 删除“两孩子”结点时，替换后还要继续删除后继/前驱原结点。
2. 插入序列不同会导致树形不同，ASL 差异很大。
3. 重复关键字策略要统一（忽略、计数、放右侧）。

六、平衡二叉树 AVL

1. 定义

• 任一结点左右子树高度差不超过 1。
• 平衡因子 bf = h(left) - h(right)，取值只可能 -1/0/1。

2. 旋转类型

• LL：右旋
• RR：左旋
• LR：先左后右
• RL：先右后左

3. 完整实现（插入 + 删除）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

#include <algorithm>

struct AVLNode {
    int key;
    int height;
    AVLNode* left;
    AVLNode* right;
    AVLNode(int k) : key(k), height(1), left(nullptr), right(nullptr) {}
};

int Height(AVLNode* n) {
    return n == nullptr ? 0 : n->height;
}

int BalanceFactor(AVLNode* n) {
    return n == nullptr ? 0 : Height(n->left) - Height(n->right);
}

void UpdateHeight(AVLNode* n) {
    if (n != nullptr) {
        n->height = std::max(Height(n->left), Height(n->right)) + 1;
    }
}

AVLNode* RotateRight(AVLNode* y) {
    AVLNode* x = y->left;
    AVLNode* t2 = x->right;
    x->right = y;
    y->left = t2;
    UpdateHeight(y);
    UpdateHeight(x);
    return x;
}

AVLNode* RotateLeft(AVLNode* x) {
    AVLNode* y = x->right;
    AVLNode* t2 = y->left;
    y->left = x;
    x->right = t2;
    UpdateHeight(x);
    UpdateHeight(y);
    return y;
}

AVLNode* Rebalance(AVLNode* root) {
    UpdateHeight(root);
    int bf = BalanceFactor(root);

    if (bf > 1) {
        if (BalanceFactor(root->left) < 0) {
            root->left = RotateLeft(root->left); // LR
        }
        return RotateRight(root); // LL
    }
    if (bf < -1) {
        if (BalanceFactor(root->right) > 0) {
            root->right = RotateRight(root->right); // RL
        }
        return RotateLeft(root); // RR
    }
    return root;
}

AVLNode* AVLInsert(AVLNode* root, int key) {
    if (root == nullptr) {
        return new AVLNode(key);
    }
    if (key < root->key) {
        root->left = AVLInsert(root->left, key);
    } else if (key > root->key) {
        root->right = AVLInsert(root->right, key);
    } else {
        return root;
    }
    return Rebalance(root);
}

AVLNode* AVLMin(AVLNode* root) {
    AVLNode* cur = root;
    while (cur && cur->left) {
        cur = cur->left;
    }
    return cur;
}

AVLNode* AVLDelete(AVLNode* root, int key) {
    if (root == nullptr) {
        return nullptr;
    }
    if (key < root->key) {
        root->left = AVLDelete(root->left, key);
    } else if (key > root->key) {
        root->right = AVLDelete(root->right, key);
    } else {
        if (root->left == nullptr || root->right == nullptr) {
            AVLNode* child = (root->left != nullptr) ? root->left : root->right;
            delete root;
            return child;
        }
        AVLNode* succ = AVLMin(root->right);
        root->key = succ->key;
        root->right = AVLDelete(root->right, succ->key);
    }
    return Rebalance(root);
}

4. AVL 删除的关键结论

1. 删除后可能出现“向上传播不平衡”。
2. 需要从删除点一路向上做 rebalance。
3. 这点和插入不同：插入通常修好“最小不平衡子树”就结束；删除可能继续传播。

5. 复杂度

• 查找/插入/删除：O(log n)

6. 易错点

1. 旋转后忘记更新高度。
2. LR/RL 的“双旋顺序”写反。
3. 删除后提前 return 导致祖先未重平衡。

七、红黑树 RBT

1. 五条性质

口诀：左根右，根叶黑，不红红，黑路同。

1. 结点非红即黑。
2. 根为黑。
3. 所有空叶（NULL）为黑。
4. 红结点不能有红孩子。
5. 任一结点到所有后代空叶路径的黑结点数相同。

2. 黑高与高度结论

• 黑高 bh(x)：从 x 到任一后代空叶路径上的黑结点数（不含 x）。
• 树高 h <= 2log2(n+1)。
• 查找复杂度：O(log n)。

3. 插入调整（核心模板）

新结点默认红：

• 若父黑：结束。
• 若父红：看叔叔颜色。

1. 红叔：父叔变黑，爷变红，指针上移到爷继续。
2. 黑叔：按 LL/RR/LR/RL 旋转 + 染色。

4. 删除说明（补全）

PPT 对删除讲得很少，但考试至少会问原则：

1. 先按 BST 规则删结点。
2. 若删掉黑结点，可能破坏黑高，进入“修复双黑”流程。
3. 修复依据：兄弟颜色、兄弟子女颜色，做旋转与染色。

常见四大类：

• 兄弟红：先旋转转化成兄弟黑情形。
• 兄弟黑且双黑子：兄弟染红，问题上移。
• 兄弟黑且近侄红远侄黑：先转成远侄红。
• 兄弟黑且远侄红：旋转 + 染色一次修复。

红黑树删除实现复杂度高，手算题通常以“判断旋转与染色步骤”为主。

5. 易错点

1. 空叶也算黑，黑高计算不能漏。
2. “红叔”不是旋转优先，是染色优先。
3. 红黑树是“弱平衡”，不是 AVL 那种高度严格平衡。

八、B树（多路平衡查找树）

1. m 阶 B 树定义

1. 每结点最多 m 棵子树，最多 m-1 个关键字。
2. 根若非叶，至少 2 棵子树。
3. 非根非叶至少 ceil(m/2) 棵子树，即至少 ceil(m/2)-1 关键字。
4. 结点内关键字有序；子树区间有序。
5. 所有叶（失败结点）在同一层。

2. B树查找

每层先在结点内定位区间，再沿对应孩子下降。

• 结点内顺序查：每层 O(m)
• 结点内折半查：每层 O(log m)

总复杂度与高度成正比，通常写 O(log n)。

3. B树插入

1. 先定位到叶结点插入。
2. 若结点关键字超上限（m 个），则分裂：
   • 中间关键字上升父结点
   • 左右分裂为两个结点
3. 若父也超限，继续向上分裂，可能导致新根产生、树高 +1。

4. B树删除

1. 若删的是内部结点关键字，用前驱/后继替换，转为删叶。
2. 删除后若结点低于下限：
   • 能向兄弟借：借 + 父子调整
   • 不能借：与兄弟及父关键字合并
3. 合并可能继续向上传播，可能导致树高 -1。

5. B树高度范围

对 n 个关键字：

1

log_m(n+1) <= h <= log_{ceil(m/2)}((n+1)/2) + 1

（不同教材 h 是否计失败层略有差异，做题按题目口径）

6. 易错点

1. B树“n 个关键字对应 n+1 子树”。
2. 根结点下限和普通内部结点下限不同。
3. 删除中的“借/并”后要同步维护父关键字。

九、B+树

1. 与 B 树核心差异

1. B+树内部结点只存索引，不存记录地址。
2. 所有关键字都在叶结点出现。
3. 叶结点按关键字顺序链起来，天然支持范围/顺序查询。
4. 非叶结点关键字可重复出现在叶结点。

2. 结构规则（m 阶）

1. 非叶结点关键字数 = 子树数（B树是子树数-1）。
2. 根关键字数区间与普通内部结点区间按教材定义走，核心是“绝对平衡 + 叶层齐平”。

3. 查找特点

不论成功失败，一般都要走到叶层，查找路径长度更稳定。

4. 为什么数据库爱用 B+树

1. 内部结点不存记录，扇出更大、树更矮、IO 更少。
2. 范围查询只需扫叶链，性能优秀。
3. 路径稳定，缓存命中友好。

5. 易错点

1. B+树不是“B树加链表”这么简单，本质是索引层与数据层分离。
2. B+树内部关键字不代表记录只在该层存在。
3. B+树顺序查找从叶层链表走，不从内部层横跳。

十、散列表（Hash Table）

1. 基本概念

• 散列函数：Addr = H(key)
• 冲突：不同 key 映射到同一地址
• 同义词：发生冲突的 key

理想平均查找 O(1)。

2. 常见散列函数

1. 除留余数法：H(key) = key % p（p 常取接近表长的质数）
2. 直接定址法
3. 数字分析法
4. 平方取中法

3. 冲突处理一：拉链法

把同义词放到同一链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

struct Node {
    int key;
    Node* next;
    Node(int k, Node* n) : key(k), next(n) {}
};

const int M = 13;
Node* table[M] = {nullptr};

int Hash(int key) { return key % M; }

void Insert(int key) {
    int idx = Hash(key);
    table[idx] = new Node(key, table[idx]);
}

bool Find(int key) {
    int idx = Hash(key);
    for (Node* p = table[idx]; p != nullptr; p = p->next) {
        if (p->key == key) {
            return true;
        }
    }
    return false;
}

特点：删除简单，装填因子可大于 1。

4. 冲突处理二：开放定址法

冲突时按探测序列找下一个位置：

1

Hi = (H(key) + di) % m

常见 di：

1. 线性探测：0,1,2,...
2. 平方探测：0,1^2,-1^2,2^2,-2^2...
3. 双散列：i * hash2(key)
4. 伪随机序列

开放定址删除关键点

• 不能物理置空，需“逻辑删除”标记。
• 否则会截断后续探测链，导致本来存在的元素查找失败。

5. 装填因子与性能

1

alpha = n / m

• n：表中元素个数
• m：散列表长度

alpha 越大，冲突概率越高，ASL 越大。

6. 聚集（堆积）现象

线性探测容易主聚集，导致连续占用区变长，后续冲突更严重。

一般可用平方探测、双散列缓解。

7. 易错点

1. 散列表长度与散列函数取模范围不一致时，失败 ASL 的“等概率空间”要按函数值域算。
2. 开放定址删除必须逻辑删。
3. 双散列若 hash2 与表长不互质，可能探测不全。

十一、全章复杂度总对比

十二、考试高频易混淆清单

1. 折半查找只能用于“有序顺序表”，不能直接用于链表。
2. BST 中序有序，但 AVL/红黑/B树/B+树本质也都保序。
3. AVL 是“严格平衡”，红黑是“近似平衡”。
4. B树关键字不重复；B+树内部关键字可在叶层重复。
5. B树：n 个关键字配 n+1 子树；B+树内部常是 n 对应 n 子树（按教材定义）。
6. 散列表平均快，不代表最坏快；冲突严重时可退化。
7. 开放定址删除不是物理删。
8. 分块查找的块内可无序，别误当二分。
9. 红黑树“黑高”按到空叶路径算，空叶是黑。
10. AVL 删除可能连续失衡向上传播。

十三、本章手算模板（考场速用）

1. 折半查找

固定写三元组：low, mid, high，每次更新后再比较。

2. BST/AVL/红黑插入

先走“BST 定位”，再做结构调整。

3. B树插删

插入：超上限就分裂上推。

删除：低下限就借，不够借就并，可能向上传播。

4. 散列表

统一先列：

1
2

H(key)
冲突处理序列 di

再逐步写探测地址，避免跳步算错。

十四、图像化总览（Mermaid）

1. 静态查找选型图

  flowchart TD
    A[查找选型] --> B[数据无序 -> 顺序查找 O(n)]
    A --> C[数据有序且可随机访问 -> 折半查找 O(log n)]
    A --> D[分块组织 -> 分块查找]
  

2. BST / AVL / 红黑树对比图

  mindmap
  root((BST/AVL/红黑树))
    BST
      不平衡可退化成链
    AVL
      严格平衡
      查找更稳
      插删旋转更频繁
    红黑树
      弱平衡
      插删代价低 工程常用
      查找 O(log n)
  

3. B树 / B+树对比图

  flowchart TD
    B[B树] --> B1[关键字分散在各层结点]
    BP[B+树] --> BP1[非叶只做索引]
    BP --> BP2[关键字集中在叶子]
    BP --> BP3[叶子有序链 范围查询快]
  

4. 散列表冲突处理图

  flowchart TD
    A[冲突发生] --> B[拉链法: 同义词挂同一链]
    A --> C[开放定址: 按探测序列找空位]
    C --> D[线性]
    C --> E[平方]
    C --> F[双散列]
    C --> G[伪随机]
  

5. 开放定址删除图

  flowchart TD
    A[开放定址删除元素] --> B[不能直接置空]
    B --> C[必须逻辑删除标记]
    C --> D[避免截断后续探测链]
  

十五、易错点与易混淆点（详细版）

A. 易混淆点（A vs B）

1. 折半查找 vs 分块查找

   • 折半：全局有序，直接二分
   • 分块：块间有序、块内可无序

2. BST vs AVL vs 红黑树

   • BST：可能退化
   • AVL：严格平衡，查找更稳
   • 红黑树：弱平衡，更新更友好

3. B树 vs B+树

   • B树：关键字分散在内部和叶子
   • B+树：数据集中在叶子，内部只索引

4. 拉链法 vs 开放定址法

   • 拉链法冲突后进链表
   • 开放定址冲突后探测下一个槽位

5. 平均 O(1) vs 最坏 O(1)

   • 散列表通常是平均 O(1)
   • 冲突极端时最坏可能退化

B. 易错点（为什么错 + 怎么改）

1. 折半查找误用于链表

   • 错因：忽略折半需要随机访问。
   • 正解：链表一般不做折半，按顺序或跳表/树结构处理。

2. AVL 删除只调一次平衡就结束

   • 错因：套用了插入场景思维。
   • 正解：删除可能向上传播失衡，要持续回溯调整。

3. 红黑树黑高漏算空叶

   • 错因：把 NULL 忽略。
   • 正解：红黑树定义里空叶是黑结点，黑高要计入路径一致性。

4. B树删除后忘记借/并向上传播

   • 错因：只修复当前结点下限。
   • 正解：父结点可能继续下溢，必须继续处理到根。

5. 开放定址删除直接清空

   • 错因：忽略探测链连续性。
   • 正解：用逻辑删除标记，必要时再重整表。

6. 散列表失败 ASL 概率空间取错

   • 错因：按表长平均，而非按散列函数可落点平均。
   • 正解：先看题目“等概率”定义，是对地址空间还是关键字空间。

C. 本章做题顺序建议

1
2
3
4
5

先判：静态查找 / 动态查找 / 散列
  |
  +-- 树题：先保有序，再保平衡
  |
  +-- 散列题：先写 H(key)，再写冲突探测序列

十六、书签级思维导图复现（第七章，Mermaid）

  mindmap
  root((第7章 查找))
    7.1 查找基础
      查找表/关键字/ASL
      成功ASL与失败ASL
      静态查找 vs 动态查找
    7.2 静态查找
      顺序查找（含哨兵）
      折半查找（有序+顺序存储）
      分块查找（索引+块内查找）
    7.3 动态查找树
      BST（查插删）
      AVL（LL/RR/LR/RL）
      红黑树（性质与调整）
    7.4 多路平衡查找
      B树（插入分裂/删除借并）
      B+树（叶链范围查询）
    7.5 散列表
      散列函数
      冲突处理（拉链/开放定址）
      装填因子 alpha
      ASL 与聚集现象
  

十七、PDF 例题与知识点补充（查找）

例题 1：顺序查找成功 ASL

题目：长度为 n 的线性表进行顺序查找，若每个元素被查概率相等，成功查找 ASL 是多少？

答案：ASL = (n+1)/2。

详细解析：

1. 第 i 个位置查找成功需要比较 i 次。
2. 等概率条件下，平均比较次数是 1..n 的算术平均。
3. 所以 ASL = (1+2+...+n)/n = (n+1)/2。

例题 2：顺序查找失败 ASL

题目：普通顺序查找在失败时通常要比较多少次？

答案：常按 n 记（部分教材口径含哨位可写 n+1）。

详细解析：

1. 不设哨兵时，失败要把 n 个元素都比较完。
2. 设哨兵时写法不同，比较次数口径可能多 1。
3. 做题时应先看教材定义再代公式。

例题 3：哨兵顺序查找返回值

题目：顺序表 1 基下标且设置哨兵时，失败通常返回什么下标？

答案：返回 0。

详细解析：

1. 常见写法把哨兵放在 a[0]。
2. 若最终停在 0，表示在真实元素区 1..n 未找到目标。

例题 4：折半查找适用条件

题目：折半查找能使用的前提是什么？

答案：数据有序，且结构支持随机访问（通常是顺序存储）。

详细解析：

1. 折半依赖“中间元素”定位，需要快速按下标访问。
2. 若是链表，访问中点代价高，整体失去折半优势。
3. 若数据无序，比较后无法排除半区。

例题 5：折半查找失败条件

题目：二分循环何时判定失败？

答案：当 low > high。

详细解析：

1. 搜索区间始终是闭区间 [low, high]。
2. 当下界越过上界，区间为空，说明目标不存在。

例题 6：分块查找结构条件

题目：分块查找对数据组织的核心要求是什么？

答案：块间有序，块内可无序。

详细解析：

1. 先在索引表中定位目标可能所在块。
2. 再在该块内顺序查找。
3. 若块间无序，则无法通过索引快速缩小范围。

例题 7：分块查找 ASL（等分块）

题目：等分块下，若索引表也顺序查找，分块查找 ASL 常用公式是什么？

答案：ASL = (b+1)/2 + (s+1)/2。

详细解析：

1. 设共有 b 块、每块 s 个元素。
2. 第一步在索引中平均比较 (b+1)/2 次。
3. 第二步块内平均比较 (s+1)/2 次。
4. 两部分相加得到整体 ASL。

例题 8：BST 中序性质

题目：二叉排序树（BST）做中序遍历有什么结论？

答案：得到关键字递增序列（无重复关键字时严格递增）。

详细解析：

1. BST 满足左子树键值小于根，右子树键值大于根。
2. 中序遍历顺序是“左-根-右”，天然输出有序结果。

例题 9：BST 删除两孩子结点

题目：BST 中删除一个有两个孩子的结点，标准处理步骤是什么？

答案：用其中序后继（或前驱）替换该结点，再删除后继（或前驱）原位置结点。

详细解析：

1. 直接删会破坏 BST 有序性质。
2. 后继是右子树最小结点（前驱是左子树最大结点），替换后仍满足有序约束。
3. 被替换来源结点最多只有一个孩子，后续删除更简单。

例题 10：AVL 旋转判定

题目：AVL 四种失衡类型对应的旋转方式是什么？

答案：

1. LL：右旋
2. RR：左旋
3. LR：先左旋子树，再右旋根
4. RL：先右旋子树，再左旋根

详细解析：

1. 单旋用于“同向失衡”（LL、RR）。
2. 双旋用于“交叉失衡”（LR、RL）。
3. 目标都是恢复每个结点平衡因子到 -1/0/1。

例题 11：AVL 删除传播

题目：AVL 删除后为什么可能需要向上多次调整？

答案：删除会降低子树高度，失衡可能沿祖先链逐层传播。

详细解析：

1. 插入通常只在首个失衡点一次旋转即可结束。
2. 删除后某层恢复平衡但高度继续变化，可能影响更高祖先。
3. 因此应回溯到根，逐层检查并旋转。

例题 12：红黑树性质核对

题目：红黑树必须满足哪些核心性质？

答案：根为黑、空叶（NIL）为黑、红结点无红孩子、任一结点到后代 NIL 的黑高相同。

详细解析：

1. 红黑树用颜色约束近似平衡，避免退化。
2. 黑高一致保证路径长度不会差太多。
3. 不红红规则阻止连续“过长红链”。

例题 13：B树删除下溢处理

题目：B 树删除导致结点关键字下溢时，处理顺序是什么？

答案：先向兄弟借，借不到再与兄弟合并，必要时继续向上传播。

详细解析：

1. 借关键字优先，因为对结构破坏最小。
2. 借不到说明兄弟也在下限，只能合并。
3. 合并会减少父结点关键字，父结点可能再次下溢。

例题 14：B+树优势

题目：相比 B 树，B+ 树为什么更适合数据库索引与范围查询？

答案：内部结点只存索引更“扇出大”，叶结点按链相连，范围扫描连续高效。

详细解析：

1. 扇出增大意味着树高更低，磁盘 I/O 更少。
2. 所有记录都在叶层，查询路径长度更稳定。
3. 叶链天然支持区间顺序遍历。

例题 15：开放定址删除

题目：开放定址散列表删除元素时为什么不能直接置空？

答案：直接置空会截断后续探测链，必须用“删除标记”进行逻辑删除。

详细解析：

1. 查找依赖连续探测序列。
2. 若中间空位被误判为“链结束”，会导致后面的真实元素找不到。
3. 删除标记可保持探测连续性，同时允许后续插入复用该槽位。

十八、第七章必背核对表

1. 折半查找不能直接用于链表。
2. 分块查找不是“全局有序”。
3. BST 删除两孩子结点要二次删除来源结点。
4. AVL 删除可能连续回溯调整。
5. 红黑树空叶也是黑。
6. B树/B+树结构差异要清晰。
7. 开放定址删除必须逻辑删。
8. 散列表复杂度通常说“平均 O(1)”。

总结

第七章真正的核心不是“记定义”，而是掌握每类查找结构在三件事上的平衡：

1. 查找速度
2. 更新成本（插删）
3. 存储与实现复杂度

从考研角度，必须吃透：

• 顺序/折半/分块的 ASL 计算
• BST/AVL/红黑的调整逻辑
• B树/B+树的结构约束与插删传播
• 散列冲突处理与装填因子影响

把这四组问题打通，第七章就不仅会做题，也能解释“为什么工业界这样设计索引”。

作者：[Austoin]
参考资料：王道考研《数据结构》第七章全部课件（E:\PPT）