从二叉查找树到平衡树

二叉查找树

BST性质

众所周知,二叉树有一种"堆性质"(每个节点的值大于或小于它的子节点的值),现在介绍二叉树上的另一种性质,如下:

  • 当前节点的值大于等于其左子树上的任何节点
  • 当前节点的值小于等于其右子树上的任何节点
  • 左右子树均满足该性质

注意这里是"大于等于"与"小于等于",不是严格大于或小于。

二叉查找树

查找

如图是一棵满足该性质的二叉树

所以这个性质有什么用呢?

在满足这个性质的二叉树上可以快速的查找某个节点:

比如在上面那张图中找 5252 我们的查找过程如下:

  1. 从根节点开始 86>5286 > 52 向左子树找
  2. 16<5216 < 52 向右子树找
  3. 32<5232 < 52 向右子树找
  4. 52=5252 = 52 找到了 返回结果

易得在满足此性质的二叉树中查找的时间复杂度取决于树高,在随机数据下期望树高为 O(logn)O(\log n) ,所以查找的期望(记住这个期望)时间复杂度就是 O(logn)O(\log n) 。由于优异的查找性能,这种二叉树被称为"二叉查找树"(Binary Search Tree,BST),而这种性质则被称为"BST性质"。

注意: 堆性质BST性质 是目前关于二叉树最重要的两个性质

C++实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//基础声明 后文若无特殊声明均使用此段代码
//std=c++14
struct Node{
int lc,rc,val;//左孩子,右孩子,值
}tree[10086];
int len,root;//用于创建节点
inline int newNode(int val){
tree[++len] = {0,0,val};
return len;
}

//BST-查找
int find(int id,int val){
if(!id) return -1;//没找到返回-1
if(tree[id].val > val) return find(tree[id].lc,val);//查询左子树
if(tree[id].val < val) return find(tree[id].rc,val);//查询右子树
return id;//如果不小于且不大于就必然等于 返回自身
}

插入

只有查找是不行的,还需要有插入操作

二叉查找树的插入也十分简单,只需要在查询时对查找路径上不存在的点执行插入操作。(为了简化操作先不考虑重复数据)

1
2
3
4
5
6
7
8
9
10
11
//BST-插入
void insert(int id,int val){//注意:此函数需要特判根节点是否为空
if(tree[id].val > val){
if(tree[id].lc) insert(tree[id].lc,val);//如果有左子树就递归
else tree[id].lc = newNode(val);//否则左子树是一个新节点
}
if(tree[id].val < val){//同上
if(tree[id].rc) insert(tree[id].rc,val);
else tree[id].rc = newNode(val);
}
}

可以使用引用简化代码(后文都将采用此写法)

1
2
3
4
5
6
7
8
9
int insert(int &id,int val){
if(!id){
id = newNode(val);//这里的id是引用,修改id就等于修改父节点的左孩子/右孩子
return;
}
if(tree[id].val > val) insert(tree[id].lc,val);//查询左子树
if(tree[id].val < val) insert(tree[id].rc,val);//查询右子树
//如果执行到这一行说明重复插入
}

Q:为什么没有删除?

A:一般不直接使用BST而是使用平衡树(原因见下文),而二叉查找树的删除极其难以实现(三种分类讨论),一般直接使用平衡树的特性实现删除,故一般不需要学习BST的删除。

如果真的很想了解可以经典算法Baidu搜索深刻体会

例题

这些就是二叉查找树的基本操作了。运用BST性质你可以完成很多其他操作:

例题:luoguP5076 普通二叉树 简化版

BST模板题,需要实现插入(insert),查排名(rnk),k小值(kth),前驱(pre),后继(nxt)五种操作。

插入很简单,刚才学过。但是查排名k小值前驱后继怎么办?

这里的节点需要额外维护一个size域,表示以当前节点为根的子树大小。

并且注意这道题的value可重,于是直接开一个count域维护相同value的节点数量

所以节点声明的代码相应的变为

