splay步步为营

admin · 发表于 2020-4-5 15:45:49

SPLAY是信息学奥赛高级数据结构里面一个很重要的内容，可以用来解决好多的实际问题，序列统计，序列翻转等，很多的BST之类的题目都可以用SPLAY来解决。为了学好它，我们步步为营一个个的做。

Splay的基本思想和并查集的有点相似，并查集在进行了查找的时候顺便压缩了路径，这是一个自调整的过程，Splay在查询的时候将这个点想转到根，因为树总在旋转，所以基本可以达到一个平衡。
Splay的精髓在于旋转，这个旋转和treap的有点相似，treap在插入的时候现先只考虑节点的val值，根据BST的特性插入到合适的位置，显然是一个叶节点，然后再比较它的rnd和父节点的rnd，若大了则旋转，这样一次旋转的话它的父亲变成了自己的儿子，它上升了一级，然后递归直到rnd满足要求。而splay的旋转也是一样，基本思想把它旋转到他父亲的位置，逐层向上直到它成为根节点。

上旋一层和treap中几乎是一样的，但是Spaly因为以后涉及到更多的操作，所以结构体中特加了一个fa域。

先来一个最简单的，只有插入和输出的splay，着重写好旋转，为了确保正确，分步手写LR和RR，免得出错。交到LG1097，AC了。基本说明旋转部分没问题。

#include<bits/stdc++.h>
using namespace std;
const int inf=9999999;
const int N=100100;
struct node
{
int val,cnt;
int fa,s[2],sz; ///s0s1左右儿子
} a[N];
int n, tot, root;
void ArrayPr() /// 调试监视使用
{
cout<<endl<<" i ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<i;
cout<<endl<<"val ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].val;
cout<<endl<<"cnt ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].cnt;
cout<<endl<<" s0 ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[0];
cout<<endl<<" s1 ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[1];
cout<<endl<<" sz ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].sz;
cout<<endl;
}
void BSTPr(int rt) ///中序输出以rt为根的BST
{
if (a[rt].s[0]>0) BSTPr(a[rt].s[0]);
cout<<a[rt].val<<' '<<a[rt].cnt<<endl;
if (a[rt].s[1]>0) BSTPr(a[rt].s[1]);
}
void LR(int rt)/// 左旋因为有了fa，所以不需要传地址但是也多了修改fa指针的操作
{
///cout<<"L\n";
int x=a[rt].fa; ///x是rt的爸爸
int y=a[x].fa;///y是x的爸爸 rt的爷爷
int l=a[rt].s[0]; ///rt的左儿子挂给x当右儿子（本来右儿子是rt）
a[x].s[1]=l;
if(l!=0) a[l].fa=x; //这个要注意空节点没有fa
a[rt].fa=y; //rt取代了他的爸爸x
a[rt].s[0]=x;//rt的原父节点x成为rt 的左儿子
if(y!=0)
{
if(x==a[y].s[0])
a[y].s[0]=rt;
else a[y].s[1]=rt;
}
a[x].fa=rt;
}
void RR(int rt) /// 同上右旋
{
///cout<<"R\n";
int x=a[rt].fa; ///x是rt的爸爸
int y=a[x].fa;///y是x的爸爸 rt的爷爷
int r=a[x].s[0]=a[rt].s[1];
if(r!=0) a[r].fa=x;
a[rt].fa=y; //rt取代了他的爸爸x
a[rt].s[1]=x;
if(y!=0)
{
if(x==a[y].s[0])
a[y].s[0]=rt;
else a[y].s[1]=rt;
}
a[x].fa=rt;
}
void splay(int rt)//伸展操作: 6种情况
{
int x,y;
while(a[rt].fa!=0)//反复进行旋转，直至将x节点调整至根部为止
{
x=a[rt].fa;///rt的爸爸
y=a[x].fa;
if(y==0)//在x为根的情况下，若x在左儿子位置，则右旋；否则左旋
{
if(rt==a[x].s[0]) RR(rt);
else LR(rt);
break;
}
if(rt==a[x].s[0])//在x位于左位置的情况下，若x的父节点位于左位置，则分别
//以x的父节点和x为基准两次右旋；否则以x为基准右旋和左旋
{
if(x==a[y].s[0]) ///LLL
{
RR(x);
RR(rt);
}
else ///LLR
{
RR(rt);
LR(rt);
}
}
else
{
if(x==a[y].s[1]) ///RRR
{
LR(x);
LR(rt);
}
else
{
LR(rt);
RR(rt);
}
}
}
root=rt;//新根
//cout<<rt<<endl;
}
void Ins(int rt, int x) /// 在rt子树中插入x
{
if(rt==0) /// 新树
{
tot=root=1;
a[1].fa=a[1].s[0]=a[1].s[1]=0;
a[1].val=x;
a[1].cnt=1;
}
else if(a[rt].val==x) a[rt].cnt++;
else if(a[rt].val<x)
{
if (a[rt].s[1]==0)
{
a[rt].s[1]=++tot;
a[tot].s[0]=a[tot].s[1]=0;
a[tot].val=x;
a[tot].fa=rt;
a[tot].cnt=1;
splay(tot);
}
else
Ins(a[rt].s[1],x);
}
else if(a[rt].val>x)
{
if (a[rt].s[0]==0)
{
a[rt].s[0]=++tot;
a[tot].s[0]=a[tot].s[1]=0;
a[tot].val=x;
a[tot].fa=rt;
a[tot].cnt=1;
splay(tot);
}
else
Ins(a[rt].s[0], x);
}
}
int main()
{
cin>>n;
while(n--)
{
int x;
cin>>x;
Ins(root,x);
}
BSTPr(root);
return 0;
}
/*
10
1 2 5 8 9 7 6 1 2 9
*/

