平衡树入门：splay

Arahc 11.0
  2021-07-11 08:00 2021-07-11 08:00 创建   2023-03-18 12:12:16 2023-03-18 12:12:16 更新      2.6k 字  11 分钟  

二叉搜索树

维护一个集合，支持如下操作：

  • 添加一个元素 xx。
  • 删除一个元素 xx。
  • 查询一个元素 xx 的排名。
  • 查询排名为 kk 的元素。

n≤5×105n\leq 5\times 10^5。

为了维护这样的集合，我们类比二叉堆的方式，定义二叉搜索树：对于一个点，其左儿子的值不大于它，右儿子的值不小于它。例如：

pic-1

下面依次考虑这些基本操作：

添加

举个例子，假设要添加 2525。

首先我们应该找到 2525 应该放在哪里，所以从根节点出发，遵循二叉搜索树左儿子小于根节点（右儿子大于根节点）的原则，因为要添加的数字 <41<41 所以来到左边，同理因为 25>2025>20 所以跳到 2020 右儿子，又因为 25<2925<29，我们得出在 2929 左子树上。因为 2929 没有左儿子，所以可以在这里新建一个节点。也就是添加完变成了这样（用颜色高亮标记了走过的点）：

pic-2

当然如果我插入一个已经存在的数字，可以记录每个数出现的次数，更为方便。

删除

还是最开始给出的二叉搜索树的例子，假设我们要删除一个点，比如 9191。

实际上，要删除一个点，就是找到这个点的位置，将其删除之后更新父亲和儿子的关系。找到这个点可以考虑和添加类似的方式在树上递归往儿子跳。问题在于如果直接删除 9191，它的儿子显然不能直接连向 6565，因为这样不符合树是二叉树。

显然假设 9191 只有一个儿子，那直接让儿子代替当前位置就可以了。不妨把右儿子代替当前位置，显然左儿子值小于右儿子，将其当作右儿子的左儿子即可。若右儿子本来就有左儿子，可以继续往左一直找找到空位。

删除 9191 的操作完成后，树会变成这样：

pic-3

查询排名/第 k 大

假设查找 5050 的排名，注意到比 5050 小的数不就是 4141 和它的左子树吗？

  • 如果我要查找的数字是某个右儿子，则它的父亲、左子树、以及其他这以左的所有点都比查找的数小，其右边所有的数都比其大。
  • 如果我要查找的数字是某个左儿子，则它的父亲比他大，但其左儿子以及这以左的所有点比查找的树小，且这个点往上查找到的所有是右儿子的祖先（且不是父亲），它们的左子树比要查的点小，除此之外所有数都比其大。

仍然是在树上跳，跳的过程中记录一下跳过的点的子树大小即可。

对于查询第 kk​ 大，则恰好反过来，根据子树大小决定往左边还是往右边就可以了。

splay

如果你在阅读完上述部分之后认为自己完全理解了，那么恭喜你！但是我还是要泼一盆冷水：这样的二叉搜索树是非常低效的。

原因在于，对于前面的任意一个操作，最坏情况下都需要从根走到一个叶子上。也就是树高同级的复杂度。当树退化成链时，单次操作复杂度就是 O(n)\mathcal O(n)。例如依次插入 10,9,8,⋯ ,110,9,8,\cdots,1 后，树就是一个链：

pic-4

为了解决这样一个问题，避免这种传统的二叉搜索树被极端数据卡飞，换句话说，我们要构造一颗始终“平衡”的树，使得树高总是等于或一直趋近与 log⁡n\log n 级别。为此珂学家们进行了无数研究探讨。其中 Tarjan 提出了一个不错的想法：构造一个伸展树。

所谓伸展树，就是接下来要讲解的 Splay。当然平衡树的实现不仅仅有 Splay，但是因为 Spaly 是本文的压轴主题，带有神圣的主角光环，所以我们只将 Spaly 而暂时舍弃别的平衡树。

