二叉搜索树( BST )

概念

目的:为了提高查找的性能,其查找在平均情况下是 O(logn) ,接近二分查找效率

定义:若其左子树不为空,则其左子树上所有结点的值都小于其根结点的值,若其右子树不为空,则其右子树上所有结点的值都大于其根结点的值

特点:二叉搜索树的中序遍历的结果是一个非降的序列

基本操作

建树

必须有的参数时节点的值,其他的需要根据题意选择

1
2
3
4
5
6
int val[maxn];//表示节点i存的权值
int cnt[maxn];//表示节点i存的值出现的次数,也就是每个节点包含的副本数
int lc[maxn];//表示节点i的左孩子结点
int rc[maxn];//表示节点i的右孩子结点
int siz[maxn];//表示节点i的子树大小
int sum;//寄存指针,表示节点的数量

中序遍历

1
2
3
4
5
6
7
void print(int x){//遍历以x为根节点的二叉搜索树
if (!x)return ;//如果为空就直接结束
print(lc[x]);//先遍历左孩子
for(int i=0;i<cnt[x];++i)
printf("%d\n",val[x]);//输出根节点的值
print(rc[x]);//最后遍历右孩子
}

插入节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void insert(int &root,int v){//在以root为根节点的二叉搜索树中插入一个值为v的新节点
if(!root){//若root为空,直接返回一个值为v的新节点
root=++sum;
val[root]=v;
cnt[root]=siz[root]=1;
return;
}
siz[root]++;
if(val[root]==v){//若root的权值等于v,该节点的附加域该值出现的次数自增1。
cnt[root]++;
return ;
}
if(val[root]<v)insert(rc[root],v);//若root的权值小于v,在root的右子树中插入权值为v的节点
if(val[root]>v)insert(lc[root],v);//若root的权值大于v,在root的左子树中插入权值为v的节点
}

删除节点

分为三种情况:要删除的节点为空,为叶节点(或者只有一个子树),有两个子树

当节点有两个子树时最难删除,这里的做法是拿出右子树最小的节点代替被删除的节点

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
int deletemin(int &root){
if(!lc[root]){
int u=root;
root =rc[root];
return u;
}
else{
int u=deletemin(lc[root]);
siz[root]-=cnt[root];
return u;
}
}

void del(int &root,int v){//删除以root为根节点的值为v的节点
siz[root]--;
if (val[root]==v){//如果找到了值为v的节点
if (cnt[root]>1){//如果节点的cnt大于1直接cnt--
cnt[root]--;
return ;
}
if(lc[root]&&rc[root]){
int temp=root;
root=deletemin(rc[root]);//如果有两个非空子节点,就删除右子树中的最小值
lc[root]=lc[temp];
rc[root]=rc[temp];
}
else root=lc[root]+rc[root];//如果是叶子节点就直接删除,如果只有一个儿子节点,就用这个儿子节点替换
return ;
}
if(val[root]>v)del(lc[root],v);//如果当前节点的值大于v,则就去当前节点的左子树中找v
if(val[root]<v)del(rc[root],v);
}

查询值为 v 的节点排名

1
2
3
4
5
6
7
8
int queryrnk(int root,int v){//求值为v的元素的排名
if(val[root]==v)
return siz[lc[root]]+1;//左子树结点数+本身
if(val[root]>v)
return queryrnk(lc[root],v);
if(val[root]<v)
return queryrnk(rc[root],v)+siz[lc[root]]+cnt[root];
}

查询排名为 k 的节点值

1
2
3
4
5
6
7
int querykth(int root,int k){//查找排名为k的元素的值
if(siz[lc[root]]>=k)//当左子树的大小大于等于k时,说明排名为k的元素位于左子树中
return querykth(lc[root],k);
if(siz[lc[root]]<k-cnt[root])//当左子树的大小小于k - cnt时,说明排名为k的元素位于右子树中
return querykth(rc[root],k-siz[lc[root]]-cnt[root]);
return val[root];
}

查询值为 v 的节点的前去后继节点值

1
2
3
4
5
6
int getpre(int root,int v){//求值为v的节点的前驱
return querykth(root,queryrnk(root,v)-1);
}
int getnext(int root,int v){//求值为v的节点的后继
return querykth(root,queryrnk(root,v)+1);
}

板子总结

这个板子没有采用数组统计存入数据再递归建树,而是直接插入

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 <bits/stdc++.h>
const int maxn=1e5+5;//存入的最大数量
using namespace std;

int val[maxn];//表示节点i存的权值
int cnt[maxn];//表示节点i存的值出现的次数,也就是每个节点包含的副本数
int lc[maxn];//表示节点i的左孩子结点
int rc[maxn];//表示节点i的右孩子结点
int siz[maxn];//表示节点i的子树大小
int sum;//表示节点的数量

void print(int x){//遍历以x为根节点的二叉搜索树
if (!x)return ;//如果为空就直接结束
print(lc[x]);//先遍历左孩子
for(int i=0;i<cnt[x];++i)
printf("%d\n",val[x]);//输出根节点的值
print(rc[x]);//最后遍历右孩子
}