1
2
3
4
5
6
7
8
struct Node{
int lc,rc,val,sz,cnt;//左孩子,右孩子,值,子树大小,数量
}tree[10086];
int root,len;
inline int newNode(int val){
tree[++len] = {0,0,val,1,1};
return len;
}

我们还需要一个pushup函数实现size域的更新。

1
2
3
inline void pushup(int id){
tree[id].sz = tree[tree[id].lc].sz + tree[tree[id].rc].sz + tree[id].cnt;
}

插入代码变为:

1
2
3
4
5
6
7
8
9
10
void insert(int &id,int val){
if(!id){
id = newNode(val);
return;
}
if(tree[id].val > val) insert(tree[id].lc,val);
else if(tree[id].val < val) insert(tree[id].rc,val);
else tree[id].cnt++;
pushup(id);//别忘了pushup
}

根据BST性质和刚才我们维护的size域就可以实现其他操作了(自己去手推一下就明白了)。

查排名:

修改版的查找操作

1
2
3
4
5
6
int rnk(int id,int val){
if(!id) return 1;
if(tree[id].val > val) return find(tree[id].lc,val);
if(tree[id].val < val) return find(tree[id].rc,val)+tree[id].sz-tree[tree[id].rc].sz;//如果val>当前节点上的值,说明val肯定比当前节点及它的左子树上的所有节点的值大
return tree[tree[id].lc].sz + 1;//如果val=当前节点上的值,说明val肯定比它左子树上的所有节点的值大 注意排名的定义是比val小的数的个数+1
}

k小值:

1
2
3
4
5
6
int kth(int id,int k){//别忘了排名(k)的意义是比val小的数的个数+1
if(!id) return -1;//没找到
if(k<=tree[tree[id].lc].sz) return kth(tree[id].lc,k);//比当前节点小的数的个数(排名-1) >= k 找左子树
else if(k<=tree[tree[id].lc].sz+tree[id].cnt) return tree[id].val;//小于等于当前节点的数的个数 >= k 返回当前值
return kth(tree[id].rc,k-tree[id].sz+tree[tree[id].rc].sz);//找右子树 k减去小于等于当前节点的数的个数
}

前驱&后继:

1
2
3
4
5
6
7
8
9
10
inline int pre(int val){
int rk = rnk(root,val);
if(rk==1) return -2147483647;
return kth(root,rk-1);
}
inline int nxt(int val){
int x = kth(root,rnk(root,val+1));
if(x==-1) return 2147483647;
return x;
}

完整版代码:

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
#include <iostream>
using namespace std;
struct Node{
int lc,rc,val,sz,cnt;
}tree[10086];
int root,len;
inline int newNode(int val){
tree[++len] = {0,0,val,1,1};
return len;
}
inline void pushup(int id){
tree[id].sz = tree[tree[id].lc].sz + tree[tree[id].rc].sz + tree[id].cnt;
}
void insert(int &id,int val){
if(!id){
id = newNode(val);
return;
}
if(tree[id].val > val) insert(tree[id].lc,val);
else if(tree[id].val < val) insert(tree[id].rc,val);
else tree[id].cnt++;
pushup(id);
}
int rnk(int id,int val){
if(!id) return 1;
if(tree[id].val > val) return rnk(tree[id].lc,val);
if(tree[id].val < val) return rnk(tree[id].rc,val)+tree[id].sz-tree[tree[id].rc].sz;
return tree[tree[id].lc].sz + 1;
}
int kth(int id,int k){
if(!id) return -1;
if(k<=tree[tree[id].lc].sz) return kth(tree[id].lc,k);
else if(k<=tree[tree[id].lc].sz+tree[id].cnt) return tree[id].val;
return kth(tree[id].rc,k-tree[id].sz+tree[tree[id].rc].sz);
}
inline int pre(int val){
int rk = rnk(root,val);
if(rk==1) return -2147483647;
return kth(root,rk-1);
}
inline int nxt(int val){
int x = kth(root,rnk(root,val+1));
if(x==-1) return 2147483647;
return x;
}
int q;
int main(){
cin >> q;
while(q--){
int op,x;
cin >> op >> x;
switch(op){
case 1:
cout << rnk(root,x) << endl;
break;
case 2:
cout << kth(root,x) << endl;
break;
case 3:
cout << pre(x) << endl;
break;
case 4:
cout << nxt(x) << endl;
break;
case 5:
insert(root,x);
break;
}
}
}

