Treap 与随机优先级搜索树

形式陈述

双重不变量

Treap 是一种随机化搜索树：每个不同键 $x$ 独立地从同一个连续概率分布抽取优先级 $p(x)$ ，并在该节点存在期间保持不变。连续同分布使有限键集的优先级以概率一互异，且其相对次序是均匀随机排列。其二叉搜索树不变量要求中序遍历按键递增，父节点优先级小于孩子；在优先级互异时，这两条性质唯一确定树形，等价于按优先级次序把键插入普通 BST。

本页统一采用 split $(T,x)$ 把树分成键 $<x$ 与 $\ge x$ 两棵的约定；merge $(L,R)$ 假设 $L$ 的键全小于 $R$ ，比较根优先级并递归接入。插入是 split 后两次 merge，删除是把目标左右子树 merge。

期望深度证明

固定排好序的互异键 $x_1,\ldots,x_n$ 。对 $i\ne j$ ， $x_i$ 是 $x_j$ 的祖先，当且仅当它在索引区间 $[\min(i,j),\max(i,j)]$ 的优先级最小。该事件概率为 $1/(|i-j|+1)$ 。对 $i\ne j$ 求和，期望祖先数为 $H_j+H_{n-j+1}-2$ ，故期望深度为 $O(\log(n+1))$ 。查询与更新的界对内部优先级取期望，采用随机化算法中“固定输入、平均随机选择”的量词；键比较与局部指针操作按常数成本计算。

直觉

键序决定中序排列，独立随机优先级决定谁先成为区间根；两者共同唯一确定一棵 Cartesian-tree 形状。固定键集合下，任意区间的最小优先级均匀落在各键，祖先概率形成调和和，因此无需显式平衡字段也有期望对数深度。

例子与边界

三键例子

键 $2,5,9$ 的优先级若依次为 $0.7,0.1,0.4$ ，键 5 必为根；2 在左，9 在右。这不是任意旋转结果，而是键序与堆序共同强制的 Cartesian-tree 形状。重新抽优先级会改变形状，却不改变存储的键集合。

随机性边界

期望不等于每次高度都对数；小概率仍可形成链。若对手能预知或挑选优先级，独立排列论证失效。实际有限位优先级可能碰撞，应给出稳定的平局规则，并把碰撞概率或由此产生的分布偏差计入分析；全表检查一次碰撞并非常数成本。用键哈希生成优先级时，还要说明种子与对手模型；重复键可用 multiplicity 或 $(key,id)$ ，否则 BST 序不唯一。Treap 与跳表都随机平衡，但前者的不变量是树上的键序加堆序。

推论与应用

Split/Merge 正确性

Split 在根键小于阈值时递归切右子树，并把返回的左部分接回根右侧；反之对称切左子树。归纳假设保证两棵返回树内部仍满足键序和优先级堆序，根与未改子树关系也未变。Merge 选择优先级较小的根，并只递归合并它朝另一树的一侧；前提“左树所有键小于右树”不可省略。

随机优先级应在键第一次插入时固定。每次访问或旋转重抽优先级会改变分布并破坏持久身份；删除后重新插入是否沿用旧优先级也需按应用的随机模型约定。

插入的状态变化

插入键 5、随机优先级 17 时，先按 BST 规则落到键序位置。若父键 7 的优先级为 23，旋转使 5 上升；若新父键 3 的优先级为 11，则停止。每次旋转保持全局中序键序，并修复新节点与当前父节点之间的优先级逆序；新节点与更高祖先之间仍可能有下一处逆序，须继续上浮。只有上浮结束后，整棵树才重新满足堆序。

等价地，可执行以下分裂—合并过程：

先查找键 5；若已经存在，按字典约定更新值并保留原节点优先级，不再插入重复节点
对不存在的键，split(T,5) 得到键小于 5 的 $L$ 与大于 5 的 $R$ ，新建单节点 $x$ 并抽取优先级
先 merge(L,x)，再与 $R$ 合并；
每次 merge 选择优先级较小的根，并递归处理唯一一侧。

期望高度来自随机优先级诱导的随机排列，对固定输入键集合取期望。对手若能看到优先级后再选择键或优先级碰撞采用有偏规则，随机 BST 的分析前提就已改变；需要隐藏随机种子或使用足够宽的独立优先级。

参考资料

Cecilia Aragon, Raimund Seidel, Randomized Search Trees, FOCS, 1989.
Raimund Seidel, Cecilia Aragon, Randomized Search Trees, Algorithmica, 1996.

形式陈述 ​

双重不变量 ​

期望深度证明 ​

三键例子 ​

随机性边界 ​

Split/Merge 正确性 ​

插入的状态变化 ​