int find(int root,int x){//从根节点root开始查找值为x的元素,找到就返回其下标,否则返回-1
if(!root)
return -1;
if(val[root]==x)
return root;
else if(val[root]<x)
return find(rc[root],x);
else return find(lc[root], x);
}

void insert(int &root,int v){//在以root为根节点的二叉搜索树中插入一个值为v的新节点
if(!root){//若root为空,直接返回一个值为v的新节点
root=++sum;
val[root]=v;
cnt[root]=siz[root]=1;
return;
}
siz[root]++;
if(val[root]==v){//若root的权值等于v,该节点的附加域该值出现的次数自增1
cnt[root]++;
return ;
}
if(val[root]<v)insert(rc[root],v);//若root的权值小于v,在root的右子树中插入权值为v的节点
if(val[root]>v)insert(lc[root],v);//若root的权值大于v,在root的左子树中插入权值为v的节点
}

int deletemin(int &root){
if(!lc[root]){
int u=root;
root =rc[root];
return u;
}
else{
int u=deletemin(lc[root]);
siz[root]-=cnt[root];
return u;
}
}

void del(int &root,int v){//删除以root为根节点的值为v的节点
siz[root]--;
if (val[root]==v){//如果找到了值为v的节点
if (cnt[root]>1){//如果节点的cnt大于1直接cnt--
cnt[root]--;
return ;
}
if(lc[root]&&rc[root]){
int temp=root;
root=deletemin(rc[root]);//如果有两个非空子节点,就删除右子树中的最小值
lc[root]=lc[temp];
rc[root]=rc[temp];
}
else root=lc[root]+rc[root];//如果是叶子节点就直接删除,如果只有一个儿子节点,就用这个儿子节点替换
return ;
}
if(val[root]>v)del(lc[root],v);//如果当前节点的值大于v,则就去当前节点的左子树中找v
if(val[root]<v)del(rc[root],v);
}

int queryrnk(int root,int v){//求值为v的元素的排名
if(val[root]==v)
return siz[lc[root]]+1;
if(val[root]>v)
return queryrnk(lc[root],v);
if(val[root]<v)
return queryrnk(rc[root],v)+siz[lc[root]]+cnt[root];
}

int querykth(int root,int k){//查找排名为k的元素的值
if(siz[lc[root]]>=k)//当左子树的大小大于等于k时,说明排名为k的元素位于左子树中
return querykth(lc[root],k);
if(siz[lc[root]]<k-cnt[root])//当左子树的大小小于k - cnt时,说明排名为k的元素位于右子树中
return querykth(rc[root],k-siz[lc[root]]-cnt[root]);
return val[root];
}

int getpre(int root,int v){//求值为v的节点的前驱
return querykth(root,queryrnk(root,v)-1);
}

int getnext(int root,int v){//求值为v的节点的后继
return querykth(root,queryrnk(root,v)+1);
}

signed main(){
int n;cin>>n;//存入的数量
int root=0;//根节点
for(int i=0;i<n;++i){
int x;cin>>x;
insert(root,x);
}
return 0;
}

平衡树

引入:BST 存入递增或者递减序列时会退化为一条链表,时间复杂度最坏变为O(n)

目的:尽可能防止二叉树退化,维持树的深度为logn

解决:一般会给二叉搜索树附加一个平衡条件来可能限制任何节点深度过深

分类 Treap树 Splay树 AVL
限制条件 在二叉搜索树的基础上加了一个随机属性来保证堆的性质 增加一个Splay操作保持树的平衡 增加一个数组保证二叉搜索树的左子树和右子树的高度差不能超过1

Treap树

概念

定义:treap 是一种弱平衡的二叉搜索树。treap 这个单词是 tree 和 heap 的组合,表明 treap 是一种由树和堆组合形成的数据结构。 treap 的每个结点上要额外储存一个值 priority(优先级)。treap 除了要满足二叉搜索树的性质之外,还需满足父结点的 priority 大于等于两个儿子的 priority 。而 priority 是每个结点建立时随机生成的,因此 treap 是期望平衡的。

特点:满足二叉搜索树性质并且父节点的优先级不低于子节点而定优先级(即随机属性满足堆的性质)

基本操作

建树

节点基本属性:val(节点值)和 dat(随机值)

默认随机函数生成的数值越大优先级越高

注意:build 操作无论如何都要先执行,它涉及到根节点的初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int ch[maxn][2];//[i][0]代表i左儿子,[i][1]代表i右儿子
int val[maxn];//表示节点i存的权值
int dat[maxn];//表示节点i随机出来的优先级
int siz[maxn];//表示节点i的子树大小
int cnt[maxn];//表示节点i存的值出现的次数,也就是每个节点包含的副本数
int tot,root;//寄存指针和根节点

int node(int v){ //新增节点,
val[++tot]=v;//节点赋值
dat[tot]=rand();//随机优先级
siz[tot]=1;//目前是新建叶子节点,所以子树大小为1
cnt[tot]=1;//新建节点同理副本数为1
return tot;
}

void pushup(int id){//和线段树的pushup更新一样
siz[id]=siz[ch[id][0]]+siz[ch[id][1]]+cnt[id]; //本节点子树大小=左儿子子树大小+右儿子子树大小+本节点副本数
}

