Treap：用高质量随机权值守护平衡的二叉搜索树

文章目录

• Treap：用高质量随机权值守护平衡的二叉搜索树
• • 一、背景：BST的回顾与缺陷
  • • 1. BST的核心性质
    • 2. BST的致命缺陷
  • 二、Treap的核心思想：BST + Heap的混血儿
  • • 为什么需要“高质量”的随机权值？
  • 三、关键优化：用mt19937替代rand()
  • • 1. 传统rand()的三大缺陷
    • 2. mt19937的核心优势
  • 四、基础操作：旋转（zig / zag）
  • • 1. 右旋（zig）
    • 2. 左旋（zag）
  • 五、核心操作实现（融入mt19937）
  • • 1. 全局定义与初始化
    • 2. 信息上提（push_up）
    • 3. 旋转操作
    • 4. 插入操作（核心优化点）
    • 5. 删除操作
    • 6. 排名查询（查询data的排名：比data小的数的个数+1）
    • 7. 数值查询（查询排名为rank的数值）
    • 8. 前驱查询（严格小于data的最大值）
    • 9. 后继查询（严格大于data的最小值）
  • 六、完整可运行代码（洛谷P3369）
  • 七、实战测试用例
  • • 输入
    • 输出
    • 结果解释
  • 八、Treap的优缺点与适用场景
  • • 核心优点
    • 核心缺点
    • 适用场景
    • 不适用场景
  • 九、总结

Treap：用高质量随机权值守护平衡的二叉搜索树

如果你已经了解二叉搜索树（BST），一定对它“有序插入就退化成链”的缺陷印象深刻。为了让BST在动态操作下保持平衡，Treap（Tree + Heap） 凭借“随机权值+旋转”的极简设计成为算法竞赛的首选——而本次我们将对其核心的随机数生成逻辑做关键优化：用C++11的mt19937（梅森旋转算法）替代传统rand()，进一步提升随机权值的质量，让Treap的平衡特性更稳定。

一、背景：BST的回顾与缺陷

在了解Treap之前，我们先快速回顾BST的核心特性与问题。

1. BST的核心性质

二叉搜索树的每个节点都满足：

• 左子树中所有节点的权值 严格小于 当前节点的权值
• 右子树中所有节点的权值 严格大于 当前节点的权值
• 中序遍历结果是一个严格递增的序列

基于这个性质，插入、删除、查询等操作在随机数据下时间复杂度为O(logn)。

2. BST的致命缺陷

BST的时间复杂度高度依赖树的高度：在有序插入的极端情况下（如依次插入1、2、3、4、5），树会退化成一条链，所有操作的时间复杂度降至O(n)，性能直接雪崩。

Treap的出现正是为了解决这个问题——它用“随机权值”打乱BST的结构，让树在概率上保持平衡；而选择高质量的随机数生成器，则是Treap稳定运行的关键。

二、Treap的核心思想：BST + Heap的混血儿

Treap的名字揭示了它的本质：Tree（二叉搜索树） + Heap（堆）。每个节点存储两个关键值：

• data：节点的实际权值，满足BST性质（左小右大）
• val：随机生成的堆权值，满足大根堆性质（父节点的val大于子节点的val）

为什么需要“高质量”的随机权值？

Treap的平衡完全依赖val的随机性：

• 若随机数质量低（如传统rand()），可能出现重复/分布不均的val序列，极端情况下仍会导致树结构失衡；
• 高质量的随机数（如mt19937生成）能保证val的均匀分布，让Treap的均摊时间复杂度稳定在O(logn)。

简单来说，Treap的平衡“根基”是随机权值，而mt19937则为这个根基提供了更坚固的保障。

三、关键优化：用mt19937替代rand()

在正式实现Treap前，我们先厘清“为什么要替换rand()”——这是本次优化的核心。

1. 传统rand()的三大缺陷

2. mt19937的核心优势

mt19937（梅森旋转算法）是C++11标准库提供的高质量伪随机数生成器：

