Splay Tree学习笔记

Splay Tree学习笔记

syysongyuyang
  2023-02-12 15:20:04 2023-02-12 15:20 创建   2023-03-29 16:09:43 2023-03-29 16:09 更新  

Splay Tree’s Introduction

$Splay$树简介

$Splay$树是伸展树，一种平衡树

相较于$Treap$的随机编号，$Splay$的$splay$操作可以有效地将树高保持在$\log n$

首先要有二叉搜索树的性质，即$\forall u,lson(u) < rson(u)$

维护物 子树大小 左右儿子 父亲 数的个数 价值

基本操作

get操作：判断点是左儿子还是右儿子

1
inline int get(int x) {int fa=t[x].fa;return x==t[fa].ch[1];}

pushup操作：统计子树大小

1
2
inline void pushup(int u) 
	{t[u].son=t[t[u].ch[1]].son+t[t[u].ch[0]].son+t[u].cnt;}

rotate操作：左旋，右旋

1
2
3
4
5
6
7
8
9
inline void rotate(int x)
{
    int y=t[x].fa,z=t[y].fa;
    int chk=get(x);
    t[y].ch[chk]=t[x].ch[chk^1],t[t[y].ch[chk]].fa=y;
    t[x].ch[chk^1]=y,t[y].fa=x,t[x].fa=z;
    if (z) t[z].ch[t[z].ch[1]==y]=x;
    pushup(y),pushup(x);
}

分析一下旋转操作：

$1.$将$y$原来的儿子$x$的位置变成$x$的儿子，将这个点指向$y$

$2.$将$x$的另一个儿子指向$y$，$y$的父亲指向$x$，$x$的父亲指向$y$

$3.$如果$y$原来的父亲$z$存在，就将$z$原来$y$所处儿子的位置指向$x$

$4.$重新计算$y,x$的子树大小

$Q:$为什么先算$y$？

$A:$ $x$的子树大小依赖于$y$，这样保证答案正确

$Splay$操作

这块便是$Splay$树的精华

我们通过$Splay$操作，保证了树高为$\log n$

这里有一个规定：每访问一个点$u$，就要将$u$旋转至$root$

这里一共有三种操作$zig,zig-zig,zig-zag$

1
2
3
4
5
6
7
8
9
10
11
inline void splay(int u,int& goal)
{
	int fa=t[goal].fa;
    while (fa!=t[u].fa)
    {
        if (t[t[x].fa].fa!=f)
            rotate(get(x)==get(t[x].fa)?t[x].fa:x);
       	rotate(x);
    }
    goal=x;
}

插入

插入算是一个比较复杂的操作

首先需要判断是否非空，若为空，插入$root$

其次，需要判断点是否存在，存在则t[u].cnt++

否则，则插入节点$u$

注意每次都要进行splay和pushup操作

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
inline void insert(int x)
{
    if (!root)
    {
        root=++tot;
        t[root].val=x;
        t[root].cnt=1;
        pushup(root);
        return ;
    }
    int u,fa;
    u=fa=root;
    while (u && t[u].val!=x) fa=u,u=t[u].ch[x>val];
    if (!u)//不存在，新插入u
    {
        u=++tot;
        t[u].val=x;
        t[u].cnt=1;
        t[u].fa=fa;
        t[fa].ch[x>t[fa].x]=x;
        pushup(u);
        splay(u,root);
        return ;
    }
    //存在
    t[u].cnt++;
    pushup(u);
    splay(u,root);
}

删除

删除也是一个比较复杂的操作

考虑将点$u$旋至$root$，然后根据cnt已经左右子树情况分类讨论

$1.$cnt>1，考虑将cnt--

$2.$cnt==1，左，右子树均为空，树为空

$3.$cnt==1，左子树为空，右子树为根。右子树有空同理

