flowchart TD
A["查找：ASL 度量"] --> B["无序 → 顺序 O(n)"]
B --> C["有序 + 顺序存储 → 折半 O(log n)<br/>判定树"]
C --> D["插删贵 → BST<br/>中序有序，高 = O(log n)~O(n)"]
D --> E["退化 → 平衡化<br/>AVL（|BF|≤1）/ 红黑树"]
D --> F["磁盘 I/O 瓶颈 → B 树<br/>多路矮胖，结点 = 页"]
F --> G["范围查询 → B+ 树<br/>数据在叶，叶成链"]
A --> H["算地址 → 散列<br/>冲突：拉链 / 开放定址<br/>装填因子 α"]
核心概念：
| 概念 | 要点 | 易考点 |
|---|---|---|
| 折半判定树 | 折半查找的比较过程构成一棵 BST； 个结点时查找成功/失败的最多比较次数 = 树高 | 2010-9（n=16，失败最多 5 次）；2023-8（600 元素最多 10 次）；判定树形状（2017-8）；比较序列合法性（2015-7：相邻比较值必须一半方向单调） |
| BST | 左 < 根 < 右（各子树递归成立）；中序遍历得升序 | 查找路径序列合法性（2011-7：路径上大小摆动要受已确定上下界约束）；生成序列（2020-5）；子树关键字范围（2024-7） |
| AVL | 任意结点左右子树高差 ≤1；插入失衡后四种旋转：LL、RR、LR、RL | 高 的最少结点数 （类斐波那契，2012-4：高 6 全 BF=1 → 33）；插入后形态（2010-4、2021-6、2013-3） |
| B 树（ 阶） | 多路平衡查找树：根至少 2 子、非根至少 子；结点关键字 = 孩子数 −1；所有叶在同一层 | 最少/最多关键字计算（2013-10：5 阶高 2 最少 8；2018-8：3 阶高 5 至少 242）；插入分裂（2020-10）、删除合并（2022-8） |
| B+ 树 | 与 B 树的三点不同：非叶只作索引（不存数据）、数据全在叶、叶结点按序链接 | 2016-10（特点识别）；2017-9（应用：数据库/文件系统索引）；2023-7（B 树查找不一定查到叶——非叶也存数据，B+ 树才一定到叶） |
| 散列 | 直接算地址；冲突解决方法：拉链法、开放定址（线性探测/平方探测） | ASL 影响因素 = 装填因子 + 散列函数 + 冲突策略，三者全部（2022-9）；线性探测有堆积（2014-8：直接影响 ASL） |