题解 | 普通平衡树
题干分析
题设要求我们动态维护一个有序数据结构，并进行若干次6种操作。
算法思路
本题有两种解决思路，一种是放弃使用树状结构，直接使用STL库提供的二分查找算法与vector容器实现。
另一种思路是维护树状的二叉查找树进行实现，同时为了提高查找效率，我们得防止我们构建的树过于不平衡，也就是说我们需要动态维护一个平衡二叉搜索树。这里个人做法是实现一颗替罪羊树，设定一个不平衡率，只要子树达到该不平衡率我们就直接重建一颗相对平衡的子树。同时针对删除，我们采取懒删除方式标记删除节点，当树发生重建时再真正删除。
实现代码
- 使用STL库+vector容器实现：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
vector<int> v;
int n; cin >> n;
for (int i = 0; i < n; ++i) {
int op, x;
cin >> op >> x;
switch (op) {
case 1:
v.insert(ranges::lower_bound(v, x), x);
break;
case 2:
v.erase(ranges::lower_bound(v, x));
break;
case 3:
cout << ranges::lower_bound(v, x) - v.begin() + 1 << endl;
break;
case 4:
cout << v[x - 1] << endl;
break;
case 5:
cout << v[ranges::lower_bound(v, x) - v.begin() - 1] << endl;
break;
case 6:
cout << v[ranges::upper_bound(v, x) - v.begin()] << endl;
break;
default: ;
}
}
return 0;
}//*/
- 维护替罪羊树的实现：
#include <bits/stdc++.h>
using namespace std;
// 替罪羊树
class ScapegoatTree {
const int N; // 最高节点数
const double alpha; // 不平衡率
struct Node {
int leftSon, rightSon; // 记录下标，为0表示空
int val;
int total; // 当前子树占用空间数量，包括懒删除节点
int size; // 子树实际存在节点数
bool del; // 删除标记
};
vector<Node> t; // 扁平存储
vector<int> order; // 记录子树销毁后的节点大小顺序(下标)
int cnt = 0; // 销毁子树的节点数
stack<int> treeStack; // 使用栈回收和分配可用节点（下标）
int root = 0; // 根节点(下标)
// 中序遍历摧毁子树
void inOrder(const int cur) {
if (cur) {
inOrder(t[cur].leftSon);
if (t[cur].del) order[++cnt] = cur;
else treeStack.push(cur);
inOrder(t[cur].rightSon);
}
}
// 重置节点参数
void initNode(const int idx) {
t[idx].leftSon = t[idx].rightSon = 0;
t[idx].size = t[idx].total = 1;
t[idx].del = true;
}
// 更新节点大小数据
void update(const int idx) {
t[idx].size = t[t[idx].leftSon].size + t[t[idx].rightSon].size + 1;
t[idx].total = t[t[idx].leftSon].total + t[t[idx].rightSon].total + 1;
}
// 重建
void build(int left, int right, int &cur) {
int mid = (left + right) >> 1;
cur = order[mid];
// 叶子节点
if (left == right) {
initNode(cur);
return;
}
// 重构左子树
if (left < mid) build(left, mid - 1, t[cur].leftSon);
if (left == mid) t[cur].leftSon = 0; // 左子树为空
// 重构右子树
build(mid + 1, right, t[cur].rightSon);
// 更新大小
update(cur);
}
// 启动重建
void rebuild(int &tar) {
cnt = 0;
inOrder(tar);
if (cnt) build(1, cnt, tar);
else tar = 0;
}
// 判断是否平衡
[[nodiscard]] bool isUnbalance(const int tar) const {
return static_cast<double>(t[tar].size) * alpha <=
static_cast<double>(max(t[t[tar].leftSon].size, t[t[tar].rightSon].size));
}
// 插入x
void insert(int &u, const int x) {
if (!u) {
// u为空节点
u = treeStack.top();
treeStack.pop();
t[u].val = x;
initNode(u);
return;
}
t[u].size++;
t[u].total++;
if (t[u].val >= x) insert(t[u].leftSon, x); // 插左树
else insert(t[u].rightSon, x); // 插右树
if (isUnbalance(u)) rebuild(u); // 不平衡，重建子树
}
// x的排名
int rank(const int u, const int x) {
if (u == 0) return 0;
if (x > t[u].val) {
const int tmp = t[t[u].leftSon].size + (t[u].del ? 1 : 0);
return tmp + rank(t[u].rightSon, x);
}
return rank(t[u].leftSon, x);
}
// 删除排名k的数
void delK(const int &u, const int k) {
t[u].size--;
if (t[u].del && t[t[u].leftSon].size + 1 == k) {
t[u].del = false;
return;
}
// 左子树上
if (t[t[u].leftSon].size + (t[u].del ? 1 : 0) >= k) delK(t[u].leftSon, k);
// 右子树上
else delK(t[u].rightSon, k - t[t[u].leftSon].size - (t[u].del ? 1 : 0));
}
public:
explicit ScapegoatTree(const int N_ = 1e6 + 10, const double alpha_ = 0.75) : N(N_), alpha(alpha_) {
t.resize(N);
order.resize(N);
// 记录所有可用的t
for (int i = N - 1; i >= 1; --i) treeStack.push(i);
}
// 对外插入接口
void Insert(const int x) { insert(root, x); }
// 对外排名接口
int Rank(const int x) { return rank(root, x); }
// 排名第k大的数
[[nodiscard]] int kth(int k) const {
int u = root;
while (u) {
if (t[u].del && t[t[u].leftSon].size + 1 == k) return t[u].val;
if (t[t[u].leftSon].size >= k) u = t[u].leftSon;
else {
k -= t[t[u].leftSon].size + (t[u].del ? 1 : 0);
u = t[u].rightSon;
}
}
return t[u].val;
}
// 对外删除第k个元素接口
void DelK(const int k) { delK(root, k); }
// 删除值为x的数
void del(const int x) {
delK(root, rank(root, x) + 1);
// 已删除节点过多，重构整个树
if (t[root].total * alpha >= t[root].size) rebuild(root);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
ScapegoatTree tree;
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
int op, x;
cin >> op >> x;
switch (op) {
case 1:
tree.Insert(x);
break;
case 2:
tree.del(x);
break;
case 3:
cout << tree.Rank(x) + 1 << endl;
break;
case 4:
cout << tree.kth(x) << endl;
break;
case 5:
cout << tree.kth(tree.Rank(x)) << endl;
break;
case 6:
cout << tree.kth(tree.Rank(x + 1) + 1) << endl;
break;
default: ;
}
}
return 0;
}
复杂度分析
- 时间复杂度：
1类操作针对vector容器实现为，平衡树实现均摊为
2类操作针对vector容器实现也为,平衡树实现均摊为
3类操作二者均为
4类操作针对vector容器实现为,平衡树实现均摊为
5类操作二者均为
6类操作二者均为
- 空间复杂度：二者均为