复制代码

这里写的代码很清晰直观，所以代码量比较大，加之我在里面写了很多的调试和测试语句，显得更长了。但是思路简单，主要是熟悉SPLAY的基本思路和几种旋转。要在纸上配合画图来理解。

admin · 发表于 2020-4-5 16:19:06

现在精简这部分的代码，用一个函数R(x)来表示将x向上旋一格，Splay(x,y)表示把x旋到y的位置，便于以后扩展的时候代码写短一点，因为比较复杂，里面加了好多的调试语句。

#include<bits/stdc++.h>
using namespace std;
const int inf=9999999;
const int N=100100;
struct node
{
int val,cnt;
int fa,s[2],sz; ///s0s1左右儿子
} a[N];
int n, tot, root;
void ArrayPr() /// 调试监视使用
{
cout<<endl<<" i ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<i;
cout<<endl<<"val ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].val;
cout<<endl<<"cnt ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].cnt;
cout<<endl<<" s0 ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[0];
cout<<endl<<" s1 ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[1];
cout<<endl<<" fa ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].fa;
cout<<endl;
int kk;
cin>>kk;
}
void BSTPr(int rt) ///中序输出以rt为根的BST
{
if (a[rt].s[0]>0) BSTPr(a[rt].s[0]);
if (a[rt].cnt>0) cout<<a[rt].val<<' '<<a[rt].cnt<<endl;
if (a[rt].s[1]>0) BSTPr(a[rt].s[1]);
}
int Son(int x)///判断x是L还是R儿子
{
int y=a[x].fa;
return a[y].s[1]==x;
}
void R(int x)
{
int y=a[x].fa;
int z=a[y].fa;
int k=Son(x);
int v=a[x].s[k^1];///v是x另外一边的儿子将要被挂在y下面
a[y].s[k]=v,a[v].fa=y;///v挂在y下要是v=0这里省略了
a[z].s[Son(y)]=x,a[x].fa=z;///x挂在z下
a[x].s[k^1]=y,a[y].fa=x;///y挂在x下
/// 这三步需要画图理解
///cout<<"R"<<k<<endl;///0表示LR 1表示RR
}
inline void Splay(int x,int rt=root) ///把x旋到rt的位置默认rt是根
{
rt=a[rt].fa;
int y,z;
while(a[x].fa!=rt) /// y==rt就到位
{
y=a[x].fa,z=a[y].fa;;
///ArrayPr();
///cout<<x<<' '<<y<<' '<<z<<' '<<endl;
if(z!=rt)
if(Son(x)==Son(y))R(y); /// 一字
else R(x);
///ArrayPr();
R(x);
///ArrayPr();
}
///cout<<"Splay Complete!\n";
if(rt==0)root=x;
///检查
///ArrayPr();
///BSTPr(root);
}
void Ins(int rt, int x) /// 在rt子树中插入x
{
if(a[rt].val==x) a[rt].cnt++;
else
{
int k=a[rt].val>x;
{
if (a[rt].s[k^1]==0)
{
a[rt].s[k^1]=++tot;
a[tot].s[0]=a[tot].s[1]=0;
a[tot].val=x;
a[tot].fa=rt;
a[tot].cnt=1;
Splay(tot,root);
}
else
Ins(a[rt].s[k^1],x);
}
}
}
int main()
{
int i;
cin>>n;
//插入-inf和inf
root=1;
tot=2;
a[1].val=-inf,a[1].s[0]=0,a[1].s[1]=2,a[1].fa=0;
a[2].val= inf,a[2].s[0]=0,a[2].s[1]=0,a[2].fa=1;
while(n--)
{
int x;
cin>>x;
Ins(root,x);
///BSTPr(root);
}
BSTPr(root);
return 0;
}
/*
10
1 2 5 8 9 7 6 1 2 9
*/

