学习数据结构对我来说真的相当困难，网上讲(Treap)的我也看不太懂，前前后后花了大概六天才把(Treap)学会。为了避免再次忘记，这里我整理一下(Treap)的基础知识和模板。
阅读此文前，你需要知道：
第一次接触(Treap)的同学请移步Treap的学习总结，本文着重强调代码实现和细节问题。
本文无指针，码风比较清新，请放心食用。
0.变量定义
(：t：Treap\_node){
-
(rd)：随机产生的优先级
-
(sz)：子树大小
-
(ch)：(0)代表左子节点，(1)代表右子节点。
-
(key)：键值（实际值大小）
-
(cnt)：当前键值节点个数
}
1.操作类型
-
(rotate) - 旋转
-
分为左旋和右旋两种，可以传一个方向的参数，把它们合成一种。
-
流程：（这里以右旋为例）
-
节点：(p)点（传址引用）， (p)的左子节点(ls)
-
把(ls)的右子树接在(p)点上
-
(ls)的右子节点变为(p)
-
更新两个节点大小
-
把连向(p)的边引向(ls)（(p = ls)）
-
Q：为什么对(p)点传址引用？
-
A：在插入/删除点的时候同样采用了传址引用。节点(Fa)搜索过程中到达它的子节点(p)时，(Fa)对(p)点的指针(t[Fa].ch[dir])会同时被传出，从而使(rotate)直接修改(Fa)和(p)的连接状况。
-
Q：为什么把(ls)的右子树接在(p)点上？
-
A：为了维护二叉搜索树的性质，在任意一棵子树中，你要保证左子树>根节点>右子树。(ls)本身所连接的右子树是合法的，根据旋转前的定义，(ls)的右子树键值<(p)点键值。为了维护旋转后(Treap)二叉的性质，我们选择把这一棵子树改接到(p)点上去。
-
关于传入的(dir)参数怎么玩，可以自己画图琢磨一下。
-
注意两个节点大小的更新顺序。
void rotate (int &p, int dir) {
//dir = 0 / 1 -> 右旋 / 左旋
int s = t[p].ch[dir ^ 0];
t[p].ch[dir ^ 0] = t[s].ch[dir ^ 1];
t[s].ch[dir ^ 1] = p;
push_up (p);
push_up (s);
p = s;
}
-
(Insert) - 插入
-
没有就加入，有就累加计数器。
-
流程：
-
判断与子节点的大小关系，大了向左，小了向右
-
一路上对每个经过节点增加子树大小
-
如果有键值相等的点，就直接累加计数器
-
如果没有（在向子树查找过程中走到编号为(0)的子树）
-
注意传址引用
-
程序里用了一点小(Trick)来记录方向，简化代码。
-
Q：这里传址引用还有什么作用？
-
A：改变连接情况的作用见上一个操作，还有一个用处是初始化根节点。每次插入都从根节点开始。如果还没有点的话，新建的节点会直接覆盖传入的根节点的地址而成为根节点。
void Insert (int &p, int key) {
if (p == 0) {
p = ++tot;
t[p].sz = 1;
t[p].cnt = 1;
t[p].key = key;
t[p].rd = rand ();
return;
}
++t[p].sz;
if (t[p].key == key) {
++t[p].cnt;
} else {
int dir = key > t[p].key;
Insert (t[p].ch[dir], key);
if (t[p].rd > t[t[p].ch[dir]].rd) {
rotate (p, dir);
}
}
}
-
(Delete) - 删除
-
流程：
-
判断与子节点的大小关系，大了向左，小了向右
-
一路上对每个经过节点减少子树大小
-
如果有键值相等的点
-
如果该点个数(>1)
-
如果点的个数(=1)
-
把当前节点不断向下旋转
-
为了保持优先级，总是把优先级更高((rd)更小)的转上来
-
如果这个点只剩(<=1)棵子树（(t[p].ch[0] * t[p].ch[1] == 0)），那么就可以把它删掉，把它还剩的那个子节点提上来。（$p = t[p].ch[0] + t[p].ch[1]; $）
void Delete (int &p, int key) {
if (p == 0) {
return;
}
if (t[p].key == key) {
if (t[p].cnt > 1) {
--t[p].sz;
--t[p].cnt;
} else {
if (t[p].ch[0] * t[p].ch[1] == 0) {
//分支 < 2
p = t[p].ch[0] + t[p].ch[1];
} else {
if (t[p].ch[0] < t[p].ch[1]) {
rotate (p, 0);
} else {
rotate (p, 1);
}
Delete (p, key);
}
}
} else {
--t[p].sz;
Delete (t[p].ch[key > t[p].key], key);
}
}
-
(nxt/pre) - 查找前驱/后继
-
也就是第一个比查找键值大/小的数
-
这里以(nxt)为例
-
流程：
-
查找的键值小于当前所在节点的键值：
-
向左走，看还有没有更小一点的值
-
防止玩脱，先记答案
-
否则直接向右走（一定不可能是后继）
-
这里本蒻使用非递归版
int pre (int key) {
int p = root, ans = 0;
while (p != 0) {
if (t[p].key < key) {
ans = t[p].key;
p = t[p].ch[1];
} else {
p = t[p].ch[0];
}
}
return ans;
}
int nxt (int key) {
int p = root, ans = 0;
while (p != 0) {
if (t[p].key > key) {
ans = t[p].key;
p = t[p].ch[0];
} else {
p = t[p].ch[1];
}
}
return ans;
}
-
(kth) - 求(k)大值
-
流程：
-
(k<=)当前点左子树大小：去左子树找
-
(k>)当前节点左子树大小 + 当前节点的计数：去右子树找
-
否则(k)就恰好落在当前节点上，直接返回当前节点的答案
-
附加操作都相对简单，不作赘述。
int kth (int k) {
int p = root;
while (p != 0) {
if (k <= t[t[p].ch[0]].sz) {
p = t[p].ch[0];
} else if (k > t[t[p].ch[0]].sz + t[p].cnt) {
k -= t[t[p].ch[0]].sz + t[p].cnt;
p = t[p].ch[1];
} else {
return t[p].key;
}
}
return false;
}
-
(get\_rnk) - 求当前数的排名
-
流程：
-
键值比当前节点大：去右子树找 && 带上左子树和当前节点的贡献
-
键值比当前节点小：去左子树找
-
键值与当前节点相等：返回答案
-
在返回答案时记得加上当前节点左子树大小（未统计的贡献）(+ 1)（排名）
int get_rnk (int key) {
int p = root, ans = 0;
while (p != 0) {
if (key < t[p].key) {
p = t[p].ch[0];
} else if (key > t[p].key) {
ans += t[p].cnt;
ans += t[t[p].ch[0]].sz;
p = t[p].ch[1];
} else {
return ans + t[t[p].ch[0]].sz + 1;
}
}
return false;
}
2.完整板子（Luogu P3369 普通平衡树）
#include <bits/stdc++.h>
#define N 100010
using namespace std;
struct Treap {
int tot, root;
struct Treap_node {
int rd, sz, ch[2], cnt, key;
}t[N];
Treap () {
tot = root = 0;
memset (t, 0, sizeof (t));
}
//注意初始化
void push_up (int p) {
t[p].sz = t[p].cnt;
t[p].sz += t[t[p].ch[0]].sz;
t[p].sz += t[t[p].ch[1]].sz;
}
//更新节点大小
void rotate (int &p, int dir) {
//dir = 0 / 1 -> 右旋 / 左旋
int s = t[p].ch[dir ^ 0];
t[p].ch[dir ^ 0] = t[s].ch[dir ^ 1];
t[s].ch[dir ^ 1] = p;
push_up (p);
push_up (s);
p = s;
}
//旋转
void Insert (int &p, int key) {
if (p == 0) {
p = ++tot;
t[p].sz = 1;
t[p].cnt = 1;
t[p].key = key;
t[p].rd = rand ();
return;
}
++t[p].sz;
if (t[p].key == key) {
++t[p].cnt;
} else {
int dir = key > t[p].key;
Insert (t[p].ch[dir], key);
if (t[p].rd > t[t[p].ch[dir]].rd) {
rotate (p, dir);
}
}
}
//插入
void Delete (int &p, int key) {
if (p == 0) {
return;
}
if (t[p].key == key) {
if (t[p].cnt > 1) {
--t[p].sz;
--t[p].cnt;
} else {
if (t[p].ch[0] * t[p].ch[1] == 0) {
//分支 < 2
p = t[p].ch[0] + t[p].ch[1];
} else {
if (t[p].ch[0] < t[p].ch[1]) {
rotate (p, 0);
} else {
rotate (p, 1);
}
Delete (p, key);
}
}
} else {
--t[p].sz;
Delete (t[p].ch[key > t[p].key], key);
}
}
//删除
int pre (int key) {
int p = root, ans = 0;
while (p != 0) {
if (t[p].key < key) {
ans = t[p].key;
p = t[p].ch[1];
} else {
p = t[p].ch[0];
}
}
return ans;
}
//前驱
int nxt (int key) {
int p = root, ans = 0;
while (p != 0) {
if (t[p].key > key) {
ans = t[p].key;
p = t[p].ch[0];
} else {
p = t[p].ch[1];
}
}
return ans;
}
//后继
int kth (int k) {
int p = root;
while (p != 0) {
if (k <= t[t[p].ch[0]].sz) {
p = t[p].ch[0];
} else if (k > t[t[p].ch[0]].sz + t[p].cnt) {
k -= t[t[p].ch[0]].sz + t[p].cnt;
p = t[p].ch[1];
} else {
return t[p].key;
}
}
return false;
}
//k大(返回的是第k大的键值)
int get_rnk (int key) {
int p = root, ans = 0;
while (p != 0) {
if (key < t[p].key) {
p = t[p].ch[0];
} else if (key > t[p].key) {
ans += t[p].cnt;
ans += t[t[p].ch[0]].sz;
p = t[p].ch[1];
} else {
return ans + t[t[p].ch[0]].sz + 1;
}
}
return false;
}
//求排名
}tree;
int n, x, opt;
int main () {
// freopen ("Data.in", "r", stdin);
srand (time (NULL));
scanf ("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf ("%d %d", &opt, &x);
if (opt == 1) {//insert
tree.Insert (tree.root, x);
}
if (opt == 2) {//delete
tree.Delete (tree.root, x);
}
if (opt == 3) {//get_rank
printf ("%d
", tree.get_rnk (x));
}
if (opt == 4) {//get_kth
printf ("%d
", tree.kth (x));
}
if (opt == 5) {//get_pre
printf ("%d
", tree.pre(x));
}
if (opt == 6) {//get_nxt
printf ("%d
", tree.nxt(x));
}
}
}