Treap(树堆)

定义

Treap 是 Tree 与 Heap 的合成词,由 Seidel 和 Aragon 于 1989 年提出:每个节点除键值外附带一个随机优先级,键值满足二叉搜索树性质,优先级满足堆性质。这等价于按随机顺序插入的 BST,因此树高期望为 O(log n)。

原理

旋转版 Treap 通过左旋右旋维持堆性质;更流行的无旋 Treap(FHQ Treap)只用 split(按键或按排名分裂)和 merge(按优先级合并)两个操作完成插入、删除、区间操作,代码简洁且天然支持可持久化。

应用

Treap 常用于实现有序集合、名次树(第 k 小、排名查询)、区间翻转等序列维护问题,是算法竞赛中最常写的平衡树之一;随机化思想也使它成为教学中讲解概率分析的典型例子。

优缺点

优点是实现远比红黑树简单、期望性能稳定、易扩展区间信息与持久化;缺点是复杂度只有期望保证而非最坏保证,依赖随机数质量。