随机化二叉搜索树的期望高度分析
随机化二叉搜索树是一种通过随机化操作来保证树高期望值为 \(O(\log n)\) 的数据结构。与确定性平衡树（如AVL、红黑树）不同，它无需显式维护平衡条件，而是通过随机性获得良好的期望性能。今天我们重点分析它的期望高度。
1. 核心思想：随机插入顺序
随机化二叉搜索树的常见构建方式是：假设所有元素互异，然后以一个随机的顺序将它们依次插入一棵初始为空的二叉搜索树中。由于插入顺序是随机的，最终生成的树结构也是随机的。我们的目标是分析这棵随机树的高度期望值。
2. 定义与设定
- 设有 \(n\) 个互异的关键字：\(x_1, x_2, \dots, x_n\)。
- 插入顺序是这 \(n\) 个关键字的一个均匀随机排列（共 \(n!\) 种，等可能）。
- 从空树开始，按照这个随机排列的顺序依次插入，得到一棵二叉搜索树 \(T\)。
- 树高 \(H(T)\) 定义为从根到最远叶子的路径边数。
目标：证明 \(E[H(T)] = O(\log n)\)，其中 \(E[\cdot]\) 表示期望。
3. 证明思路
我们将证明一个更强的结论：随机化二叉搜索树的高度以高概率为 \(O(\log n)\)，这自然隐含了期望高度为 \(O(\log n)\)。常用方法是借助二叉搜索树与快速排序的等价性，并利用已知的快速排序分析结论。
步骤1：等价性观察
- 在快速排序中，若始终选择当前子数组的第一个元素作为基准（pivot），则递归调用树恰好对应于按输入顺序插入形成的二叉搜索树。
- 具体来说：将随机排列的 \(n\) 个元素依次插入BST，根节点是第一个插入的元素（即排列的第一个元素）。在快速排序中，若输入是同一随机排列，且总选第一个元素为基准，则递归树中，根是第一个基准，左子树对应小于基准的元素，右子树对应大于基准的元素。这与BST的插入过程完全一致。
- 因此，随机化BST的高度等于以第一个元素为基准的快速排序递归树的深度。
步骤2：递归关系
设 \(H_n\) 为随机化BST的高度（随机变量）。由等价性，有递归关系：
\[H_n = 1 + \max(H_{L}, H_{R}) \]
其中 \(L\) 和 \(R\) 分别是左子树和右子树的大小。由于第一个插入的元素（根）是随机排列中的第一个元素，它在 \(n\) 个元素中均匀随机，故 \(L\) 服从参数为 \(n\) 的均匀分布：\(P(L = k) = \frac{1}{n}\)，\(k = 0,1,\dots,n-1\)，且 \(R = n-1-L\)。
步骤3：期望分析（思路）
直接对期望做递推较复杂，我们转而分析高度超过某个阈值的概率。常用技巧是：定义随机变量 \(X\) 为从根到某个固定叶子（如按顺序的最小元素）的路径长度。可以证明 \(E[X] = O(\log n)\)。但这只考虑了单一路径，不足以得到树高。
更好的方法是考虑树中任意节点到根的路径长度（即节点深度）。可以证明，随机化BST中任意节点的期望深度为 \(O(\log n)\)。这由以下递推得出：
设 \(D_n\) 为随机节点在随机树中的深度期望。对于随机排列，根是均匀随机的，故一个给定节点在左子树或右子树中的概率与其大小成正比。经推导可得：
\[D_n = 1 + \frac{1}{n} \sum_{k=0}^{n-1} \frac{k D_k + (n-1-k) D_{n-1-k}}{n-1} \]
化简后可得 \(D_n = H_{n} - 1\)，其中 \(H_n\) 是调和数 \(H_n = \sum_{i=1}^n 1/i\)，故 \(D_n = O(\log n)\)。
但节点深度期望是 \(O(\log n)\) 并不能直接推出树高期望是 \(O(\log n)\)，因为树高是最大深度。我们需要高概率界。
步骤4：高概率界证明
标准方法：证明存在常数 \(c > 0\)，使得树高超过 \(c \log n\) 的概率很小。一种经典证明如下：
- 考虑树中任意一个特定节点序列（一条从根到叶的可能路径）。由于每个节点的左右子树大小由随机划分决定，这条路径的长度可以视为一系列随机选择的“划分比例”的结果。
- 另一种方式：注意到快速排序的递归树深度已知为 \(O(\log n)\) 的高概率。因为快速排序的比较次数期望为 \(O(n \log n)\)，且深度超过 \(c \log n\) 的概率不超过 \(n^{-\alpha}\) 对于某个 \(\alpha > 0\)。这可以通过计算概率或使用鞅不等式得到。
一个常见结论：存在常数 \(c\)，使得
\[P(H_n > c \log n) \leq \frac{1}{n} \]
这可以通过观察：每次递归划分，子树大小至少以常数因子缩小的概率很高，重复 \(c \log n\) 次后子树大小应缩至1。
步骤5：期望高度的推导
有了高概率界，我们可以计算期望高度：
\[E[H_n] = \sum_{h=1}^{n} h \cdot P(H_n = h) \leq \sum_{h=1}^{c \log n} h \cdot 1 + \sum_{h=c \log n+1}^{n} h \cdot P(H_n = h) \]
第一个和式上界为 \(c \log n\)。对于第二个和式，利用尾概率界 \(P(H_n > h) \leq n \cdot (3/4)^h\)（这是一个已知结论，来源于：每次划分，子树大小不超过 \(3/4\) 原大小的概率至少 \(1/2\)，故路径长度超过 \(h\) 的概率被限定）。则：
\[\sum_{h=c \log n+1}^{n} h \cdot P(H_n = h) \leq \sum_{h=c \log n+1}^{\infty} h \cdot n (3/4)^h \]
这是一个收敛的几何级数，当 \(c\) 足够大时，这个和是 \(o(1)\)。因此，\(E[H_n] \leq c \log n + o(1) = O(\log n)\)。
4. 结论
随机化二叉搜索树（通过随机插入顺序构建）的期望高度为 \(O(\log n)\)。这意味着无需显式平衡操作，仅凭随机性就能以高概率获得平衡的树结构。这一结论是随机化算法在数据结构中成功应用的经典范例，也揭示了二叉搜索树、快速排序和随机划分之间的深刻联系。