Splay

Let us play！

Let u splay！

BST 平均 O(logn)

Treap 期望 O(logn)

Splay 均摊 O(logn)

AVL 严格 O(logn)

SBT 严格 O(logn)

AVL不大指望能在赛场写出来，SBT在绝大多数时候是个不错的选择，Treap…嗯……但偏偏Splay被人看成是BST中的万金油……为什么呐？

Splay一个最大的特点就是：每一个操作都要splay一下……除此之外没了……

splay操作的作用就是把某一节点旋转到根，以加快之后的访问速度。它还可以在旋转过程中维持树的基本平衡。

zig: 当目标节点是根节点的左子节点或右子节点时，进行一次zig，将目标节点调整到根节点的位置。
zig-zig:当目标节点是根节点的左（右）子节点的左（右）子节点时，进行一次zig-zig，将目标节点调整到根节点位置。
zig-zag:当目标节点是根节点的左（右）子节点的右（左）子节点时，进行一次zig-zag，将目标节点调整到根节点位置。

重复这几种操作直到目标节点为根。

一次zig、zig-zig、zig-zag又可以分解为几次单旋。

Search/Insert/Rank/Select

与BST相同，只不过记得把插入的节点Splay到根。

Join

作用是把两棵子树S1,S2连成一个Splay，其中S1中所有元素小于S2。

先找到S1中的最大节点x，Splay到S1的根，再把x的右子树链接到S2。

Delete

先找到目标节点，Splay到根，执行Join操作即可。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>

#define C(x) ((int)(T[T[(x)].f].s[1]==(x)))
#define S(x) T[(x)].s
#define L(x) T[(x)].s[0]
#define Ln(x) T[T[(x)].s[0]]
#define R(x) T[(x)].s[1]
#define Rn(x) T[T[(x)].s[1]]
#define F(x) T[(x)].f
#define W(x) T[(x)].w
#define Z(x) T[(x)].size
using namespace std;
typedef long long LL;
const int MAXN=300;
const int INF=2147483647;
const int NINF=-1<<30;
const int ERR=-1;

struct Node{
	int size,w,f;int s[2];//0-L,1-R;
	Node():size(0),w(0),f(0){s[0]=s[1]=0;}
};

Node T[MAXN*3];
int root,sz;
void link(int s,int f,int t){F(s)=f;S(f)[t]=s;}
void Up(int x);void Down(int x);void Join(int f,int s);
int Max(int x);int Min(int x);
void Rot(int x,int c){
	int f=F(x);
	link(x,F(f),C(f));
	link(S(x)[1^c],f,c);
	link(f,x,1^c);
	Up(f);
}
void Splay(int x,int g){
	for(Down(x);F(x)!=g;){
		int f=F(x);
		if(F(f)==g)			Rot(x,C(x));else{
			if(C(x)==C(f))	Rot(f,C(f));  
              else 			Rot(x,C(x));  
							Rot(x,C(x));  
		}
	}
	Up(x);
	if(!g)root=x;
}
void Up(int x){Z(x)=Z(L(x))+Z(R(x))+1;}
void Down(int x){/*Do YOLO*/}
void Insert(int &s,int f,int v) {
	if(s==0) {
		s=++sz;W(s)=v;Z(s)=1;F(s)=f;int x=s;Splay(x,0);
		return;
	}
	Z(s)++;
	if(W(s)>v) 	Insert(L(s),s,v);
	else		Insert(R(s),s,v);	
}
int Search(int s,int v) {
	if(s==0)return ERR;
	if(W(s)==v)return	Splay(s,0),s;
	if(W(s)>v)return 	Search(L(s),v);
	return				Search(R(s),v);
}
void Join(int l,int r){
	int lm=l;if (!l){root=r;F(r)=0; return; }
	while(R(lm))lm=R(lm);
	Splay(lm,F(l));
	R(lm)=r;
	F(r)=lm;
	F(lm)=0;
	Up(lm);
	root=lm;
}
int Delete(int s,int v){
	int x=Search(s,v);
	if(x==ERR)return ERR;
	//Splay(x,0);
	Join(L(x),R(x));
	return 0;
}
int Select(int s,int k) {
	int Lt=Z(L(s));
	if(k==Lt)return Splay(s,0),W(s);
	if(Lt>k)return	Select(L(s),k);
	return			Select(R(s),k-Lt-1);
}
int Rank(int s,int v) {
	int Lt=Z(L(s));
	if(W(s)==v)return	Splay(s,0),Lt;
	if(W(s)>v) return	Rank(L(s),v);
	return				Rank(R(s),v)+Lt+1;
}

