一.定义
伸展树（Splay Tree）是一种自调整二叉搜索树，它通过不断进行伸展（splay）操作，将最近访问的节点移动到树的根节点，以提高对这些节点的访问效率。伸展树的主要特点是在插入、查找和删除操作时，都会执行伸展操作，使得最近访问的节点位于根节点，从而实现了一种局部性原理，即频繁访问的节点更容易被快速访问。
伸展树的基本伸展操作有三种：
-
伸展到根（Splay to Root）：将某个节点x伸展到树的根节点，通过一系列旋转操作实现，使得x成为新的根节点。
-
伸展到左子树的最右节点（Splay to Right Child's Leftmost Descendant）：将某个节点x伸展到其左子树的最右节点，同样通过一系列旋转操作实现。
-
伸展到右子树的最左节点（Splay to Left Child's Rightmost Descendant）：将某个节点x伸展到其右子树的最左节点，同样通过一系列旋转操作实现。
伸展树的操作包括插入、查找和删除。在每次操作之后，都会对相关的节点进行伸展，以保持树的平衡性和局部性原理。这种自调整性质使得伸展树在一般情况下表现出良好的性能，但最坏情况下的性能可能较差，因为它不保证平衡。
总之，伸展树是一种简单而有效的自平衡二叉搜索树，适用于需要频繁访问最近使用节点的场景。在实际应用中，可以根据具体需求选择合适的自平衡数据结构，如AVL树、红黑树等。
二.数据存储方式 && main函数
struct node{int val,cnt; //它的值 ,值有几个 int fa,son[2]; // 它的father和它的两个sonint siz; //它的子树个数 （即<=它的数有几个）
}tree[maxn];int main(){insert(-2147483647);insert(+2147483647);scanf("%d",&n);int ops,x;for(int i=1;i<=n;i++){scanf("%d%d",&ops,&x);if(ops==1) insert(x);else if(ops==2) del(x);else if(ops==3) Find(x),printf("%d\n",tree[tree[root].son[0]].siz);else if(ops==4) printf("%d\n",kth(x+1));else if(ops==5) printf("%d\n",tree[pre(x)].val);else printf("%d\n",tree[nxt(x)].val);}return 0;
}三. insert
void insert(int x){int u=root,fa=0;while(u && tree[u].val!=x){fa=u;u=tree[u].son[x>tree[u].val];}//已经有这个数字 if(u){tree[u].cnt++;}else{u=++cnt;if(fa){tree[fa].son[x>tree[fa].val]=u;}tree[u].fa=fa;tree[u].son[0]=tree[u].son[1]=0;tree[u].val=x;tree[u].cnt=tree[u].siz=1;} splay(u,0);
}四.splay
- 若共线要先转一下父节点，再转x
- 不共线，转两下x即可
- 重复上面操作，直到到达目标
void splay(int x,int goal){while(tree[x].fa!=goal){int fa=tree[x].fa,gfa=tree[fa].fa;if(gfa!=goal){//同ture意思是都为左孩子,异或为0；同false都为右孩子，异或为0 ((tree[fa].son[0]==x)^(tree[gfa].son[0]==fa))==0 ? rotate(fa) : rotate(x);} rotate(x);}if(goal==0) root=x; }
五.rotate
注意：这边使用了异或和判断孩子的功能，固左转和右转通用
void updata(int x){tree[x].siz=tree[ tree[x].son[0] ].siz+tree[ tree[x].son[1] ].siz+tree[x].cnt;
}
void rotate(int x){//预处理 int fa=tree[x].fa,gfa=tree[fa].fa;int k=(tree[fa].son[1]==x); //左右孩子 //继承fa为gfa的孩子tree[gfa].son[ tree[gfa].son[1]==fa ] = x;tree[x].fa=gfa;//调整fa的son，即找人代替x为fa的k儿子 tree[fa].son[k]=tree[x].son[k^1];tree[ tree[x].son[k^1] ].fa = fa;//风水轮流转，爸爸成儿子tree[x].son[k^1]=fa;tree[fa].fa=x; //fa和x子树有变动，要更新 updata(fa);updata(x);
}六.前驱后继
int pre(int x){Find(x);if(tree[root].val<x) return root; //特判//左子树中找最右的点int u=tree[root].son[0];while(tree[u].son[1]) u=tree[u].son[1];return u;
}
int nxt(int x){Find(x);if(tree[root].val>x) return root; //特判 //右子树中找最左的点int u=tree[root].son[1];while(tree[u].son[0]) u=tree[u].son[0];return u;
}七.delete
void del(int x){int p=pre(x),s=nxt(x);splay(p,0);splay(s,p);int del=tree[s].son[0];if(tree[del].cnt>1){tree[del].cnt--;//存在多个这个数字，直接减去一个 splay(del,0);}else{tree[s].son[0]=0;//清除掉节点 }
}八.查排名
int kth(int x){int u=root;if(tree[u].siz<x) return false;while(1){int y=tree[u].son[0];if(x>tree[y].siz+tree[u].cnt){ //排在u的后面 x-=tree[y].siz+tree[u].cnt;u=tree[u].son[1];}else if(tree[y].siz>=x){ //在u的前面 u=y;}else{return tree[u].val;}}
}九.查排第几
将其变成根，看看左子树有多少个即可
十.AC代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n;
int root,cnt;
struct node{int val,cnt; //它的值 ,值有几个 int fa,son[2]; // 它的father和它的两个sonint siz; //它的子树个数 （即<=它的数有几个）
}tree[maxn];
void updata(int x){tree[x].siz=tree[ tree[x].son[0] ].siz+tree[ tree[x].son[1] ].siz+tree[x].cnt;
}
void rotate(int x){//预处理 int fa=tree[x].fa,gfa=tree[fa].fa;int k=(tree[fa].son[1]==x); //左右孩子 //继承fa为gfa的孩子tree[gfa].son[ tree[gfa].son[1]==fa ] = x;tree[x].fa=gfa;//调整fa的son，即找人代替x为fa的k儿子 tree[fa].son[k]=tree[x].son[k^1];tree[ tree[x].son[k^1] ].fa = fa;//风水轮流转，爸爸成儿子tree[x].son[k^1]=fa;tree[fa].fa=x; //fa和x子树有变动，要更新 updata(fa);updata(x);
}
void splay(int x,int goal){while(tree[x].fa!=goal){int fa=tree[x].fa,gfa=tree[fa].fa;if(gfa!=goal){//同ture意思是都为左孩子,异或为0；同false都为右孩子，异或为0 ((tree[fa].son[0]==x)^(tree[gfa].son[0]==fa))==0 ? rotate(fa) : rotate(x);} rotate(x);}if(goal==0) root=x;
}
void insert(int x){int u=root,fa=0;while(u && tree[u].val!=x){fa=u;u=tree[u].son[x>tree[u].val];}//已经有这个数字 if(u){tree[u].cnt++;}else{u=++cnt;if(fa){tree[fa].son[x>tree[fa].val]=u;}tree[u].fa=fa;tree[u].son[0]=tree[u].son[1]=0;tree[u].val=x;tree[u].cnt=tree[u].siz=1;} splay(u,0);
}
void Find(int x){int u=root;if(!u) return;//若x不存在，则u一定有误差，但在pre or nxt函数中已经特判了 while(tree[u].son[x>tree[u].val] && x!=tree[u].val){u=tree[u].son[x>tree[u].val];}splay(u,0);
}
int pre(int x){Find(x);if(tree[root].val<x) return root; //特判//左子树中找最右的点int u=tree[root].son[0];while(tree[u].son[1]) u=tree[u].son[1];return u;
}
int nxt(int x){Find(x);if(tree[root].val>x) return root; //特判 //右子树中找最左的点int u=tree[root].son[1];while(tree[u].son[0]) u=tree[u].son[0];return u;
}
void del(int x){int p=pre(x),s=nxt(x);splay(p,0);splay(s,p);int del=tree[s].son[0];if(tree[del].cnt>1){tree[del].cnt--;//存在多个这个数字，直接减去一个 splay(del,0);}else{tree[s].son[0]=0;//清除掉节点 }
}
int kth(int x){int u=root;if(tree[u].siz<x) return false;while(1){int y=tree[u].son[0];if(x>tree[y].siz+tree[u].cnt){ //排在u的后面 x-=tree[y].siz+tree[u].cnt;u=tree[u].son[1];}else if(tree[y].siz>=x){ //在u的前面 u=y;}else{return tree[u].val;}}
}
int main(){insert(-2147483647);insert(+2147483647);scanf("%d",&n);int ops,x;for(int i=1;i<=n;i++){scanf("%d%d",&ops,&x);if(ops==1) insert(x);else if(ops==2) del(x);else if(ops==3) Find(x),printf("%d\n",tree[tree[root].son[0]].siz);else if(ops==4) printf("%d\n",kth(x+1));else if(ops==5) printf("%d\n",tree[pre(x)].val);else printf("%d\n",tree[nxt(x)].val);}return 0;
}
