数据结构——平衡树
GJX_Algorithm
·
2025-03-01 19:08:28
·
算法·理论
平衡树
二叉搜索树 ＆ 平衡树
二叉搜索树（Binary Search Tree）基础
定义：二叉搜索树是一种二叉树结构，满足如下性质：
每个节点的左子树所有节点的值小于当前节点的值。
每个节点的右子树所有节点的值大于当前节点的值。
左右子树也分别为二叉搜索树。
时间复杂度分析：
理想情况（高度最小）：二叉搜索树为完全平衡树时，若总节点数为 n，则树的高度为 \lfloor \log_2n \rfloor。其插入、删除、查询操作的时间复杂度皆为 O(\log n)。
最坏情况（高度最大）：二叉搜索树退化成链表时，若总节点数为 n，则树的高度为 n。其插入、删除、查询操作的时间复杂度皆为 O(n)。
平衡树（Balance Tree）基础
广泛定义：是指一棵树形结构，对任意节点 x，其左右子树的高度差不超过 1。
二叉搜索平衡树（后文提到的平衡树皆指二叉搜索平衡树）：上文提到 BST 的退化问题，为了解决，利用平衡树特定的平衡性质，使二叉搜索树的高度始终保持理想情况。以下给出普通 BST（退化的 BST）与经平衡后的 BST 的区别：
算法竞赛中常见的平衡树实现，本文重点介绍 FHQ-Treap：
平衡树类型
平衡策略
Treap
随机优先级，左旋与右旋
Splay
贪心
FHQ-Treap（无旋 Treap）
无旋，分裂+合并
FHQ-Treap 的实现
为什么要选择 FHQ-Treap？
无旋操作：目前笔者只学过 FHQ-Treap，似乎分裂与合并比左旋右旋更容易理解？
天然支持区间操作：结合延迟标记（如区间翻转），之后文艺平衡树会讲到。
高效稳定：所有操作严格 O(\log n)。
数据结构的定义与初始化：
struct node
{
int val, rnk, lc, rc, size; // 值、优先级、左右子节点、子树的大小
}tree[N];
int tot, root; // 总节点数与根节点
功能：储存树的信息。
结点的管理
void update(int k)
{
tree[k].size = tree[tree[k].lc].size + tree[tree[k].rc].size + 1;
return ;
}
int add_node(int val)
{
tree[++tot].size = 1;
tree[tot].val = val;
tree[tot].lc = tree[tot].rc = 0;
tree[tot].rnk = rand(); //Treap 的基本策略，随机优先级
return tot; //返还对应的结点编号
}
功能：
update：统计子树大小，左儿子子树大小+右儿子子树大小+自己。
add_node：新建节点并初始化结点信息。
分裂
主要思路如图：
void split(int k, int &a, int &b, int val)
{
if(k == 0) // 结点不存在
{
a = b = 0;
return ;
}
if(tree[k].val <= val) // 按值分裂，以 k 为根的子树
{
a = k;
split(tree[k].rc, tree[k].rc, b, val); // 继续分裂以 k 的右儿子为根的子树，分成 k 的右儿子本身与 b 树
}
else
{
b = k;
split(tree[k].lc, a, tree[k].lc, val);
}
update(k);
return ;
}
功能：给定一棵平衡树 k，按照某个权值 val，分裂成平衡树 a 和 b，且 a 树所有点的权值不超过 val，b 树的所有点权大于 val。
合并
主要思路如图：
void merge(int &k, int a, int b)
{
if(a == 0 || b == 0)
{
k = a + b;
return ;
}
if(tree[a].rnk < tree[b].rnk) // a 的优先级更高，a 做根结点，且 a 的右孩子与 b 竞争成为 a 的右孩子
{
k = a;
merge(tree[a].rc, tree[a].rc, b);
}
else
{
k = b;
merge(tree[b].lc, a, tree[b].lc);
}
update(k);
return ;
}
功能：将两棵平衡树 a 和 b 合并成一棵平衡树 k，且保证 a 树的点权都小于 b 树的点权。
插入
void insert(int &k, int val)
{
int a = 0, b = 0, cur = add_node(val);
split(k, a, b, val);
merge(a, a, cur);
merge(k, a, b);
return ;
}
void del(int &k, int val)
{
int a = 0, b = 0, z = 0;
split(k, a, b, val); // 先把比 val 大的子树划出去
split(a, a, z, val - 1); // 把值为 val 的节点分裂出来，成为 z 树
merge(z, tree[z].lc, tree[z].rc); // 将待删除的 z 节点的左右子树合并，取代 z 的位置
merge(a, a, z);
merge(k, a, b);
return ;
}
功能：
insert：插入新值 val，通过分裂找到位置后合并。
del：删除值为 val 的节点，处理重复值情况。
查询
int find_num(int k, int x)
{
while(tree[tree[k].lc].size + 1 != x)
{
if(tree[tree[k].lc].size >= x)
k = tree[k].lc;
else
{
x -= tree[tree[k].lc].size + 1;
k = tree[k].rc;
}
}
return tree[k].val;
}
int find_rank(int &k, int val)
{
int a = 0, b = 0;
split(k, a, b, val - 1); // 分裂出 int tmp = tree[a].size + 1; merge(k, a, b); return tmp; } int prev(int &k, int val) { int a = 0, b = 0; split(k, a, b, val - 1); int tmp = find_num(a, tree[a].size); // a树的最大值即前驱 merge(k, a, b); return tmp; } int suf(int &k, int val) { int a = 0, b = 0; split(k, a, b, val); int tmp = find_num(b, 1); // b树的最小值即后继 merge(k, a, b); return tmp; } 功能： find_num：通过遍历树结构找到第 k 小的元素。 find_rank：查询值 val 的排名（比 val 小的元素数量 + 1）。 prev 和 suf：分别通过分裂树找到前驱（比 val 小的最大元素）和后继（比 val 大的最小元素）。 文艺平衡树 什么是文艺平衡树？ 定义：文艺平衡树泛指支持区间操作的平衡树，例如： 区间翻转：将指定区间内的元素逆序。 区间求和/最值：快速查询区间内的统计值。 区间赋值：批量修改区间内的元素。 核心需求：在维持平衡树性质的同时，高效处理区间操作，时间复杂度需保持在 O(\log n)。 FHQ-Treap 的文艺平衡树实现 懒惰标记：说起区间操作，相比读者会想起经典的线段树，那线段树在某些方面的核心操作就是懒惰标记（Lazy Tag）。 原理：将区间操作的修改暂时记录在结点标记中，仅在必要时（如查询或进一步分裂）下传给子结点。 示例：区间翻转。 void pushdown(int k) { if (tree[k].rev) { swap(tree[k].lc, tree[k].rc); // 交换左右子节点 tree[tree[k].lc].rev ^= 1; // 下传标记到左子树 tree[tree[k].rc].rev ^= 1; // 下传标记到右子树 tree[k].rev = 0; // 清除当前节点的标记 } return ; } 区间操作 分裂提取区间：通过两次split分离出目标区间。 应用标记：在区间根节点上设置标记（如 rev ^= 1）。 合并还原树：将处理后的子树合并回原树。 示例：区间翻转。 void reverse(int l, int r) { int a, b, c; // 分割出前 l - 1 个节点 a 和剩余部分 b + c split(root, a, b, l - 1); // 从剩余部分分割出 r - l + 1 个节点 b 和剩余部分 c split(b, b, c, r - l + 1); tree[b].rev ^= 1; // 标记翻转 merge(a, a, b); // 合并 a 和翻转后的 b merge(root, a, c); // 合并得到最终树 return ; } 完整代码示例 P3369 【模板】普通平衡树 #include using namespace std; const int N = 1e6 + 5; const int INF = 0x3f3f3f3f; struct node { int val, rnk, lc, rc, size; }tree[N]; int n, tot, root; void update(int k) { tree[k].size = tree[tree[k].lc].size + tree[tree[k].rc].size + 1; return ; } int add_node(int val) { tree[++tot].size = 1; tree[tot].val = val; tree[tot].lc = tree[tot].rc = 0; tree[tot].rnk = rand(); return tot; } void split(int k, int &a, int &b, int val) { if (k == 0) { a = b = 0; return ; } if (tree[k].val <= val) { a = k; split(tree[k].rc, tree[k].rc, b, val); } else { b = k; split(tree[k].lc, a, tree[k].lc, val); } update(k); return ; } void merge(int &k, int a, int b) { if (a == 0 || b == 0) { k = a + b; return ; } if (tree[a].rnk < tree[b].rnk) { k = a; merge(tree[a].rc, tree[a].rc, b); } else { k = b; merge(tree[b].lc, a, tree[b].lc); } update(k); return ; } void insert(int &k, int val) { int a = 0, b = 0, cur = add_node(val); split(k, a, b, val); merge(a, a, cur); merge(k, a, b); return ; } void del(int &k, int val) { int a = 0, b = 0, z = 0; split(k, a, b, val); split(a, a, z, val - 1); merge(z, tree[z].lc, tree[z].rc); merge(a, a, z); merge(k, a, b); return ; } int find_num(int k, int x) { while (tree[tree[k].lc].size + 1 != x) { if (tree[tree[k].lc].size >= x) k = tree[k].lc; else { x -= tree[tree[k].lc].size + 1; k = tree[k].rc; } } return tree[k].val; } int find_rank(int &k, int val) { int a = 0, b = 0; split(k, a, b, val - 1); int tmp = tree[a].size + 1; merge(k, a, b); return tmp; } int prev(int &k, int val) { int a = 0, b = 0; split(k, a, b, val - 1); int tmp = find_num(a, tree[a].size); merge(k, a, b); return tmp; } int suf(int &k, int val) { int a = 0, b = 0; split(k, a, b, val); int tmp = find_num(b, 1); merge(k, a, b); return tmp; } int main() { cin >> n; root = 0; srand(time(0)); for (int i = 1; i <= n; i++) { int op, val; cin >> op >> val; if (op == 1) insert(root, val); else if (op == 2) del(root, val); else if (op == 3) cout << find_rank(root, val) << "\n"; else if (op == 4) cout << find_num(root, val) << "\n"; else if (op == 5) cout << prev(root, val) << "\n"; else cout << suf(root, val) << "\n"; } return 0; } P3391 【模板】文艺平衡树 #include using namespace std; const int N = 1e5 + 5; struct node { int val, rnk, lc, rc, size; bool rev; }tree[N]; int n, m, root, tot; void update(int k) { tree[k].size = tree[tree[k].lc].size + tree[tree[k].rc].size + 1; return ; } void pushdown(int k) { if (tree[k].rev) { swap(tree[k].lc, tree[k].rc); tree[tree[k].lc].rev ^= 1; tree[tree[k].rc].rev ^= 1; tree[k].rev = 0; } return ; } int add_node(int val) { tree[++tot].size = 1; tree[tot].val = val; tree[tot].lc = tree[tot].rc = 0; tree[tot].rnk = rand(); tree[tot].rev = 0; return tot; } void split(int k, int &a, int &b, int sz) { if (k == 0) { a = b = 0; return; } pushdown(k); if (tree[tree[k].lc].size + 1 <= sz) { a = k; split(tree[k].rc, tree[k].rc, b, sz - tree[tree[k].lc].size - 1); } else { b = k; split(tree[k].lc, a, tree[k].lc, sz); } update(k); return ; } void merge(int &k, int a, int b) { if (a == 0 || b == 0) { k = a + b; return; } if (tree[a].rnk < tree[b].rnk) { pushdown(a); k = a; merge(tree[a].rc, tree[a].rc, b); } else { pushdown(b); k = b; merge(tree[b].lc, a, tree[b].lc); } update(k); return ; } void insert(int &k, int val) { int a = 0, b = 0, cur = add_node(val); split(k, a, b, val); merge(a, a, cur); merge(k, a, b); return ; } void reverse(int l, int r) { int a = 0, b = 0, c = 0; split(root, a, b, l - 1); split(b, b, c, r - l + 1); tree[b].rev ^= 1; merge(a, a, b); merge(root, a, c); return ; } void print(int k) { if (k == 0) return; pushdown(k); print(tree[k].lc); cout << tree[k].val << " "; print(tree[k].rc); return ; } int main() { cin >> n >> m; root = 0; srand(time(0)); for (int i = 1; i <= n; i++) insert(root, i); for (int i = 1; i <= m; i++) { int l, r; cin >> l >> r; reverse(l, r); } print(root); return 0; } 练习 P1486 [NOI2004] 郁闷的出纳员 P2234 [HNOI2002] 营业额统计 P3224 [HNOI2012] 永无乡 P3850 [TJOI2007] 书架 P3765 总统选举 P5217 贫穷