无旋Treap详解：基于split与merge的平衡树核心操作

无旋 Treap也叫无旋平衡树这个名字这几年在算法圈子里已经快变成默认平衡树的代名词了。它本质上还是一棵 Treap——键值满足二叉搜索树BST性质、优先级满足堆性质的二叉树但特殊之处在于完全不需要旋转操作所有增删查改都能用 split分裂和 merge合并两个基础原语组合出来。这篇是 Treap 系列的第二篇目标是把无旋 Treap 的基本操作讲透从节点定义到插入、删除、排名、第 k 小、前驱后继再到踩坑排查覆盖新手从入门到能独立实现的全过程。适合已经了解二叉搜索树基本概念、想换一款好用平衡树的读者。如果你已经会旋转版 Treap那看起来会更快——无旋版本的分裂合并思路会让很多原本麻烦的区间操作变得异常直觉。1. 整体设计为什么是无旋 Treap1.1 Treap 的本质BST 的平衡靠运气Treap 就是 Tree Heap 的组合词。每个节点同时满足两组约束键值 val 满足 BST 性质左子树所有 val 小于当前节点右子树所有 val 大于当前节点。优先级 prio 满足堆性质父节点的 prio 小于或大于取决于实现约定两个子节点的 prio。BST 性质保证我们可以像在有序数组里一样二分查找堆性质则保证树高是受控的。这里有一个很多人没想透的关键点如果每个节点的 prio 是独立均匀随机生成的那么整棵树的形态等价于按 prio 从小到大依次插入键值的随机二叉搜索树期望高度是 O(log n)。换句话说平衡不是靠旋转规则硬调出来的而是靠概率包出来的。你只需要保证 prio 的随机性足够好树的形态就大概率是均匀的。这也就是为什么 Treap 不需要 AVL 那样的严格平衡条件也不会像裸 BST 那样插入有序序列就退化成一条链。随机化让人安心也让代码简单。1.2 无旋 到底解决了什么问题旋转版 Treap 在插入、删除时靠左旋、右旋来恢复堆性质。无旋版本把调整彻底换成分裂合并我实际用了很久体会到三个核心优势。第一思维负担小。所有操作都是同一个套路split 切两刀得到若干棵树再按需 merge 回去。你不需要记四种旋转组合不需要处理祖父节点、父节点、当前节点之间的复杂关系递归的每一层只关心当前节点该归哪边。第二可组合性强。split 和 merge 是通用原语可以随意组合出删除一段区间翻转区间在任意位置插入这类高级操作。这是后续做区间操作最重要的跳板也是无旋 Treap 相比旋转版最大的扩展空间。第三可持久化友好。split 和 merge 每次只修改递归路径上的一串节点只要把原地修改改成复制节点再修改就能直接做成可持久化平衡树。旋转版要持久化难度直接上一个档次。1.3 先问自己你需要平衡树干什么学习任何数据结构之前最好先想清楚使用场景。如果只是维护一个有序集合做插入、删除、查前驱后继那么 C 的 std::set 完全够用没必要自己造轮子。但如果你需要查询第 k 小元素某个值的排名这类按序统计或者以后要写区间翻转、区间最值、可持久化这些操作std::set 就无能为力了无旋 Treap 几乎是性价比最高的选择。这也是为什么很多搞竞赛和做算法底层工作的同学最后都把无旋 Treap 当作默认平衡树——它是一棵可以被组装的平衡树核心代码短扩展空间大值得花时间彻底吃透。2. 地基操作split 与 merge2.1 节点定义和两个辅助函数无旋 Treap 的节点定义非常朴素struct Node { int l, r; // 左右孩子下标0 表示空 int val; // 键值满足 BST 性质 uint32_t prio; // 随机优先级满足堆性质 int sz; // 子树大小 };相比普通二叉树只多了 prio 和 sz。sz 用于支持排名、第 k 小查询也是 split 按大小拆时必需的信息。所有操作基于下标完成root 为 0 表示空树这样可以用静态数组存储避免频繁 new/delete在性能敏感场景下更稳。辅助函数只有两个int tot 0; int new_node(int val) { tr[tot] {0, 0, val, next_rand(), 1}; return tot; } void push_up(int u) { tr[u].sz tr[tr[u].l].sz tr[tr[u].r].sz 1; }push_up 在任何子树结构变更后都要调用用来重算 sz。这个函数看着不起眼漏调一次就是大面积错误后面排查部分我会专门强调。2.2 split 的两种口径按值和按大小split 是把一棵树沿某个分界线拆成两棵树。无旋 Treap 里有两种常见口径按值拆和按大小拆。按值拆给定 val拆成 a 和 ba 里所有节点键值 valb 里所有节点键值 val。// 把树 u 按值拆成 a val和 b val void split_val(int u, int val, int a, int b) { if (u 0) { a b 0; return; } if (tr[u].val val) { a u; // u 和它的左子树都属于 a split_val(tr[u].r, val, tr[u].r, b); // 右子树里可能还有 val 的 push_up(a); } else { b u; // u 和它的右子树都属于 b split_val(tr[u].l, val, a, tr[u].l); // 左子树里可能还有 val 的 push_up(b); } }这里最需要理解递归里的方向选择。当前节点 val 时它应该留在左边这棵树 a 里而且它的左子树一定也都 valBST 性质保证所以只需要递归拆它的右子树把右子树拆成 val 和 val 两半前者接回 u 的右儿子位置后者作为 b 传递出去。当前节点 val 的情况完全对称只是方向反转。按大小拆给定 k拆成 a 和 ba 包含原树中序遍历的前 k 个节点也就是最小的 k 个b 是剩余部分。// 把树 u 按大小拆成 a前 k 个和 b剩余 void split_k(int u, int k, int a, int b) { if (u 0) { a b 0; return; } int left_sz tr[tr[u].l].sz; if (left_sz 1 k) { a u; split_k(tr[u].r, k - left_sz - 1, tr[u].r, b); push_up(a); } else { b u; split_k(tr[u].l, k, a, tr[u].l); push_up(b); } }按值拆用于所有按值操作插入、删除、排名、前驱后继按大小拆用于按位序操作查第 k 小、区间操作。两者一个看 val、一个看 sz其余逻辑完全一致学会一个另一个就是照猫画虎。2.3 merge 的铁律全序前提merge 是把两棵树拼回一棵它有一个必须满足的前提a 中所有节点的键值都严格小于 b 中所有节点的键值。在这个前提下合并只看优先级// 合并 a、b返回新根前提是 a 中所有 val b 中所有 val int merge(int a, int b) { if (a 0 || b 0) return a b; if (tr[a].prio tr[b].prio) { tr[a].r merge(tr[a].r, b); push_up(a); return a; } else { tr[b].l merge(a, tr[b].l); push_up(b); return b; } }为什么必须有全序前提因为 BST 性质要求任意节点的左子树全部小于自己、右子树全部大于自己。如果 a、b 之间存在键值交错merge 之后中序遍历就不再有序后面的查询全部失效。代码里 merge 只管 prio但使用者必须心里清楚这两棵树到底是不是 a b。每次调用 merge都要能说清它的两棵子树分别代表哪一段值域否则 bug 会埋得非常深。merge 的细节也值得讲当 prio[a] prio[b] 时a 成为新根。因为 a 里所有键都小于 b所以 b 只能出现在 a 的右子树方向于是递归 merge(a.r, b)。反之b 成为根时a 只能出现在 b 的左子树方向递归 merge(a, b.l)。这个方向写反是新手最容易犯的错误。2.4 复杂度直觉为什么是期望 O(log n)split 和 merge 的每次操作都只沿着一条根到叶子的路径走代价是 O(树高)。树的期望高度是 O(log n)源自随机优先级带来的随机 BST 等价性因此所有基于 split/merge 的操作都是期望 O(log n)。需要强调一下期望两个字。随机化数据结构不保证每次都是 O(log n)而是长期运行下平均表现稳定。实际工程中这个概率模型非常可靠配合好的随机数发生器几乎不会出问题。用大 O 描述时多数资料直接写 O(log n)但心里要明白这是期望意义下的。3. 基本操作的完整实现3.1 插入和删除拆两刀焊回去插入 val 是最好理解的void insert(int val) { int a, b; split_val(root, val, a, b); root merge(merge(a, new_node(val)), b); }把原树按 val 拆成 val 和 val 两棵新建节点先和 a 合并再和 b 合并。整个过程没有任何旋转思路就是切一刀、放进去、焊起来。删除一个等于 val 的节点要稍微绕一点void erase_one(int val) { int a, b, c; split_val(root, val, a, b); // a: val, b: val split_val(a, val - 1, a, c); // 再拆: a: val-1, c: val c merge(tr[c].l, tr[c].r); // 拿走 c 的根把剩余子树合并回 root merge(merge(a, c), b); }这里有个关键细节如果允许重复值c 里可能不是单个节点而是一棵子树。所以不能直接把 c 丢掉而是只拿走 c 的根节点把 c 的左右子树合并后接回原位。这样每次删除恰好移除一个 val符合多重集的操作语义。如果要求删除所有等于 val 的节点直接把 c 丢弃即可但我个人不推荐在静态数组实现里这么做原因后面讲内存时会提到。上面这种删除一个节点但保留其余重复值的方法操作次数多但语义干净是我在竞赛和工程里最常用的做法。如果你确定元素不重复也可以简化成直接丢弃 c代码更短。3.2 kth 和 rank一个走树一个拆树第 k 小查询不需要 split直接沿树走下去int kth(int k) { int u root; while (u) { int left_sz tr[tr[u].l].sz; if (left_sz 1 k) return tr[u].val; if (left_sz 1 k) { u tr[u].l; } else { k - left_sz 1; u tr[u].r; } } return -1; // 找不到 }核心是 left_sz 1 这个表达式它表示当前节点在中序遍历里的排名。比 k 大就往左比 k 小就往右并把 k 减掉当前节点和左子树的贡献非常像在数组上做二分查找。求排名有多少个数严格小于 val再加 1用拆树更直观int rank_of(int val) { int a, b; split_val(root, val - 1, a, b); // a 里全是严格小于 val 的 int ans tr[a].sz 1; root merge(a, b); return ans; }注意这里拆的是 val - 1不是 val。如果拆 vala 里会包含等于 val 的节点排名就变成小于等于了语义不准确。为什么 val - 1 可行因为键值是整数 val-1 等价于 val。用 val - 1 这个细节充分体现了对 split 边界的精确掌控后面排错部分还会遇到。3.3 前驱和后继拆出一半来找边界前驱是严格小于 val 的最大键后继是严格大于 val 的最小键。实现思路是拆出一半再在边界上找最值int get_pre(int val) { int a, b; split_val(root, val - 1, a, b); // a 里全是 val-1 int res -1; int u a; while (u) { res tr[u].val; // 一路向右记录经过的值 u tr[u].r; } root merge(a, b); return res; // 右走到尽头就是最大前驱 } int get_nxt(int val) { int a, b; split_val(root, val, a, b); // b 里全是 val int res -1; int u b; while (u) { res tr[u].val; u tr[u].l; } root merge(a, b); return res; }前驱就是 a 树中序遍历的最后一个节点一路往右到底后继就是 b 树中序遍历的第一个节点一路往左到底。这个实现比用 kth 和 rank 组合拼前驱后继要快也更能体现拆树思维的价值。3.4 中序遍历和完整示例中序遍历可以验证整棵树的正确性——无旋 Treap 的中序遍历一定是升序序列void inorder(int u) { if (u 0) return; inorder(tr[u].l); cout tr[u].val ; inorder(tr[u].r); }把前面所有操作拼成一个最小可运行示例int main() { int n; cin n; for (int i 0; i n; i) { int x; cin x; insert(x); } inorder(root); cout \n; cout 第3小: kth(3) \n; cout 5的排名: rank_of(5) \n; }我建议你拿到代码后先打印中序遍历确认有序性再做查询操作。这一步很便宜却能帮你排除掉大量低级错误。4. 常见问题与排查技巧实录4.1 等号问题split 边界一毫米都不能差split 按值拆时到底用 val 还是 val这不只是风格问题而是语义问题。我推荐统一约定为left 树取 valright 树取 val然后所有操作都严格按这个约定写。最常见的 bug 出现在删除操作里。第一次 split(root, val) 拆走所有 val 的节点第二次 split(a, val - 1) 才能把等于 val 的节点单独拎出来。如果有人把第二次写成 split(a, val)结果 c 永远是空树等于 val 的节点根本删不掉。这一类问题很难靠肉眼发现因为插入、查询可能都正常只有重复删除时才露馅。注意每次调用 split 前都要想清楚这条分界线到底要卡在哪尤其是涉及 val-1 这种偏移时宁可多花十秒脑内模拟也不要写完就提交。4.2 push_up 的黄金法则sz 维护错误是新手第二个重灾区。原则只有一条凡是修改了子树结构的递归函数在返回前必须调用 push_up。split 两个分支里各调一次merge 两个分支里各调一次少一次就是灾难。为什么后果严重sz 不准会直接污染 kth、rank、split_k 这些依赖子树大小的操作。而且这个错误有隐蔽性——插入删除次数少时可能碰巧正常次数多了排名结果就开始飘。排查时如果发现 kth 和 rank 结果不一致、且中序遍历正常优先怀疑 sz 是否在某个分支上忘了更新。4.3 rand 的坑远比你想的多实现里那个 next_rand() 千万别直接用 C 标准库的 rand()。问题在于 rand() 在部分平台上 RAND_MAX 只有 32767一旦节点数量超过这个范围随机优先级就严重不够用等价于在较小的值域里重复采样堆性质容易退化。我踩过这个坑之后的所有实现都统一用 mt19937 加时间种子static mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); uint32_t next_rand() { return rng(); }mt19937 的周期和质量对于平衡树场景绰绰有余生成一次 32 位随机数也就几纳秒完全不是性能瓶颈。另外有人用 prio rng() ^ 某个递增计数器来进一步打散这属于微优化实际表现差别不大看个人习惯。4.4 递归深度和数组内存的隐患无旋 Treap 的期望树高 O(log n)但随机数发生器质量差或者种子碰巧坏掉时单次操作偶尔也会递归很深。在 Windows 默认 1MB 栈空间下几十万层递归会直接爆栈。我在自己的代码里一般会加一句编译指令开大栈或者把递归改成显式栈迭代前者在竞赛场景更省事。数组内存是另一个容易被忽略的点。如果采用删除时直接丢弃节点的策略每次删除都会产生一个垃圾节点虽然逻辑上不可达但物理上仍占用数组空间。操作量大时数组会被快速耗尽。解决方案是维护一个回收栈int bin[N], bin_top 0; // 回收栈 int new_node(int val) { int u; if (bin_top) u bin[bin_top--]; else u tot; tr[u] {0, 0, val, next_rand(), 1}; return u; } void recycle(int u) { if (u 0) return; recycle(tr[u].l); recycle(tr[u].r); bin[bin_top] u; }删除整个子树时先回收再拼接内存就能循环使用。这个技巧在持久化场景下反而不能用但在普通静态数组实现里非常实用。4.5 调试神器和 std::multiset 对拍我调试平衡树类数据结构时最依赖的方法就是对拍。思路很简单用 std::multiset 作为标准答案随机生成操作序列同时喂给两套实现每次操作后比对结果。不需要什么复杂框架几十行代码就能跑。// 伪代码示意 multisetint st; for (int i 0; i 100000; i) { int op rng() % 4; int val rng() % 1000; if (op 0) { st.insert(val); insert(val); } else if (op 1) { auto it st.find(val); if (it ! st.end()) st.erase(it); erase_one(val); } else if (op 2) { assert(kth(3) *next(st.begin(), 2)); } else if (op 3) { int r 1; for (int x : st) if (x val) break; else r; assert(rank_of(val) r); } }这个对拍脚本帮我抓出过至少三种隐蔽 bugsplit 等号边界错误、erase 后 sz 未更新、merge 顺序写反。如果你自己写了一遍无旋 Treap 却总感觉哪里不对别硬看代码写个对拍跑一万次随机操作问题自动现形。最后再分享一个小技巧无旋 Treap 的代码结构非常规整建议把 split_val、split_k、merge 三个函数背下来剩下所有操作都是它们的组合。所谓基本操作本质就是拆得好、合得对这六个字。后面做区间翻转、持久化、可持久化文艺平衡树你会发现用的还是这三个函数只是分界线从值变成了位置仅此而已。