void build(){
root=node(-inf),ch[root][1]=node(inf);//先加入正无穷和负无穷,便于之后操作
pushup(root);//因为inf>-inf,所以是右子树,
}

插入节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void insert(int &id,int v){ // id依然是引用,在新建节点时可以体现
if(!id){
id=node(v); //若节点为空,则新建一个节点
return ;
}
if(v==val[id])
cnt[id]++;//若节点已存在,则副本数++;
else{//要满足BST性质,小于插到左边,大于插到右边
int d=v<val[id]?0:1;//这个d是方向的意思,按照BST的性质,小于本节点则向左,大于向右
insert(ch[id][d],v);//递归实现
if(dat[id]<dat[ch[id][d]])rotate(id,d^1);//(参考一下图)与左子节点交换右旋,与右子节点交换左旋
}
pushup(id); //现在更新一下本节点的信息
}

旋转节点

旋转实质是在满足 BST 的性质的基础上比较优先级,通过交换本节点和其某个叶子节点把链叉开成二叉形状从而控制深度

注意:旋转的时候操作对象是当前节点及其子节点,与父节点无关

1
2
3
4
5
6
7
void rotate(int &id, int d){// id是引用传递,d(irection)为旋转方向,0为左旋,1为右旋
int temp=ch[id][d^1];//旋转理解:找个动图看一看就好(或参见其他OIer的blog)
ch[id][d^1]=ch[temp][d];//这里讲一个记忆技巧,这些数据都是被记录后马上修改
ch[temp][d] = id;//所以像“Z”一样
id=temp; //比如这个id,在上一行才被记录过,ch[temp][d]、ch[id][d ^ 1]也是一样的
pushup(ch[id][d]), pushup(id);//旋转以后siz会改变,看图就会发现只更新自己和转上来的点,pushup一下,注意先子节点再父节点
}

删除结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void del(int &id,int v){
if(!id)return ;//到这了发现查不到这个节点,该点不存在,直接返回
if(v==val[id]){ //检索到了这个值
if(cnt[id]>1){
cnt[id]--,pushup(id);
return;
}//若副本不止一个,减去一个就好
if(ch[id][0]| ch[id][1]){//发现只有一个值,且有儿子节点,我们只能把值旋转到底部删除
if (!ch[id][1]||dat[ch[id][0]]>dat[ch[id][1]]){ //当前点被移走之后,会有一个新的点补上来(左儿子或右儿子),按照优先级,优先级大的补上来
rotate(id,1),del(ch[id][1],v); //我们会发现,右旋是与左儿子交换,当前点变成右节点;左旋则是与右儿子交换,当前点变为左节点
}
else rotate(id,0),del(ch[id][0],v);
pushup(id);
}
else id = 0;//发现本节点是叶子节点,直接删除
return;//这个return对应的是检索到值de所有情况
}
v<val[id]?del(ch[id][0],v):del(ch[id][1],v);//继续BST性质
pushup(id);
}

查询值为v的节点排名

1
2
3
4
5
6
7
8
int get_rank(int id,int v){
if(!id)return 0; //若查询值不存在,返回
if(v==val[id])
return siz[ch[id][0]]+1;//查询到该值,由BST性质可知:该点左边值都比该点的值(查询值)小,故rank为左儿子大小 + 1
else if (v<val[id])
return get_rank(ch[id][0],v);//发现需查询的点在该点左边,往左边递归查询
else return siz[ch[id][0]] + cnt[id] + get_rank(ch[id][1], v);//若查询值大于该点值。说明询问点在当前点的右侧,且此点的值都小于查询值,所以要加上cnt[id]
}

查询排名为k的节点值

1
2
3
4
5
6
7
8
int get_val(int id,int k){
if(!id)return inf;//一直向右找找不到,说明是正无穷
if(k<=siz[ch[id][0]])
return get_val(ch[id][0], k);//左边排名已经大于k了,说明k对应的值在左儿子那里
else if(k<=siz[ch[id][0]]+cnt[id])
return val[id];//上一步排除了在左区间的情况,若是k在左与中(目前节点)中,则直接返回目前节点(中区间)的值
else return get_val(ch[id][1],k-siz[ch[id][0]]-cnt[id]);//剩下只能在右区间找了,k减去左区间大小和中区间,继续递归
}

查询值为v的节点的前去后继节点值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int get_pre(int v){
int id=root, pre;//递归不好返回,以循环求解
while(id){//查到节点不存在为止
if(val[id]<v)
pre=val[id],id=ch[id][1];//满足当前节点比目标小,往当前节点的右侧寻找最优值
else id=ch[id][0];//无论是比目标节点大还是等于目标节点,都不满足前驱条件,应往更小处靠近
}
return pre;
}

int get_next(int v){
int id=root,next;
while(id){
if(val[id]>v)
next=val[id],id=ch[id][0];//同理,满足条件向左寻找更小解(也就是最优解)
else id = ch[id][1];//与上方同理
}
return next;
}

板子总结

这个板子没有采用用数组统计存入数据再递归建树,而是直接插入,但是还是要先调用build()初始化根节点

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
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=1000019,inf=0x3f3f3f3f;//存入节点最大数量

int read(){//快读
int out =0,flag=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') flag=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
out=out*10+c-'0';
c=getchar();
}
return flag*out;
}

