当前位置: 代码迷 >> 综合 >> splay tree 学习笔记
  详细解决方案

splay tree 学习笔记

热度:89   发布时间:2023-12-25 05:18:23.0

首先感谢litble的精彩讲解,原文博客:

litble的小天地


在学完二叉平衡树后,发现这是只是一个不稳定的垃圾玩意,真正实用的应有Treap、AVL、Splay这样的查找树。于是最近刚学了学了点Splay。

一般地【一般地】,Splay有一下操作:

  1. insert    插入
  2. find       查找
  3. del        删除
  4. pre        查找前驱
  5. post      查找后缀
  6. Splay    *伸展

其中前几个都是普通二叉查找树就有的操作,Splay操作则是Splay tree的特有的。


我们先建一个结构体:

class node
{public:int v,ch[2],f;
}e[maxn];

储存每个节点的信息:权值,左右儿子,父亲,【还可以有树的大小等,因需而异】


splay

为了方便,我们先讲splay操作

splay ,顾名思义,就是伸展,将某个节点在保持树的性质的前提下伸展到根节点

有什么用呢?

想象世界上有那么多博客,大神们的博客每天都有成千上万人访问,而我这种蒟蒻一般就没什么人看,所以每次将访问的节点伸展到根,访问少的自然就在下面,访问多的就在上边,大大减少的查询时间。

虽说某一次的查询复杂度可能达到O(n),但平摊下平均是logn的,具体我不会证= =

所以splay分3种情况伸展【其实有6种】:

1、当前节点u的父亲为根节点,这个时候我们只需一次翻转就可以到达根结点了

2、当前节点u与其父节点都为同一侧的儿子,即zig-zig型或zag-zag型,这个时候我们需要将父节点翻转一次,再将u翻转一次

3、当前节点u与其父节点为异侧节点,即zig-zag或zag-zig型,这个时候我们需将u翻转两次


代码如下【借鉴litble的,写的确实很巧妙,合并了zig-zag操作,巧妙利用C++真为1假为0与数组的0和1下标结合】

#define isr(u) (e[e[u].f].ch[1]==u).........inline void spin(int u)
{int s=isr(u),fa=e[u].f;e[u].f=e[fa].f;e[e[fa].f].ch[isr(fa)]=u;e[fa].f=u;e[fa].ch[s]=e[u].ch[s^1];if(e[u].ch[s^1]) e[e[u].ch[s^1]].f=fa;e[u].ch[s^1]=fa;
}inline void splay(int u)
{while(e[u].f){if(!e[e[u].f].f) spin(u);else if(isr(u)^isr(e[u].f)) spin(u),spin(u);else spin(e[u].f),spin(u);}root=u;
}




insert

inline void insert(int& u,int v,int fa)
{if(!u) e[u=++siz].v=v,e[u].f=fa,e[u].ch[0]=e[u].ch[1]=0,splay(u),cnt++;else if(v<e[u].v) insert(e[u].ch[0],v,u);else insert(e[u].ch[1],v,u);
}
插入操作与二叉查找树相同,不过多了一个splay操作


find

int find(int v,int u=root)
{if(!u) return 0;if(e[u].v==v) {splay(u);return u;}if(e[u].v>v) return find(v,e[u].ch[0]);else return find(v,e[u].ch[1]);
}
按照查找树左小右大的性质查找,记得每次访问时先splay一下


del

void del(int u)
{if(!u) return;splay(u);if(e[u].ch[0]*e[u].ch[1]==0) root=e[u].ch[0]+e[u].ch[1];else{int t=e[u].ch[1];while(e[t].ch[0]) t=e[t].ch[0];e[t].ch[0]=e[u].ch[0];e[e[u].ch[0]].f=t;root=e[u].ch[1];}e[root].f=0;cnt--;
}

先splay到根,这下就很好讨论了,不像二叉查找树那么麻烦,就分两种情况:

1、u有一次儿子为空,那么直接删去就好了,将另一侧节点设为根节点

2、u两子健全,先找到u的后继t【前驱类似】,将根节点的左儿子拔下来,插到后继t的左儿子上,这时候u只剩右儿子无牵无挂,直接将root交给右儿子随风而去~~


pre和post

int pre(int v,int u=root)
{if(!u) return 0;if(e[u].v==v) {splay(u);return u;}if(e[u].v>v) return pre(v,e[u].ch[0]);else{int x=pre(v,e[u].ch[1]);if(!x) return u;return e[u].v>e[x].v ? u:x;}
}


int post(int v,int u=root)
{if(!u) return 0;if(e[u].v==v) {splay(u);return e[u].v;}if(e[u].v<v) return post(v,e[u].ch[1]);else{int x=post(v,e[u].ch[0]);if(!x) return u;return e[u].v<e[x].v ? u:x;}
}

和插入类似,利用查找树的性质查找,注意当找到一个符合条件的节点时不一定是最优的,以后继为例,还要向左儿子找有没有更小但不比v小的节点

