Treap

本文最后更新于：2023年5月18日 下午

前置

请先学会 BST，如果没有弄会 BST 的话建议去这里。

Intro

书接上回，我们在 BST 的结尾留下了一个问题：如何将 BST 弄平衡？

答案是：弄成一颗平衡二叉搜索树！以后我们就将其简称为平衡树。

平衡树有很多类型，今天我们介绍一种入门级的平衡树——Treap。

写一天博文都快累死了。

Theory

Treap 是 Tree + Heap 的合成词。

我们都知道，满足 BST 性质且中序遍历为相同序列的二叉查找树并不唯一，也就是不管这些树内部是什么样的，它们都是等价的，所以我们可以在满足 BST 性质的前提下对这个 BST 做一些事情，改变它的形态，使每个节点的左右子树达到平衡，这样整棵树的深度都维持在 $\mathcal{O}(\log n)$，这样时间复杂度就好说了。

基本上改变 BST 的基本操作就是旋转，最基本的旋转就是“单旋转”，单旋转又分为左旋和右旋，这里的左旋右旋操作都统一对“旋转前处于父节点位置”的节点执行左右旋操作。

我们拿右旋来举例吧：（图我不想找了，大家上网找张图看吧）

初始情况下，$x$ 是 $y$ 的左子节点，A 和 B 分别是 $x$ 的左右子树，C 是 $y$ 的右子树。

$x$ 要变成 $y$ 的父亲，因为 $x$ 的关键值比 $y$ 的小，因此 $y$ 要作为 $x$ 的右子节点，那么 B 就没有位置了，因此要把 B 设为 $y$ 的左子节点，A 的位置并没有被占据，继续当 $x$ 的左子树就好了。

1
2
3
4
5
6
7
8
9
10
11
void zig(int &p) {
    int q = a[p].l;
    a[p].l = a[q].r, a[q].r = p;
    p = q;
}

void zag(int &p) {
    int q = a[p].r;
    a[p].r = a[q].l, a[q].l = p;
    p = q;
}

左旋也是一样的道理。

合理的旋转可以让 BST 变得很平衡，怎样才能干出合理的旋转呢？

我们发现，在随机数据下 BST 是趋近平衡的，Treap 的思想就是利用“随机”来创造平衡，旋转的时候必须维持 BST 性质，因此我们就只好用堆性质来搞了。在插入新节点的时候，随机生成一个额外的权值，如果某个节点不满足大根堆性质的话，就旋转。

删除的时候，因为 Treap 支持旋转，为了避免节点信息更新，堆性质维护等复杂问题，我们找到要删除的节点之后把它向下旋转成叶子节点，然后直接删除。

Treap 的检查，插入，求前驱后继和删除节点的时间复杂度都是 $\mathcal{O}(\log n)$ 的。

Problems

有生之年终于来例题了啊！

P3369

有相同的值啊，我们给每个节点加一个 $cnt$，表示这个节点上的值有多少个，又要查询排名，我们可以加一个 $siz$，记录以该节点为根的子树中所有节点的 $cnt$ 和，如果不存在重复的 $cnt$ 的话，$siz$ 就是子树大小。记住插入和删除以及旋转的时候修改下 $siz$ 就好辣！