int ch[maxn][2];//[i][0]代表i左儿子,[i][1]代表i右儿子
int val[maxn];//表示节点i存的权值
int dat[maxn];//表示节点i随机出来的优先级
int siz[maxn];//表示节点i的子树大小
int cnt[maxn];//表示节点i存的值出现的次数,也就是每个节点包含的副本数
int tot,root;//寄存指针和根节点

int node(int v){ //新增节点,
val[++tot]=v;//节点赋值
dat[tot]=rand();//随机优先级
siz[tot]=1;//目前是新建叶子节点,所以子树大小为1
cnt[tot]=1;//新建节点同理副本数为1
return tot;
}

void pushup(int id){//和线段树的pushup更新一样
siz[id]=siz[ch[id][0]]+siz[ch[id][1]]+cnt[id]; //本节点子树大小=左儿子子树大小+右儿子子树大小+本节点副本数
}

void build(){
root=node(-inf),ch[root][1]=node(inf);//先加入正无穷和负无穷,便于之后操作(貌似不加也行)
pushup(root);//因为inf>-inf,所以是右子树,
}

void rotate(int &id, int d){// id是引用传递,d(irection)为旋转方向,0为左旋,1为右旋
int temp=ch[id][d^1];//旋转理解:找个动图看一看就好(或参见其他OIer的blog)
ch[id][d^1]=ch[temp][d];//这里讲一个记忆技巧,这些数据都是被记录后马上修改
ch[temp][d] = id;//所以像“Z”一样
id=temp; //比如这个id,在上一行才被记录过,ch[temp][d]、ch[id][d ^ 1]也是一样的
pushup(ch[id][d]), pushup(id);//旋转以后siz会改变,看图就会发现只更新自己和转上来的点,pushup一下,注意先子节点再父节点
} //旋转实质是({在满足BST的性质的基础上比较优先级}通过交换本节点和其某个叶子节点)把链叉开成二叉形状(从而控制深度),可以看图理解一下

void insert(int &id,int v){ // id依然是引用,在新建节点时可以体现
if(!id){
id=node(v); //若节点为空,则新建一个节点
return ;
}
if(v==val[id])
cnt[id]++;//若节点已存在,则副本数++;
else{//要满足BST性质,小于插到左边,大于插到右边
int d=v<val[id]?0:1;//这个d是方向的意思,按照BST的性质,小于本节点则向左,大于向右
insert(ch[id][d],v);//递归实现
if(dat[id]<dat[ch[id][d]])rotate(id,d^1);//(参考一下图)与左子节点交换右旋,与右子节点交换左旋
}
pushup(id); //现在更新一下本节点的信息
}

void del(int &id,int v){
if(!id)return ;//到这了发现查不到这个节点,该点不存在,直接返回
if(v==val[id]){ //检索到了这个值
if(cnt[id]>1){
cnt[id]--,pushup(id);
return;
}//若副本不止一个,减去一个就好
if(ch[id][0]| ch[id][1]){//发现只有一个值,且有儿子节点,我们只能把值旋转到底部删除
if (!ch[id][1]||dat[ch[id][0]]>dat[ch[id][1]]){ //当前点被移走之后,会有一个新的点补上来(左儿子或右儿子),按照优先级,优先级大的补上来
rotate(id,1),del(ch[id][1],v); //我们会发现,右旋是与左儿子交换,当前点变成右节点;左旋则是与右儿子交换,当前点变为左节点
}
else rotate(id,0),del(ch[id][0],v);
pushup(id);
}
else id = 0;//发现本节点是叶子节点,直接删除
return;//这个return对应的是检索到值de所有情况
}
v<val[id]?del(ch[id][0],v):del(ch[id][1],v);//继续BST性质
pushup(id);
}

int get_rank(int id,int v){
if(!id)return 0; //若查询值不存在,返回
if(v==val[id])
return siz[ch[id][0]]+1;//查询到该值,由BST性质可知:该点左边值都比该点的值(查询值)小,故rank为左儿子大小 + 1
else if (v<val[id])
return get_rank(ch[id][0],v);//发现需查询的点在该点左边,往左边递归查询
else return siz[ch[id][0]] + cnt[id] + get_rank(ch[id][1], v);//若查询值大于该点值。说明询问点在当前点的右侧,且此点的值都小于查询值,所以要加上cnt[id]
}

int get_val(int id,int k){
if(!id)return inf;//一直向右找找不到,说明是正无穷
if(k<=siz[ch[id][0]])
return get_val(ch[id][0], k);//左边排名已经大于k了,说明k对应的值在左儿子那里
else if(k<=siz[ch[id][0]]+cnt[id])
return val[id];//上一步排除了在左区间的情况,若是k在左与中(目前节点)中,则直接返回目前节点(中区间)的值
else return get_val(ch[id][1],k-siz[ch[id][0]]-cnt[id]);//剩下只能在右区间找了,k减去左区间大小和中区间,继续递归
}

int get_pre(int v){
int id=root, pre;//递归不好返回,以循环求解
while(id){//查到节点不存在为止
if(val[id]<v)
pre=val[id],id=ch[id][1];//满足当前节点比目标小,往当前节点的右侧寻找最优值
else id=ch[id][0];//无论是比目标节点大还是等于目标节点,都不满足前驱条件,应往更小处靠近
}
return pre;
}

