无旋 Treap(FHQ Treap)

无旋 Treap(FHQ Treap),又称范浩强 Treap 或 Merge-Split Treap,是一种平衡二叉搜索树的实现方式。它保留了 Treap 用随机优先级维持期望平衡的思想,但摒弃了传统的旋转操作,改用分裂(Split)和合并(Merge)两种基本操作来完成所有修改,因实现简洁且功能强大而广受欢迎。

概述

Treap 同时维护二叉搜索树的键值有序性和堆的随机优先级性质,后者保证树高在期望意义下为对数级。传统 Treap 通过旋转维护堆性质,而无旋 Treap 只依赖分裂与合并,任何插入、删除、查询区间等操作都可由这两者组合实现。该实现方式经中国选手范浩强推广,在竞赛圈中被广泛使用。

核心原理

• 分裂:按键值或按子树大小,把一棵 Treap 拆成两棵,使得左树所有元素小于等于分界、右树大于分界,递归下行完成,复杂度为对数级。
• 合并:把两棵满足前者全部小于后者的 Treap 合并为一棵,合并时依据随机优先级决定谁作为根,保证堆性质。
• 插入删除:插入时把树分裂成两部分再依次合并新节点;删除时分裂出目标区间再直接合并旁边两块。
• 区间操作:按子树大小分裂可精确取出任意下标区间,配合懒标记支持区间翻转、区间加等操作。

应用场景

无旋 Treap 可作为有序集合、名次树使用,支持第 k 大、排名查询等;也常被当作维护序列的平衡树,支持区间翻转、区间修改与查询;还能方便地扩展为可持久化版本,保存历史版本。

常见问题

问:无旋 Treap 与红黑树、AVL 树相比如何?答:红黑树、AVL 树是严格平衡的,常用于工程库;无旋 Treap 依赖随机保证期望平衡,代码更短、更容易支持区间与可持久化操作,更受竞赛青睐。

问:随机优先级的作用是什么?答:随机优先级让树的形态近似随机,期望树高为对数级,从而保证分裂与合并等操作的期望复杂度为对数级,避免退化为链。