06 篇用每个节点的高度差约束整棵树。如果输入按升序到来，AVL 仍保证对数高度。另一种选择是让树形由算法生成的随机数决定：键负责搜索顺序，随机优先级负责哪个节点在上面。这能得到期望对数代价，但允许某次随机选择产生一条长链。二者的保证不能互换。

本篇实现 Treap 多重集，沿用上一章 add/discard/count/rank/select 的语义；再手算跳表搜索，比较随机化在树形和分层链表中的作用。令 n 为元素总数，d 为不同键数，键比较成本仍按常数计算。重复键增加计数，不重新抽取已有节点的优先级。

两种顺序怎样确定一棵树

Treap 同时满足二叉搜索树键序和优先级最小堆序。优先级互异时，最小优先级的键必须是根；比根小的键属于左子树，比根大的键属于右子树。对子树重复这个论证，整棵树被唯一确定。这也是 Cartesian tree 的一个构造视角。

插入先按键找到空位置，再在新节点优先级小于父节点时旋转上移。旋转不改变中序顺序；旋转后较小优先级节点上移，逐步消除新产生的堆序冲突。每步向根靠近，因此终止。子树 size 仍按06的公式从下向上重算，重复计数不参与优先级比较。

删除最后一个副本时，可以把左右 Treap 合并。左树所有键小于右树所有键，比较两根优先级：较小者成为合并结果根，递归合并它靠近另一树的孩子与另一棵树。归纳前提保持键域分离，根的选择保持堆序，每步消去一个待选根，因此得到同一个键集合对应的唯一 Treap。删除一个重复副本则只减计数。

rank 和 select 的正确性完全复用06的子树分区证明。它们不依赖“AVL”或“随机”，只依赖键序与正确的大小字段。改变平衡策略不应顺便改变查询语义。

对谁取期望

固定 d 个不同键，让它们的优先级相对次序服从均匀随机排列。由于最小优先级键均匀分布，根等价于随机选出的键；递归子区间具有相同性质。这与按均匀随机顺序插入普通 BST 得到的分布一致。输入键可以已经排序，随机性来自优先级而不是输入顺序。

把不同键按序编号为1到d。对第 i 个键，较小键 j 成为其祖先，当且仅当区间 j到i 内优先级最小者是 j，概率为1/(i−j+1)。较大键同理。因此期望深度为

E[Di]=∑j<i1i−j+1+∑j>i1j−i+1=Hi+Hd−i+1−2=O(log⁡(d+1)).\mathbb{E}[D_i] =\sum_{j<i}\frac{1}{i-j+1}+\sum_{j>i}\frac{1}{j-i+1} =H_i+H_{d-i+1}-2=O(\log(d+1)).

这里用线性期望相加，不要求祖先事件彼此独立。固定查询的成功搜索期望代价为对数，失败搜索可用相邻键间隙的搜索路径分析得到相同阶数。插入先经历一次搜索，再做沿路径的旋转；删除的合并路径也受随机搜索树分析控制，期望更新为 O(log(d+1))。

期望树高不能直接由“每个固定节点期望深度为对数”推出，因为最大值与期望不能任意交换。要得到期望高度上界，需要额外控制深度尾部。本篇的祖先求和只证明固定节点期望深度；有限种子的高度表只用于观察实现，不替代高度定理。

当优先级恰好随键递增，最小键成为根，其余键全部在右子树，最坏高度为 d。搜索最大键要访问 d 个节点。这个事件在理想随机排列中概率非零，所以单次最坏 O(d) 与期望 O(log(d+1)) 同时成立。本篇不把期望界改写为未给失败概率的“高概率保证”。

随机源也是前提

实验使用固定种子的伪随机生成器，便于复跑；数学模型使用均匀随机优先级次序。二者必须区分。有限位宽抽样可能碰撞，只用插入ID打破碰撞会改变优先级相对次序的分布。教学实现对当前已用优先级碰撞重采样，均匀候选模型下等价于无放回抽样，再以独立于随机数的固定操作序列分析。

这仍不授权对能够观察内部优先级并据此选择后续操作的自适应对手套用同一个证明。随机优先级不提供密码安全；若负载具有敌意，应单独定义可见信息、随机源与重建策略。PRNG种子实验只能说明这些具体序列发生了什么。

优先级空间若有 U 个候选值，当前使用 d 个，理想重采样接受概率为1−d/U；期望尝试次数为U/(U−d)，且没有有限的最坏尝试次数，接近耗尽时抽样开销不能忽略。本文采用128位优先级和远小于该空间的有限数据，不把抽样无限制地算作常数。实际 Python 递归还受解释器深度限制，构造长链不能用“期望平衡”消除栈溢出的可能。

跳表把随机性放到层数

跳表第0层包含全部不同键。每个节点从0层开始独立抛公平硬币，正面就再升一层，首次反面停止。节点出现在第 l 层的概率为2的负l次方。因此一个节点的期望层出现数为

∑l≥02−l=2.\sum_{l\ge0}2^{-l}=2.

d 个节点的期望存储为 O(d)，不是固定每个节点都恰有两条指针。搜索从最高层哨兵开始，只要下一节点的键小于目标就向右，否则向下一层；降到0层时，前驱与后继给出目标位置。每步不会越过目标，下降只是缩小步长，正确性不依赖随机分布。

例如固定层布局如下，搜索键6：

1
2
3
层2: -∞ -------- 4 -------- 8 ---- +∞
层1: -∞ --- 2 -- 4 --- 6 -- 8 ---- +∞
层0: -∞ -1-2-3-4-5-6-7-8 ------- +∞

在层2先到4，8过大，于是在4下降到层1，遇到6即可命中；若采用始终求严格前驱的实现，则在4继续下降到层0，经5检查后继6。两种返回规则都能正确，但访问计数必须对应选定版本。

期望搜索成本可反向分析：从底层目标附近回走，沿同层向左寻找上升节点，独立公平晋升使每层所需步数有常数期望；再结合期望最高层数为 O(log(d+1))，得到期望对数搜索。完整处理顶层边界的论证见 ODS 4.4。若所有节点都只在0层，搜索退化为线性扫描。把层数硬限制为固定常数，也不能对无限增长的 d 宣称相同的无条件对数界。

实验与选择边界

本篇只实现 Treap，跳表采用上述可检查手算，避免为比较名称再复制一套容器。从仓库根运行 python3 examples/advanced-algorithms/check_treap.py。本次结果保存在 examples/advanced-algorithms/results/treap.json，4679条序列、22857次操作与列表参照一致。按顺序插入0到255，种子0–7的高度分别为15、16、20、19、17、17、17、17；查询255的访问节点数分别为3、8、5、8、9、5、3、5。注入递增优先级时，128个键形成高度128的链，查询末端访问128个节点。完整数据和计数口径见实验检查卡。结构存储为 O(d) 节点，递归栈最坏 O(d)；有限多种子的高度和访问量应与理论保证分列。

AVL 给每次操作最坏对数界；Treap 在已声明随机模型下给期望对数界；跳表通过分层导航获得期望界。三者都需要准确的操作契约。不能仅凭一张高度表选择生产实现，更不能把随机种子调到更平衡后隐去调参过程。

练习

  1. 为键1、2、3分别指定优先级30、10、20，画唯一Treap，给出rank(3)和select(2)。把优先级改成10、20、30，说明哪些正确性不变量仍成立、哪个成本保证不能按最坏情况使用。
  2. 将同一固定操作序列在十个种子下复跑，报告每个种子的最大高度与查询访问量，不丢弃最差样本。随后注入递增优先级，检验链状反例；说明这个实验能反驳什么，不能证明什么。

参考资料