引言
平衡二叉搜索树是算法世界中的基石结构。从AVL树到红黑树，各种平衡策略层出不穷，但它们的实现往往伴随着复杂的旋转逻辑和大量的边界条件处理。今天我们要介绍一种优雅得多的方案——Treap（树堆），它通过为每个节点赋予一个随机优先级，将二叉搜索树（BST）与堆（Heap）两种结构巧妙地融合在一起，以极高的概率维持树的平衡。
本文采用非旋转式Treap（Split-Merge Treap）的实现方式。与传统依靠左旋、右旋来维持平衡的树不同，非旋转式Treap仅通过两个核心操作 split 与 merge 就能完成插入、删除和区间操作，代码简洁而强大。
Treap的核心思想
Treap这个名字本身即是 Tree + Heap 的组合。它要求每个节点同时满足两个性质：
- 二叉搜索树性质：节点的左子树所有值小于该节点，右子树所有值大于该节点。
- 堆性质：每个节点的优先级小于（或大于）其子节点的优先级。
关键洞察在于：只要优先级是随机分配的，Treap的期望高度就是 O(log n)。这就好比随机快速排序的期望复杂度是 O(n log n) 一样——随机性为我们省却了繁琐的平衡维护。
非旋转式Treap的两大核心操作
Split 操作
split(root, key) 将一棵树拆分为两棵子树 L 和 R，使得 L 中所有节点的值小于等于 key，R 中所有节点的值大于 key。
拆分逻辑十分直观：
– 若 root.val <= key，则根节点及其左子树属于 L，继续对右子树递归拆分。
– 若 root.val > key，则根节点及其右子树属于 R，继续对左子树递归拆分。
Merge 操作
merge(L, R) 将两棵子树合并为一棵，前提是 L 中所有值小于 R 中所有值。
合并逻辑同样简洁：
– 比较两棵树的根节点优先级，优先级更高的作为新根。
– 若 L 的根优先级更高，L 的右子树与 R 递归合并。
– 若 R 的根优先级更高，R 的左子树与 L 递归合并。
完整Java实现
下面给出非旋转式Treap的完整Java实现，包含插入、删除、查询、前驱、后继以及中序遍历。代码经过精心设计，可以直接运行。
import java.util.Random;
/**
* 非旋转式Treap（Split-Merge Treap）实现
* 通过随机优先级维持期望 O(log n) 的高度
*/
public class Treap {
private static final Random RAND = new Random();
private Node root;
/**
* Treap节点定义
* val: 节点值（BST比较依据）
* priority: 随机优先级（Heap比较依据）
* size: 子树节点数（用于隐式Treap的索引查询）
*/
private static class Node {
int val;
int priority;
Node left, right;
int size;
Node(int val) {
this.val = val;
this.priority = RAND.nextInt();
this.size = 1;
}
}
/** 获取子树大小，空节点为0 */
private int getSize(Node node) {
return node == null ? 0 : node.size;
}
/** 更新节点size字段 */
private void update(Node node) {
if (node != null) {
node.size = 1 + getSize(node.left) + getSize(node.right);
}
}
/**
* 按值拆分：将树拆分为 <= key 和 > key 两部分
* @return 包含左右子树根节点的数组
*/
private Node[] split(Node node, int key) {
if (node == null) {
return new Node[]{null, null};
}
if (node.val <= key) {
// 当前节点属于左半部分，递归拆分右子树
Node[] splitRight = split(node.right, key);
node.right = splitRight[0];
update(node);
return new Node[]{node, splitRight[1]};
} else {
// 当前节点属于右半部分，递归拆分左子树
Node[] splitLeft = split(node.left, key);
node.left = splitLeft[1];
update(node);
return new Node[]{splitLeft[0], node};
}
}
/**
* 合并两棵子树，要求 leftTree 中所有值 < rightTree 中所有值
*/
private Node merge(Node leftTree, Node rightTree) {
if (leftTree == null) return rightTree;
if (rightTree == null) return leftTree;
// 优先级高的作为根，保持堆性质
if (leftTree.priority < rightTree.priority) {
leftTree.right = merge(leftTree.right, rightTree);
update(leftTree);
return leftTree;
} else {
rightTree.left = merge(leftTree, rightTree.left);
update(rightTree);
return rightTree;
}
}
/** 插入一个值 */
public void insert(int val) {
// 先拆分为 < val 和 >= val 两部分
Node[] split = split(root, val - 1);
Node newNode = new Node(val);
// 顺序合并：左部 + 新节点 + 右部
root = merge(merge(split[0], newNode), split[1]);
}
/** 删除一个值（删除一个出现即可） */
public void delete(int val) {
// 拆分为 < val, = val, > val 三部分
Node[] split1 = split(root, val - 1);
Node[] split2 = split(split1[1], val);
// 丢弃中间部分（等于val的子树），将其左右子树合并后接回
Node mid = split2[0];
Node mergedMid = merge(mid == null ? null : mid.left, mid == null ? null : mid.right);
root = merge(split1[0], merge(mergedMid, split2[1]));
}
/** 查询值是否存在 */
public boolean contains(int val) {
Node cur = root;
while (cur != null) {
if (cur.val == val) return true;
cur = val < cur.val ? cur.left : cur.right;
}
return false;
}
/** 查找前驱（小于val的最大值） */
public Integer predecessor(int val) {
Node cur = root;
Integer res = null;
while (cur != null) {
if (cur.val < val) {
res = cur.val;
cur = cur.right;
} else {
cur = cur.left;
}
}
return res;
}
/** 查找后继（大于val的最小值） */
public Integer successor(int val) {
Node cur = root;
Integer res = null;
while (cur != null) {
if (cur.val > val) {
res = cur.val;
cur = cur.left;
} else {
cur = cur.right;
}
}
return res;
}
/** 中序遍历输出（BST性质保证有序） */
public void inorder() {
inorder(root);
System.out.println();
}
private void inorder(Node node) {
if (node == null) return;
inorder(node.left);
System.out.print(node.val + " ");
inorder(node.right);
}
/** 获取树中第 k 小的元素（1-based），利用size字段 */
public Integer kth(int k) {
if (k < 1 || k > getSize(root)) return null;
Node cur = root;
while (cur != null) {
int leftSize = getSize(cur.left);
if (k <= leftSize) {
cur = cur.left;
} else if (k == leftSize + 1) {
return cur.val;
} else {
k -= leftSize + 1;
cur = cur.right;
}
}
return null;
}
// ========== 测试入口 ==========
public static void main(String[] args) {
Treap treap = new Treap();
int[] values = {50, 30, 70, 20, 40, 60, 80, 25, 35, 75};
for (int v : values) {
treap.insert(v);
}
System.out.print("中序遍历: ");
treap.inorder(); // 输出: 20 25 30 35 40 50 60 70 75 80
System.out.println("包含 40? " + treap.contains(40)); // true
System.out.println("包含 100? " + treap.contains(100)); // false
System.out.println("40 的前驱: " + treap.predecessor(40)); // 35
System.out.println("40 的后继: " + treap.successor(40)); // 50
System.out.println("第 5 小: " + treap.kth(5)); // 40
treap.delete(40);
System.out.print("删除 40 后: ");
treap.inorder(); // 输出不含 40
System.out.println("包含 40? " + treap.contains(40)); // false
}
}
隐式Treap：超越键值的区间操作
非旋转式Treap有一个极其强大的扩展——隐式Treap（Implicit Treap）。在隐式Treap中，节点不再按键值排序，而是按位置（索引）排序。每个节点的排名由左子树的大小决定。
通过 splitBySize(root, k) 将树拆分为前 k 个元素和剩余元素，我们可以轻松实现以下操作：
- 区间翻转：将
[l, r]区间拆分出来，打上懒标记交换左右子树。 - 区间插入：将一段新序列整体插入到指定位置。
- 区间删除：将指定区间拆分出来并丢弃。
- 区间查询：查询子树和、最大值等聚合信息。
隐式Treap的代码与显式Treap几乎一致，仅需将 split 的比较条件从 val <= key 改为 leftSize <= k，是数据结构领域中代码复用率的典范。
复杂度分析
| 操作 | 期望时间复杂度 | 最坏时间复杂度 |
|---|---|---|
| 插入 | O(log n) | O(n) |
| 删除 | O(log n) | O(n) |
| 查询 | O(log n) | O(n) |
| 前驱/后继 | O(log n) | O(n) |
| 第 k 小 | O(log n) | O(n) |
| Split / Merge | O(log n) | O(n) |
期望复杂度为 O(log n) 的数学依据是：随机优先级等价于随机插入顺序，而随机BST的期望高度为 O(log n)。最坏情况仅在极小的概率下发生（优先级全序排列的概率为 1/n!）。
空间复杂度为 O(n)，每个节点仅需存储值、优先级、左右指针和子树大小。
应用场景
Treap 及隐式Treap 在竞赛编程和实际工程中都有广泛应用：
- 动态集合维护：需要频繁插入、删除且要求有序遍历的场景。
- 区间操作问题：如序列翻转、区间最值查询、区间和更新等，隐式Treap是经典解法。
- 笛卡尔树构建：将数组值作为BST键、下标作为堆优先级，可在线性时间内构建笛卡尔树。
- 可持久化数据结构：非旋转式Treap的Split-Merge语义天然适合函数式编程风格，便于实现可持久化版本。
总结
Treap 用一种近乎作弊的方式解决了平衡树的难题——不依赖复杂的旋转规则，而是将问题交给随机性。非旋转式实现更是将代码优雅度提升到了新的高度：仅需 split 与 merge 两个递归函数，就能支撑起整套平衡树操作。掌握 Treap，不仅能让你在面对平衡树问题时多一把利器，更能加深对随机化算法本质的理解：有时，让概率为我们工作，比让确定性规则束缚我们更加高效。