【我这里返回的是节点编号,直接返回值也可以而且更加方便】




大概基本的操作就这些啦,我们可以做做题练习一下:

洛谷P2286 宠物收养所


比较裸的一道练习,带前驱与后继操作

#include<iostream>
#include<cstdio>
#include<algorithm>
#define isr(u) (e[e[u].f].ch[1]==u)
using namespace std;
const int maxn=80005,INF=2000000000,P=1000000;inline int read()
{int out=0,flag=1;char c=getchar();while(c<48||c>57) {if(c=='-') flag=-1;c=getchar();}while(c>=48&&c<=57) {out=out*10+c-48;c=getchar();}return out*flag;
}class node
{public:int v,ch[2],f;
}e[maxn];
int siz=0,root=0,cnt=0,flag=-1;inline void spin(int u)
{int s=isr(u),fa=e[u].f;e[u].f=e[fa].f;e[e[fa].f].ch[isr(fa)]=u;e[fa].f=u;e[fa].ch[s]=e[u].ch[s^1];if(e[u].ch[s^1]) e[e[u].ch[s^1]].f=fa;e[u].ch[s^1]=fa;
}inline void splay(int u)
{while(e[u].f){if(!e[e[u].f].f) spin(u);else if(isr(u)^isr(e[u].f)) spin(u),spin(u);else spin(e[u].f),spin(u);}root=u;
}inline void insert(int& u,int v,int fa)
{if(!u) e[u=++siz].v=v,e[u].f=fa,e[u].ch[0]=e[u].ch[1]=0,splay(u),cnt++;else if(v<e[u].v) insert(e[u].ch[0],v,u);else insert(e[u].ch[1],v,u);
}int find(int v,int u=root)
{if(!u) return 0;if(e[u].v==v) {splay(u);return u;}if(e[u].v>v) return find(v,e[u].ch[0]);else return find(v,e[u].ch[1]);
}int pre(int v,int u=root)
{if(!u) return 0;if(e[u].v==v) {splay(u);return u;}if(e[u].v>v) return pre(v,e[u].ch[0]);else{int x=pre(v,e[u].ch[1]);if(!x) return u;return e[u].v>e[x].v ? u:x;}
}int post(int v,int u=root)
{if(!u) return 0;if(e[u].v==v) {splay(u);return e[u].v;}if(e[u].v<v) return post(v,e[u].ch[1]);else{int x=post(v,e[u].ch[0]);if(!x) return u;return e[u].v<e[x].v ? u:x;}
}void del(int u)
{if(!u) return;splay(u);if(e[u].ch[0]*e[u].ch[1]==0) root=e[u].ch[0]+e[u].ch[1];else{int t=e[u].ch[1];while(e[t].ch[0]) t=e[t].ch[0];e[t].ch[0]=e[u].ch[0];e[e[u].ch[0]].f=t;root=e[u].ch[1];}e[root].f=0;cnt--;
}int main()
{int N,ans=0,cmd,x;scanf("%d",&N);while(N--){scanf("%d%d",&cmd,&x);if(!cnt){flag=cmd;insert(root,x,0);}else{if(cmd==flag) insert(root,x,0);else{int l=pre(x),r=post(x);if(!r) ans=(ans+x-e[l].v)%P,del(l);else if(!l) ans=(ans+e[r].v-x)%P,del(r);else{if(x-e[l].v<=e[r].v-x) ans=(ans+x-e[l].v)%P,del(l);else ans=(ans+e[r].v-x)%P,del(r);}}}}cout<<ans<<endl;//system("pause >nul");return 0;
}

洛谷P2596 书架

 

这道题需要查找第K大以及元素的排名,这个时候需要我们引入siz这个元素,表示以u为根的子树的大小

 

这个时候同样需要添加一些操作维护:

1、在插入时,对应经过的节点siz++;

2、在删除时,由于u节点splay到了根节点,对其儿子没有影响,但是u的左子树插到了t下,所以需要对t以及t的祖先们的siz都加上u的左儿子siz大小【假装splay操作已自动维护好了siz】

3、在splay操作中,由于我们翻转了节点,树的形态发生了变化,需要维护一下siz的值,只需要添加这一句函数:

inline void up(int u) {e[u].siz=e[e[u].ch[0]].siz+e[e[u].ch[1]].siz+1;}


然后在spin结束时顺序【顺序!】调用up(fa)和up(u)就好了。

如下

inline void spin(int u)
{int fa=e[u].f,s=isr(u);e[u].f=e[fa].f;if(e[fa].f) e[e[fa].f].ch[isr(fa)]=u;e[fa].f=u;e[fa].ch[s]=e[u].ch[s^1];if(e[u].ch[s^1]) e[e[u].ch[s^1]].f=fa;e[u].ch[s^1]=fa;up(fa);up(u);
}

 

有了siz的辅助,我们很快就可以写出插到k大值与查询排名的函数

order