平衡树

关于BST,它死了

前面说过,二叉查找树的时间复杂度取决于树高,然而这个树高虽然期望是 logn\log n 级别 但是一旦遇到特殊构造的数据就会退化到 nn 级,然后得到 TLE\color{red}{\huge{\text{TLE}}}

"特殊构造数据"其实很简单,比如有序数据就可以卡掉不做优化的BST

比如依次插入1,2,3,4,5,6,7,8,你就会得到这么个玩意:

一叉查找链

可以发现二叉查找树退化成了一叉查找链链表,查询时间复杂度变成了惊人的 O(n)O(n)

我们肯定更希望自己的二叉查找树变成这样:

平衡树

图二与图一的树的内容完全一样,但是图二所示的树的树高只有 logn\log n 这正是我们希望看到的。从这里可以看出来,
对于相同的数据,二叉查找树可能有不同的结构。

我们希望有一种特殊的二叉查找树,它最好能够自动维持平衡,防止退化,这个时候就需要平衡树了。

旋转的二叉树

先介绍一下"旋转"操作,它能在不破坏BST性质的前提下交换当前节点与左孩子/右孩子。

旋转操作

右旋可以将父节点与左孩子交换(然后本来的左孩子的右孩子变成了本来的父节点),左旋可以将父节点与右孩子交换(然后本来的右孩子的左孩子变成了本来的父节点)。

一般将左旋称为zag,右旋称为zig

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void zig(int &id){
int p = tree[id].lc;
tree[id].lc = tree[p].rc;
tree[p].rc = id;
tree[p].sz = tree[id].sz;
pushup(id);
id = p;
}
void zag(int &id){
int p = tree[id].rc;
tree[id].rc = tree[p].lc;
tree[p].lc = id;
tree[p].sz = tree[id].sz;
pushup(id);
id = p;
}

Treap

不难发现,在随机数据下BST是趋近平衡的。但是作为一种在线数据结构,我们像不可能优化快排一样将输入数据随机打乱。

可以考虑在每个节点上新增一个weight域,每次新建节点时将weight域赋值为随机数。

1
2
3
4
5
6
7
8
9
struct Node{
int lc,rc,val,sz,cnt,w;
}tree[100010];
int root,len;
mt19937 mt(chrono::system_clock::to_time_t(chrono::system_clock::now()));//C++11 高性能随机数生成器 #include <random> & #include <chrono>
inline int newNode(int val){
tree[++len] = {0,0,val,1,1,(int)mt()};//w为随机数
return len;
}

然后呢?为了随机打乱这棵树,我们可以用weight域建一个堆。

堆的插入需要交换节点,还记得上面提到的旋转吗?

旋转操作可以交换父子节点,这样就可以维护堆性质了!把大根堆和BST进行结合,我们就得到了树堆(Treap,Tree+Heap=Treap)。

插入

先复习一下大根堆的插入:在最后一个节点后插入,如果当前节点值小于父节点值则交换。把它放到二叉查找树的插入里:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void insert(int &id,int val){
if(!id){
id = newNode(val);
return;
}
tree[id].sz++;//因为插入必定成功,所以路径上的每一个点都要更新(不用写pushup了)
if(tree[id].val > val){
insert(tree[id].lc,val);
if(tree[tree[id].lc].w > tree[id].w) zig(id);//如果父节点的w大于子节点就交换
}else if(tree[id].val < val){
insert(tree[id].rc,val);
if(tree[tree[id].rc].w > tree[id].w) zag(id);
}else tree[id].cnt++;//重复节点
}