int get_next(int v){
int id=root,next;
while(id){
if(val[id]>v)
next=val[id],id=ch[id][0];//同理,满足条件向左寻找更小解(也就是最优解)
else id = ch[id][1];//与上方同理
}
return next;
}

signed main() {
build();//不要忘记初始化[运行build()会连同root一并初始化,所以很重要]
int t;t=read();
for(int i=1;i<=t;i++){
int cmd=read(),x=read();//操作选择和
if(cmd==1)
insert(root,x);//函数都写好了,注意:需要递归的函数都从根开始,不需要递归的函数直接查询
else if(cmd==2)
del(root,x);
else if(cmd==3)
printf("%d\n",get_rank(root,x)-1);//注意:因为初始化时插入了inf和-inf,所以查询排名时要减1(-inf不是第一小,是“第零小”)
else if (cmd==4)
printf("%d\n", get_val(root,x+1));//同理,用排名查询值得时候要查x + 1名,因为第一名(其实不是)是-inf
else if (cmd==5)
printf("%d\n",get_pre(x));
else if (cmd==6)
printf("%d\n",get_next(x));
}
return 0;
}
  • [ ] 还差个非旋转 Treap 树

Splay树(伸展树)

概念

定义:Splay 是一种二叉搜索树,它通过不断将某个结点旋转到根结点,使得整棵树仍然满足二叉搜索树的性质,并且保持平衡而不至于退化为链表

特点:每次操作都 Splay 一下使当前操作的节点上旋到根节点

Splay 的主要思想就是对于查找频率较高的结点,使其处于离根结点相对较近的结点。这样就提高了查找效率。

基本操作

建树

1
2
3
4
5
6
7
8
9
int sz;//表示当前节点个数
int rt;//表示当前根节点的编号
int f[N];//表示编号x节点的父亲的编号
int key[N];//表示编号为x的节点的对应的数值
int siz[N];//表示以编号为x的节点为根的子树的节点个数
int recy[N];//表示以编号为x的节点的数值重复次数
int son[N][2];
//son[x][0]表示以编号为x的节点的左儿子的编号
//son[x][1]表示以编号为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
void insert(int x){//插入节点
if(!rt){//树中没有一个节点
rt=++sz;
key[rt]=x;
siz[rt]=recy[rt] = 1;
son[rt][0]=son[rt][1]=0;//赋初值
return ;
}
int now=rt,fa=0;
while(1){
if(key[now]==x){//树中已有此点,重复+1
++recy[now];
update(now);update(fa);
splay(now);//splay一下,保证平衡
return ;
}
fa=now,now=son[now][x>key[now]];//满足二叉查找树的性质,往下跑
if(!now){
++sz;
key[sz] = x;
siz[sz] = recy[sz] = 1;//赋初值
f[sz] = fa;//父亲是fa
son[fa][x > key[fa]] = sz;//更新父亲的新儿子
update(fa);//更新父亲的siz
splay(sz);//splay一下,保证平衡
return ;
}
}
}

删除节点

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
void del(int x){
int no_use=find(x);//find主要是把当前数的对应点找到,然后旋到根,返回值的排名在这里没用
if(recy[rt]>1){//情况1:有重复,重复-1,更新,退出
--recy[rt];
update(rt);
return ;
}
//接下来都是没有重复的情况
if(!son[rt][0]&&!son[rt][1]){//情况2:没有儿子,直接清空
clear(rt);
rt=0;
return ;
}
if(!son[rt][0]){//情况3:没有左儿子,只有右儿子,右儿子变成根,清除自己
int tmp=rt;
f[rt=son[rt][1]]=0;
clear(tmp);
return ;
}
if(!son[rt][1]){//情况4:没有右儿子,只有左儿子,左儿子变成根,清除自己
int tmp=rt;
f[rt=son[rt][0]]=0;
clear(tmp);
return ;
}
//情况5:两个儿子都有,这是需要一个很简便的做法
//把前驱splay到根,保持左子树其他节点不用动
//原根右儿子变成前驱的右儿子
//原根功成身退,清除掉
//最后对前驱的siz进行更新
int tmp=rt,left=pre();
splay(left);
connect(son[tmp][1],rt,1);
clear(tmp);
update(rt);
}

上旋节点

上旋操作就是把当前节点向上移动一个深度,所以操作对象是当前节点以及其父节点和子节点

注意:和 Treap 的旋转节点操作原理一样,但是注意区分操作对象不同

1
2
3
4
5
6
7
void rotate(int x){//上旋x 
int fa=f[x],ffa=f[fa],m=get(x),n=get(fa);//确定x,fa的关系
connect(son[x][m^1],fa,m);//把要转的儿子转到父亲下,关系为m
connect(fa,x,m^1);//把父亲转到自己下面,关系为m^1
connect(x,ffa,n);//把自己转到父亲的父亲下,关系为n
update(fa),update(x);//先更新fa,再更新自己,可以自己想想为什么是这个顺序
}

连接节点

1
2
3
4
void connect(int x,int y,int z){//x连到y下面,关系为z 
if(x)f[x]=y;//存在x,则x的父亲为y
if(y)son[y][z]=x;//存在y,y的z关系儿子为x
}