• 超长周期：(2^{19937}-1)，几乎不会出现重复序列；
• 分布均匀：生成的随机数统计特性优异，能保证Treap权值的均匀性；
• 取值范围大：返回[0, 2^32-1]的无符号整数，权值随机性拉满；
• 跨平台一致：C++标准统一实现，不同编译器运行结果一致。

这也是为什么在算法竞赛中，mt19937已成为Treap/FHQ Treap等随机化平衡树的标配。

四、基础操作：旋转（zig / zag）

和所有平衡树一样，Treap的核心调整手段是旋转——在保持BST和Heap性质的前提下，调整节点位置，让树的结构更平衡。

旋转分为右旋（zig） 和左旋（zag） 两种，是互逆的镜像操作。

1. 右旋（zig）

适用场景：节点X是父节点Y的左孩子，且X的堆权值val大于Y的val时，右旋让X上移为新的父节点。

Y X
/ \\ / \\
X C → A Y
/ \\ / \\
A B B C

核心逻辑：将X从Y的左孩子变为父节点，Y变为X的右孩子，X原来的右子树B挂到Y的左孩子位置，保持BST和Heap性质。

2. 左旋（zag）

适用场景：节点X是父节点Y的右孩子，且X的堆权值val大于Y的val时，左旋让X上移为新的父节点。

Y X
/ \\ / \\
A X → Y C
/ \\ / \\
B C A B

核心逻辑：将X从Y的右孩子变为父节点，Y变为X的左孩子，X原来的左子树B挂到Y的右孩子位置，保持BST和Heap性质。

旋转的关键作用：插入/删除节点后，通过旋转修复堆性质，同时让树的结构更平衡。

五、核心操作实现（融入mt19937）

基于旋转和mt19937，我们实现Treap的所有核心操作：插入、删除、查询排名、查询值、前驱后继等。

1. 全局定义与初始化

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int INF = 1e9;
// 初始化mt19937：用系统时间作为动态种子，保证每次运行随机序列不同
mt19937 rnd(114514);
// Treap节点结构
struct Treap {
int l, r; // 左孩子、右孩子编号
int data; // 节点实际权值（BST关键字）
int val; // 随机堆权值（大根堆关键字）
int size; // 子树大小（含当前节点）
int cnt; // 节点值的重复次数
} tr[N];
int root, idx; // root：根节点编号；idx：节点计数器（分配新节点）

2. 信息上提（push_up）

节点旋转/修改后，需更新子树大小，保证排名查询的准确性：

void push_up(int u) {
// 子树大小 = 左子树大小 + 右子树大小 + 当前节点重复次数
tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + tr[u].cnt;
}

3. 旋转操作

// 右旋：将u的左孩子上移为新的根节点
void zig(int &u) {
int x = tr[u].l; // x是u的左孩子
tr[u].l = tr[x].r; // x的右子树挂到u的左孩子位置
tr[x].r = u; // u挂到x的右孩子位置
u = x; // 更新根节点为x
push_up(tr[u].r); // 先更新原根节点（u）的信息
push_up(u); // 再更新新根节点（x）的信息
}
// 左旋：将u的右孩子上移为新的根节点
void zag(int &u) {
int x = tr[u].r; // x是u的右孩子
tr[u].r = tr[x].l; // x的左子树挂到u的右孩子位置
tr[x].l = u; // u挂到x的左孩子位置
u = x; // 更新根节点为x
push_up(tr[u].l); // 先更新原根节点（u）的信息
push_up(u); // 再更新新根节点（x）的信息
}

4. 插入操作（核心优化点）

void insert(int &u, int data) {
if (!u) { // 到达空节点，创建新节点
u = ++idx;
tr[u].data = data;
tr[u].val = rnd(); // 核心优化：用mt19937生成随机权值
tr[u].size = tr[u].cnt = 1;
return;
}
if (tr[u].data == data)
tr[u].cnt++; // 节点值已存在，重复次数+1
else if (data < tr[u].data) {
insert(tr[u].l, data); // 插入左子树
// 左孩子val更大，违反大根堆性质，右旋调整
if (tr[tr[u].l].val > tr[u].val) zig(u);
} else {
insert(tr[u].r, data); // 插入右子树
// 右孩子val更大，违反大根堆性质，左旋调整
if (tr[tr[u].r].val > tr[u].val) zag(u);
}
push_up(u); // 更新当前节点的子树大小
}

