问题描述:
写一种数据结构（可参考题目标题）维护一些数，需要提供以下操作：
1.插入问题 x ;
2.删除数字 x （若有多个相同的数，只删除一个）；
3.查询数字.的排名（排名定义为比当前数小的数的个数加 1）；
4.查询排名为 k 的数，即第 k 大问题；
5.求的前驱（前驱定义为小于 x 且最大的数）；
6.求工的后继（后继定义为大于 x 且最小的数）。
| 输入样例 | 输出样例 |
| 10 1 106465 4 1 1 317721 1 460929 1 644985 1 84185 1 89851 6 81968 1 492737 5 493598 | 106465 84185 492737 |
替罪羊树
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
const double alpha = 0.75; //不平衡率。一般用alpha来表示
struct Node{
int ls,rs; //左右儿子
int val; //结点存的数字
int tot; //当前子树占用的空间数量，包括实际存储的结点和被标记删去的点
int size; //子树上实际存储数字的数量
int del; //=1表示这个结点存有数字，=0表示这个点存的数字被删了
}t[N];
int order[N],cnt; //order[]记录拍扁后的结果，即那些存有数字的结点。cnt是数量
int tree_stack[N],top = 0; //用一个栈来回收和分配可用的结点
int root = 0; //根结点，注意重建过程中根结点会变化
void inorder(int u){ //中序遍历，“拍平”摧毁这棵子树
if(!u) return; //已经到达叶子，退出
inorder(t[u].ls); //先遍历左子树
if(t[u].del) order[++cnt] = u; //如果该结点存有数字，读取它
else tree_stack[++top] = u; //回收该结点，等待重新分配使用
inorder(t[u].rs); //再遍历右子树
}
void Initnode(int u){ //重置结点的参数
t[u].ls = t[u].rs = 0;
t[u].size = t[u].tot = t[u].del = 1;
}
void Update(int u){
t[u].size = t[t[u].ls].size + t[t[u].rs].size + 1;
t[u].tot = t[t[u].ls].tot + t[t[u].rs].tot + 1;
}
//int rebuild_num=0; //测试：统计重建次数
void build(int l,int r,int &u){ //把拍扁的子树拎起来，重建
// rebuild_num++; //测试：统计重建次数
int mid = (l + r) >> 1; //新的根设为中点，使重构出的树尽量平衡
u = order[mid];
if(l == r){Initnode(u); return;} //如果是叶子，重置后返回
if(l < mid) build(l,mid - 1,t[u].ls); //重构左子树
if(l == mid) t[u].ls = 0; //注意这里，不要漏了
build(mid + 1,r,t[u].rs); //重构右子树
Update(u); //更新
}
void rebuild(int &u){ //重建。注意是&u
cnt = 0;
inorder(u); //先拍平摧毁
if(cnt) build(1,cnt,u); //再拎起，重建树
else u = 0; //特判该子树为空的情况
}
bool notbalance(int u){ //判断子树u是否平衡
if((double)t[u].size*alpha <=(double)max(t[t[u].ls].size,t[t[u].rs].size)) //元素数量 * 不平衡率 <= 左子树数量与右子树数量
return true; //不平衡了
return false; //还是平衡的
}
void Insert(int &u,int x){ //插入数字x。注意是&u，传回了新的u，最后
if(!u){ //如果结点u为空，直接将x插到这里
u = tree_stack[top--]; //从栈顶拿出可用的空结点
t[u].val = x; //结点赋值
Initnode(u); //其他参数初始化
return;
}
t[u].size++;
t[u].tot++;
if(t[u].val >= x) Insert(t[u].ls,x); //递归插到左子树
else Insert(t[u].rs,x); //递归插到右子树
if(notbalance(u)) rebuild(u); //如果不平衡了，重建这棵子树
}
int Rank(int u,int x){ //排名，x是第几名
if(u==0) return 0; //根节点返回
if(x>t[u].val) return t[t[u].ls].size+ t[u].del + Rank(t[u].rs, x); //左子树+当前节点+递归右子树
return Rank(t[u].ls,x); //递归左子树
}
int kth(int k){ //第k大数是几?
int u = root;
while(u){ //当前节点的“键值”
if(t[u].del && t[t[u].ls].size + 1 == k) return t[u].val;
else if(t[t[u].ls].size >= k) u = t[u].ls; //在左子树
else{
k -= t[t[u].ls].size + t[u].del; //在右子树
u = t[u].rs;
}
}
return t[u].val;
}
void Del_k(int &u,int k){ //删除排名为k的数
t[u].size--; //要删除的数肯定在这棵子树中，size减1
if(t[u].del && t[t[u].ls].size + 1 == k){
t[u].del = 0; //del=0表示这个点u被删除了，但是还保留位置
return;
}
if(t[t[u].ls].size + t[u].del >= k) Del_k(t[u].ls,k); //在左子树上
else Del_k(t[u].rs,k - t[t[u].ls].size - t[u].del); //在右子树上
}
void Del(int x){ //删除值为k的数
Del_k(root,Rank(root,x)+1); //先找x的排名，然后用Del_k()删除
if(t[root].tot * alpha >= t[root].size)
rebuild(root); //如果子树上被删除的结点太多，就重构
}
/*
void print_tree(int u){ //测试：打印二叉树，观察
if(u){
cout<<"v="<<t[u].val<<",l="<<t[u].ls<<",r="<<t[u].rs<<endl;
print_tree(t[u].ls);
print_tree(t[u].rs);
}
}
int tree_deep[N]={0},deep_timer=0,max_deep=0; //测试
void cnt_deep(int u){ //测试：计算二叉树的深度
if(u){
tree_deep[u]=++deep_timer; //结点u的深度
max_deep = max(max_deep,tree_deep[u]); //记录曾经的最大深度
cnt_deep(t[u].ls);
cnt_deep(t[u].rs);
deep_timer--;
}
} */
int main(){
for(int i=N-1;i>=1;i--) tree_stack[++top] = i; //把所有可用的t[]记录在这个栈里面
int q; cin>>q;
//rebuild_num = 0;deep_timer=0;max_deep=0; //测试
while(q--){
int opt,x; cin >> opt >> x;
switch (opt){
case 1: Insert(root,x); break;
case 2: Del(x); break;
case 3: printf("%d\n",Rank(root,x)+1); break;
case 4: printf("%d\n",kth(x)); break;
case 5: printf("%d\n",kth(Rank(root,x))); break;
case 6: printf("%d\n",kth(Rank(root,x+1)+1)); break; //Rank()函数里查找使用的是小于号x+1是避免x在平衡树里
}
// cout<<">>"<<endl;print_tree(root);cout<<endl<<"<<"<<endl; //测试：打印二叉树
// cnt_deep(root); //测试：计算曾经的最大深度
}
//cout<<"rebuild num="<<rebuild_num<<endl; //测试：打印重建次数
//cout<<"deep="<<max_deep<<endl; //测试：打印替罪羊树的最大深度
return 0;
}
笔记：替罪羊树的意思就是一个结点的变化可能导致子树摧毁重建，这颗子树就是“替罪羊”。二叉树平衡不一定非要绝对平衡，这时候“差不多平衡的树”会减少很大的计算量，不平衡率(alpha)就是判断一棵树平衡的标准。平衡率趋近于1树的深度也会增加计算量，所以一般来说不平衡率设置0.7左右。中序遍历可以获得有序排列，插入数值的时候，通过“键值”来比较大小后插入到合适的位置上。如果树超过不平衡率先摧毁并储存节点值，再重建二叉树。删除节点为了减少计算量是删除标记，但是保留位置。查找数值比较简单，直接比较当前节点再左子树或者右子树的查找
基于旋转法的Treap操作
#include<bits/stdc++.h>
using namespace std;
const int M=1e6+10;
int cnt = 0; //t[cnt]: 最新结点的存储位置
struct Node{
int ls,rs; //左右儿子
int key,pri; // key：键值；pri：随机的优先级
int size; //当前结点为根的子树的结点数量，用于求第k大和rank
}t[M]; //tree[]，存树
void newNode(int x){ //初始化一个新结点
cnt++; //从t[1]开始存储结点，t[0]被放弃。若子结点是0，表示没有子结点
t[cnt].size = 1;
t[cnt].ls = t[cnt].rs = 0; //0表示没有子结点
t[cnt].key = x; //key: 键值
t[cnt].pri = rand(); //pri：随机产生，优先级
}
void Update(int u){ //更新以u为根的子树的size
t[u].size = t[t[u].ls].size + t[t[u].rs].size+1;
}
void rotate(int &o,int d){ //旋转 d=0右旋，d=1左旋
int k;
if(d==1) { //左旋，把o的右儿子k旋到根部
k=t[o].rs;
t[o].rs=t[k].ls;
t[k].ls=o;
}
else { //右旋，把o的左儿子k旋到根部
k=t[o].ls;
t[o].ls=t[k].rs;
t[k].rs=o;
}
t[k].size=t[o].size;
Update(o);
o=k; //新的根是k
}
void Insert(int &u,int x){
if(u==0){newNode(x);u=cnt;return;} //递归到了一个空叶子，新建结点
t[u].size++;
if(x>=t[u].key) Insert(t[u].rs,x); //递归右子树找空叶子，直到插入
else Insert(t[u].ls,x); //递归左子树找空叶子，直到插入
if(t[u].ls!=0 && t[u].pri>t[t[u].ls].pri) rotate(u,0); //优先级比父节点高，旋转法
if(t[u].rs!=0 && t[u].pri>t[t[u].rs].pri) rotate(u,1);
Update(u);
}
void Del(int &u,int x){
t[u].size--;
if(t[u].key==x){
if(t[u].ls==0&&t[u].rs==0){u=0; return;} //左右儿子都空
if(t[u].ls==0||t[u].rs==0){u=t[u].ls+t[u].rs; return;} //左右儿子有一个空
if(t[t[u].ls].pri < t[t[u].rs].pri) //左儿子优先级高
{ rotate(u,0); Del(t[u].rs, x); return;}
else{ rotate(u,1); Del(t[u].ls, x); return;}
}
if(t[u].key>=x) Del(t[u].ls,x); //递归查找
else Del(t[u].rs,x);
Update(u);
}
int Rank(int u,int x){ //排名，x是第几名
if(u==0) return 0;
if(x>t[u].key) return t[t[u].ls].size+1+Rank(t[u].rs, x); //递归右子树累加上左子树节点数量
return Rank(t[u].ls,x);
}
int kth(int u,int k){ //第k大数是几?
if(k==t[t[u].ls].size+1) return t[u].key; //这个数为根
if(k> t[t[u].ls].size+1) return kth(t[u].rs,k-t[t[u].ls].size-1);//右子树
if(k<=t[t[u].ls].size) kth(t[u].ls,k); //左子树
}
int Precursor(int u,int x){
if(u==0) return 0;
if(t[u].key>=x) return Precursor(t[u].ls,x); //先递归左子树慢慢靠近x
int tmp = Precursor(t[u].rs,x); //再递归右子树接近x
if(tmp==0) return t[u].key; //子树空节点返回
return tmp;
}
int Successor(int u,int x){ //逻辑同Precursor()
if(u==0) return 0;
if(t[u].key<=x) return Successor(t[u].rs,x);
int tmp = Successor(t[u].ls,x);
if(tmp==0) return t[u].key;
return tmp;
}
int main(){
srand(time(NULL)); //随机种子
int root = 0; //root是整棵树的树根，0表示初始为空
int n; cin>>n;
while(n--){
int opt,x; cin >> opt >> x;
switch (opt){
case 1: Insert(root,x); break;
case 2: Del(root,x); break;
case 3: printf("%d\n",Rank(root,x)+1); break;
case 4: printf("%d\n",kth(root,x)); break;
case 5: printf("%d\n",Precursor(root,x)); break;
case 6: printf("%d\n",Successor(root,x)); break;
}
}
return 0;
}
笔记：“Treap树的形态唯一性”是因为所有的节点键值与优先值确定的情况下，树的形态是确定下来只有一种的。程序里的优先级是随机筛选出来的，题目本意是不需要的，为了讲解Treap树加上的，插入节点如果优先级比父节点高会通过左旋或者右旋来更改树的形态，但是中序遍历后的结果不会改变。删除节点需要将节点左旋右旋到叶子上再删除
FHQ的基本操作
#include<bits/stdc++.h>
using namespace std;
const int M=1e6+10;
int cnt=0, root=0; //t[cnt]: 最新结点的存储位置；root:整棵树的根，用于访问树
struct Node{
int ls,rs; //左儿子lson，右儿子rson
int key,pri; //key：键值，pri：随机的优先级
int size; //当前结点为根的子树的结点数量，用于求第k大和rank
}t[M]; //tree[],存树
void newNode(int x){ //建立只有一个点的树
cnt++; //从t[1]开始存储结点，t[0]被放弃
t[cnt].size = 1;
t[cnt].ls = t[cnt].rs = 0; //0表示没有子结点
t[cnt].key = x; //key: 键值
t[cnt].pri = rand(); //pri：随机产生，优先级
}
void Update(int u){ //更新以u为根的子树的size
t[u].size = t[t[u].ls].size + t[t[u].rs].size+1;
}
void Split(int u,int x,int &L,int &R) { //权值分裂。返回以L和R为根的2棵树
if(u == 0){L = R = 0; return;} //到达叶子，递归返回
if(t[u].key <= x){ //本结点比x小，那么到右子树上找x
L = u; //左树的根是本结点
Split(t[u].rs, x, t[u].rs, R); //通过rs传回新的子结点
}
else{ //本结点比x大，继续到左子树找x
R = u; //右数的根是本结点
Split(t[u].ls,x,L,t[u].ls);
}
Update(u); //更新当前结点的size
}
int Merge(int L,int R){ //合并以L和R为根的两棵树，返回一棵树的根
if(L==0 || R==0) return L+R; //到达叶子。若L==0，就是返回L+R=R
if(t[L].pri > t[R].pri){ //左树L优先级大于右树R，则L节点是父结点
t[L].rs = Merge(t[L].rs,R); //合并R和L的右儿子,并更新L的右儿子
Update(L);
return L; //合并后的根是L
}
else{ //合并后R是父结点
t[R].ls = Merge(L,t[R].ls); //合并L和R的左儿子,并更新R的左儿子
Update(R);
return R; //合并后的根是R
}
}
int Insert(int x){ //插入数字x
int L,R;
Split(root,x,L,R);
newNode(x); //新建一棵只有一个点的树t[cnt]
int aa = Merge(L,cnt);
root = Merge(aa,R);
}
int Del(int x){ //删除数字x。
int L,R,p;
Split(root,x,L,R); //<=x的树和>x的树
Split(L,x-1,L,p); //<x的树和==x的树
p = Merge(t[p].ls,t[p].rs); //合并x=p的左右子树，也就是删除了x
root = Merge(Merge(L,p),R);
}
void Rank(int x){ //查询数x的排名
int L,R;
Split(root,x-1,L,R); //<x的树和>=x的树
printf("%d\n",t[L].size+1);
root = Merge(L,R); //恢复
}
int kth(int u,int k){ //求排名第k的数
if(k==t[t[u].ls].size+1) return u; //这个数为根
if(k<=t[t[u].ls].size) return kth(t[u].ls,k); //在左子树
if(k>t[t[u].ls].size) return kth(t[u].rs,k-t[t[u].ls].size-1); //在右子树
}
void Precursor(int x){ //求x的前驱
int L,R;
Split(root,x-1,L,R);
printf("%d\n",t[kth(L,t[L].size)].key);
root = Merge(L,R); //恢复
}
void Successor(int x){ //求x的后继
int L,R;
Split(root,x,L,R); //<=x的树和>x的树
printf("%d\n",t[kth(R,1)].key);
root = Merge(L,R); //恢复
}
int main(){
srand(time(NULL));
int n; cin >> n;
while(n--){
int opt,x; cin >> opt >> x;
switch (opt){
case 1: Insert(x); break;
case 2: Del(x); break;
case 3: Rank(x); break;
case 4: printf("%d\n",t[kth(root,x)].key); break; //排名x的结点
case 5: Precursor(x); break;
case 6: Successor(x); break;
}
}
return 0;
}
笔记：FHQ Treap的基本操作是分裂与合并两个步骤，按照新节点x节点分为L和R两棵树，L树的节点都小于等于x，R树的节点都大于x，先合并x到L树中，再合并L与R两颗树按照优先级合并。删除节点也是先分裂出x，再合并。注：洛谷运行需要取消【开启 O2 优化】