Splay

Splay 操作是维持平衡的关键,每一个操作之后都要 Splay 一下,如果担心就有事没事都 Splay 一下

如果不考虑祖父节点、父节点和当前节点的关系随意上旋只会导致平衡树混乱,所以后两种情况两次上旋需要判断三个节点的关系

1
2
3
4
5
void splay(int x){//将x转到根节点
for(int fa;fa=f[x];rotate(x))//每次总是旋转自己
if(f[fa])rotate(get(x)==get(fa)?fa:x);//如果有爷爷(父亲的父亲),看父亲与父亲的父亲的关系决定转哪个
rt=x;//别忘了,把根赋为当前点
}

查询值为 v 的节点排名

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int find(int v){//查排名
int now=rt,ans=0;
while(1){
if(v<key[now]){
now=son[now][0];
continue;//在左子树中
}
ans+=siz[son[now][0]];//排名加上左子树节点个数
if(v==key[now]){
splay(now);
return ans+1;
}//值等于当前点,splay一下,保证平衡,排名+1为当前排名
ans+=recy[now];//排名加上当前节点的数的个数
now=son[now][1];//在右子树中
}
}

查询排名为 k 的节点值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int kth(int k){//查找排名为k的数
int now=rt;
while(1){
if(son[now][0]&&k<=siz[son[now][0]]){//在左子树中
now=son[now][0];
continue;
}
if(son[now][0])k-=siz[son[now][0]];//存在左儿子,排名减去左子树节点数
if(k<=recy[now]){
splay(now);
return key[now];
}//说明就是当前点,splay一下,保证平衡,退出
k-=recy[now];//排名减去当前节点数的个数
now=son[now][1];//在右子树中
}
}

查询根节点的前驱后继节点

注意:查询的结果是节点,要是想知道节点值要外套 key[]

那么如何查询某一个节点的前驱后继节点呢?因为每一个操作之后都会执行 Splay 使节点到达根节点,那么可以通过先插入要查询的节点使其到达根节点,然后在调用当前函数,最后在删除插入的节点来实现

1
2
3
4
5
6
7
8
9
10
11
int pre(){//前驱为左子树中最大的那个 
int now=son[rt][0];
while(son[now][1])now=son[now][1];
return now;
}

int nxt(){//后继为右子树中最小的那个
int now=son[rt][1];
while(son[now][0])now=son[now][0];
return now;
}

板子总结

这个板子没有采用数组统计存入数据再递归建树,而是直接插入

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
#include <bits/stdc++.h>
const int N=100010;
using namespace std;

int sz;//表示当前节点个数
int rt;//表示当前根节点的编号
int f[N];//表示编号x节点的父亲的编号
int key[N];//表示编号为x的节点的对应的数值
int siz[N];//表示以编号为x的节点为根的子树的节点个数
int recy[N];//表示以编号为x的节点的数值重复次数
int son[N][2];
//son[x][0]表示以编号为x的节点的左儿子的编号
//son[x][1]表示以编号为x的节点的右儿子的编号

inline int read(){//快读
int s=0,w =1;
char c=getchar();
for (;!isdigit(c);c=getchar())if(c=='-')w=-1;
for (;isdigit(c);c=getchar())s=(s<<1)+(s<<3)+(c^48);
return s*w;
}

void clear(int x){//清除
f[x]=key[x]=siz[x]=recy[x]=son[x][0]=son[x][1]=0;
//5个数组全部清零
}

int get(int x){//判断节点是父节点的左右孩子
return son[f[x]][1]==x;//如果自己是父亲的右儿子,返回1;否则返回0(0为左儿子,1为右儿子)
}

void update(int x){//更新节点参数
if(x){//如果这个点存在
siz[x]=recy[x];//自己重复的次数先累计
if(son[x][0])siz[x]+=siz[son[x][0]];
if(son[x][1])siz[x]+=siz[son[x][1]];
//如果存在儿子,把儿子的siz累积到自己
//然后发现一个问题,更新自己的siz时,必须保证儿子的siz是正确的
//所以后面的操作,当牵扯到儿子和父亲时,应该先更新新儿子,后更新新父亲
}
}

void connect(int x,int y,int z){//x连到y下面,关系为z
if(x)f[x]=y;//存在x,则x的父亲为y
if(y)son[y][z]=x;//存在y,y的z关系儿子为x
}

void rotate(int x){//上旋x
int fa=f[x],ffa=f[fa],m=get(x),n=get(fa);//确定x,fa的关系
connect(son[x][m^1],fa,m);//把要转的儿子转到父亲下,关系为m
connect(fa,x,m^1);//把父亲转到自己下面,关系为m^1
connect(x,ffa,n);//把自己转到父亲的父亲下,关系为n
update(fa),update(x);//先更新fa,再更新自己,可以自己想想为什么是这个顺序(因为fa此时变成了x的子节点,要自下而上更新)
}

void splay(int x){//将x转到根节点
for(int fa;fa=f[x];rotate(x))//每次总是旋转自己
if(f[fa])rotate(get(x)==get(fa)?fa:x);//如果有爷爷(父亲的父亲),看父亲与父亲的父亲的关系决定转哪个
rt=x;//别忘了,把根赋为当前点
}