我不想写注释了，不懂直接问吧，我已经学了整整一天平衡树了不想思考了:(。

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <random>
#include <cstdlib>
#include <ctime>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;

const int N = 1e5 + 5;

int rd() {
    int x = 0, w = 1;
    char c = getchar();

    while(c < '0' || c > '9') {
        if(c == '-') w = -1;
        c = getchar();
    }

    while(c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = getchar();
    }

    return x * w;
}

struct Treap {
    int l, r;
    int val, dat;
    int cnt, siz;
}a[N];

int tot, rt;
int n;

int New(int val) {
    a[++tot].val = val;
    a[tot].dat = rand();
    a[tot].cnt = a[tot].siz = 1;
    return tot;
}

void upd(int p) {
    a[p].siz = a[a[p].l].siz + a[a[p].r].siz + a[p].cnt;
}

/* int get(int p, int val) {
    if(p == 0) return 0;
    if(val == a[p].val) return p;
    return val < a[p].val ? get(a[p].l, val) : get(a[p].r, val);
} */

int get_rk(int p, int val) {
    if(p == 0) return 0;
    if(val == a[p].val) return a[a[p].l].siz + 1;
    if(val < a[p].val) return get_rk(a[p].l, val);
    return get_rk(a[p].r, val) + a[a[p].l].siz + a[p].cnt;
}

int get_val(int p, int rk) {
    if(p == 0) return INF;
    if(a[a[p].l].siz >= rk) return get_val(a[p].l, rk);
    if(a[a[p].l].siz + a[p].cnt >= rk) return a[p].val;
    return get_val(a[p].r, rk - a[a[p].l].siz - a[p].cnt);
}

void zig(int &p) {
    int q = a[p].l;
    a[p].l = a[q].r, a[q].r = p;
    p = q;
    upd(a[p].r), upd(p);
}

void zag(int &p) {
    int q = a[p].r;
    a[p].r = a[q].l, a[q].l = p;
    p = q;
    upd(a[p].l), upd(p);
}

void ins(int &p, int val) {
    if(p == 0) {
        p = New(val);
        return ;
    }
    if(val == a[p].val) {
        ++a[p].cnt, upd(p);
        return ;
    }
    if(val < a[p].val) {
        ins(a[p].l, val);
        if(a[p].dat < a[a[p].l].dat) zig(p);
    } else {
        ins(a[p].r, val);
        if(a[p].dat < a[a[p].r].dat) zag(p);
    }
    upd(p);
}

int get_nxt(int val) {
    int ans = 2;
    int p = rt;

    while(p) {
        if(a[p].val == val) {
            if(a[p].r > 0) {
                p = a[p].r;
                while(a[p].l > 0) p = a[p].l;
                ans = p;
            }
            break;
        }
        if(a[p].val > val && a[p].val < a[ans].val) ans = p;
        p = val < a[p].val ? a[p].l : a[p].r;
    }
    return a[ans].val;
}

int get_pre(int val) {
    int ans = 1;
    int p = rt;
    while(p) {
        if(val == a[p].val) {
            if(a[p].l > 0) {
                p = a[p].l;
                while(a[p].r > 0) p = a[p].r;
                ans = p;
            }
            break;
        }

        if(a[p].val < val && a[p].val > a[ans].val) ans = p;
        p = val < a[p].val ? a[p].l : a[p].r;
    }
    return a[ans].val;
}

void del(int &p, int val) {
    if(p == 0) return ;
    if(val == a[p].val) {
        if(a[p].cnt > 1) {
            --a[p].cnt, upd(p);
            return ;
        }
        if(a[p].l || a[p].r) {
            if(a[p].r == 0 || a[a[p].l].dat > a[a[p].r].dat) zig(p), del(a[p].r, val);
            else zag(p), del(a[p].l, val);
            upd(p);
        }
        else p = 0;
        return ;
    }
    val < a[p].val ? del(a[p].l, val) : del(a[p].r, val);
    upd(p);
}

int main() {
    srand((int)time(0));
    n = rd();
    New(-INF);
    New(INF);
    rt = 1, a[1].r = 2;
    upd(rt);

    while(n--) {
        int opt = rd(), x = rd();
        if(opt == 1) ins(rt, x);
        else if(opt == 2) del(rt, x);
        else if(opt == 3) printf("%d\n", get_rk(rt, x) - 1);
        else if(opt == 4) printf("%d\n", get_val(rt, x + 1));
        else if(opt == 5) printf("%d\n", get_pre(x));
        else printf("%d\n", get_nxt(x));
    }
    return 0;
}
OI
#Data Structure
Treap
http://dxrprime.github.io/2022/08/25/Treap/
作者
Shelter Prime
发布于
2022年8月25日
许可协议