本课时有配套视频讲解，购买后即可观看（永久有效）
平衡二叉树
一、课上练习
编程练习
（暂无）
二、知识总结
✨ 核心思想
普通二叉搜索树（BST）在最坏情况下会退化为链，操作复杂度退化为 O(n)。平衡二叉树通过维护树的平衡性，保证所有操作的时间复杂度为 O(log n)。
本节介绍竞赛中最实用的平衡树——Treap（Tree + Heap）。Treap 给每个节点分配一个随机的优先级，同时满足 BST 性质（按 key）和堆性质（按 priority），通过随机化保证期望树高为 O(log n)。
✨ 算法原理
Treap 的两种实现
- 旋转 Treap：通过左旋/右旋维护堆性质
- 无旋 Treap（FHQ Treap）：通过 split/merge 操作实现，代码更简洁，功能更强
本节重点介绍无旋 Treap（FHQ Treap），它在竞赛中更常用。
FHQ Treap 的核心操作
Split（按值分裂）：将树分成两棵，左树所有值 ≤ k，右树所有值 > k。
Merge（合并）：将两棵树合并，要求左树所有值 < 右树所有值。按 priority 决定谁做根。
有了 split 和 merge，所有 BST 操作都能轻松实现：
- 插入 val：split(root, val-1) → merge(left, newNode) → merge(result, right)
- 删除 val：split 出 val，再 split 出单个节点，merge 回去
- 查排名、查第 k 大、前驱、后继：split 后利用子树大小信息
✨ 代码实现
FHQ Treap（无旋Treap）完整实现
1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 200005;
5
6mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
7
8struct FHQTreap {
9 int ls[MAXN], rs[MAXN]; // 左右子节点
10 int val[MAXN]; // 键值
11 int pri[MAXN]; // 随机优先级
12 int sz[MAXN]; // 子树大小
13 int tot = 0; // 节点计数
14 int root = 0; // 根节点
15
16 int newNode(int v) {
17 int p = ++tot;
18 ls[p] = rs[p] = 0;
19 val[p] = v;
20 pri[p] = rng();
21 sz[p] = 1;
22 return p;
23 }
24
25 void pushUp(int p) {
26 sz[p] = sz[ls[p]] + sz[rs[p]] + 1;
27 }
28
29 // 按值分裂：val <= k的归左树，val > k的归右树
30 void split(int p, int k, int &x, int &y) {
31 if (!p) { x = y = 0; return; }
32 if (val[p] <= k) {
33 x = p;
34 split(rs[p], k, rs[p], y);
35 } else {
36 y = p;
37 split(ls[p], k, x, ls[p]);
38 }
39 pushUp(p);
40 }
41
42 // 合并两棵树（x的所有值 < y的所有值）
43 int merge(int x, int y) {
44 if (!x || !y) return x | y;
45 if (pri[x] > pri[y]) {
46 rs[x] = merge(rs[x], y);
47 pushUp(x);
48 return x;
49 } else {
50 ls[y] = merge(x, ls[y]);
51 pushUp(y);
52 return y;
53 }
54 }
55
56 // 插入值v
57 void insert(int v) {
58 int x, y;
59 split(root, v, x, y);
60 root = merge(merge(x, newNode(v)), y);
61 }
62
63 // 删除一个值为v的节点
64 void erase(int v) {
65 int x, y, z;
66 split(root, v, x, z);
67 split(x, v - 1, x, y);
68 // y中都是值为v的节点，删除一个（去掉根）
69 y = merge(ls[y], rs[y]);
70 root = merge(merge(x, y), z);
71 }
72
73 // 查询v的排名（比v小的数的个数+1）
74 int getRank(int v) {
75 int x, y;
76 split(root, v - 1, x, y);
77 int rank = sz[x] + 1;
78 root = merge(x, y);
79 return rank;
80 }
81
82 // 查询排名为k的值
83 int getKth(int p, int k) {
84 while (true) {
85 int leftSz = sz[ls[p]];
86 if (k <= leftSz) {
87 p = ls[p];
88 } else if (k == leftSz + 1) {
89 return val[p];
90 } else {
91 k -= leftSz + 1;
92 p = rs[p];
93 }
94 }
95 }
96
97 int getKth(int k) {
98 return getKth(root, k);
99 }
100
101 // 查询v的前驱（严格小于v的最大值）
102 int getPrev(int v) {
103 int x, y;
104 split(root, v - 1, x, y);
105 int ans = getKth(x, sz[x]); // x中的最大值
106 root = merge(x, y);
107 return ans;
108 }
109
110 // 查询v的后继（严格大于v的最小值）
111 int getNext(int v) {
112 int x, y;
113 split(root, v, x, y);
114 int ans = getKth(y, 1); // y中的最小值
115 root = merge(x, y);
116 return ans;
117 }
118} treap;
119
120int main() {
121 ios::sync_with_stdio(false);
122 cin.tie(nullptr);
123
124 int n;
125 cin >> n;
126
127 while (n--) {
128 int op, x;
129 cin >> op >> x;
130 switch (op) {
131 case 1: treap.insert(x); break;
132 case 2: treap.erase(x); break;
133 case 3: cout << treap.getRank(x) << "\n"; break;
134 case 4: cout << treap.getKth(x) << "\n"; break;
135 case 5: cout << treap.getPrev(x) << "\n"; break;
136 case 6: cout << treap.getNext(x) << "\n"; break;
137 }
138 }
139
140 return 0;
141}✨ 执行示例
依次执行以下操作：
| 操作 | 说明 | 结果 |
|---|---|---|
| insert(3) | 插入 3 | 树：{3} |
| insert(1) | 插入 1 | 树：{1, 3} |
| insert(5) | 插入 5 | 树：{1, 3, 5} |
| insert(2) | 插入 2 | 树：{1, 2, 3, 5} |
| getRank(3) | 3 的排名 | 3（前面有 1, 2） |
| getKth(2) | 第 2 小 | 2 |
| getPrev(3) | 3 的前驱 | 2 |
| getNext(3) | 3 的后继 | 5 |
| erase(3) | 删除 3 | 树：{1, 2, 5} |
| getRank(4) | 4 的排名 | 3（前面有 1, 2） |
Split 过程示意
执行 split(root, 3) 将树按值 3 分裂：
1原树： 分裂后：
2 3 左树(<=3): 右树(>3):
3 / \ 3 5
4 2 5 /
5 / 2
6 1 /
7 1Merge 过程示意
合并左树和右树时，比较根节点的 priority：
- 若左根 priority 更大，左根做根，递归合并左根的右子和右树
- 否则右根做根，递归合并左树和右根的左子
✨ 解题步骤详解
FHQ Treap 支持的操作一览
| 操作 | 实现方式 | 复杂度 |
|---|---|---|
| 插入 | split + merge | O(log n) |
| 删除 | 两次 split + merge | O(log n) |
| 查排名 | split + 子树大小 | O(log n) |
| 查第 k 大 | 在树上二分 | O(log n) |
| 前驱/后继 | split + 查最值 | O(log n) |
| 区间翻转 | 按大小 split + 打标记 | O(log n) |
为什么 FHQ Treap 比旋转 Treap 好？
- 代码更短：只需要 split 和 merge 两个核心函数
- 功能更强：天然支持区间操作（可持久化、区间翻转等）
- 不需要理解旋转：旋转的正确性比较难理解
AVL 树简介
AVL 树通过维护每个节点的平衡因子（左右子树高度差不超过 1）来保证平衡。失衡时通过四种旋转恢复：
- LL 旋转（右旋）
- RR 旋转（左旋）
- LR 旋转（先左旋后右旋）
- RL 旋转（先右旋后左旋）
AVL 树的平衡条件更严格，查询稍快，但插入删除时旋转次数多于 Treap。竞赛中一般优先选择 FHQ Treap。
✨ 常见错误
- 随机数生成器质量差：使用
rand()可能不够随机，推荐mt19937。 - split 后忘记 pushUp：split 会改变子树结构，必须更新 sz。
- merge 的前提条件不满足：merge(x, y) 要求 x 中所有值 < y 中所有值，否则结果不正确。
- 删除时删多了：erase 只应删除一个值为 v 的节点。split 出 y 后，
y = merge(ls[y], rs[y])只去掉根节点（一个）。 - 空节点没处理：
sz[0]必须为 0，ls[0] = rs[0] = 0。
✨ 算法评价
| 指标 | 复杂度 |
|---|---|
| 插入 | 期望 O(log n) |
| 删除 | 期望 O(log n) |
| 查询 | 期望 O(log n) |
| 空间 | O(n) |
与 STL 对比：
std::set/std::multiset底层是红黑树，支持插入、删除、查找，但不支持查第 k 大、查排名- 需要排名操作时，必须手写平衡树或使用
_gnupbds::tree
竞赛建议：FHQ Treap 是竞赛中最推荐的平衡树实现，代码量适中，功能齐全，背板后可以快速应用。