Splay

引入

平衡树是一棵二叉查找树 ($Binary Search Tree, BST$).

$BST$定义:

  1. 树上每个节点都有一个权值;
  2. 若左子树非空, 则左子树上所有节点的值均小于其根节点的值;
  3. 若右子树非空, 则右子树上所有节点的值均大于其根节点的值.

数组名称约定:

$son[i][2]: $ 数组第二维的 $0$,$1$ 分别存储 $i$ 的左右子树根节点编号
$val[i]: i$ 节点上放置的数的权值
$cnt[i]: $ 我们把具有相同 $val$ 的树放置到同一个节点上,用 $cnt$ 来存储 $i$ 节点上数的个数
$siz[i]: $ 以 $i$ 为根的子树的节点个数
$fa[i]: i$ 的父节点

为了便于更新根节点 #$ \mathcal Define \ \ root \ \ son[0][1]$

splay

  • pos
    返回 $node$ 位于父节点的子节点方位
    左子树: $0 \ \ \ \ \ $ 右子树 :$1$
1
2
3
int pos(int node){
return son[fa[node]][1] == node;
}
  • connect
    将 $node$ 节点作为 $par$ 的 $pos$ 子树根节点
    双方互相承认父子关系
1
2
3
4
void connect(int node, int par, int pos){ 
fa[node] = par;
son[par][pos] = node;
}
  • update
    在旋转的过程中树的结构会改变
    于是需要这个操作来更新节点的 $siz$
1
2
3
void update(int node){
siz[node] = siz[son[node][0]] + siz[son[node][1]] + cnt[node];
}
  • swing
    将 $node$ 节点旋转到它的父节点位置
    $S:son \ \ \ \ F: father \ \ \ \ G: grandpa$


    定义 $\Rightarrow$ 为旋转后节点之间的父子关系, $\to$ 为旋转前节点之间的父子关系.
    根据保持二叉查找树性质不变的原则, 代码应该像下面这样写
1
2
3
4
5
6
7
void swing(int node){
int par = fa[node], nodepos = pos(node), parpos = pos(par);
connect(son[node][nodepos^1], par, nodepos); //B -> F
connect(node, fa[par], parpos);//S -> G
connect(par, node, nodepos^1);//F -> S
update(par), update(node);
}
注意顺序和方向

⭐️
双旋$splay$: 把 $node$ 旋转到 $to$ 的位置
也就是令 $node$ 成为 $fa[to]$ 的子节点
分三种情况处理即可(不太理解)

1
2
3
4
5
6
7
8
9
void splay(int node, int to){
to = fa[to];
while(fa[node] != to){
int par = fa[node];
if(fa[par] != to)//if pos[par] = pos[node] first swing par
pos(par) ^ pos(node) ? swing(node) : swing(par);
swing(node);
}
}

以下的操作基本都需要 $splay$ 的辅助

insert

插入一个数
特判树上没有节点剩余的情况

  • 新建节点
1
2
3
4
5
void newnode(int num, int par){
val[++ ncnt] = num;
siz[ncnt] = cnt[ncnt] = 1;
fa[ncnt] = par;
}
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
void insert(int num){
if(!root){
newnode(num, 0);
root = ncnt;
return;
}
int now = root, nowpos;
while(1){
++ siz[now];//important
if(val[now] == num){
++ cnt[now];
splay(now, root);//*
return;
}
if(val[now] > num) nowpos = 0;
else nowpos = 1;
if(!son[now][nowpos]){
newnode(num, now);
son[now][nowpos] = ncnt;
splay(ncnt, root);
return;
}
now = son[now][nowpos];//别漏掉
}
}

find

返回值为 $num$ 的节点编号

1
2
3
4
5
6
7
8
9
10
11
12
int find(int num){
int now = root;
while(now){
if(val[now] == num){
splay(now, root);//*
return now;
}
if(val[now] > num) now = son[now][0];
else now = son[now][1];
}
return 0;
}

ruin

删除值为 $num$ 的节点
先找到该节点
如果 $cnt$ 大于 $1$, 减掉即可
如果不是,就分三种情况讨论
注意在 $find$ 的时候已经把该节点 $splay$ 到了根节点
1.左右子树为空: 删除该节点后树为空, $root=0$
2.左右子树都不为空: 为了维护删除节点后树的性质, 我们把左子树中值最大的节点 $(bef)$ $splay$ 到左子树根节点, 连接右子树根节点与该节点, 再让该点成为 $root$
3.左右子树有一个为空树: 直接改变 $root$ 即可

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
void ruin(int num){
int now = find(num);
if(!num) return;//数据万一有锅?
if(cnt[now] > 1){
-- cnt[now];
-- siz[now];//别忘了
return;
}
if(!son[now][0] && !son[now][1]){
root = 0;
return;
}
if(son[now][0] && son[now][1]){
int par = son[now][0];
while(son[par][1]) par = son[par][1];
splay(par, son[now][0]);
connect(son[now][1], par, 1);
connect(par, 0, 1);
update(par);
return;
}
int nowpos;
if(son[now][0]) nowpos = 0;
else nowpos = 1;
root = son[now][nowpos];
fa[root] = 0;
}

frank

返回值为 $num$ 的节点在树中按照大小排序的名次
其实就是把它 $splay$ 到根节点后,它左子树的大小 $+1$

1
2
3
4
5
int frank(int num){
int now = find(num);
splay(now, root);
return siz[son[now][0]] + 1;
}

arank

返回树中名次为 $k$ 的节点权值

1
2
3
4
5
6
7
8
9
10
11
int arank(int k){
int now = root;
while(1){
if(siz[son[now][0]] >= k) now = son[now][0];
else if(siz[son[now][0]] + cnt[now] >= k) {
splay(now, root);
return val[now];
}else k -= siz[son[now][0]] + cnt[now], now = son[now][1];
//转而在右子树中寻找
}
}

bef&aft

寻找某数的后驱与前驱,即小于中的最大或者大于中的最小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int bef(int num){
int now = root, ans = -MAXN;
while(now){
if(val[now] < num) ans = max(ans, val[now]), now = son[now][1];
else now = son[now][0];
}
return ans;
}

int aft(int num){
int now = root, ans = MAXN;
while(now){
if(val[now] > num) ans = min(ans, val[now]), now = son[now][0];
else now = son[now][1];
}
return ans;
}

reverse

区间翻转

  • downtag
    下传标记
    区间翻转时我们不考虑维护树的性质
    只用在 $arank$ 函数中更新即可
1
2
3
4
5
6
7
8
void downtag(int node){
if(tag[node]){
tag[node] = 0;
tag[son[node][0]] ^= 1;
tag[son[node][1]] ^= 1;
swap(son[node][0], son[node][1]);
}
}

注意这里我们为了防止越界,分别放置了一个值为 $inf$ 的节点和值为 $-inf$ 的节点
所以排在第 $k+1$ 位的节点其实是第 $k$ 位
与删除节点时的思想类似,我们把区间左边的节点旋到 $root$ 节点,把区间右边的节点旋到 $son[root][1]$ 节点,给 $son[ son[root][1] ][0]$ 打上标记

1
2
3
4
5
void reverse(int l, int r){
l = arank(l), r = arank(r + 2);
splay(l, root), splay(r, son[l][1]);
tag[son[r][0]] ^= 1;
}

print

中序遍历

1
2
3
4
5
6
7
8
9
void print(int node){
if(!node) return;
//downtag(node);
print(son[node][0]);
//if(val[node] != 1 && val[node] != n + 2)
//特判不输出为了防越界而加的节点
printf("%d ", val[node] - 1);
print(son[node][1]);
}