首先把话放在前头，因为平衡树也是二叉搜索树的一种，所以平衡树的六大操作基本和朴素的二叉搜索树一致。而 Tarjan 提出了将一组节点“旋转”的方法，控制了树的平衡。我们要保证查询的点尽可能离根更近，因此，我们可以简单地假设：现在查到的这个点就是经常容易被查到的点，不管后面查没查过提到根就对了。

这句话听起来十分玄乎，因此还是具体地分析一下“旋转”到底如何进行。

旋转

既然要把一个节点提到根，我们首先考虑怎么把这个节点移到它父亲的位置上，假设某一个平衡树构造是这样的，其中 x,y,zx,y,z 为三个点，A,B,C,DA,B,C,D 为四个子树的根。

pic-5

七个点之间的数量关系：D<z<C<y<B<x<AD<z<C<y<B<x<A。

现在我们进行了一次单旋操作，将 xx 的位置变到 yy：

  • 首先 x,yx,y 位置颠倒了，为了维护大小关系，因此 xx 在 zz 右儿子，yy 在 xx 左儿子。
  • 对于原本 xx 左儿子上的 BB，由于 B>yB>y，所以 BB 应该放到 yy 的右儿子。

pic-6

可以写出如下代码：

1
2
3
4
5
6
7
8
inline void rotate(int x){
    int y=a[x].fa,z=a[y].fa;
    int k=getson(x),p=getson(y);
    connect(a[x].son[k^1],y,k),
    connect(y,x,k^1),
    connect(x,z,p);
    resize(y),resize(x);
}

如果我们真的遇到一个退化成链的平衡树，现在我想把叶子节点提到根上来，可不可以不停地单旋完成呢？

手玩一下可以发现，单纯靠这样的旋转不能做到平衡。一次不行的话，就一次旋转两次。定义函数 splay(x,to)\rm{splay}(x,to) 表示把 xx 通过若干次旋转提到 toto 的位置。每次先旋转一个点的父亲，然后再旋转这个点本身。分类讨论有三种情况：

  1. to=faxto=fa_x，单旋 xx。
  2. x,fax,fafaxx,fa_x,fa_{fa_x} 共线（例如 xx 和 faxfa_x 都是左儿子），先旋转 faxfa_x，再旋转 xx。
  3. x,fax,fafaxx,fa_x,fa_{fa_x} 不共线，旋转两次 xx。
1
2
3
4
5
6
7
8
9
10
inline void splay(int x,int to){
    to=a[to].fa;
    while(a[x].fa!=to){
        int y=a[x].fa,z=a[y].fa;
        int k=getson(x),p=getson(y);
        if(z==to) rotate(x); // 第一种情况
        else if(k==p) rotate(y),rotate(x); // 第二种情况
        else rotate(x),rotate(x); // 第三种情况
    }
}

代码

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
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
#include<bits/stdc++.h>
#define root a[0].son[1]
using namespace std;
const int max_n=100005,inf=2000000005;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) x=-x,putchar('-');
    if(x>9) write(x/10);
    putchar(x%10^48);
}

int tot;

struct dot{
    int size,cnt,data,son[2],fa;
    dot(){fa=size=cnt=data=son[0]=son[1]=0;}
}a[max_n];

inline int getson(int x){
    return (a[a[x].fa].son[1]==x?1:0);
}
inline void connect(int u,int fa,int k){
    a[u].fa=fa,
    a[fa].son[k]=u;
}
inline void resize(int u){
    int lsize=a[a[u].son[0]].size,rsize=a[a[u].son[1]].size;
    a[u].size=lsize+rsize+a[u].cnt;
}

