查找是在一组记录中定位目标。算法效率取决于数据是否有序、能否随机访问、更新是否频繁，以及一次比较或访存的成本。
本章用两个问题串起基础查找与树形查找：
- 范围怎样缩小？ 顺序查找逐个排除，折半查找每次排除一半；
- 有序性怎样维持？ BST、AVL、红黑树用结构不变量支撑动态查找。
多路索引（B 树、B+ 树）与散列表属于第 9 章散列与索引结构：前者把本章的树形查找推广到外存，后者换到“地址计算”路线。
学习目标
完成本章后，你应该能够：
- 区分静态查找表与动态查找表，用平均查找长度（ASL）衡量比较代价；
- 手算顺序查找、分块查找和折半查找的比较次数，解释折半判定树；
- 完成 BST 的查找、插入和三类删除，判断插入顺序为何会造成退化；
- 根据失衡形态选择 AVL 的 LL、RR、LR、RL 调整，并说明红黑树的工程取舍。
理论框架
| 层次 | 核心约束 | 典型结构 | 查找代价从哪里来 |
|---|---|---|---|
| 线性查找 | 可无序；顺序访问即可 | 顺序查找 | 已检查元素的数量 |
| 有序静态表 | 有序且支持随机访问 | 折半查找 | 判定树深度 |
| 分级索引 | 块间有序、块内可无序 | 分块查找 | 索引查找 + 块内查找 |
| 动态有序表 | 插删后仍保持次序 | BST、AVL、红黑树 | 树高 |
统一分析法
先写出结构成立的前提，再确定一次查找经过哪些位置，最后计算路径长度或比较次数。只背 O(log n)、O(1)，很容易漏掉退化条件和统计口径。
三篇文章如何分工
| 学习问题 | 对应文章 | 完成后的可检查能力 |
|---|---|---|
| 静态表中怎样查找并计算 ASL？ | 8.1 基础查找与折半查找 | 能画折半判定树并比较顺序、分块、折半查找 |
| 动态有序集合怎样增删查？ | 8.2 二叉排序树 | 能处理 BST 三类删除并分析退化 |
| 怎样把树高稳定在对数级？ | 8.3 平衡查找树 | 能判断 AVL 旋转并解释红黑树性质 |
推荐学习顺序
- 从基础查找与折半查找建立 ASL、判定树和比较次数的统一语言。
- 学习二叉排序树，观察静态的折半思想如何变成动态树结构。
- 继续学习平衡查找树，理解“修复局部结构”如何换来最坏情况保证。
- 完成操作 Lab 后，用历年理论题做一次自测，再进入第 9 章的B 树与散列表。
配套理论题
本章理论练习按知识主题拆成三组，覆盖基础查找与树形查找。选择题可在网页中即时提交和重做； 题源为历年 408 统考真题与王道《2026 年数据结构考研复习指导》第 7 章习题，每题均标注出处。
| 顺序 | 主题与入口 | 题数 |
|---|---|---|
| 01 | 查找理论选择题精练（顺序 / 分块 / 折半） | 15 |
| 02 | 二叉排序树理论题精练 | 12 |
| 03 | 平衡查找树理论题精练（AVL 与红黑树） | 14 |
配套 Labs
- Lab 08-T-01：查找理论选择题精练
- Lab 08-T-02：二叉排序树理论题精练
- Lab 08-T-03：平衡查找树理论题精练
- Lab 08-E-01：BST 增删查与边界测试
- Lab 08-E-02：折半查找首次出现位置
- Lab 08-E-03：折半查找首末位置
- Lab 08-E-04：数对计数 A−B=C
- Lab 08-E-05：有序数组转平衡 BST
- Lab 08-E-06：验证二叉搜索树
- Lab 08-E-07：二叉搜索树的最近公共祖先
- Lab 08-E-08：平衡二叉树判断
- Lab 08-E-09：【模板】普通平衡树
- Lab 08-P-01：自平衡查找树——AVL 旋转维护与退化对比
散列与索引相关的 Lab 见第 9 章各页的配套 Lab。
选型时先问什么
| 问题 | 更合适的起点 |
|---|---|
| 数据量小，或只查一次 | 顺序查找 |
| 数据基本不变、已有序且能随机访问 | 折半查找 |
| 只需要粗粒度索引，块内更新方便 | 分块查找 |
| 需要动态插删、范围查询和有序遍历 | 平衡搜索树 |
交互式演示
本章的部分页面嵌入了可交互演示，用来把抽象结构变成能一步步观察的过程：
- 折半查找 · 判定树（8.1）：手动走查找，看
low/mid/high如何每次砍掉一半，并同步生成判定树。 - 二叉排序树 · 退化与删除（8.2）：用不同插入顺序对比树形与 ASL，点结点看三类删除。
- AVL 树 · 旋转实验室（8.3）：观察平衡因子，逐键插入触发 LL/RR/LR/RL 旋转。
准备好后，从8.1 基础查找与折半查找开始。你想先动手，翻到对应页面点开演示即可。