平衡树——Treap&Splay

Dylan 收录于 OI 和数据结构树

2018-03-07 2025-08-16 约 2100 字预计阅读 5 分钟 - 次阅读 - 条评论

平衡树——Treap&Splay

平衡树学习总结 2016-12-29

概述

朴素的BST有时会退化成一条链，从而使二分查找的效率大大降低，为了防止这种情况的发生,平衡树应运而生。

顾名思义，平衡树的各个子树的深度应该相等或者相似。

两种基本操作：左旋&右旋 zig()&zag()

保证平衡树仍然满足BST的性质，但能够调换节点在树中的相对位置。

其余操作： insert(),delete(),findKth(),findRank(),precursor()//pre(),successor()//suc()

两种常用的平衡树：

1. Treap =Tree+heap

靠随机化减小退化的概率。

1
2
3
4
5
6
7
8
struct node
{
	int v,fix,l,r,weight,size;
	node()
	{
		v=fix=l=r=weight=size=0;
	}
}treap[100005];

插入：

插入时由随机数决定改变该节点的位置。

我们使用fix存放随机数，且Treap中fix应满足堆的性质（小根堆或大根堆，但在代码中要保证一致）。因此在按照BST的插入方法插入完毕后，fix=Rand();再通过左右旋使其满足堆。

删除：

与BST类似，但删去节点后要判断其子节点fix是否满足堆的性质，逐层修改。

其余操作与BST基本相同。

另外大部分操作函数的参数最好使用传引用的方式（int& k），减少手动修改。

完整代码：（需保证各种操作的元素一定已经在树内）

luogu3369

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<ctime>
using namespace std;
struct node
{
	int v,fix,l,r,weight,size;
	node()
	{
		v=fix=l=r=weight=size=0;
	}
	inline int lsize();
	inline int rsize();
}tree[100005];
int& start=tree[0].r;//存放树的虚拟根
#define now tree[k]//在各种操作中简化代码
#define son tree[y]
int amount=0;
inline int node::lsize()
{
	if(l==0)return 0;
	else return tree[l].size;
}
inline int node::rsize()
{
	if(r==0)return 0;
	else return tree[r].size;
}
inline node& left(node k)
{
	return tree[k.l];
}
inline node& right(node k)
{
	return tree[k.r];
}
inline bool isLeave(node k)//判断叶子节点
{
	return (bool)k.l==0&&k.r==0;
}
inline void rt(int& k)
{
	int y=now.l;
	now.l=son.r;//swap the subtree
	son.r=k;
	k=y;
	y=now.r;//needless if not use size but important
	son.size=son.lsize()+son.rsize()+son.weight;
	now.size=now.lsize()+now.rsize()+now.weight;
}
inline void lt(int& k)
{
	int y=now.r;
	now.r=son.l;//swap the subtree
	son.l=k;
	k=y;
	y=now.l;
	son.size=son.lsize()+son.rsize()+son.weight;
	now.size=now.lsize()+now.rsize()+now.weight;
}
inline void insert(int& k,int key)
{
	if(k==0)//新建
	{
		k=++amount;
		now.v=key;
		now.fix=rand();
		now.l=now.r=0;
		now.weight=1;
		now.size=1;
	}
	else 
	{
		if(key<now.v)
		{
			++now.size;//先加后递归 
			insert(now.l,key);
			if(now.fix<left(now).fix)
			{
				rt(k);
			}
		}
		else if(key>now.v)
		{
			++now.size;
			insert(now.r,key);
			if(now.fix<right(now).fix)
			{
				lt(k);
			}
		}
		else //key==now.v
		{
			++now.size;//勿忘
			++now.weight;
		}
	}
}
inline void remove(int &k,int key)
{
	if(k==0)return;

	if(now.v!=key)
	{
		if(now.l!=0&&key<now.v)
		{
			remove(now.l,key);
			--now.size; //先递归再减 
		}
		else if(now.r!=0&&key>now.v)
		{
			remove(now.r,key);
			--now.size; 
		}
		return;
	}
	if(now.weight>1)
	{
		--now.weight;
		--now.size;// don't forget this one
		return ;
	}
	if(isLeave(now))
	{
		k=0;
		return;
	}
	else if(now.l==0)
	{
		k=now.r;
		return;
	}
	else if(now.r==0)
	{
		k=now.l;
		return;
	}
	else
	{
		if(left(now).fix<right(now).fix)
		{
			lt(k);
			remove(now.l,key);
			--now.size; 
		}
		else 
		{
			rt(k);
			remove(now.r,key);
			--now.size; 
		}
	}
}
int MAX,MIN;//供pre()&suc()使用
inline int pre(int k,int key)
{
	if(k==0)return MAX;
	if(now.v<key)
	{
		MAX=now.v;
		pre(now.r,key);
	}
	else 
	{
		pre(now.l,key);
	}
	return MAX;
}
inline int suc(int k,int key)
{
	if(k==0)return MIN;
	if(now.v>key)
	{
		MIN=now.v;
		suc(now.l,key);
	}
	else 
	{
		suc(now.r,key);
	}
	return MIN;
}
inline int findkth(int k,int key)
{
	if(key<now.lsize()+1)
	{
		return findkth(now.l,key);
	}
	else if(key>now.lsize()+now.weight)
	{
		return findkth(now.r,key-now.lsize()-now.weight);
	}
	else return now.v;
}
inline int findrank(int k,int key,int cur=0)
{
	if(now.v==key)
	{
		return now.lsize()+cur+1;
	}
	else if(key<now.v)
	{
		return findrank(now.l,key,cur);
	}
	else if(key>now.v)
	{
		return findrank(now.r,key,cur+now.lsize()+now.weight);
	}
}
void midq(int &k)//中序遍历输出
{
	if(k==-1)return;
	if(now.l!=0)
	{
		midq(now.l);
	}
	for(int i=1;i<=now.weight;++i)printf("%d ",now.v);
	if(now.r!=0)
	{
		midq(now.r);
	}
}
inline void init()
{
 	   srand(time(NULL));
}
int main()
{
	int n,opt,x;
	init();
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&opt,&x);
		switch (opt)
		{
			case 1:insert(start,x);break;
			case 2:remove(start,x);break;
			case 3:printf("%d\n",findrank(start,x));break;
			case 4:printf("%d\n",findkth(start,x));break;
			case 5:printf("%d\n",pre(start,x));break;
			case 6:printf("%d\n",suc(start,x));break;
		}	
		//printf("\t");midq(start);printf("\n");
	}
	return 0;
}