void insert(int x){//插入节点
if(!rt){//树中没有一个节点
rt=++sz;
key[rt]=x;
siz[rt]=recy[rt] = 1;
son[rt][0]=son[rt][1]=0;//赋初值
return ;
}
int now=rt,fa=0;
while(1){
if(key[now]==x){//树中已有此点,重复+1
++recy[now];
update(now);update(fa);
splay(now);//splay一下,保证平衡
return ;
}
fa=now,now=son[now][x>key[now]];//满足二叉查找树的性质,往下跑
if(!now){
++sz;
key[sz] = x;
siz[sz] = recy[sz] = 1;//赋初值
f[sz] = fa;//父亲是fa
son[fa][x > key[fa]] = sz;//更新父亲的新儿子
update(fa);//更新父亲的siz
splay(sz);//splay一下,保证平衡
return ;
}
}
}

int find(int v){//查排名
int now=rt,ans=0;
while(1){
if(v<key[now]){
now=son[now][0];
continue;//在左子树中
}
ans+=siz[son[now][0]];//排名加上左子树节点个数
if(v==key[now]){
splay(now);
return ans+1;
}//值等于当前点,splay一下,保证平衡,排名+1为当前排名
ans+=recy[now];//排名加上当前节点的数的个数
now=son[now][1];//在右子树中
}
}

int kth(int k){//查找排名为k的数
int now=rt;
while(1){
if(son[now][0]&&k<=siz[son[now][0]]){//在左子树中
now=son[now][0];
continue;
}
if(son[now][0])k-=siz[son[now][0]];//存在左儿子,排名减去左子树节点数
if(k<=recy[now]){
splay(now);
return key[now];
}//说明就是当前点,splay一下,保证平衡,退出
k-=recy[now];//排名减去当前节点数的个数
now=son[now][1];//在右子树中
}
}

int pre(){//前驱为左子树中最大的那个
int now=son[rt][0];
while(son[now][1])now=son[now][1];
return now;
}

int nxt(){//后继为右子树中最小的那个
int now=son[rt][1];
while(son[now][0])now=son[now][0];
return now;
}

void del(int x){
int no_use=find(x);//find主要是把当前数的对应点找到,然后旋到根,返回值的排名在这里没用
if(recy[rt]>1){//情况1:有重复,重复-1,更新,退出
--recy[rt];
update(rt);
return ;
}
//接下来都是没有重复的情况
if(!son[rt][0]&&!son[rt][1]){//情况2:没有儿子,直接清空
clear(rt);
rt=0;
return ;
}
if(!son[rt][0]){//情况3:没有左儿子,只有右儿子,右儿子变成根,清除自己
int tmp=rt;
f[rt=son[rt][1]]=0;
clear(tmp);
return ;
}
if(!son[rt][1]){//情况4:没有右儿子,只有左儿子,左儿子变成根,清除自己
int tmp=rt;
f[rt=son[rt][0]]=0;
clear(tmp);
return ;
}
//情况5:两个儿子都有,这是需要一个很简便的做法
//把前驱splay到根,保持左子树其他节点不用动
//原根右儿子变成前驱的右儿子
//原根功成身退,清除掉
//最后对前驱的siz进行更新
int tmp=rt,left=pre();
splay(left);
connect(son[tmp][1],rt,1);
clear(tmp);
update(rt);
}

signed main(){
int t=read();
while(t--){
int opt=read(),x=read();
if(opt==1)insert(x);
if(opt==2)del(x);
if(opt==3)printf("%d\n",find(x));
if(opt==4) printf("%d\n",kth(x));
if(opt==5){
insert(x);
printf("%d\n",key[pre()]);
del(x);
}
if(opt == 6){
insert(x);
printf("%d\n",key[nxt()]);
del(x);
}
}
return 0;
}

拓展操作

其实上述的基本操作Splay树操作Treap树也完全可以,但是Splay树的强大远远没有体现出来,否则他它也不会有“序列之王”的称号了,Splay树因为上旋和Splay可以实现对序列的区间翻转、移动等操作

首先无疑的是伸展树的中序遍历可以按照顺序输出序列,很重要的一个操作是如何在伸展树中表示任意一个区间?

如果要提取 [a,b] 区间,那么将 a 前一个节点转到根节点,将 b 的后一个节点转到根节点的右边,则根节点的左子树就是我们想要的 [a,b] 区间

利用上述功能我们可以实现线段树所有的功能:在每个节点记录关于这个节点和以该节点为根的子树的信息,然后询问时先提取区间,在读取子树的信息。同时还可以对区间整体进行修改,利用类似线段树的“懒操作”标记,下次查询的时候如果发现标记就将标记释放到子节点然后向下查询子节点

除了实现线段树区间功能,Splay树还可以实现线段树无法实现的操作:

  • a 节点后面插入一数:先把要插入的数建成一个Splay树然后将 a 节点转到根节点并把 a 节点的后一个节点转到根节点的右边,最后将新建的这个树挂到根节点的右子节点的左子树上
  • 删除一个区间 [a,b] 的数:先提取出 [a,b] 区间然后直接删除
  • 翻转区间 [a,b] :先取出 [a,b] 区间然后通过“懒标记”记录,查询时存在标记就翻转当前节点左右子节点并下传标记