删除

本来这个东西非常麻烦,需要三个分类讨论,但是我们现在有了旋转 (然而还是很麻烦) 。直接把待删除的节点转到叶子节点(或只有一个子节点的节点)然后直接删除即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void erase(int &id,int val){
if(!id) return;
if(tree[id].val==val){//找到了就开始删
if(tree[id].cnt>1){
tree[id].cnt--;
pushup(id);//千万不要忘了这个pushup! 每次写return前最好都检查一下
return;
}else{
if(!tree[id].lc||!tree[id].rc) id = tree[id].lc + tree[id].rc;//如果只有一个子节点或没有子节点就直接删除
else if(tree[tree[id].lc].w < tree[tree[id].rc].w) zig(id),erase(tree[id].rc,val);
else zag(id),erase(tree[id].lc,val);//如果有两个子节点把那个较小的旋上来然后向另一边递归
}
}else if(tree[id].val > val) erase(tree[id].lc,val);//标准的BST上查找
else erase(tree[id].rc,val);
pushup(id);//别忘了更新size域
}

由于Treap同时满足堆性质和BST性质,所以其他操作直接复制BST的就行。

例题

例题:luoguP3369 模板:普通平衡树

和上面那个普通二叉树基本上一样,只是增强了数据,多了删除操作,还改了下操作编号。

代码:

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
#include <iostream>
#include <random>
#include <chrono>
using namespace std;
struct Node{
int lc,rc,val,sz,cnt,w;
}tree[100010];
int root,len;
mt19937 mt(chrono::system_clock::to_time_t(chrono::system_clock::now()));
inline int newNode(int val){
tree[++len] = {0,0,val,1,1,(int)mt()};
return len;
}
inline void pushup(int id){
tree[id].sz = tree[tree[id].lc].sz + tree[tree[id].rc].sz + tree[id].cnt;
}
void zig(int &id){
int p = tree[id].lc;
tree[id].lc = tree[p].rc;
tree[p].rc = id;
tree[p].sz = tree[id].sz;
pushup(id);
id = p;
}
void zag(int &id){
int p = tree[id].rc;
tree[id].rc = tree[p].lc;
tree[p].lc = id;
tree[p].sz = tree[id].sz;
pushup(id);
id = p;
}
void insert(int &id,int val){
if(!id){
id = newNode(val);
return;
}
tree[id].sz++;
if(tree[id].val > val){
insert(tree[id].lc,val);
if(tree[tree[id].lc].w > tree[id].w) zig(id);
}else if(tree[id].val < val){
insert(tree[id].rc,val);
if(tree[tree[id].rc].w > tree[id].w) zag(id);
}else tree[id].cnt++;
}
void erase(int &id,int val){
if(!id) return;
if(tree[id].val==val){
if(tree[id].cnt>1){
tree[id].cnt--;
pushup(id);
return;
}else{
if(!tree[id].lc||!tree[id].rc) id = tree[id].lc + tree[id].rc;
else if(tree[tree[id].lc].w < tree[tree[id].rc].w) zig(id),erase(tree[id].rc,val);
else zag(id),erase(tree[id].lc,val);
}
}else if(tree[id].val > val) erase(tree[id].lc,val);
else erase(tree[id].rc,val);
pushup(id);
}
int rnk(int id,int val){
if(!id) return 1;
if(tree[id].val > val) return rnk(tree[id].lc,val);
if(tree[id].val < val) return rnk(tree[id].rc,val)+tree[id].sz-tree[tree[id].rc].sz;
return tree[tree[id].lc].sz + 1;
}
int kth(int id,int k){
if(!id) return -1;
if(k<=tree[tree[id].lc].sz) return kth(tree[id].lc,k);
else if(k<=tree[tree[id].lc].sz+tree[id].cnt) return tree[id].val;
return kth(tree[id].rc,k-tree[id].sz+tree[tree[id].rc].sz);
}
inline int pre(int val){
int rk = rnk(root,val);
if(rk==1) return -2147483647;
return kth(root,rk-1);
}
inline int nxt(int val){
int x = kth(root,rnk(root,val+1));
if(x==-1) return 2147483647;
return x;
}
int q;
int main(){
cin >> q;
while(q--){
int op,x;
cin >> op >> x;
switch(op){
case 1:
insert(root,x);
break;
case 2:
erase(root,x);
break;
case 3:
cout << rnk(root,x) << endl;
break;
case 4:
cout << kth(root,x) << endl;
break;
case 5:
cout << pre(x) << endl;
break;
case 6:
cout << nxt(x) << endl;
break;
}
}
}

