平衡树

Posted on | In |
Words count in article: 3k | Reading time ≈ 14

这里讲两种解法：Splay和FHQ Treap

首先是Splay

我们知道，Splay是一种树形结构，它具有二叉搜索树的性质，维护树上的节点有序，即对于某一节点，它的左子树中所有节点的值都小于这个点，它的右子树中所有点的值都大于这个点。

然后就是Splay中的重点操作，Rotate。我们都知道Splay的复杂度之所以维持在logn级别与旋转操作有着很大的关系，旋转分为两种：左旋和右旋。旋转见图示（感谢You Siki的图片）

然后为了将某个值旋转至树根便于操作，又有了3种操作：Zig、Zig-Zig、Zig-Zag。具体见图示

然后是各种简单操作（Search等较简单的，人人都会的我就不讲了）

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
void Rotate(int x)
{
    int y=fa[x];
    int z=fa[y];
    if(child[z][0]==y)
        child[z][0]=x;
    else
        child[z][1]=x;
    fa[x]=z;
    int w;
    if(child[y][0]==x)
        w=0;
    else
        w=1;
    child[y][w]=child[x][w^1];
    fa[child[x][w^1]]=y;
    child[x][w^1]=y;
    fa[y]=x;
    ct[y]=ct[child[y][0]]+ct[child[y][1]]+num[y];
    ct[x]=ct[child[x][0]]+ct[child[x][1]]+num[x];
}
void splay(int x)
{
    while(fa[x])
    {
        int y=fa[x];
        int z=fa[y];
        if(z==0)
            Rotate(x);
        else
        {
            if((child[z][0]==y)^(child[y][0]==x))
                Rotate(x);
            else
                Rotate(y);
            Rotate(x);
        }
    }
    root=x;
}

Splay和Rotate，这两个是整个Splay的核心函数，请自行参照图示去理解（注：splay函数里的if语句用于判定Zig还是Zag

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
void Insert(int x)
{
    if(tot==0)
    {
        tot=1;
        a[1]=x;
        num[1]=1;
        root=1;
        ct[1]=1;
        fa[1]=0;
        return;
    }
    int k=Search(root,x);
    int node=0;
    if(a[k]==x)
    {
        num[k]++;
        node=k;
    }
    else
    {
        ++tot;
        a[tot]=x;
        num[tot]=1;
        ct[tot]=1;
        fa[tot]=k;
        if(x<a[k])
            child[k][0]=tot;
        else
            child[k][1]=tot;
    }
    while(k)
    {
        ct[k]++;
        k=fa[k];
    }
    if(node)
        splay(node);
    else
        splay(tot);
}

Insert其实比较规矩，就是找到一个与这个值相近的点（一定是叶子节点），然后判断一下x与a[k]的大小关系，如果比a[k]大就接到右子树，比a[k]小就接到左子树。

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
void Delete(int x)
{
    int k=Search(root,x);
    if(a[k]!=x)
        splay(k);
    else
    {
        splay(k);
        if(num[k]>1)
        {
            num[k]--;
            ct[k]--;
        }
        else
        {
            if(child[k][0]==0)
            {
                root=child[k][1];
                fa[root]=0;
                a[k]=MIN;
                num[k]=0;
                ct[k]=0;
                child[k][0]=0;
                child[k][1]=0;
            }
            else
            {
                fa[child[k][0]]=0;
                int kk=Search(child[k][0],2147483647);
                splay(kk);
                ct[root]+=ct[child[k][1]];
                child[root][1]=child[k][1];
                fa[child[k][1]]=root;
                a[k]=MIN;
                num[k]=0;
                ct[k]=0;
                child[k][0]=0;
                child[k][1]=0;
            }
        }
    }
}

Delete其实算是比较烦的了，分了四种情况，前两种比较简单，主要是后两种。如果要删除的节点没有左子树，就直接把该节点删除，根节点变为右儿子；如果有，就先切断该节点与左儿子的连接，然后将左子树中的最大值旋转到左子树的根，然后将右子树接到左子树的右边。