int order(int v,int u=root)
{if(!u) return INF;if(e[u].v==v) {splay(u);return e[e[u].ch[0]].siz+1;}if(e[u].v>v) return order(v,e[u].ch[0]);return order(v,e[u].ch[1]);
}


kth

kth
int kth(int k,int u=root)
{if(!u) return INF;if(k==e[e[u].ch[0]].siz+1) {splay(u);return u;}if(k<e[e[u].ch[0]].siz+1) return kth(k,e[u].ch[0]);return kth(k-e[e[u].ch[0]].siz-1,e[u].ch[1]);
}

有了这两个函数的帮助,我们就可以很快写出这道题了【原谅我代码的啰嗦,但还算清晰】

我用了手动给书加上权值值的方法维护书的顺序的

#include<iostream>
#include<cstdio>
#include<algorithm>
#define isr(x) (e[e[x].f].ch[1]==x)
using namespace std;
const int maxn=800005,INF=2000000000;
int big=maxn,small=maxn;
int code[maxn];inline int read()
{int out=0,flag=1;char c=getchar();while(c<48||c>57) {if(c=='-') flag=-1;c=getchar();}while(c>=48&&c<=57) {out=out*10+c-48;c=getchar();}return out*flag;
}class node
{public:int id,v,f,siz,ch[2];node() {ch[0]=ch[1]=0;siz=0;}//node(int a,int b,int c) {id=a;b=v;f=c;siz=1;ch[0]=ch[1]=0;}
}e[maxn];
int nodei=0,root=0;inline void up(int u) {e[u].siz=e[e[u].ch[0]].siz+e[e[u].ch[1]].siz+1;}inline void spin(int u)
{int fa=e[u].f,s=isr(u);e[u].f=e[fa].f;if(e[fa].f) e[e[fa].f].ch[isr(fa)]=u;e[fa].f=u;e[fa].ch[s]=e[u].ch[s^1];if(e[u].ch[s^1]) e[e[u].ch[s^1]].f=fa;e[u].ch[s^1]=fa;up(fa);up(u);
}void splay(int u)
{while(e[u].f){if(!e[e[u].f].f) spin(u);else if(isr(u)^isr(e[u].f)) spin(u),spin(u);else spin(e[u].f),spin(u);}root=u;
}void insert(int& u,int v,int id,int fa)
{if(!u) {e[u=++nodei].id=id;e[u].v=v;e[u].f=fa;e[u].siz=1;splay(u);}else if(v<e[u].v) e[u].siz++,insert(e[u].ch[0],v,id,u);else e[u].siz++,insert(e[u].ch[1],v,id,u);
}int find(int v,int u=root)
{if(!u) return 0;if(e[u].v==v) {splay(u);return u;}if(e[u].v>v) return find(v,e[u].ch[0]);else  return find(v,e[u].ch[1]);
}void del(int u)
{if(!u) return;splay(u);if(e[u].ch[0]*e[u].ch[1]==0) root=e[u].ch[0]+e[u].ch[1];else{int p=e[u].ch[1];while(e[p].ch[0]) p=e[p].ch[0];e[p].ch[0]=e[u].ch[0];e[e[u].ch[0]].f=p;while(e[p].f!=u) e[p].siz+=e[e[u].ch[0]].siz,p=e[p].f;root=e[u].ch[1];}e[root].f=0;
}int order(int v,int u=root)
{if(!u) return INF;if(e[u].v==v) {splay(u);return e[e[u].ch[0]].siz+1;}if(e[u].v>v) return order(v,e[u].ch[0]);return order(v,e[u].ch[1]);
}int kth(int k,int u=root)
{if(!u) return INF;if(k==e[e[u].ch[0]].siz+1) {splay(u);return u;}if(k<e[e[u].ch[0]].siz+1) return kth(k,e[u].ch[0]);return kth(k-e[e[u].ch[0]].siz-1,e[u].ch[1]);
}void printpre(int u)
{if(u){printpre(e[u].ch[0]);printf("%d ",e[u].id);printpre(e[u].ch[1]);}
}char cmd[10];
int main()
{int N=read(),M=read(),x,t,u,p;for(int i=1;i<=N;i++){x=read();code[x]=++big;insert(root,code[x],x,0);}while(M--){//printpre(root);cout<<endl;scanf("%s",cmd);x=read();switch(cmd[0]){case 'T':del(find(code[x]));code[x]=--small;insert(root,code[x],x,0);break;case 'B':del(find(code[x]));code[x]=++big;insert(root,code[x],x,0);break;case 'I':t=read();if(t){u=find(code[x]);p=e[u].ch[t==1];while(e[p].ch[t==-1]) p=e[p].ch[t==-1];code[x]=e[p].v;code[e[p].id]=e[u].v;swap(e[u].id,e[p].id);}break;case 'A':printf("%d\n",order(code[x])-1);break;case 'Q':printf("%d\n",e[kth(x)].id);break;default:break;}}//system("pause >nul");return 0;
}



  相关解决方案