Treap 与随机优先级搜索树

双重不变量 ​

每个不同键 $x$ 取得独立连续随机优先级 $p(x)$。中序遍历按键递增，父节点优先级小于孩子；在优先级互异时，这两条性质唯一确定树形，等价于按优先级次序把键插入普通 BST。

split$(T,x)$ 按键把树分成 $\le x$ 与 $>x$ 两棵；merge$(L,R)$ 假设 $L$ 的键全小于 $R$，比较根优先级并递归接入。插入是 split 后两次 merge，删除是把目标左右子树 merge。

期望深度证明 ​

在排好序的键 $x_1,\dots ,x_n$ 中，$x_i$ 是 $x_j$ 的祖先，当且仅当它在闭区间 $[i,j]$ 的优先级最小。该事件概率为 $1/(|i-j|+1)$。对固定 $x_j$ 求和，期望祖先数为两个调和和，故期望深度 $O(\log n)$，更新和查询也对随机优先级取期望为 $O(\log n)$。

三键例子 ​

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

随机性边界 ​

期望不等于每次高度都对数；小概率仍可形成链。若对手能预知或挑选优先级，独立排列论证失效。用键哈希生成确定性优先级时，要说明哈希种子是否隐藏及碰撞 tie-break；重复键可用 multiplicity 或 $(key,id)$，否则 BST 序不唯一。Treap 与跳表公理库跳表skip list用独立几何高度建立多层稀疏链表，以期望对数时间支持有序字典操作。都随机平衡，但前者的不变量是树上的键序加堆序。

Split/Merge 正确性 ​

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

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

插入的状态变化 ​

插入键 5、随机优先级 17 时，先按 BST 规则落到键序位置。若父键 7 的优先级为 23，旋转使 5 上升；若新父键 3 的优先级为 11，则停止。每次旋转同时保留中序键序和最小堆序，故不需要在两个不变量之间二选一。

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

1. split(T,5) 得到键小于 5 的 $L$ 与不小于 5 的 $R$；
2. 新建单节点 $x$，检查其优先级未与现存键冲突；
3. 先 merge(L,x)，再与 $R$ 合并；
4. 每次 merge 选择优先级较小的根，并递归处理唯一一侧。

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

参考资料

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