Rank和Find比较简单，这里不讲

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int pre(int x)
{
    int k=Search(root,x);
    splay(k);
    if(a[k]<x)
        return a[k];
    int kk=Search(child[k][0],2147483647);
    splay(kk);
    return a[kk];
}
int succ(int x)
{
    int k=Search(root,x);
    splay(k);
    if(a[k]>x)
        return a[k];
    int kk=Search(child[k][1],-2147483647);
    splay(kk);
    return a[kk];
}

pre（前驱）和succ（后缀）的思路基本相同，都是先将要找的值（如果有的话）旋转到根，然后pre是在左子树中找最大值，succ是在右子树中找最小值

以下是合代码

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
#include <bits/stdc++.h>
#define N 100000+110
#define MIN -1e8
using namespace std;
int child[N][2],fa[N],a[N],ct[N],num[N];
int n,tot,root;
int Search(int x,int w)
{
    if(a[x]==w)
        return x;
    while(a[x]!=w)
    {
        if(a[x]>w)
        {
            if(child[x][0])
                x=child[x][0];
            else
                break;
        }
        else if(a[x]==w)
            return x;
        else
        {
            if(child[x][1])
                x=child[x][1];
            else
                break;
        }
    }
    return x;
}
void Rotate(int x)
{
    int y=fa[x];
    int z=fa[y];
    if(child[z][0]==y)
        child[z][0]=x;
    else
        child[z][1]=x;
    fa[x]=z;
    int w;
    if(child[y][0]==x)
        w=0;
    else
        w=1;
    child[y][w]=child[x][w^1];
    fa[child[x][w^1]]=y;
    child[x][w^1]=y;
    fa[y]=x;
    ct[y]=ct[child[y][0]]+ct[child[y][1]]+num[y];
    ct[x]=ct[child[x][0]]+ct[child[x][1]]+num[x];
}
void splay(int x)
{
    while(fa[x])
    {
        int y=fa[x];
        int z=fa[y];
        if(z==0)
            Rotate(x);
        else
        {
            if((child[z][0]==y)^(child[y][0]==x))
                Rotate(x);
            else
                Rotate(y);
            Rotate(x);
        }
    }
    root=x;
}
void Insert(int x)
{
    if(tot==0)
    {
        tot=1;
        a[1]=x;
        num[1]=1;
        root=1;
        ct[1]=1;
        fa[1]=0;
        return;
    }
    int k=Search(root,x);
    int node=0;
    if(a[k]==x)
    {
        num[k]++;
        node=k;
    }
    else
    {
        ++tot;
        a[tot]=x;
        num[tot]=1;
        ct[tot]=1;
        fa[tot]=k;
        if(x<a[k])
            child[k][0]=tot;
        else
            child[k][1]=tot;
    }
    while(k)
    {
        ct[k]++;
        k=fa[k];
    }
    if(node)
        splay(node);
    else
        splay(tot);
}
void Delete(int x)
{
    int k=Search(root,x);
    if(a[k]!=x)
        splay(k);
    else
    {
        splay(k);
        if(num[k]>1)
        {
            num[k]--;
            ct[k]--;
        }
        else
        {
            if(child[k][0]==0)
            {
                root=child[k][1];
                fa[root]=0;
                a[k]=MIN;
                num[k]=0;
                ct[k]=0;
                child[k][0]=0;
                child[k][1]=0;
            }
            else
            {
                fa[child[k][0]]=0;
                int kk=Search(child[k][0],2147483647);
                splay(kk);
                ct[root]+=ct[child[k][1]];
                child[root][1]=child[k][1];
                fa[child[k][1]]=root;
                a[k]=MIN;
                num[k]=0;
                ct[k]=0;
                child[k][0]=0;
                child[k][1]=0;
            }
        }
    }
}
int Rank(int x)
{
    int k=Search(root,x);
    splay(k);
    return ct[child[k][0]]+1;
}
int Find(int x)
{
    int k=root;
    while(!(x>=ct[child[k][0]]+1&&x<=ct[child[k][0]]+num[k])&&k!=0)
    {
        if(x>ct[child[k][0]]+num[k])
        {
            x-=ct[child[k][0]]+num[k];
            k=child[k][1];
        }
        else
            k=child[k][0];
    }
    return a[k];
}
int pre(int x)
{
    int k=Search(root,x);
    splay(k);
    if(a[k]<x)
        return a[k];
    int kk=Search(child[k][0],2147483647);
    splay(kk);
    return a[kk];
}
int succ(int x)
{
    int k=Search(root,x);
    splay(k);
    if(a[k]>x)
        return a[k];
    int kk=Search(child[k][1],-2147483647);
    splay(kk);
    return a[kk];
}
int main()
{
    scanf("%d",&n);
    memset(a,MIN,sizeof(a));
    for(int i=1;i<=n;i++)
    {
        int x,z;
        scanf("%d%d",&z,&x);
        switch(z)
        {
            case 1:Insert(x);break;
            case 2:Delete(x);break;
            case 3:printf("%d\n",Rank(x));break;
            case 4:printf("%d\n",Find(x));break;
            case 5:printf("%d\n",pre(x));break;
            case 6:printf("%d\n",succ(x));break;
        }
    }
    return 0;
}