5. 删除操作

void remove(int &u, int data) {
if (!u) return; // 空节点，直接返回
if (tr[u].data == data) {
// 情况1：节点有重复值，仅减少次数
if (tr[u].cnt > 1)
tr[u].cnt—;
// 情况2：叶子节点/单孩子节点，直接删除
else if (!tr[u].l || !tr[u].r)
u = tr[u].l | tr[u].r; // 非空孩子成为新节点
// 情况3：有两个孩子，旋转成叶子后删除
else {
// 选择val更大的孩子旋转上来，保证堆性质
if (tr[tr[u].l].val > tr[tr[u].r].val) {
zig(u); // 右旋左孩子，u下沉到右子树
remove(tr[u].r, data);
} else {
zag(u); // 左旋右孩子，u下沉到左子树
remove(tr[u].l, data);
}
}
} else if (data < tr[u].data)
remove(tr[u].l, data); // 递归删除左子树
else
remove(tr[u].r, data); // 递归删除右子树
if (u) push_up(u); // 更新子树大小（u非空时）
}

6. 排名查询（查询data的排名：比data小的数的个数+1）

int get_rank(int u, int data) {
if (!u) return 0; // 空节点，返回0
if (tr[u].data == data)
// 排名 = 左子树大小 + 1
return tr[tr[u].l].size + 1;
else if (data < tr[u].data)
// data在左子树，递归查询左子树
return get_rank(tr[u].l, data);
else
// data在右子树，排名 = 左子树大小 + 当前节点次数 + 右子树查询结果
return tr[tr[u].l].size + tr[u].cnt + get_rank(tr[u].r, data);
}

7. 数值查询（查询排名为rank的数值）

int get_val(int u, int rank) {
if (!u) return 0; // 空节点，返回0
if (tr[tr[u].l].size >= rank)
// 排名在左子树，递归查询左子树
return get_val(tr[u].l, rank);
else if (tr[tr[u].l].size + tr[u].cnt >= rank)
// 排名命中当前节点，返回当前节点值
return tr[u].data;
else
// 排名在右子树，递归查询右子树（更新rank）
return get_val(tr[u].r, rank – tr[tr[u].l].size – tr[u].cnt);
}

8. 前驱查询（严格小于data的最大值）

int get_prev(int u, int data) {
if (!u) return –INF; // 空节点，返回负无穷
if (tr[u].data >= data)
// 当前节点值≥data，前驱在左子树
return get_prev(tr[u].l, data);
else
// 当前节点值<data，前驱是“当前节点”和“右子树前驱”的较大值
return max(tr[u].data, get_prev(tr[u].r, data));
}

9. 后继查询（严格大于data的最小值）

int get_next(int u, int data) {
if (!u) return INF; // 空节点，返回正无穷
if (tr[u].data <= data)
// 当前节点值≤data，后继在右子树
return get_next(tr[u].r, data);
else
// 当前节点值>data，后继是“当前节点”和“左子树后继”的较小值
return min(tr[u].data, get_next(tr[u].l, data));
}