Splay

访问局部性原理:

  • 最近刚刚被访问过的节点极易被再次访问(时间局部性)
  • 最近刚刚被访问过的节点的相邻节点极易被访问(空间局部性)

Splay(伸展树)是另一种平衡树实现。

由 Daniel Sleator 和 Robert Tarjan 发明 (怎么又是你)

Splay根据访问局部性原理设计,这种平衡树在访问节点后将它放在距离根节点较近的位置以增加查找速度。

Treap不同,Splay不需要实时保持全树平衡。它只需要在每次访问一个节点后将它旋转到根节点并在沿途的旋转操作中调整树高。

splay操作

splaySplay树的一种特殊操作。(这句话区分大小写)

splay操作通过一系列旋转将一个节点移动到平衡树的根节点(或其他节点)。

为了将节点移动到根节点,我们需要记录每个结点的父节点,这意味着需要重写节点定义和旋转操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct Node {//节点定义 ch[0]为左孩子 ch[1]为右孩子 fa为父节点
int ch[2], fa, val, sz, cnt;
} tree[100010];
int root, len;
inline int newNode(int val, int fa = 0) {
return tree[++len] = {{0, 0}, fa, val, 1, 1}, len;
}
inline int getlr(int id) {//辅助函数 判断节点是父节点的左孩子还是右孩子 0为左 1为右
return tree[tree[id].fa].ch[1] == id;
}
inline void pushup(int id) {
tree[id].sz = tree[tree[id].ch[0]].sz + tree[tree[id].ch[1]].sz + tree[id].cnt;
}
inline void rotate(int id) {//将节点旋转到自己父节点的位置 左右旋转写在同一个函数中
int fa = tree[id].fa, gf = tree[fa].fa, lr = getlr(id), ch = tree[id].ch[lr ^ 1];
//fa 父节点 gf 祖父节点 lr 当前节点是左孩子还是右孩子 ch 当前节点另一边(如果当前节点是父节点的左孩子则是当前节点的右孩子,反之同理)的孩子
tree[fa].ch[lr] = ch, tree[ch].fa = fa;//原父节点的孩子变成当前节点另一边的孩子,同时更新当前节点孩子的fa
tree[gf].ch[getlr(fa)] = id, tree[id].fa = gf;//原祖父节点的孩子变成当前节点,同时更新当前节点的fa
tree[id].ch[lr ^ 1] = fa, tree[fa].fa = id;//当前节点的孩子变成原父节点,同时更新原父节点的fa
pushup(fa), pushup(id);//因为旋转后fa是id的子节点,所以先更新fa再更新id
}

逐层伸展(spaly)

图片来自Freddie的洛谷博客

有了旋转操作,splay怎么实现就一目了然了。

逐层伸展

于是我们可以很容易的写出splay操作的代码:

1
2
3
4
5
//将节点旋转成goal的孩子,goal=0时旋转到根节点
inline void spaly(int id, int goal = 0) {
while(tree[id].fa != goal) rotate(id);
if(!goal) root = id;
}

但这样做有一个致命的问题:可以被恶意构造的数据卡成 O(n)O(n)

如图:

逐层伸展-危

可见只需要几个简单的单调数据就可以把平衡树卡成一叉查找链。

双层伸展(splay)

为了解决这个致命的问题,我们引入双层伸展。

根据平衡树的结构,大致可将splay操作需要处理的类型分为两种。

