贴个代码而已
不算学习笔记,以后补下平衡树的
大部分代码参照底端的图片。
#include<bits/stdc++.h>
#define ll long long
#define inf (1<<30)
using namespace std;
const int N=1e6+10;
int T;
struct Splay_Tree{
int rt,sz=0;//根节点编号 , 整棵树元素个数。
int val[N],ch[N][2],fa[N],siz[N],cnt[N];
//权值,左儿子右儿子,父亲,子树大小,节点出现次数(数出现的个数)。
void clear(int x){
ch[x][0]=ch[x][1]=siz[x]=cnt[x]=val[x]=0;
return;
}//清空,摧毁x节点。
int get(int x){
return ch[fa[x]][1]==x;
}//判断左右儿子。
void updata(int x){
if(x){
siz[x]=cnt[x];
if(ch[x][0])siz[x]+=siz[ch[x][0]];
if(ch[x][1])siz[x]+=siz[ch[x][1]];
}
return;
}//更新x节点的节点信息。
void rotate(int x){//splay操作核心。
int f=fa[x],gf=fa[f],wh=get(x);
ch[f][wh]=ch[x][wh^1];
fa[ch[f][wh]]=f;
ch[x][wh^1]=f;
fa[f]=x;
fa[x]=gf;
if(gf)ch[gf][ch[gf][1]==f]=x;
updata(f);updata(x);//重点,要更新。
}
void splay(int x){
for(int f;f=fa[x];rotate(x))
if(fa[f])rotate((get(f)==get(x))?f:x);//一直旋转至平衡(不在一条线上)。
rt=x;
return;
}
int search(int u,int x){//单纯查找x的编号。返回其id。
while(val[u]!=x){
if(val[u]>x)
if(ch[u][0])
u=ch[u][0];
else break;
if(val[u]<x)
if(ch[u][1])
u=ch[u][1];
else break;
}
return u;
}
void ins(int x){//插入数值x。
if(rt==0){//如果树为空。
sz++;
ch[sz][0]=ch[sz][1]=fa[sz]=0;
rt=sz;
siz[sz]=cnt[sz]=1;
val[sz]=x;
return;
}
int u=search(rt,x);
if(val[u]==x){//已存在此节点。
cnt[u]++;
splay(u);//旋至根。
return;
}
//新建一个节点。
val[++sz]=x;
cnt[sz]=1;
fa[sz]=u;
ch[u][x>val[u]]=sz;
splay(sz);return;
}
int rnk(int x){//查询数值为x的排名。
int u=search(rt,x);
splay(u);
if(val[u]>=x)return siz[ch[u][0]]+1;
else return siz[ch[u][0]]+cnt[u]+1;
}
int kth(int x){//查询第k小的数。
int u=rt;
while(true){
if(ch[u][0]&&x<=siz[ch[u][0]])
u=ch[u][0];
else{
int tmp=(ch[u][0]?siz[ch[u][0]]:0)+cnt[u];
if(x<=tmp)return val[u];
x-=tmp;u=ch[u][1];
}
}
}
int gmost(int u,int op){//以u为根子树的最大或最小。
if(!op)return search(u,(-inf));
else return search(u,inf);
}
int pre_nxt(int x,int op){//查找前驱或后继。
int u=search(rt,x);
splay(u);
if((val[u]<x&&!op)||(val[u]>x&&op))return u;
else return gmost(ch[u][op],op^1);
}
int pre(int x){return val[pre_nxt(x,0)];}//前驱
int nxt(int x){return val[pre_nxt(x,1)];}//后继
void del(int x){//删除x。
int u=search(rt,x);
if(val[u]!=x)return;//不存在x
splay(u);//旋至根。
if(--cnt[u])return;//如有多个只删除一个。
if(!ch[u][0]){//没有左儿子,直接以右儿子为根。
fa[ch[u][1]]=0;
rt=ch[u][1];
clear(u);
}else{//否则将左子树中最大的节点旋上来,连上右子树。
fa[ch[u][0]]=0;
splay(gmost(ch[u][0],1));
ch[rt][1]=ch[u][1];
siz[rt]+=siz[ch[u][1]];
if(ch[rt][1])fa[ch[rt][1]]=rt;
clear(u);
}
return;
}
}Tree;
int main(){
}