次优查找树 · 静态带权查找的工程折中
当一组关键字的查找概率不均时，「热门」关键字应当离根更近，以压低平均查找长度 (ASL)。在所有形状里 ASL 最小的那棵叫最优查找树 (optimal BST)，但求它需要 O(n³) 的动态规划。次优查找树 (nearly optimal / suboptimal BST) 换一个思路：不追求全局最优，而是在每个区间用一条局部贪心准则——选「左右子树权重最接近」的关键字作根——自顶向下一次把树搭好，代价仅 O(n log n)。本页先建立带权查找与 WPL 的度量，再单步演示次优构造的 ΔP 选根，然后用动态规划求出真正的最优树做对照，最后量化构造代价与查找质量的折中。每个 demo 都能改关键字与权重、单步播放、随时校验。
四步：为什么查找树的「形状」要看权重 → 次优查找树：选「左右最均衡」的点作根 → 最优查找树：O(n³) 动态规划的对照 → 次优到底「次」多少：代价与质量的折中。
1 · 为什么查找树的「形状」要看权重
一棵二叉查找树里，查找一个关键字的比较次数 = 它所在的层数 lᵢ（根为第 1 层）。若每个关键字被查的频率不同，衡量整棵树好坏的就不是树高，而是带权路径长度:
——权重 wᵢ 正比于关键字 i 的查找概率，lᵢ 是它在树中的层数。把高权重的关键字放在靠近根的位置（小 lᵢ），就能压低 WPL。等概率时各 wᵢ 相同，WPL 退化为「总层数」，平衡树最优；一旦权重悬殊，最优形状就会向高频项倾斜。
下面是一棵形状固定的平衡 BST。拖动每个关键字的权重滑块，观察 WPL 实时变化，以及每个节点对 WPL 的贡献 ——同样的权重加在深层节点，远比加在根上更「贵」。
形状固定时只能靠权重观察代价；真正的优化是反过来改形状。 本 demo 树形被锁死，你只能改权重看 WPL 怎么动。下一步要问的是：给定权重，什么形状的树 WPL 最小？——这正是次优查找树（贪心近似）与最优查找树（动态规划）要解决的问题。
2 · 次优查找树：选「左右最均衡」的点作根
本节假设已了解带权查找与 WPL 的度量。次优构造的核心是一条局部贪心准则：一棵查找树的代价主要由「高权重关键字离根多近」决定，而根把序列劈成左右两棵子树。若能让左右子树的累计权重尽量接近，两侧就都不会被压得过深，整棵树自然趋于「按权重平衡」。
ΔP 准则： 对区间 [low, high]，设前缀权重
。以第 i 个关键字作根时，右子树权重 =
、左子树权重 =
，定义
。选 ΔP 最小的 i 作根，再对左区间
与右区间 [i+1, high] 递归同一准则。每个区间只做一次扫描选根，总代价 O(n log n)。
输入升序关键字与各自权重（逗号分隔，一一对应），点「构造」，再用「下一步」逐个区间看选根决策：上方权重条标出当前区间与选中的根，右侧 ΔP 表列出该区间所有候选并高亮最小者，左侧的树自顶向下逐个落点。
为什么是「权重」而不是「个数」均衡？ 朴素平衡 BST 让左右节点数相等，但在带权查找下，决定代价的是权重。ΔP 准则正是用累计权重做天平——把高频项尽量托近根。这也解释了为什么次优树的形状可能不左右对称：它对齐的是查找概率，而非节点计数。
3 · 最优查找树：O(n³) 动态规划的对照
次优构造用一条贪心准则一次定根，不保证全局最优。真正的最优查找树由动态规划给出——它枚举区间内每一个关键字作根，递归取最小代价：
设
为区间总权，
为区间 [i,j] 构成子树的最小带权代价：。选 r 作根：左右子树各自的最优代价相加，再加
——因为把这两棵子树挂到 r 下，它们每个节点都下沉一层，整体代价正好增加一个区间总权。按区间长度 len 从小到大填表，
即最优 WPL。三重循环 (len × i × r) 故 O(n³)。
输入 keys 与 weights，点「构造」，「下一步」按 DP 顺序逐格填 C 表：当前格高亮，右侧列出该格每个候选根的代价并标出最小者（即写入该格的 root）。填满后由 root 表回溯出最优树，并与次优树的 WPL 并排对照。
4 · 次优到底「次」多少：代价与质量的折中
次优构造用 O(n log n) 一次定根，最优 DP 用 O(n³) 枚举全部根。省下的构造代价，代价是 WPL 可能略大。本节把两棵树并排，在两组数据间切换，量化这条折中线。
4.1 · 两种构造的对照
| 维度 | 次优查找树 | 最优查找树 |
|---|---|---|
| 构造思路 | 每区间一次贪心：选 ΔP 最小 （左右权重最均衡） 作根，递归 | 枚举区间内每个根，动态规划取全局最小代价 |
| 构造代价 | O(n log n) (类似快排，每层 O(n) 选根) | O(n³),Knuth 单调性优化后 O(n²) |
| 空间 | O(n) （前缀权重 + 递归栈） | O(n²) （C 表与 root 表） |
| 查找质量 | 近似最优，多数分布下等于或极接近最优 | WPL 全局最小，定义上的下界 |
| 适用 | n 大、需快速建表、可接受微小次优 | n 不大、构造一次长期复用、要求最优 |
为什么次优常常「碰巧」等于最优？ ΔP 准则让左右子树权重最接近，这与「最小化带权深度」的目标高度同向。当权重分布较平滑时，局部均衡累加起来就接近全局最优；只有当某些极端权重需要靠「牺牲局部均衡换全局收益」时，贪心才会偏离最优（切到「次优 > 最优」数据组即可看到这种偏离）。这与分支限界里「贪心解未必最优、但常是很好的上界」是同一类工程权衡。
本系列约定： 关键字按升序排列（静态查找表，构建后不增删），圆圈内是 key、下方小字是该 key 的权重 w（正比于查找概率）。根在第 1 层,WPL = Σ wᵢ·lᵢ。当前区间选中的根用深色高亮。本系列只计成功查找权重（不含失败结点），与考研常见的简化版本一致。