inline void rotate(int x){
    int y=a[x].fa,z=a[y].fa;
    int k=getson(x),p=getson(y);

    connect(a[x].son[k^1],y,k),
    connect(y,x,k^1),
    connect(x,z,p);

    resize(y),resize(x);
}
inline void splay(int x,int to){
    to=a[to].fa;
    while(a[x].fa!=to){

        int y=a[x].fa,z=a[y].fa;
        int k=getson(x),p=getson(y);

        if(z==to) rotate(x);
        else if(k==p) rotate(y),rotate(x);
        else rotate(x),rotate(x);
    }
}
inline int find(int x){
    int u=root;
    while(1){
        if(!u) return 0;
        if(a[u].data==x){
            splay(u,root);
            return u;
        }
        int k=(x>a[u].data?1:0),v=a[u].son[k];
        u=v;
    }
}
inline int adnew(int data,int fa){
    a[++tot].fa=fa;
    a[tot].data=data;
    a[tot].cnt=a[tot].size=1;
    return tot;
}
inline void add(int x){
    int u=root;
    if(!root){
        root=adnew(x,0);
        return;
    }
    while(1){
        ++a[u].size;
        if(a[u].data==x){
            ++a[u].cnt;
            splay(u,root);
            return;
        }
        int k=(x>a[u].data?1:0),v=a[u].son[k];
        if(!v){
            int p=adnew(x,u);
            a[u].son[k]=v=p;
            splay(p,root);
            return;
        }
        u=v;
    }
}
inline void delet(int x){
    int u=find(x);
    if(!u) return;
    if(a[u].cnt>=2){
        --a[u].cnt,
        --a[u].size;
        return;
    }
    if(!a[u].son[1] && !a[u].son[0]){
        root=0;
        return;
    }
    if(!a[u].son[0]){
        root=a[u].son[1],
        a[root].fa=0;
        return;
    }
    int v=a[u].son[0];
    while(a[v].son[1]) v=a[v].son[1];
    splay(v,a[u].son[0]);
    connect(a[u].son[1],v,1),
    connect(v,0,1);
    resize(v);
}
inline int getrank(int x){
    int u=find(x);
    splay(u,root);
    return a[a[u].son[0]].size+1;
}
inline int getnum(int x){
    int u=root;
    while(1){
        int rank=a[u].size-a[a[u].son[1]].size;
        if(x>a[a[u].son[0]].size && x<=rank){
            splay(u,root);
            return a[u].data;
        }
        if(x<rank) u=a[u].son[0];
        else x-=rank,u=a[u].son[1];
    }
}
inline int smaller(int x){
    int u=root,res=-inf;
    while(u){
        if(a[u].data<x && a[u].data>res){
            splay(u,root);
            res=a[u].data;
        }
        if(x>a[u].data) u=a[u].son[1];
        else u=a[u].son[0];
    }
    return res;
}
inline int bigger(int x){
    int u=root,res=inf;
    while(u){
        if(a[u].data>x && a[u].data<res){
            splay(u,root);
            res=a[u].data;
        }
        if(x<a[u].data) u=a[u].son[0];
        else u=a[u].son[1];
    }
    return res;
}


signed main(){
    int T=read();
    while(T--){
        int tp=read(),x=read();
        if(tp==1){
            add(x);
            continue;
        }
        if(tp==2){
            delet(x);
            continue;
        }
        if(tp==3){
            int ans=getrank(x);
            write(ans),putchar('\n');
            continue;
        }
        if(tp==4){
            int ans=getnum(x);
            write(ans),putchar('\n');
            continue;
        }
        if(tp==5){
            int ans=smaller(x);
            write(ans),putchar('\n');
            continue;
        }
        if(tp==6){
            int ans=bigger(x);
            write(ans),putchar('\n');
            continue;
        }
    }
    return 0;
}
  • 标题: 平衡树入门：splay
  • 作者: Arahc
  • 创建于 : 2021-07-11 08:00:00
  • 更新于 : 2023-03-18 12:12:16
  • 链接: https://arahc.github.io/2021/07/11/【笔记】平衡树入门：splay/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
平衡树入门：splay
  1. 二叉搜索树
    1. 添加
    2. 删除
    3. 查询排名/第 k 大
  2. splay
    1. 旋转
  3. 代码