搜索树是二分查找这一分治过程的“物化”：查找的代价等于树高。平衡保证树高为 $O(\log n)$，而分叉数 $k$ 的取舍取决于代价模型。
1. 问题与下界
给定 $n$ 个有序的键 $a_1 < a_2 < \dots < a_n$，对查询 $x$ 求其排名，即满足 $a_i\le x$ 的最大 $i$（不存在时为 $0$）。只允许比较。
顺序扫描需要 $O(n)$ 次比较；二分查找每次比较中间的键并丢弃一半，$T(n)=T(n/2)+1$，需要 $O(\log n)$ 次。它已经不能再快了：
任何基于比较的算法，在最坏情况下至少需要 $\lceil\log_2(n+1)\rceil$ 次比较。
将算法看成一棵决策树：每个内部节点是一次比较，两个分支对应两种结果，每个叶子对应一个输出。排名有 $0,1,\dots,n$ 共 $n+1$ 种可能，每一种都必须出现在某个叶子上，故叶子数至少为 $n+1$。高为 $h$ 的二叉树至多有 $2^h$ 个叶子，于是 $2^h\ge n+1$。$\square$
二分查找恰好达到这一下界。
2. 搜索树：把二分查找存下来
二分查找所走过的“比较中间元素”的结构，正是一棵以中位数为根的平衡二叉搜索树；把这棵树显式存下来，就得到了搜索树。数组上的二分查找已经是最优的，但插入或删除一个键需要移动 $O(n)$ 个元素；搜索树则可以在 $O(\text{树高})$ 内完成插入与删除。
推广到 $k$ 叉：每个节点存至多 $k-1$ 个有序的键和至多 $k$ 棵子树，第 $i$ 棵子树中的键位于第 $i-1$ 与第 $i$ 个键之间。查找时在节点内定位 $x$ 所在的区间，再进入对应的子树。于是
$$ \text{查找代价} = \text{树高}\times\text{每个节点的代价}. $$含 $n$ 个键的 $k$ 叉搜索树，高度（根到叶的层数）至少为 $\lceil\log_k(n+1)\rceil$。
第 $i$ 层至多有 $k^{i-1}$ 个节点，每个节点至多 $k-1$ 个键，故高为 $h$ 的树至多有 $(k-1)(1+k+\dots+k^{h-1})=k^h-1$ 个键，即 $k^h\ge n+1$。$\square$
达到这一量级（$\Theta(\log_k n)$）的树称为平衡的。反之，把有序的键依次插入一棵朴素的二叉搜索树，得到的是一条链，树高为 $n$，查找退化为 $O(n)$，正对应分治中 $n-1$ 与 $1$ 的退化划分。
3. 比较模型：分叉数无关紧要
若代价只计比较次数，在 $k-1$ 个有序键中定位 $x$，用二分查找需要 $\lceil\log_2 k\rceil$ 次比较，于是总比较次数约为
$$ \log_k n\cdot\lceil\log_2 k\rceil\ \ge\ \log_k n\cdot\log_2 k=\log_2 n, $$$k$ 为 2 的幂时取等。增大 $k$ 使树变矮，但每层的比较变多，两者恰好抵消，这与比较下界一致：任何 $k$ 都不可能少于 $\log_2 n$ 次比较。若节点内用顺序扫描，代价为 $(k-1)\log_k n$，$k$ 越大越差：
| $k$ | 节点内二分查找 | 节点内顺序扫描 |
|---|---|---|
| 2 | $1.00\log_2 n$ | $1.00\log_2 n$ |
| 3 | $1.26\log_2 n$ | $1.26\log_2 n$ |
| 4 | $1.00\log_2 n$ | $1.50\log_2 n$ |
| 8 | $1.00\log_2 n$ | $2.33\log_2 n$ |
| 16 | $1.00\log_2 n$ | $3.75\log_2 n$ |
同理，数组上的“三分查找”每层用 $2$ 次比较把区间缩为 $1/3$，共 $2\log_3 n\approx 1.26\log_2 n$ 次，反而比二分查找慢。
4. I/O 模型：分叉数越大越好
当数据存放在磁盘上（或从缓存层次结构的角度看内存），代价的主体不再是比较，而是读取一个节点所在的块：一次磁盘读取约为毫秒量级，一次内存访问未命中约为百纳秒量级，而块内的比较几乎没有代价。此时
$$ \text{查找代价} \approx \text{访问的节点数} = \text{树高}\approx\log_k n, $$$k$ 越大越好，应使一个节点恰好占满一个块。例如 $n=10^9$ 时，二叉搜索树需要约 $30$ 次块读取，而每个节点容纳约 $1000$ 个键的 B 树只需约 $3$ 到 $4$ 次（根节点常驻内存时更少）。
B 树以最小度数 $t\ge2$ 刻画：除根之外，每个节点有 $t-1$ 到 $2t-1$ 个键（即 $t$ 到 $2t$ 棵子树），根至少有 $1$ 个键，且所有叶子位于同一深度。
含 $n\ge1$ 个键、最小度数为 $t$ 的 B 树，高度（根的深度为 $0$）满足 $h\le\log_t\dfrac{n+1}{2}$。
根至少有 $1$ 个键、$2$ 棵子树；深度 $i\ge1$ 的层至少有 $2t^{i-1}$ 个节点，每个至少 $t-1$ 个键。于是
$$ n\ \ge\ 1+(t-1)\sum_{i=1}^{h}2t^{i-1}=2t^h-1.\qquad\square $$
“所有叶子位于同一深度”是最严格的平衡；插入时节点满则分裂、删除时节点不足半满则与兄弟合并或借键，都只沿一条根到叶的路径进行，代价为 $O(h)$ 次节点操作。
5. 维持平衡
静态情形下，平衡是容易得到的：对有序数组分治，以中位数为根、两半递归建树，$T(n)=2T(n/2)+O(1)=O(n)$，得到完全平衡的树。困难在于动态的插入与删除会破坏平衡，各种平衡树的区别，就在于用什么不变量约束形状、用什么局部操作恢复它：
| 结构 | 平衡条件 | 树高上界 | 恢复操作 |
|---|---|---|---|
| AVL 树 | 每个节点左右子树高度差不超过 $1$ | $\approx 1.44\log_2 n$ | 旋转 |
| 红黑树 | 根到叶的黑节点数相同，红节点不相邻 | $2\log_2(n+1)$ | 旋转与变色 |
| B 树 | 叶子同深度，非根节点至少半满 | $\log_t\frac{n+1}{2}$ | 分裂与合并 |
三者的平衡条件都比“完全平衡”宽松，正是这点余量使得每次插入删除只需 $O(\log n)$ 次局部调整。
含 $n$ 个节点的 AVL 树，高度（以节点数计）$h\le\log_\varphi(n+1)\approx1.44\log_2(n+1)$，其中 $\varphi=\frac{1+\sqrt5}{2}$。
记 $N(h)$ 为高为 $h$ 的 AVL 树的最少节点数。最少时两棵子树的高分别为 $h-1$ 与 $h-2$，故 $N(h)=N(h-1)+N(h-2)+1$，$N(1)=1$，$N(2)=2$。于是 $N(h)+1$ 满足 Fibonacci 递推，且 $N(1)+1=F_3$，$N(2)+1=F_4$，得 $N(h)+1=F_{h+2}\ge\varphi^{h}$。由 $n\ge N(h)$ 得 $n+1\ge\varphi^h$。$\square$
6. 小结：与分治的对照
| 分治 | 搜索树 |
|---|---|
| 递归树 | 搜索树 |
| 子问题的规模 | 子树中键的个数 |
| 平衡划分：树高 $O(\log n)$ | 平衡树：树高 $O(\log n)$ |
| 退化划分：$T(n)=T(n-1)+cn=\Theta(n^2)$ | 退化为链：查找 $O(n)$ |
| 总代价 $\approx$ 每层代价 $\times$ 树高 | 查找代价 $=$ 每个节点的代价 $\times$ 树高 |
| 子问题个数 $a$ 决定叶子数 $n^{\log_b a}$ | 分叉数 $k$：比较模型下无关，I/O 模型下越大越好 |
两者说的是同一件事：代价沿树的深度累积，平衡使深度为 $O(\log n)$；而树的“宽度”（分治的子问题个数、搜索树的分叉数）是否有利，则取决于每一层的代价如何计量。分治中的平衡问题见算法设计：分治的补充一节。