inline bool getint(int &x){
int y,flag;
while(isspace(y=getchar()));
if(y==-1) return false;
if(y=='-') flag=-1,x=0;
else flag=1,x=y-'0';
while(isdigit(y=getchar())) x=x*10+(y-'0');
x*=flag;
return true;
}
int main(){
	int c;
	int x;
	//freopen("SBT.in6","r",stdin);
	//freopen("SBT.outsplay6","w",stdout);
	while(getint(c)) {
		switch(c) {
		case 0:
			getint(x);
			Insert(root,0,x);
			break;
		case 1:
			getint(x);
			Delete(root,x);
			break;
		case 2:
			getint(x);
			printf("%d\n",Search(root,x));
			break;
		case 3:
			getint(x);
			printf("%d\n",Select(root,x));  //x<S(root)
			break;
		case 4:
			getint(x);
			printf("%d\n",Rank(root,x));    //Search(x)>0
			break;
		default:
			printf("\n\n\n");
		}
	}

	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<vector>

#include<cmath>

#include<queue>

#define C(x) ((int)(T[T[(x)].f].s[1]==(x)))

#define S(x) T[(x)].s

#define L(x) T[(x)].s[0]

#define Ln(x) T[T[(x)].s[0]]

#define R(x) T[(x)].s[1]

#define Rn(x) T[T[(x)].s[1]]

#define F(x) T[(x)].f

#define W(x) T[(x)].w

#define Z(x) T[(x)].size

using namespace std;

typedef long long LL;

const int MAXN=300;

const int INF=2147483647;

const int NINF=-1<<30;

const int ERR=-1;

struct Node{

int size,w,f;int s[2];//0-L,1-R;

Node():size(0),w(0),f(0){s[0]=s[1]=0;}

};

Node T[MAXN*3];

int root,sz;

void link(int s,int f,int t){F(s)=f;S(f)[t]=s;}

void Up(int x);void Down(int x);void Join(int f,int s);

int Max(int x);int Min(int x);

void Rot(int x,int c){

int f=F(x);

link(x,F(f),C(f));

link(S(x)[1^c],f,c);

link(f,x,1^c);

Up(f);

}

void Splay(int x,int g){

for(Down(x);F(x)!=g;){

int f=F(x);

if(F(f)==g) Rot(x,C(x));else{

if(C(x)==C(f)) Rot(f,C(f));

else Rot(x,C(x));

Rot(x,C(x));

}

Up(x);

if(!g)root=x;

}

void Up(int x){Z(x)=Z(L(x))+Z(R(x))+1;}

void Down(int x){/*Do YOLO*/}

void Insert(int &s,int f,int v) {

if(s==0) {

s=++sz;W(s)=v;Z(s)=1;F(s)=f;int x=s;Splay(x,0);

return;

}

Z(s)++;

if(W(s)>v) Insert(L(s),s,v);

else Insert(R(s),s,v);

}

int Search(int s,int v) {

if(s==0)return ERR;

if(W(s)==v)return Splay(s,0),s;

if(W(s)>v)return Search(L(s),v);

return Search(R(s),v);

}

void Join(int l,int r){

int lm=l;if (!l){root=r;F(r)=0; return; }

while(R(lm))lm=R(lm);

Splay(lm,F(l));

R(lm)=r;

F(r)=lm;

F(lm)=0;

Up(lm);

root=lm;

}

int Delete(int s,int v){

int x=Search(s,v);

if(x==ERR)return ERR;

//Splay(x,0);

Join(L(x),R(x));

return 0;

}

int Select(int s,int k) {

int Lt=Z(L(s));

if(k==Lt)return Splay(s,0),W(s);

if(Lt>k)return Select(L(s),k);

return Select(R(s),k-Lt-1);

}

int Rank(int s,int v) {

int Lt=Z(L(s));

if(W(s)==v)return Splay(s,0),Lt;

if(W(s)>v) return Rank(L(s),v);

return Rank(R(s),v)+Lt+1;

}

inline bool getint(int &x){

int y,flag;

while(isspace(y=getchar()));

if(y==-1) return false;

if(y=='-') flag=-1,x=0;

else flag=1,x=y-'0';

while(isdigit(y=getchar())) x=x*10+(y-'0');

x*=flag;

return true;

}

int main(){

int c;

int x;

//freopen("SBT.in6","r",stdin);

//freopen("SBT.outsplay6","w",stdout);

while(getint(c)) {

switch(c) {

case 0:

getint(x);

Insert(root,0,x);

break;

case 1:

getint(x);

Delete(root,x);

break;

case 2:

getint(x);

printf("%d\n",Search(root,x));

break;

case 3:

getint(x);

printf("%d\n",Select(root,x)); //x<S(root)

break;

case 4:

getint(x);

printf("%d\n",Rank(root,x)); //Search(x)>0

break;

default:

printf("\n\n\n");

}

return 0;

}

Tag Archives: Splay

[Dr.Lib]Note:Data Structures – Bottom-up SPLAY

Splay

Search/Insert/Rank/Select

Join

Delete

代码

朋友们

TAG CLOUD