zigzig/zagzag型

双旋-zigzig

当祖父节点,父亲节点与当前节点在同一条直线上时,先旋转父亲节点再旋转当前节点。

zigzag/zagzig型

双旋-情况2

当祖父节点,父亲节点与当前节点不在同一条直线上时,直接按照逐层伸展的方式处理即可。

这样即可得到双层伸展的splay操作:

1
2
3
4
5
6
7
8
9
10
11
inline void splay(int id, int goal = 0) {
while(tree[id].fa != goal) {
int fa = tree[id].fa, gf = tree[fa].fa;
if(gf != goal) {
if(getlr(id) == getlr(fa)) rotate(fa);//zigzig/zagzag
else rotate(id);//zigzag/zagzig
}
rotate(id);
}
if(!goal) root = id;
}

对比一下逐层伸展和双层伸展:

双层伸展

可见双层伸展每次可让树高大致减少一半。

因此当毒瘤出题人试图去访问一条长链时,每次访问都会让树高减少一半。

虽然每次操作时间复杂度最差为 O(n)O(n) ,但Splay树的均摊复杂度为 O(n)+O(n/2)+O(n/4)+O(n/8)+...+O(1)=O(nlogn)O(n) + O(n/2) + O(n/4) + O(n/8) + ... + O(1) = O(n \log n)

查找

由于在Splay中查找后会导致被查找结点旋转到根节点,所以Splay中查找是一个很有用的操作。

这个函数查找的是小于等于val的最大节点,如果val在平衡树中会被旋转到根节点,否则将val的前驱旋转到根节点。

1
2
3
4
5
6
7
int find(int val) {
if(!root) return -1;
int p = root;
while(tree[p].ch[tree[p].val < val] && tree[p].val != val) p = tree[p].ch[tree[p].val < val];
splay(p);//找到了就转到根节点
return p;
}

前驱/后继

有了find函数后就十分容易实现。

查找前驱只需要find(x)后在根节点的左子树上找最大值(如果根节点就是x的前驱直接返回就好,否则左子树的最大值就是小于x的最大值,即为前驱)。

查找后继同理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
inline int pre(int x) {
find(x);
if(tree[root].val < x) return root;//如果根节点就是x的前驱那么直接返回
int id = tree[root].ch[0];//根节点的左子树
while(tree[id].ch[1]) id = tree[id].ch[1];//向右爬
splay(id);//别忘了把被查找结点转上去
return id;
}
inline int nxt(int x) {
find(x);
if(tree[root].val > x) return root;
int id = tree[root].ch[1];
while(tree[id].ch[0]) id = tree[id].ch[0];
splay(id);
return id;
}

查排名

几乎是为find函数量身定制的。

find(val)后全部比val小的节点都会在根节点的左子树上,所以只需要输出根节点左子树的大小+1即可。

1
2
3
4
inline int rnk(int val) {
find(val);
return tree[tree[root].ch[0]].sz + 1;
}

删除

显然,一个数的前驱和后继之间只可能有它自己。

1
2
3
4
5
6
7
8
9
void erase(int val) {
int p = pre(val), q = nxt(val);//找前驱后继
splay(p), splay(q, p);//把前驱转到根节点,后继转到前驱的(右)孩子
int id = tree[q].ch[0];//此时后继的左孩子上即为大于前驱小于后继的节点,就是要删除的节点
if(tree[id].cnt > 1) tree[id].cnt--,tree[id].sz--, splay(id);//如果元素数量大于一就删掉一个然后转到根节点
else tree[q].ch[0] = 0;//如果只剩下一个就直接扔掉就好了
pushup(q);//别忘了更新
pushup(p);
}

但是这样删除会出现问题:如果val的前驱或后继不存在整棵树会爆炸(把一个不存在的节点转到根节点?)。

因此需要在建树时插入两个值为 infinfinf-inf 的哨兵节点。相应的,kth操作和rnk操作也需要特殊的处理。