六、完整可运行代码（洛谷P3369）

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int INF = 1e9;
mt19937 rnd(time(0));
struct Treap {
int l, r;
int data, val;
int size, cnt;
} tr[N];
int root, idx;
void push_up(int u) {
tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + tr[u].cnt;
}
void zig(int &u) {
int x = tr[u].l;
tr[u].l = tr[x].r;
tr[x].r = u;
u = x;
push_up(tr[u].r);
push_up(u);
}
void zag(int &u) {
int x = tr[u].r;
tr[u].r = tr[x].l;
tr[x].l = u;
u = x;
push_up(tr[u].l);
push_up(u);
}
void insert(int &u, int data) {
if (!u) {
u = ++idx;
tr[u].data = data;
tr[u].val = rnd();
tr[u].size = tr[u].cnt = 1;
return;
}
if (tr[u].data == data)
tr[u].cnt++;
else if (data < tr[u].data) {
insert(tr[u].l, data);
if (tr[tr[u].l].val > tr[u].val)
zig(u);
} else {
insert(tr[u].r, data);
if (tr[tr[u].r].val > tr[u].val)
zag(u);
}
push_up(u);
}
void remove(int &u, int data) {
if (!u) return;
if (tr[u].data == data) {
if (tr[u].cnt > 1)
tr[u].cnt—;
else if (!tr[u].l || !tr[u].r)
u = tr[u].l | tr[u].r;
else {
if (tr[tr[u].l].val > tr[tr[u].r].val) {
zig(u);
remove(tr[u].r, data);
} else {
zag(u);
remove(tr[u].l, data);
}
}
} else if (data < tr[u].data)
remove(tr[u].l, data);
else
remove(tr[u].r, data);
if (u) push_up(u);
}
int get_rank(int u, int data) {
if (!u) return 0;
if (tr[u].data == data)
return tr[tr[u].l].size + 1;
else if (data < tr[u].data)
return get_rank(tr[u].l, data);
else
return tr[tr[u].l].size + tr[u].cnt + get_rank(tr[u].r, data);
}
int get_val(int u, int rank) {
if (!u) return 0;
if (tr[tr[u].l].size >= rank)
return get_val(tr[u].l, rank);
else if (tr[tr[u].l].size + tr[u].cnt >= rank)
return tr[u].data;
else
return get_val(tr[u].r, rank – tr[tr[u].l].size – tr[u].cnt);
}
int get_prev(int u, int data) {
if (!u) return –INF;
if (tr[u].data >= data)
return get_prev(tr[u].l, data);
else
return max(tr[u].data, get_prev(tr[u].r, data));
}
int get_next(int u, int data) {
if (!u) return INF;
if (tr[u].data <= data)
return get_next(tr[u].r, data);
else
return min(tr[u].data, get_next(tr[u].l, data));
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
while (n—) {
int op, x;
cin >> op >> x;
if (op == 1) insert(root, x);
else if (op == 2) remove(root, x);
else if (op == 3) cout << get_rank(root, x) << endl;
else if (op == 4) cout << get_val(root, x) << endl;
else if (op == 5) cout << get_prev(root, x) << endl;
else if (op == 6) cout << get_next(root, x) << endl;
}
return 0;
}

七、实战测试用例

输入

10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

输出

106465
84185
492737

结果解释

八、Treap的优缺点与适用场景

核心优点

核心缺点

适用场景

• 算法竞赛中的普通平衡树问题（如洛谷P3369）；
• 需高效支持“插入/删除/排名查询”的有序集合场景；
• 对代码简洁性和运行效率要求高的场景。

不适用场景

• 需要高效处理区间操作的动态序列问题（选Splay/FHQ Treap）；
• 对确定性平衡要求极高的场景（选AVL树）；
• 需要可持久化的场景（选FHQ Treap）。

九、总结

Treap是“随机化算法”的经典应用——它没有引入复杂的平衡规则，而是用“高质量随机权值”这一简单手段，让BST的结构变得随机化，从而避免了退化。本次优化的mt19937则进一步强化了这一核心：相比传统rand()，它提供了更长的周期、更均匀的分布，让Treap的平衡特性更稳定。

从学习角度来说，Treap是入门平衡树的最佳选择：

• 理解它的“BST+Heap”双性质，能帮你打通平衡树的核心逻辑；
• 掌握mt19937的应用，能让你在后续学习FHQ Treap等进阶结构时更轻松；
• 其简洁的代码风格，也非常适合算法竞赛的快速编码场景。

如果需要处理区间操作，你可以进一步学习Treap的变种FHQ Treap（无旋Treap）——它通过分裂（split）和合并（merge）操作，实现了高效的区间处理能力，同时保留了Treap“随机化+代码简洁”的优势。

最后建议：手动实现一遍本文的完整代码，结合洛谷P3369等题目实战，你会彻底掌握这个“用随机守护平衡”的经典数据结构。