Treap 的意思就是 Tree + Heap，其中 Tree 指的 BST，二叉搜索树，而 Heap 指的是堆。
考虑一类维护元素偏序关系的数据结构，我们通过引入 Heap 来优化 BST 的插入/删除，对于 \(n\) 个元素 \(a_1, \ldots, a_n\)，假设已经按照升序排序。那么给每个 \(i\) 随机赋予权值 \(p_i\)，并根据 \(p\) 构建一个笛卡尔树，那么 Treap 就是这棵笛卡尔树。
考虑证明 Treap 的复杂度，容易发现几乎所有平衡树的操作都是 \(O(dep)\) 的，所以考虑证明 \(E(\max dep)\)，注意这里要和 \(\max E(dep)\) 区分开来，这俩不一定相等。像 OI-wiki 就是证的后者，是伪证，有人在评论给出了构造。
怎么求 \(E(\max dep)\) 呢？我们希望得出的结论是 \(E(\max dep) = O(\log n)\)，所以设 \(a_n = \sum_{i = 1}^n 2^{dep_i}\)。
有 \(a_n = 1 + \frac{4}{n}\sum_{i = 1}^{n - 1} a_i\)，设 \(b_n = \sum_{i = 1}^n a_i\)，对于 \(n \ge 2\)，有 \(b_n = \frac{n + 4}{n} b_{n - 1} + 1\)。
写出生成函数 \(B(x) = \sum_{n \ge 1} n b_n x^n\)，则
化简得 \((1 - x) B'(x) = 5B(x) + \frac{1}{(1 - x)^2}\)，解一阶线性微分方程解出 \(B(x) = \frac{1}{3} \left(\frac{1}{(1 - x)^5} - \frac{1}{(1 - x)^2}\right)\)，则 \(b_n = [x^n]B(x) = \frac{1}{3}\left(\binom{n + 4}{n} - \binom{n + 1}{n} \right) = (\frac{1}{72} + O(1)) n^4\)。
则 \(a_n = (\frac{1}{18} + O(1)) n^3\)，接下来设 \(H_n\) 为最大深度，有 \(P(H_n > (3 + \epsilon) \log_2 n) = P(2^{H_n} > n^{3 + \epsilon}) \le \frac{E(2^{H_n})}{n^{3 + \epsilon}}\)，而 \(E(2^{H_n}) \le a_n = (\frac{1}{18} + O(1)) n^3\)，于是 \(P(H_n > (3 + \epsilon) \log_2 n) \le \frac{1}{18} \cdot \frac{n^3}{n^{3 + \epsilon}}\)，故 \(H_n \le 3\log_2 n + \log_2 \log n\)。
更精确的界可以参照论文，它说明了高度大约是 \(\alpha \ln n\)，其中 \(\alpha\) 是方程 \(\alpha \ln (\alpha / 2) = 1\) 的较大实根，\(\alpha\) 大约为 \(4.31107\)，将底数换成 \(2\) 能够得到 \(\alpha \ln n \approx 2.988 \log_2 n\)。
所以 Treap 的深度大概有 3 倍的常数，这也是为什么跑不过写的比较好的 WBLT。