Splay树的其他操作和其他平衡树一致,只是别忘了在访问节点后进行splay操作。

给出普通平衡树的代码:

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
#include <iostream>
using namespace std;
const int inf = 2147483647;
struct Node {
int ch[2], fa, val, sz, cnt;
} tree[100010];
int root, len;
inline int newNode(int val, int fa = 0) {
return tree[++len] = {{0, 0}, fa, val, 1, 1}, len;
}
inline int getlr(int id) {
return tree[tree[id].fa].ch[1] == id;
}
inline void pushup(int id) {
tree[id].sz = tree[tree[id].ch[0]].sz + tree[tree[id].ch[1]].sz + tree[id].cnt;
}
inline void rotate(int id) {
int fa = tree[id].fa, gf = tree[fa].fa, lr = getlr(id), ch = tree[id].ch[lr ^ 1];
tree[fa].ch[lr] = ch, tree[ch].fa = fa;
tree[gf].ch[getlr(fa)] = id, tree[id].fa = gf;
tree[id].ch[lr ^ 1] = fa, tree[fa].fa = id;
pushup(fa), pushup(id);
}
inline void splay(int id, int goal = 0) {
while(tree[id].fa != goal) {
int fa = tree[id].fa, gf = tree[fa].fa;
if(gf != goal) {
if(getlr(id) == getlr(fa)) rotate(fa);
else rotate(id);
}
rotate(id);
}
if(!goal) root = id;
}
int find(int val) {
if(!root) return -1;
int p = root;
while(tree[p].ch[tree[p].val < val] && tree[p].val != val) p = tree[p].ch[tree[p].val < val];
splay(p);
return p;
}
void insert(int &id, int fa, int val) {
if(!id) {
splay(id = newNode(val, fa));
return;
}
if(tree[id].val == val) tree[id].cnt++, splay(id);
else insert(tree[id].ch[tree[id].val < val], id, val);
}
inline int rnk(int val) {
find(val);
return tree[tree[root].ch[0]].sz + 1;
}
int kth(int id, int k) {
if(!id) return -1;
if(k <= tree[tree[id].ch[0]].sz) return kth(tree[id].ch[0], k);
else if(k <= tree[tree[id].ch[0]].sz + tree[id].cnt) return splay(id), tree[id].val;
return kth(tree[id].ch[1], k - tree[id].sz + tree[tree[id].ch[1]].sz);
}
inline int pre(int x) {
find(x);
if(tree[root].val < x) return root;
int id = tree[root].ch[0];
while(tree[id].ch[1]) id = tree[id].ch[1];
splay(id);
return id;
}
inline int nxt(int x) {
find(x);
if(tree[root].val > x) return root;
int id = tree[root].ch[1];
while(tree[id].ch[0]) id = tree[id].ch[0];
splay(id);
return id;
}
void erase(int val) {
int p = pre(val), q = nxt(val);
splay(p), splay(q, p);
int id = tree[q].ch[0];
if(tree[id].cnt > 1) tree[id].cnt--, tree[id].sz--, splay(id);
else tree[q].ch[0] = 0;
pushup(q);
pushup(p);
}
int q;
int main() {
insert(root, 0, inf), insert(root, 0, -inf);
cin >> q;
while(q--) {
int op, x;
cin >> op >> x;
switch(op) {
case 1:
insert(root, 0, x);
break;
case 2:
erase(x);
break;
case 3:
cout << rnk(x) - 1 << endl;
break;
case 4:
cout << kth(root, x + 1) << endl;
break;
case 5:
cout << tree[pre(x)].val << endl;
break;
case 6:
cout << tree[nxt(x)].val << endl;
break;
}
}
system("pause");
return 0;
}

热知识:使用逐层伸展(即"单旋",同样的,双层伸展称为"双旋")的Splay树一般被称为Spaly。这个名字来源于luoguP3721 单旋

在随机数据下单旋Splay的常数比双旋Splay小。(普通平衡树中无论吸不吸O2单旋都比双旋快 5070ms50-70ms