这一部分为什么存在？
在完整笔记中阅读本节概念 要点 易考点 折半判定树 折半查找的比较过程构成一棵 BST；n 个结点时查找成功/失败的最多比较次数 = 树高 \lceil \log2(n+1) \rceil 2010-9（n=16，失败最多 5 次）；2023-8（600 元素最多 10 次）；判定树形状（2017-8）；比较序列合法性（2015-7：相邻比较值必须一半方向单调） BST 左 < 根 < 右（各子树递归成立）；中序遍历得升序 查找路径序列合法性（2011-7…
在完整笔记中阅读本节折半查找（必须能手写）
在完整笔记中阅读本节结构 查找 插入/删除 有序遍历 适用 有序数组（折半） O(\log n) O(n) 天然 静态、内存、随机访问 BST O(h)，最坏 O(n) O(h) 中序 动态、内存 AVL / 红黑树 O(\log n) 保证 O(\log n)，有旋转代价 中序 动态、内存、要求稳定性能 B / B+ 树 O(\logm n) 次 I/O 同阶 I/O B+ 树叶链最优 外存、数据库/文件索引 散列 平均 O(1) 平均 O(1) 不支持…
在完整笔记中阅读本节形态一：折半与判定树：2010-9、2015-7、2017-8、2023-8、2024-5（链表不能折半）、2013-42（概率加权大题）。
在完整笔记中阅读本节向前依赖：DS-1（顺序存储 vs 链式决定折半可行性）、DS-3（BST/AVL/B 树都是“树 + 约束”；判定树概念）。 向后引出： 排序是折半与 BST 的前提 → DS-6（“为什么排序有用”在本章找到答案）； 散列思想 → Cache 组相联的地址映射、TLB（CO-3/X-1，同构的“算 + 查”）；B+ 树 → OS 文件索引（OS-7）、数据库索引（X-8）； 代码题衔接：折半查找必须能手写；BST 判定（2022-4…
在完整笔记中阅读本节查找快慢用什么度量？（ASL，比较次数的概率加权） 折半查找的两个前提是什么？为什么有序链表也不行？ 折半的比较次数为什么可以用判定树高度回答？ 有序数组插删贵，怎么救？（BST：链接 + 中序有序） BST 最坏会变成什么？怎么强制平衡？（链；AVL 旋转四种） AVL 高 h 的最少结点数怎么递推？为什么这样构造最省？ 磁盘查找的瓶颈是比较次数吗？B 树为什么又矮又胖？（I/O；结点=页） B 树的阶、高度、关键字数上下界怎么算？插…
在完整笔记中阅读本节