$4.$cnt==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
inline void del(int x)
{
    rank(x);
    if (t[root].cnt>1)
    {
        t[root].cnt--;
        pushup(root);
        return ;
    }
    if (!t[root].ch[0] && !t[root].ch[1])
    {
        t[root].clear();
        root=0;
        return ;
    }
    else if (!t[root].ch[0])
    {
        root=t[root].ch[1];
        t[root].fa=0;
    }
    else if (!t[root].ch[1])
    {
        root=t[root].ch[0];
        t[root].fa=0;
    }
    else
    {
        int u=t[root].ch[0];
        while (t[u].ch[1])
        	u=t[u].ch[1];
        splay(u,t[root].ch[0]);
        t[u].ch[1]=t[root].ch[1];
        t[t[root].ch[1]].fa=u;t[u].fa=0;
        pushup(u);
        root=u;
    }
}

查询前驱后继

对于值$x$，如果$x>val_u$，则往右子树查找，否则往左子树查找

基于此，我们可以查询前驱，后继。

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
inline int pre(int x)
{
    int res,u=root;
    while (u)
    {
        if (x>t[u].val)
        {
            res=t[u].val;
            u=t[u].ch[1];
        }
        else u=t[u].ch[0];
    }
    return res;
}
inline int next(int x)
{
    int res,u=root;
    while (u)
    {
        if (x<t[u].val)
        {
            res=t[u].val;
            u=t[u].ch[0];
        }
        else u=t[u].ch[1];
    }
    return res;
}

查询$x$的排名

将点$u$找到后翻到根，然后记录左子树size+1就是答案

或者可以根据二叉搜索树的性质来搞，一样的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
inline int rank(int x)
{
    int res=0,u=root;
    while (true)
    {
        if (x<t[u].val)
            u=t[u].ch[0];
       	else
        {
            res+=t[t[u].ch[0]].son;
            if (x==t[u].val)
            {
                splay(u,root);
                return res+1;
            }
            res+=t[u].cnt;
            u=t[u].ch[1];
        }
    }
}

查询排名为$k$的数