2. Splay（伸展树）

又名自调整二叉树，在每次操作时将目标节点旋到根。

可以实现区间操作（例如区间翻转）。

在Splay中，满足BST性质的是节点对应在数组（不是存树的数组）中的下标，因此需要一个变量存放之。

1
2
3
4
5
6
7
8
9
struct Splay
{		
	int root;
	
	int f[maxn],c[maxn][2];
	#define lc(i) (c[i][0])
	#define rc(i) (c[i][1])
	int size[maxn];
};

基本操作：Splay() 伸展

将将目标节点旋到根。为了提高效率我们使用双旋，即一次判断两层的情况。

区间操作：

可以借鉴线段树中的lazy-tag思想，在使用到子节点时下放tag，减少冗余操作。对于翻转的父节点，需要重新计算在数组中的下标值。

另外Splay因为使用双旋，所以在节点中的各种操作需要用到节点的father，因此各种操作函数的参数最好不要使用传引用（还是手动改比较靠谱）。

左右旋与Treap有些许区别：

Treap的zig(k)是将k的左节点旋上来，而Splay的zig(k)是把k旋到它的父节点（k是k.father的左子树）。
Splay的旋转操作需要修改f值。

完整代码：~~（因为传的引用至今未调试成功，计划重构）~~已重构√

例题:luogu3391 Bzoj3223 Tyvj1729

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
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
/*
luogu3391
splay
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
template<typename T>
void read(T& w)
{
	char r;int f=1;
	for(r=getchar();(r!='-')&&(r<48||r>57);r=getchar());
	if(r=='-')f=-1,r=getchar();
	for(w=0;r>=48&&r<=57;r=getchar())w=w*10+r-48;
	w*=f;
}
template<typename T>
void write(T w,char c=0)
{
	if(w<0)putchar('-'),w=-w;
	if(w>9)write(w/10);
	putchar(char(w%10+48));
	if(c)putchar(c);
}
const int maxn=100003;
//Splay
int n,m;
struct Splay
{
		
	int root;
	
	int f[maxn],c[maxn][2];
	#define lc(i) (c[i][0])
	#define rc(i) (c[i][1])
	int size[maxn];
	bool rev[maxn];
	void update(int x)
	{
		size[x]=size[lc(x)]+size[rc(x)]+1;
	}
	void tagdown(int x)
	{
		if(rev[x])
		{
			swap(lc(x),rc(x));
			rev[lc(x)]^=1,rev[rc(x)]^=1;
			rev[x]=0;
		}
	}
	void rotate(int x,int& k)
	{
		int y=f[x],z=f[y],d;
		if(x==lc(y)) d=1;
		else d=0;
		if(y==k)k=x;
		else
		{
			if(y==lc(z)) lc(z)=x;
			else rc(z)=x;
		}
		f[x]=z,f[y]=x,f[c[x][d]]=y;
		c[y][d^1]=c[x][d],c[x][d]=y;
		update(y),update(x);
	}
	void splay(int x,int& k)
	{
		while(x!=k)
		{
			int y=f[x],z=f[y];
			if(y!=k)
			{
				if(x==lc(y) ^ y==lc(z))
					rotate(x,k);
				else rotate(y,k);
			}
			rotate(x,k);
		}
	}
	int find(int x,int rank)
	{
		tagdown(x);
		if(size[lc(x)]+1==rank)return x;
		if(rank<=size[lc(x)])
			return find(lc(x),rank);
		return find(rc(x),rank-size[lc(x)]-1);
	}
	void rever(int l,int r)
	{
		int x=find(root,l),y=find(root,r+2);
		splay(x,root),splay(y,rc(x));
		rev[lc(y)]^=1;
	}
	void build(int l,int r,int fa)
	{
		int k;
		if(l==r)
			size[k=l]=1;
		else
		{
			k=(l+r)/2;
			if(l<=k-1)build(l,k-1,k);
			if(k+1<=r)build(k+1,r,k);
			update(k);
		}
		f[k]=fa;
		if(k<fa)lc(fa)=k;
		else rc(fa)=k;
	}
	void init()
	{
		build(1,n+2,0);
		root=(n+3)/2;
	}
}splay;

void output();
void solve()
{
	splay.init();
	for(int i=1,l,r;i<=m;++i)
	{
		read(l),read(r);
		splay.rever(l,r);
		//output();
	}
}
void output()
{
	for(int i=2;i<=n+1;++i)
		write(splay.find(splay.root,i)-1,i==n+1?'\n':' ');
}
int main()
{
	freopen("luogu3391#1.in","r",stdin);
	//freopen("luogu3391.out","w",stdout);
	read(n),read(m);
	solve();
	output();
	return 0;
}

参考

%%%黄学长的Splay模板

收录于合集・数据结构 14

DancingLinksX|精确覆盖&重复覆盖四分树

收录于合集・树 7

扫描线四分树