splay(平衡树)

【引入】

先来看一道题:营业额统计

显然,对于每一天的营业额只要找出已有的营业额与其差值最小的就行了。那么便可以用二叉搜索树来实现这样的查找。

如果一棵二叉树如同下图,为一条链,那么每次查找的时间复杂度就和暴力没有什么差了。

我们可以发现,下图的二叉树与上图的二叉树是等价的,但下图的深度比上图的深度少了2,这样查找的时间复杂度也就减少了,那如何将上图的二叉树转化成下图的呢?splay便可以实现。

【思想】

【rotate】

这是原来的树。为了减小深度,我们把B结点旋转到根结点,那么A结点就成了B结点的儿子。由二叉树的性质我们可以知道B<E<A<C,那么可以得到如下的一棵新树。

rotate代码如下:


1
2
3
4
5
6
7
8
9
10
11
void Rotate(int x)
{
    int fa = tree[x].fat, s = (x == tree[fa].son[1]), s1 = (fa == tree[tree[fa].fat].son[1]);
    tree[tree[x].son[s^1]].fat = fa;
    tree[fa].son[s] = tree[x].son[s^1];
    if (tree[fa].fat)
        tree[tree[fa].fat].son[s1] = x;
    tree[x].fat = tree[fa].fat;
    tree[x].son[s^1] = fa;
    tree[fa].fat = x;
}

【splay】

splay则是rotate的拓展,因为对于一个点,只进行一次rotate显然并不会有多少优化,只有将其旋转至根结点才方便之后的操作。

splay的过程中需要分类讨论,如果是三点一线的话(x,x的父亲,x的祖父)需要先rotate x的父亲,否则需要先rotate x本身(否则会形成单旋使平衡树失衡)。


1
2
3
4
5
6
7
8
9
10
void splay(int x)
{
    for (int y; (y = tree[x].fat) > 0;)
    {
        if (tree[y].fat)
            Rotate((tree[tree[y].fat].son[1] == y)^(tree[y].son[1] == x) ? y : x);
        Rotate(x);
    }
    root = x;
}

【insert/find/delete】

插入、查找、删除的操作于普通平衡树一样。只是在最后要将操作的点旋转到根结点。

插入:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void ins(int va)
{
    int x = root;
    if (!tree[x].val)
    {
        tree[++tot].val = va;
        tree[tot].tot = tot;
        root = tot;
        return ;
    }
    for (;tree[x].son[va > tree[x].val] && tree[x].val != va; x = tree[x].son[va > tree[x].val]);
    if (tree[x].val == va)
    {
        tree[x].cnt++;
        return ;
    }
    tree[++tot].val = va;
    tree[tot].fat = x;
    tree[x].son[va > tree[x].val] = tot;
    splay(tot);
}

查找:


1
2
3
4
5
6
void Find(int va)
{
    int x = root;
    for (;tree[x].val != va; x = tree[x].son[va > tree[x].val]);
    splay(x);
}

查找前驱/后继:


1
2
3
4
5
6
7
int Find_max(int x)
{
    int y = tree[x].son[0];
    for (;tree[y].son[1]; y = tree[y].son[1]);
        splay(y)
    return y;
}

删除:

删除的操作相对麻烦。如果其只有一个儿子,那么将它的儿子当作根结点就可以。否则,要先找出当前结点的前驱/后继,将其旋转到根结点。那么要操作的结点一定是根的一个儿子,并且它只有一个儿子,于是只要将根的儿子指向要操作的结点的儿子即可。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void del(int x)
{
    if (tree[x].cnt > 1)
    {
        tree[x].cnt--;
        return ;
    }
    int l = (tree[x].son[0] != 0), r = (tree[x].son[1] != 0);
    if (!l && !r)
    {
        root = 0;
        return;
    }
    if (!l)
    {
        tree[tree[x].son[1]].fat = 0;
        root = tree[x].son[1];
        return ;
    }
    splay(Find_max(x));
    tree[root].son[1] = tree[x].son[1];
    if (r) tree[tree[x].son[1]].fat = root;
}

【总结】

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
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
 
using namespace std;
 
struct Tr
{
    int val, son[2], fat, cnt, tot;
    Tr()
    {
        cnt = 1;
    }
}tree[10000];
 
int n, m, apple[10000], root = 0, tot = 0;
 
struct io  
{
    io()  {
        freopen("apple.in","r",stdin);
       freopen("apple.out","w",stdout);
    }
    ~io()  {
        fclose(stdin);
       fclose(stdout);
    }
};
 
int Read()
{
    char ch;
    int val = 0, opt = 1;
    while (!(isdigit(ch = getchar()) || ch == '-'));
    if (ch == '-') opt = -1;
    else val = ch - '0';
    while (isdigit(ch = getchar())) (val *= 10) += ch - '0';
    return opt * val;
}
 
void Rotate(int x)
{
    int fa = tree[x].fat, s = (x == tree[fa].son[1]), s1 = (fa == tree[tree[fa].fat].son[1]);
    tree[tree[x].son[s^1]].fat = fa;
    tree[fa].son[s] = tree[x].son[s^1];
    if (tree[fa].fat)
        tree[tree[fa].fat].son[s1] = x;
    tree[x].fat = tree[fa].fat;
    tree[x].son[s^1] = fa;
    tree[fa].fat = x;
}
 
void splay(int x)
{
    for (int y; (y = tree[x].fat) > 0;)
    {
        if (tree[y].fat)
            Rotate((tree[tree[y].fat].son[1] == y)^(tree[y].son[1] == x) ? y : x);
        Rotate(x);
    }
    root = x;
}
 
void ins(int va)
{
    int x = root;
    if (!tree[x].val)
    {
        tree[++tot].val = va;
        tree[tot].tot = tot;
        root = tot;
        return ;
    }
    for (;tree[x].son[va > tree[x].val] && tree[x].val != va; x = tree[x].son[va > tree[x].val]);
    if (tree[x].val == va)
    {
        tree[x].cnt++;
        return ;
    }
    tree[++tot].val = va;
    tree[tot].fat = x;
    tree[x].son[va > tree[x].val] = tot;
    splay(tot);
}
 
int Find_max(int x)
{
    int y = tree[x].son[0];
    for (;tree[y].son[1]; y = tree[y].son[1]);
    return y;
}
 
void Find(int va)
{
    int x = root;
    for (;tree[x].val != va; x = tree[x].son[va > tree[x].val]);
    splay(x);
}
 
void del(int x)
{
    if (tree[x].cnt > 1)
    {
        tree[x].cnt--;
        return ;
    }
    int l = (tree[x].son[0] != 0), r = (tree[x].son[1] != 0);
    if (!l && !r)
    {
        root = 0;
        return;
    }
    if (!l)
    {
        tree[tree[x].son[1]].fat = 0;
        root = tree[x].son[1];
        return ;
    }
    splay(Find_max(x));
    tree[root].son[1] = tree[x].son[1];
    if (r) tree[tree[x].son[1]].fat = root;
}
 
int main(void)
{
 
   
    n = Read();
    m = Read();
    int ans = (m == 5?m:m-1);
    for (int i = 1;i <= n; i++) apple[i] = Read() - 1;
    for (int i = 1;i <= m; i++)
    {
        int hig = Read();
        if (hig <= 0) continue;
        ins(hig);
    }
    for (int i = 1;i <= n; i++)
    {
        ins(apple[i]);
        int y = Find_max(root);
        if (y)
        {
            splay(y);
            del(root);
            ans--;
        }
        Find(apple[i]);
        del(root);
    }
    cout << ans;
 
 
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注