AC记录

用时: 380ms / 内存: 3488KB

然后是FHQ Treap

由于省去了Rotate的操作，非旋的Treap就显得极为简洁（鄙人Splay代码200+，FHQ Treap代码仅130+）。再加上它几乎可以实现Splay的全部功能（LCT除外），所以当然是选择FHQ Treap啦。（开讲之前先%一波FHQ

是不是觉得Splay也好，Treap也好，转来转去的很烦人呢？那么如果我们可以暴力的把区间切成两段（或三段），然后对其中某一段操作完后再合起来是不是会简单的多呢？来学FHQ Treap吧，这东西绝对对你胃口！

那么既然这个东西要把一个区间切成数段，就需要一个split，实际上它有两种分法：一种是把权值比k小的放入一颗树，比k大的放入另一颗树；另一种是把前k个点放入一棵树，其他的放入另一棵树。这里给出第一种的讲解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void split(int now,int k,int &l,int &r)
{
    if(!now)
        l=r=0;
    else
    {
        if(a[now]<=k)
        {
            l=now;
            split(child[now][1],k,child[now][1],r);
        }
        else
        {
            r=now;
            split(child[now][0],k,l,child[now][0]);
        }
        pushup(now);
    }
}

对于我们遍历到每一个点，假如它的权值小于k，那么它的所有左子树，都要分到左边的树里，然后遍历它的右儿子。假如大于k，把它的所有右子树分到右边的树里，遍历左儿子。

因为它的最多操作次数就是一直分到底，效率就是O(logn)

接下来是合并的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int Merge(int x,int y)
{
    if(!x||!y)
        return x+y;
    if(pri[x]<pri[y])
    {
        child[x][1]=Merge(child[x][1],y);
        pushup(x);
        return x;
    }
    else
    {
        child[y][0]=Merge(x,child[y][0]);
        pushup(y);
        return y;
    }
}

因为第一个Treap的权值都比较小，我们比较一下它的tar(附加权值)，假如第一个的tar小，我们就可以直接保留它的所有左子树，接着把第一个Treap变成它的右儿子。反之，我们可以保留第二棵的所有右子树，指针指向左儿子。

你可以把这个过程形象的理解为在第一个Treap的左子树上插入第二个树，也可以理解为在第二个树的左子树上插入第一棵树。因为第一棵树都满足小于第二个树，所以就变成了比较tar来确定树的形态。

也就是说，我们其实是遍历了第一个Treap的根->最大节点，第二个Treap的根->最小节点，也就是O(logn)