复制代码

这个程序我还好久没有写了，以前都是写LR RR那样清晰明了的，现在把他们合N为一，代码段肯定是短了，但是有错的话就很难调出来，你看我的程序里面都保留了我曾经的调试痕迹，体会下我是怎么样步步为营做程序的。

直观的加了-inf和-inf，也用cnt控制了它们的时候输出，交到LG1097，AC了。

admin · 发表于 2020-4-10 18:01:53

现在插入和遍历都是正确的，特别检查了旋转，既然LG1097AC了，基本既没有问题，现在添上删除部分，要删除x的话需要先查找到x所在的节点，找到后旋转到根，设为root，然后看它有没有左子树l，有的话，把左子树中的最大节点p，旋转到此节点l的位置，那么这个树l就完全没有右子树了，因为根是最大嘛！然后把root的右子树r作为l的右子树，接到l上，修改下root，新根为l。

int Find(int rt,int x) /// 找到x对应的a[rt]
{
if (rt==0) return 0;
if (a[rt].val==x)
{
Splay(rt,root);
return rt;
}
int k=a[rt].val<x; /// k=0表示左子树中去1表示去右子树
return Find(a[rt].s[k],x);
}
void Del(int x) //删除节点
{
int rt=Find(root,x);///找到对应的rt
if(rt==0) return;
if(a[rt].cnt>1) a[rt].cnt--;
else if(a[rt].s[0]==0) /// 没有左子树
{
root=a[rt].s[1];
a[root].fa=0;
}
else
{
int p,l,r;
l=a[rt].s[0];
r=a[rt].s[1];
/// 左子树里面去找最右的儿子
p=l;
while(a[p].s[1]>0) p=a[p].s[1];
Splay(p,l); ///转上来作为根的左子树
/// 因为最大，没有右子树，把他作为新根
a[p].s[1]=r; ///rt的右儿子接上去
a[r].fa=p;
a[root=p].fa=0;/// 新根
pushup(p);
}
///要不要回收？
}

复制代码

检查了下这段，把刚才插入的结点无聊的乱序一个个的删除，发现真的都删除了。

admin · 发表于 2020-4-11 13:21:23