注意:没进行一次对序列的修改操作之后都要维护一下Splay树,即对受到影响的节点的参数进行更新,一种方法是对影响到的点自下而上进行更新操作,挥着直接将修改的节点旋转到根节点,因为旋转操作的同时会维护每个节点的值。另外一个问题是如果序列的第一个数字之前没有数字了,并且最后一个数字后边也没有数字了,此时再提取区间就会出现一些问题。为了防止进行过多的特殊判断,在序列的最前面和最后面分别放一个不影响操作结果的数(一般是负无穷和正无穷),在Splay树中就体现为两个节点。如此提取区间是原来的第k个数就变成了第 k+1 个数。

模板题:文艺平衡树(翻转指定区间)

因为题不涉及插入节点,所以采用数组先存数据再递归建树

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
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define N 100005//数组不用加倍 因为平衡树一个点对应一个点 而不是一段区间
#define mid ((l+r)>>1)

int sum=0,root=0;//寄存指针和根节点
int siz[N];
int key[N];//表示以编号为x的节点为根的子树的节点个数
int lazy[N];
int a[N];//
int fa[N];
int son[N][3];
//son[x][0]表示以编号为x的节点的左儿子的编号
//son[x][1]表示以编号为x的节点的右儿子的编号

void update(int s){//更新参数
siz[s]=siz[son[s][0]]+siz[son[s][1]]+1;
}//+1因为有它自己

int build(int f,int l,int r){//建树
if(l>r) return 0;
int s=++sum;
key[s]=a[mid]; fa[s]=f; lazy[s]=0;
son[s][0]=build(s,l,mid-1);//注意与线段树的差异:s记录的是mid这个点 而它的左右儿子分别记录l~mid-1 mid+1~r
son[s][1]=build(s,mid+1,r);
update(s);
return s;
}

int get(int x){ //判断自己是父节点的左右孩子
return (son[fa[x]][1]==x) ;
}

void pushdown(int x){//下传翻转标记
if(x&&lazy[x]){
lazy[son[x][0]]^=1;//向左右儿子传标记
lazy[son[x][1]]^=1;
swap(son[x][0],son[x][1]);//区间翻转
lazy[x]=0;
}
}

void rotate(int x){//上旋
int old=fa[x],oldf=fa[old],whison=get(x);
son[old][whison]=son[x][whison^1];
fa[son[old][whison]]=old;
fa[old]=x; son[x][whison^1]=old;
fa[x]=oldf;
if(oldf) son[oldf][son[oldf][1]==old]=x;
update(old),update(x);
}

void splay(int x,int tt){//将x旋到tt的右孩子节点
//其实这个操作旋了两次 一次是for结束时 一次是if判断后
for(int f;(f=fa[x])!=tt;rotate(x))
//判断旋两次后能不能到tt的儿子节点 如果能到 就不用旋了 直接通过for循环来旋
if(fa[fa[x]]!=tt) rotate(get(x)==get(f)?f:x);//如果在一条直线 就要先旋fa
if(!tt) root=x;
}

int get_rank(int x){//查询节点的排名
int now=root;
while(1){
pushdown(now);//查找排名时记得下传标记
if(x<=siz[son[now][0]]) now=son[now][0];
else{
x=x-siz[son[now][0]]-1;//与线段树不同的是 它不仅要减去儿子节点 还要减去它自己 因为它自己存了mid这个点
if(!x) return now;
now=son[now][1];
}
}
}

void turn(int l,int r){//翻转[l,r]区间
int x=get_rank(l),y=get_rank(r+2);//因为维护的是值域平衡树 所以要先找到在平衡树中的排位(也就是说对应着哪个点)
splay(x,0); splay(y,x);//把x旋到根节点(0是因为根的父亲是0) 把y旋到x的右节点
lazy[son[son[root][1]][0]]^=1;
}

void dfs(int now){
pushdown(now);
if(son[now][0]) dfs(son[now][0]);
if(key[now]!=-inf&&key[now]!=inf) printf("%d ",key[now]);//注意是key里面存储真正的值 而now只是平衡树的节点
if(son[now][1]) dfs(son[now][1]);
}

signed main(){
int n,m;
//scanf("%d%d",&n,&m);//n个数据,m次操作
cin>>n>>m;
for(int i=2;i<=n+1;i++)
a[i]=i-1;//从2开始存入n个数
a[1]=-inf; a[n+2]=inf;//为了防止区间翻转特殊判断分别加上正负无穷
root=build(0,1,n+2);//根是0,注意是1到 n+2因为加了正无穷和负无穷
int l,r;
while(m--){
//scanf("%d%d",&l,&r);
cin>>l>>r;
turn(l,r);//翻转操作
}
dfs(root);//中序遍历输出结果
system("pause");
return 0;
}

对比总结

以目前学习的阶段来看Treap树和Splay树的差异不大,代码复杂程度和效率都不相上下。但是 Splay 不需要额外的随机域,并且 Splay 的区间操作有时比较方便(虽然Treap树也可以强行区间修改但是失去了本身随机域维持期望平衡的意义)