splay tree 学习笔记-白红宇

splay tree 学习笔记

阅读量：5053 次

发布时间：2019-06-12

本文共 6417 字，大约阅读时间需要 21 分钟。

首先感谢litble的精彩讲解，原文博客：

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

一般地【一般地】，Splay有一下操作：

insert 插入

find 查找

del 删除

pre 查找前驱

post 查找后缀

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

插入操作与二叉查找树相同，不过多了一个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小的节点

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

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

洛谷P2286 宠物收养所

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

#include
    
     #include
     
      #include
      
       #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
       
        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
        
         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

kthint 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

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

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

#include
    
     #include
     
      #include
      
       #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
       
        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
        
         nul");	return 0;}