因为Splay强调了R过程，所以查询排名和Treap有点不同，SPLAY查询的时候带着了旋转。
要想查找x的排名，先要找到x，当找到x的时候，其实x已经被旋到了根，现在只要直接输出左子树下的sz就行了。但是这里我们有两个假节点 +/-inf ，所以真实的排名要调整。

int Rank(int x) ///在RT子树中比x小的数 +1
{
int rt=Find(root,x);
int l=a[rt].s[0];
return a[l].sz;/// 包含那个-inf 所以不需要+1
}

复制代码

admin · 发表于 2020-4-23 18:27:29

至于求前驱和后继，和以前的一样，但是这次我们选择使用非递归的写法，

int Pre(int rt, int x)
{
int p=rt, ans;
while(p>0)
{
if(x<=a[p].val) p=a[p].s[0];
else
{
ans=p;
p=a[p].s[1];
}
}
return ans;
}
int Suc(int rt, int x)
{
int p=rt, ans;
while(p>0)
{
if(a[p].val<=x) p=a[p].s[1];
else
{
ans = p;
p=a[p].s[0];
}
}
return ans;
}

复制代码

admin · 发表于 2020-4-23 18:36:37

结合上面所有的代码，3369的做法如下，交上去，顺利AC.

#include<bits/stdc++.h>
using namespace std;
const int inf=99999999;
const int N=100100;
struct node
{
int val,cnt;
int fa,s[2],sz; ///s0s1左右儿子
} a[N];
int n, tot, root;
void ArrayPr() /// 调试监视使用
{
cout<<endl<<" i ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<i;
cout<<endl<<"val ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].val;
cout<<endl<<"cnt ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].cnt;
cout<<endl<<" s0 ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[0];
cout<<endl<<" s1 ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[1];
cout<<endl<<" fa ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].fa;
cout<<endl<<" sz ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].sz;
cout<<endl;
}
void BSTPr(int rt) ///中序输出以rt为根的BST
{
if (a[rt].s[0]>0) BSTPr(a[rt].s[0]);
if (a[rt].cnt>0) cout<<a[rt].val<<' '<<a[rt].cnt<<endl;
if (a[rt].s[1]>0) BSTPr(a[rt].s[1]);
}
void pushdown(int rt) ///类似线段树网上调整
{
///暂时无用
}
void pushup(int rt) ///类似线段树网上调整
{
int l=a[rt].s[0], r=a[rt].s[1];
a[rt].sz=a[l].sz+a[r].sz+a[rt].cnt;
}
int Son(int x)///判断x是L还是R儿子
{
int y=a[x].fa;
return a[y].s[1]==x;
}
void R(int x)
{
int y=a[x].fa;
int z=a[y].fa;
int k=Son(x);
int v=a[x].s[k^1];///v是x另外一边的儿子将要被挂在y下面
pushdown(x),pushdown(y);///下传
a[y].s[k]=v,a[v].fa=y;///v挂在y下要是v=0这里省略了
a[z].s[Son(y)]=x,a[x].fa=z;///x挂在z下
a[x].s[k^1]=y,a[y].fa=x;///y挂在x下
/// 这三步需要画图理解
pushup(y),pushup(x);///上传，注意顺序
}
inline void Splay(int x,int rt=root) ///把x旋到rt的位置默认rt是根
{
rt=a[rt].fa;
int y,z;
while(a[x].fa!=rt) /// y==rt就到位
{
y=a[x].fa,z=a[y].fa;;
if(z!=rt)
if(Son(x)==Son(y))R(y); /// 一字
else R(x);
R(x);
}
if(rt==0)root=x;
}
int Find(int rt,int x) /// 找到x对应的a[rt]
{
if (a[rt].val==x)
{
Splay(rt,root);
return rt;
}
int k=a[rt].val<x; /// k=0表示左子树中去1表示去右子树
if (a[rt].s[k]>0) return Find(a[rt].s[k],x);
else return 0;
}
void Ins(int rt, int x) /// 在rt子树中插入x
{
a[rt].sz++;
if(a[rt].val==x) a[rt].cnt++;
else
{
int k=(a[rt].val<x);/// k=0表示左子树中去1表示去右子树
if (a[rt].s[k]==0)
{
a[rt].s[k]=++tot;
a[tot].s[0]=a[tot].s[1]=0;
a[tot].val=x;
a[tot].fa=rt;
a[tot].cnt=a[tot].sz=1;
Splay(tot,root);
}
else
Ins(a[rt].s[k],x);
}
}
void Del(int x) //删除节点
{
int rt=Find(root,x);///找到对应的rt
if(rt==0) return;
a[rt].sz--;
if(a[rt].cnt>1) a[rt].cnt--;
else if(a[rt].s[0]==0) /// 没有左子树
{
root=a[rt].s[1];
a[root].fa=0;
}
else
{
int p,l,r;
l=a[rt].s[0];
r=a[rt].s[1];
/// 左子树里面去找最右的儿子
p=l;
while(a[p].s[1]>0) p=a[p].s[1];
Splay(p,l); ///转上来作为根的左子树
/// 因为最大，没有右子树，把他作为新根
a[p].s[1]=r; ///rt的右儿子接上去
a[r].fa=p;
a[root=p].fa=0;;/// 新根
pushup(p);
}
///要不要回收？
}
int Rank(int x) ///在RT子树中比x小的数 +1
{
int rt=Find(root,x);
int l=a[rt].s[0];
return a[l].sz;/// 包含那个-inf 所以不需要+1
}
int Getkth(int rt, int x) ///在RT子树中找第k小
{
int l=a[a[rt].s[0]].sz; /// RT的左儿子下的个数
if(l+1<=x && x<=l+a[rt].cnt) return a[rt].val;
if(l+1>x) return Getkth(a[rt].s[0], x); ///左儿子里去找
if(l+a[rt].cnt<x) return Getkth(a[rt].s[1], x-(l+a[rt].cnt));
}
int Pre(int rt, int x)
{
int p=rt, ans;
while(p>0)
{
if(x<=a[p].val) p=a[p].s[0];
else
{
ans=p;
p=a[p].s[1];
}
}
return ans;
}
int Suc(int rt, int x)
{
int p=rt, ans;
while(p>0)
{
if(a[p].val<=x) p=a[p].s[1];
else
{
ans = p;
p=a[p].s[0];
}
}
return ans;
}
int main()
{
///freopen("3369.in","r",stdin);
///freopen("3369.out","w",stdout);
int x,opt;
cin>>n;
//插入-inf和inf
root=1;
tot=2;
a[1].val=-inf,a[1].s[0]=0,a[1].s[1]=2,a[1].fa=0;
a[2].val= inf,a[2].s[0]=0,a[2].s[1]=0,a[2].fa=1;
a[1].sz=2,a[2].sz=1;
a[1].cnt=a[2].cnt=1;
while(n--)
{
cin>>opt>>x;
if(opt==1) Ins(root, x);
if(opt==2) Del(x);
if(opt==3) cout<<Rank(x)<<endl;
if(opt==4) cout<<Getkth(root, x+1)<<endl;
if(opt==5) cout<<a[Pre(root, x)].val<<endl;
if(opt==6) cout<<a[Suc(root, x)].val<<endl;
}
return 0;
}
/*
40
1 3 7 5 9 2 8 4 6 0
11 13 17 15 19 12 18 14 16 10
31 33 37 35 39 32 38 34 36 30
11 13 17 15 19 12 18 14 16 10
*/

复制代码

admin · 发表于 2020-4-24 13:04:20

上面的例子是SPLAY的一个应用，就是把某个点旋转到根，在查询的过程中总在转动的话这棵树的平衡性不会太差，所以可以当AVL来用。还有一个更牛的应用就是伸展操作，把
在学这个的时候要注意转换一下思想，把区间的下标当做树的节点。
一个典型的简单应用基础题是P3391 文艺平衡树 http://hsyit.cn/forum.php?mod=viewthread&tid=69341

		自动登录	找回密码
密码			立即注册