然后对于Insert，就不过是一个按照x的权值分开，插入后再合并的的过程罢了，Delete就是把树按照x分成l和r,再把l按照x-1分成c,d。把c的两个子儿子合并起来，再和r合并。

找前驱的话把root按x-1分成l,r，在l里面找最大值；找后继的话把root按x分成l,r，在r里找最小值。

Rank就是把root按x-1分成l,r，排名就是ct[l]；Find的过程和Splay差别并不大，都不细讲。

值得注意的是，FHQ Treap的本质还是一个Treap，是将树上的值按rand值排序的，r值小的在上面，r值大的在下面。这也是为什么Treap（树堆）成为Treap。

部分搬运某dalao博客QwQ

以下是合代码

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
#include <bits/stdc++.h>
#define N 100010
#define inf 2147483647
using namespace std;
int n,tot,root;
int child[N][2],ct[N],a[N],pri[N];
void pushup(int x)
{
    ct[x]=1+ct[child[x][0]]+ct[child[x][1]];
}
int new_node(int x)
{
    ct[++tot]=1;
    a[tot]=x;
    pri[tot]=rand();
    return tot;
}
int Merge(int x,int y)
{
    if(!x||!y)
        return x+y;
    if(pri[x]<pri[y])
    {
        child[x][1]=Merge(child[x][1],y);
        pushup(x);
        return x;
    }
    else
    {
        child[y][0]=Merge(x,child[y][0]);
        pushup(y);
        return y;
    }
}
void split(int now,int k,int &l,int &r)
{
    if(!now)
        l=r=0;
    else
    {
        if(a[now]<=k)
        {
            l=now;
            split(child[now][1],k,child[now][1],r);
        }
        else
        {
            r=now;
            split(child[now][0],k,l,child[now][0]);
        }
        pushup(now);
    }
}
void Insert(int x)
{
    int l,r;
    split(root,x,l,r);
    root=Merge(Merge(l,new_node(x)),r);
}
void Delete(int x)
{
    int l,r,p;
    split(root,x,l,p);
    split(l,x-1,l,r);
    r=Merge(child[r][0],child[r][1]);
    root=Merge(Merge(l,r),p);
}
int Rank(int x)
{
    int l,r;
    split(root,x-1,l,r);
    int ans=ct[l]+1;
    root=Merge(l,r);
    return ans;
}
int Find(int now,int k)
{
    while(1)
    {
        if(k<=ct[child[now][0]])
            now=child[now][0];
        else if(k==ct[child[now][0]]+1)
            return a[now];
        else
        {
            k-=ct[child[now][0]]+1;
            now=child[now][1];
        }
    }
}
int pre(int x)
{
    int l,r;
    split(root,x-1,l,r);
    int ans=Find(l,ct[l]);
    root=Merge(l,r);
    return ans;
}
int suc(int x)
{
    int l,r;
    split(root,x,l,r);
    int ans=Find(r,1);
    root=Merge(l,r);
    return ans;
}
int main()
{
    srand(19260817);
    //srand(998244353);
    //srand(1e9+7);
    //srand((unsigned)time(NULL));
    //以上是常用随机种子
    scanf("%d",&n);
    memset(a,-inf,sizeof(a));
    for(int i=1;i<=n;i++)
    {
        int z,x;
        scanf("%d%d",&z,&x);
        switch(z)
        {
            case 1:Insert(x);break;
            case 2:Delete(x);break;
            case 3:printf("%d\n",Rank(x));break;
            case 4:printf("%d\n",Find(root,x));break;
            case 5:printf("%d\n",pre(x));break;
            case 6:printf("%d\n",suc(x));break;
        }
    }
    return 0;
}

AC记录

用时: 316ms / 内存: 3265KB

事实上可以看出Treap比Splay跑的要快一点（说不定是我的Splay太弱了呢？

然而由于我太蒻了，还是有点懵逼，有dalao能指出我的不足的话感激不尽，也欢迎各位找我讨论

0%