对于排名为$k$，我们不妨考虑一直减去左子树中小于它的数，当$k\leq0$时，即为答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
inline int kth(int x)
{
    int u=root;
    while (true)
    {
        if (t[u].ch[0] && k<=t[u].son)
            u=t[u].ch[0];
       	else
        {
            k-=t[t[u].ch[0]].son-t[u].cnt;
            if (k<=0)
            {
                splay(u,root);
                return t[u].val;
            }
            u=t[u].ch[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
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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<bitset>
#include<map>
using namespace std;
typedef long long ll;
const int N=5e5+5;
int n;
namespace Splay{
    struct Tree{
        int ch[2];
        int cnt;
        int son;
        int val;
        int fa;
        inline void clear(){
            ch[1]=ch[0]=cnt=son=val=fa=0;
        }
    }t[N];
    int root=0,tot=0;
    inline void pushup(int u) {t[u].son=t[t[u].ch[0]].son+t[t[u].ch[1]].son+t[u].cnt;}
    inline int get(int x) {int fa=t[x].fa;return t[fa].ch[1]==x;}
    inline void rotate(int x)
    {
        int y=t[x].fa,z=t[y].fa;
        int chk=get(x);
        t[y].ch[chk]=t[x].ch[chk^1],t[t[y].ch[chk]].fa=y;
        t[x].ch[chk^1]=y,t[y].fa=x;t[x].fa=z;
        if (z) t[z].ch[t[z].ch[1]==y]=x;
        pushup(y),pushup(x);
    }
    inline void splay(int x,int &goal)
    {
        int f=t[goal].fa;
        while (t[x].fa!=f)
        {
            if (t[t[x].fa].fa!=f)
                rotate(get(x)==get(t[x].fa)?t[x].fa:x);
            rotate(x);
        }
        goal=x;
    }
    inline void insert(int x)
    {
        if (!root)
        {
            root=++tot;
            t[root].val=x;
            t[root].cnt=1;
            pushup(root);
            return ;
        }
        int u,fa;
        u=fa=root;
        while (u && t[u].val!=x) fa=u,u=t[u].ch[x>t[u].val];
        if (!u)
        {
            u=++tot;
            t[u].cnt=1;
            t[u].val=x;
            t[u].fa=fa;
            t[fa].ch[x>t[fa].val]=u;
            pushup(u);
            splay(u,root);
            return ;
        }
        t[u].cnt++;
        pushup(u);
        splay(u,root);
    }
    inline int rank(int x)
    {
        int res=0,u=root;
        while (true)
        {
            if (x<t[u].val) 
                u=t[u].ch[0];
            else
            {
                res+=t[t[u].ch[0]].son;
                if (x==t[u].val) 
                {
                    splay(u,root);
                    return res+1;
                }
                res+=t[u].cnt;
                u=t[u].ch[1];
            }
        }
    }
    inline int kth(int k)
    {
        int u=root;
        while (true)
        {
            if (t[u].ch[0] && k<=t[t[u].ch[0]].son)
                u=t[u].ch[0];
            else
            {
                k-=t[u].cnt+t[t[u].ch[0]].son;
                if (k<=0)   
                {
                    splay(u,root);
                    return t[u].val;
                }
                u=t[u].ch[1];
            }
        }
    }
    inline int pre(int x)
    {
        int res,u=root;
        while (u)
        {
            if (x>t[u].val)
            {
                res=t[u].val;
                u=t[u].ch[1];
            }
            else u=t[u].ch[0];
        }
        return res;
    }
    inline int next(int x)
    {
        int res,u=root;
        while (u)
        {
            if (x<t[u].val)
            {
                res=t[u].val;
                u=t[u].ch[0];
            }
            else u=t[u].ch[1];
        }
        return res;
    }
    inline void del(int x)
    {
        rank(x);
        if (t[root].cnt>1)
        {
            t[root].cnt--;
            pushup(root);
            return ;
        }
        if (!t[root].ch[0] && !t[root].ch[1])
        {
            t[root].clear();
            root=0;
            return ;
        }
        else if (!t[root].ch[0])
        {
            root=t[root].ch[1];
            t[root].fa=0;
        }
        else if (!t[root].ch[1])
        {
            root=t[root].ch[0];
            t[root].fa=0;
        }
        else
        {
            int u=t[root].ch[0];
            while (t[u].ch[1])
                u=t[u].ch[1];
            splay(u,t[root].ch[0]);
            t[u].ch[1]=t[root].ch[1];
            t[t[root].ch[1]].fa=u;t[u].fa=0;
            pushup(u);
            root=u;
        }
    }
}
using namespace Splay;
inline int read(){
    int s=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') {f=-1;} ch=getchar();}
    while(isdigit(ch)) {s=(s<<1)+(s<<3)+ch-'0'; ch=getchar();}
    return s*f;
}
inline void write(int x){
    int top=0,sta[35];
    while(x) {sta[top++]=x%10,x/=10;}
    while(top) {putchar(sta[--top]+'0');}
}
int main()
{
    n=read();
    for (int i=1;i<=n;i++)
    {
        int opt=read();
        if (opt==1)
        {
            int x=read();
            insert(x);
        }
        if (opt==2)
        {
            int x=read();
            del(x);
        }
        if (opt==3)
        {
            int x=read();
            int res=Splay::rank(x);
            printf("%d\n",res);
        }
        if (opt==4)
        {
            int x=read();
            int res=kth(x);
            printf("%d\n",res);
        }
        if (opt==5)
        {
            int x=read();
            int res=pre(x);
            printf("%d\n",res);
        }
        if (opt==6)
        {
            int x=read();
            int res=next(x);
            printf("%d\n",res);
        }
    }
    return 0;
}
  • 本文标题：Splay Tree学习笔记
  • 本文作者：syysongyuyang
  • 创建时间：2023-02-12 15:20:04
  • 本文链接：https://syysongyuyang.github.io/2023/02/12/Splay/
  • 版权声明：本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
 评论
此页目录
Splay Tree学习笔记
  1. $Splay$树简介
  2. 基本操作
  3. $Splay$操作
  4. 插入
  5. 删除
  6. 查询前驱后继
  7. 查询$x$的排名
  8. 查询排名为$k$的数
  9. 完整代码：