Treap 树高的一种证明

_xm_ · 2025-07-23 20:59:43 · 算法·理论

我们考虑笛卡尔树的建树过程：将 n 个节点按键值从小到大排序，此时选出优先级最小的节点 i 作为根节点，剩下 [1,i-1], [i+1,n] 的节点递归建树。

优先级最小的节点等概率的出现在 [1,n] 中，令 f(n) 为 Treap 的期望树高，我们可以列出：

显然 f(0)=0，f(1)=1。

Proof

我们考虑数学归纳法，假设存在常数 c,d>0，使得对所有 k \in [1,n)，有 f(k)\le c \ln k + d，目标是证 f(n)\le c \ln n + d。

注：需要注意的是，\ln 0 是未定义的，我们可以在表达式中省略 f(0) 来规避这个问题。

由于 f(n) 单调递增，\max 取较大的那个即可只考虑一半：

当 n 为奇数时中位数 i = \lfloor \frac{n}{2} \rfloor+1 对应的项 \frac{1}{n} f(\lfloor \frac{n}{2} \rfloor) 会被计算两次。

由于 \ln x 单调递增，所以 \sum_{i=m}^n \ln i < \int_{m}^{n+1} \ln x \, dx，用积分近似求和：

计算积分：

从而：

为使不等式 f(n) < c\ln 2n - c + d + 1 \le c \ln n + d 成立，解不等式：

当 n=1 时，f(1)=1。只要取 d \ge 1 就有 f(1)\le c \ln 1 + d。

综上，我们得到了比较紧的上界 f(n)\le \frac{1}{1-\ln 2} \ln n + 1，因此 Treap 树高的期望为 O(\log n)。

附一张数值表：