Splay模版:P3369[模版/普通平衡树]
于2022年3月30日2022年3月30日由Sukuna发布
题目描述
输出格式
对于操作 3,4,5,6.每行输出一个数，表示对应答案.
splay的定义
伸展树（Splay Tree），也叫分裂树，是一种二叉排序树，它能在 O(logn)内完成插入、查找和删除操作. 它由丹尼尔·斯立特Daniel Sleator 和 罗伯特·恩卓·塔扬Robert Endre Tarjan在1985年发明的.
在伸展树上的一般操作都基于伸展操作： 假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置. 于是想到设计一个简单方法： 在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方. 伸展树应运而生： 伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去. 它的优势在于不需要记录用于平衡树的冗余信息.
总的来说,伸展树在每一次增改查之后就会把被查询的元素放到根部
数据结构定义
代码语言：javascript复制struct splay{
int ch[2];
int val;//数值
int size;//子树大小
int cnt;//每个节点所含副本数
int parent;
}splay[N];
int total;
int root;这里用数组来模拟树,树的节点个数为total,根结点记录在root,那么splay[root]就是根结点,其中每个节点记录本身的值,左子树和右子树信息,每个节点含有副本数量,和这个节点对应子树的大小.
PushOff操作
在每一次对树进行操作的之后都要进行一次pushoff操作,来更新size区域.
代码语言：javascript复制void pushup(int node_id){
int l=splay[node_id].ch[0];
int r=splay[node_id].ch[1];
splay[node_id].size=splay[l].size splay[r].size splay[node_id].cnt;
}单旋转操作
每次旋转操作其实上都是将父亲和儿子进行交换,就是x和x.parent进行交换.
代码语言：javascript复制void rotate (int x) {
int fa = splay[x].parent;
int Gfa = splay[fa].parent;
int k = (splay[fa].ch[1]==x);
int g = (splay[Gfa].ch[1]==fa);
splay[Gfa].ch[g]=x;
splay[x].parent=Gfa;
splay[fa].ch[k]=splay[x].ch[k^1];
splay[splay[x].ch[k^1]].parent=fa;
splay[x].ch[k ^ 1]=fa;
splay[fa].parent=x;
pushup(fa);
pushup(x);
}交换需要借助父亲的父亲,也就是祖父的力量,首先我们先记录x是fa=x.parent左儿子还是右儿子,结果记为k(1:右儿子,0:左儿子),然后记录fa是Gfa=fa.parent的左儿子还是右儿子,计为g(1:右儿子,0:左儿子).
下面为了叙述方便,我们定义一个奇怪的定义,就是外孙,比如说x是fa的左儿子,那么x的右儿子就是fa的外孙;x是fa的右儿子,那么x的左儿子就是x的外孙.
这个时候有三个点,分别是父亲、祖父和儿子,分别代表Gfa、fa和x. 首先第一步就是祖父的儿子从fa替换成x. 第二步就是父亲的儿子从x替换成x的外孙. 第三步就是原本x的外孙的位子由fa占领.
这个是最难的一部分,还是希望还是可以记住执行的顺序,一个是替换祖父的儿子,然后替换父亲的儿子,然后替换儿子的儿子,这是替换顺序,替换成什么可以记下来,分别是儿子,父亲的外孙和父亲.
实在太难怎么办?把旋转的画法画下来带进考场,反正CSP是开卷orz.
splay操作
我们需要做到的就是增改查的节点送到根结点,那么我们可以设计一个函数,这个函数叫做splayed(x,y).目的就是把编号为x的节点送到y的儿子处.所以说用形式语言我们可以这么写
.就是x的父亲为y.
说句题外话,因为节点是从1开始编号的,所以说有且只有一个结点就是根结点的父亲为0.所以说想把数送到根结点需要执行splayed(x,0).
我们在之前还是知道rotate操作可以把一个数在树中的层数-1.这就好办,我们每次都做rorate操作,直到这个数的父亲是y为止.但是学过AVL的旋转我们知道,旋转可以分为单旋和双旋的,其实这个也是一样的.
判断究竟是一字旋转还是之字旋转其实就判断(splay[Gfa].ch[0] == fa) ^ (splay[fa].ch[0] == x).这个异或可以判断儿子情况是不是一样的.
但是有一个问题就是,我们不知道旋转能不能做,因为在rotate函数中,我们充分相信fa和Gfa都是有意义的.所以说在splay操作调用rotate时我们要保证x是有意义的.
由于旋转是两个两个来做的,首先第一步,我们判断我们能不能做两次旋转操作,然后判断我们能不能做一次操作.判断的方法在代码中有说.
代码语言：javascript复制//将x旋转到goal的儿子
void splayed ( int x, int goal ) {
while (splay[x].parent != goal) {
int fa = splay[x].parent, Gfa = splay[fa].parent;
//能做两次吗?
if (Gfa!= goal)
((splay[Gfa].ch[0] == fa) ^ (splay[fa].ch[0] == x)) ? rotate(x) : rotate (fa);
//splay[x].parent != goal 判断能做一次旋转操作吗?
rotate (x);
}
//如果goal为0,代表要改根结点
if (!goal)
root=x;
}insert操作
解决了最核心的旋转问题,我们可以专注搞增删改查了.
代码语言：javascript复制void insert(int x) {
int u=root, fa=0;
while (u && splay[u].val!=x) {
fa = u;
u=splay[u].ch[x>splay[u].val];
}
if (u)
splay[u].cnt ;
else {
u= total;
if (fa)
splay[fa].ch[x > splay[fa].val] = u;
splay[u].ch[0] = splay[u].ch[1] = 0;
splay[u].val = x;
splay[u].parent = fa;
splay[u].cnt = splay[u].size = 1;
}
splayed(u,0);
}我们注意到有一个前提,这个前提就是这个树是一个BST,也就是说我们查找可以根据BST性质来进行查找,查找的目的就是找到合适的地方来处理.
如果查找到的地方是空,说明之前没有插入过值为x的结点,如果找到了就增加引用数即可.
find操作
insert操作其实就是基于find操作执行的,也是满足BST性质,如果你忘了我就告诉你一下,小的往左,大的往右,在空和找到了的地方下停下来.
代码语言：javascript复制void find(int x){
if (!root)
return;
int u=root;
while (splay[u].ch[x > splay[u].val] && x!=splay[u].val)
u=splay[u].ch[x > splay[u].val];
splayed (u,0);
}前序和后序操作
我们首先调用find(x)函数,find(x)函数会帮我找到x并且把x放到根.我们假设x存在,那么x是根结点.那么就很好做,前序结点就是先往左然后一直往右,后序结点就是先往右然后一直往左.
但是万一x没找到呢?也不要紧,那么我们可以知道查询的结果往往是最接近x的结果,所以说我们可以假设,如果找的是前序结点并且当前根结点小于x,那就是根结点.同样的,如果要找后序结点并且根结点大于x,那就是根结点.如果不对的话,那我们还是按照x存在的方法寻找.
代码语言：javascript复制int PreSuf (int x, int f) {
find (x);
if (splay[root].val>x&&f)
return root;
if (splay[root].val < x && !f)
return root;
int u = splay[root].ch[f];
if (!u)
return 0;
while (splay[u].ch[f ^ 1])
u =splay[u].ch[f ^ 1];
return u;
}Delete操作
代码语言：javascript复制void Delete (int x) {
int pre = PreSuf(x,0);
int suf = PreSuf(x,1);
splayed(pre,0);
splayed(suf,pre);
int u = splay[suf].ch[0];
if (splay[u].cnt>1) {
splay[u].cnt--;
splayed ( u, 0 );
}
else{
splay[suf].ch[0] = 0;
}
}我们求得x的前序和后序,然后把前序放到根,后序在根的右儿子,这个时候比x前序还小的在根结点左儿子,比x后序还大的在根结点的右儿子的右儿子,x就在根结点的右儿子的左儿子.然后比较cnt,删除即可.
第k个操作
之前的size派上用场了!因为左子树的size就是比x小的个数,右子树的size是比x大的个数.那么我们可以选择往左还是往右,判断的依据是
.如果往右的话,k要减去left.size 1,因为我们不考虑最小的left.size 1个元素了,你现在是k-left.size 1小的元素了.以此类推.
代码语言：javascript复制int findkth (int x) {
if (splay[root].size<x)
return -1;
int u=root;
while (1) {
if ( x <= splay[splay[u].ch[0]].size )
u = splay[u].ch[0];
else if ( x <= splay[u].cnt splay[splay[u].ch[0]].size )
return u;
else {
x -= ( splay[splay[u].ch[0]].size splay[u].cnt );
u = splay[u].ch[1];
}
}
}插入INF和-INF
INF和-INF可以作为哨兵,如果有哨兵存在，那么这些点永远都不会是死在最前面或者死的时候垫在最下面，就帮助我们少考虑很多边界，我昨天没有加哨兵，不停地补刀做手术，还是千疮百孔，病很多都是并发症，医不过来，加了个哨兵，自己就好了
总的代码
代码语言：javascript复制#include <stdio.h>
#include <stdlib.h>
#define N 1000005
#define INF 0x7f7f7f7f
struct splay{
int ch[2];
int val;//数值
int size;//子树大小
int cnt;//每个节点所含副本数
int parent;
}splay[N];
int total;
int root;
int na;
void pushup(int node_id){
int l=splay[node_id].ch[0];
int r=splay[node_id].ch[1];
splay[node_id].size=splay[l].size splay[r].size splay[node_id].cnt;
}
void rotate (int x) {
int fa = splay[x].parent;
int Gfa = splay[fa].parent;
int k = (splay[fa].ch[1]== x);
splay[Gfa].ch[splay[Gfa].ch[1]==fa] = x;
splay[x].parent = Gfa;
splay[fa].ch[k] = splay[x].ch[k^1];
splay[splay[x].ch[k^1]].parent= fa;
splay[x].ch[k ^ 1] = fa;
splay[fa].parent = x;
pushup(fa);
pushup(x);
}
//将x旋转到goal的儿子
void splayed ( int x, int goal ) {
while (splay[x].parent != goal) {
int fa = splay[x].parent, Gfa = splay[fa].parent;
if (Gfa!= goal )
( (splay[Gfa].ch[0] == fa) ^ (splay[fa].ch[0] == x)) ? rotate(x) : rotate (fa);
rotate (x);
}
if (!goal)
root=x;
}
void insert(int x) {
int u=root, fa=0;
while (u && splay[u].val!=x) {
fa = u;
u=splay[u].ch[x>splay[u].val];
}
if (u)
splay[u].cnt ;
else {
u= total;
if (fa)
splay[fa].ch[x > splay[fa].val] = u;
splay[u].ch[0] = splay[u].ch[1] = 0;
splay[u].val = x;
splay[u].parent = fa;
splay[u].cnt = splay[u].size = 1;
}
splayed(u,0);
}
void find(int x){
if (!root)
return;
int u=root;
while (splay[u].ch[x > splay[u].val] && x!=splay[u].val)
u=splay[u].ch[x > splay[u].val];
splayed (u,0);
}
int PreSuf (int x, int f) {
find (x);
if (splay[root].val>x&&f)
return root;
if (splay[root].val < x && !f)
return root;
int u = splay[root].ch[f];
if (!u)
return 0;
while (splay[u].ch[f ^ 1])
u =splay[u].ch[f ^ 1];
return u;
}
void Delete (int x) {
int pre = PreSuf(x,0);
int suf = PreSuf(x,1);
splayed(pre,0);
splayed(suf,pre);
int u = splay[suf].ch[0];
if (splay[u].cnt>1) {
splay[u].cnt--;
splayed ( u, 0 );
}
else{
splay[suf].ch[0] = 0;
}
}
int findkth (int x) {
if (splay[root].size<x)
return -1;
int u=root;
while (1) {
if ( x <= splay[splay[u].ch[0]].size )
u = splay[u].ch[0];
else if ( x <= splay[u].cnt splay[splay[u].ch[0]].size )
return u;
else {
x -= ( splay[splay[u].ch[0]].size splay[u].cnt );
u = splay[u].ch[1];
}
}
}
void build(){
insert(INF);
insert(-INF);
}
int main(){
int n;
build();
scanf("%d",&n);
int opt,x;
int u;
while(n--){
scanf("%d %d",&opt,&x);
switch (opt) {
case 1:
insert(x);
break;
case 2:
Delete(x);
break;
case 3:
find(x);
printf("%dn",splay[splay[root].ch[0]].size);
break;
case 4:
u=findkth(x 1);
printf("%dn",splay[u].val);
break;
case 5:
u=PreSuf(x, 0);
printf("%dn",splay[u].val);
break;
case 6:
u=PreSuf(x, 1);
printf("%dn",splay[u].val);
break;
default:
break;
}
}
}
