Weight Balanced Leafy Tree
Tangninghaha
·
·
算法·理论
Leafy Tree
Leafy Tree 是一种 仅 将信息储存在叶子的数据结构。线段树是一种常见的 Leafy Tree。
使用 Leafy Tree 的结构，进行加权维护，可以得到一棵平衡二叉搜索树。
WBLT
定义
WBLT 定义为一棵 Leafy Tree，即，叶子节点维护序列中的数值，非叶子节点维护其子树内的最大值。每一个节点具有两个或零个儿子。
$ls_x$ 表示 $x$ 的左子树，$rs_x$ 表示 $x$ 的右子树。
一个点的 $x$ 平衡度定义为 $\frac{\min(sz_{ls_x}, sz_{rs_x})}{sz_x}$，也就是较小的子树占整棵树的比例。
定义重构参数 $\alpha\in (0,\frac{1}{2}]$，当点 $x$ 的平衡度小于 $\alpha$，也就是较小子树过小时，我们认为点 $x$ 的子树失衡，需要进行平衡维护。否则我们认为 $x$ 子树是平衡的。
### 重构参数
若 $\alpha$ 过大，则平衡维护次数过多；若 $\alpha$ 过小，则树的深度较大。所以 $\alpha$ 一般适中，取 $0.25$ 可以避免浮点数运算，提升效率。
### 性质
由于 Leafy Tree 只有叶子存储信息，所以需要大约 $n$ 个非叶子节点，总结点数大约是 $2n$ 的。所以这是 WBLT 的一个缺点，它需要两倍的空间。
根据平衡度与重构参数的定义，当整棵树平衡时，每向父亲走一条边，树的大小至少乘 $\frac{1}{1-\alpha}$，那么总树高是 $O(\log n)$ 的。当 $\alpha=0.25$ 时，这个 $\log$ 大约是以二为底的 $\log$ 的 2 倍。
### 合并操作
假设合并两棵分别以 $x$ 和 $y$ 为根的 WBLT，需要保证 $x$ 的所有权值不大于 $y$ 的。
不失一般性地，假设 $sz_x\ge sz_y$，另一种情况是对称的。
若 $\frac{sz_y}{sz_x+sz_y}\ge \alpha$，那么此时直接合并即可。
若 $\frac{sz_{ls_x}}{sz_x+sz_y}\ge \alpha$，则递归合并 $x$ 的右儿子和 $y$，再将结果和 $x$ 的左儿子合并即可。
否则，将 $x$ 的左儿子与右儿子的左儿子合并，再将右儿子的右儿子与 $y$ 合并，将这两个结果合并即可。
从上到下分了三种情况，第一种情况是直接满足。当左儿子足够大时，直接将左儿子与剩余部分合并。否则，将左儿子拼上一个右儿子的左儿子，这样就足够大了，再进行合并。
OI-wiki 上说这样合并复杂度是 $O(\log \frac{sz_x}{sz_y})$ 的。
当插入或删除完成之后，可以使用这种操作合并两个子树，来维护平衡。由于树本身是平衡的，插入一个节点之后左右子树大小不会相差太多，所以这样的复杂度应该是常数的。
### 分裂操作
分裂有按值分裂和按排名分裂两种，但是应该是类似的。
根据子树权值大小决定递归分裂哪一侧。但是为了保证树的平衡，需要使用 merge 函数进行合并。
### 其它操作
其它操作基于分裂合并，并不是很难做。例如插入操作，可以懒惰地写作，先分裂，插入后，再合并。
## 代码实现
### 节点定义
```c++
struct Node {
int val, sz;
Node *ls, *rs;
Node() : val(0), sz(0), ls(nullptr), rs(nullptr) {}
Node(int v) : val(v), sz(1), ls(nullptr), rs(nullptr) {}
Node(Node *l, Node *r) : val(0), sz(0), ls(l), rs(r) {
if (l != nullptr) val = max(val, l->val), sz += l->sz;
if (r != nullptr) val = max(val, r->val), sz += r->sz;
}
bool leaf() {
return ls == nullptr;
}
} pool[OP_CNT << 1];
size_t pool_cnt;
Node *new_node(Node v) {
return &(pool[pool_cnt++] = v);
}
```
注意在有多个相同的值时，用不同的节点储存相同的值，防止无法平衡。
### 合并操作
```c++
void merge(Node *rt, Node *u, Node *v) {
if (u == nullptr) return void(*rt = *v);
if (v == nullptr) return void(*rt = *u);
int w = u->sz + v->sz;
if (min(u->sz, v->sz) * 10 >= w * 3) return void(*rt = Node(u, v));
if (u->sz > v->sz) {
if (u->ls->sz * 10 >= w * 3) {
Node *t = u->ls;
merge(u, u->rs, v);
return void(*rt = Node(t, u));
}
Node *t1 = u->rs, *t2 = u->rs->rs;
merge(u, u->ls, u->rs->ls);
merge(t1, t2, v);
return void(*rt = Node(u, t1));
}
if (v->rs->sz * 10 >= w * 3) {
Node *t = v->rs;
merge(v, u, v->ls);
return void(*rt = Node(v, t));
}
Node *t1 = v->ls, *t2 = v->ls->ls;
merge(v, v->ls->rs, v->rs);
merge(t1, u, t2);
return void(*rt = Node(t1, v));
}
```
合并只修改儿子指针指向的值，而不会修改指针本身，防止造成混乱。
合并时将空余节点进行了利用，防止出现过多垃圾节点，导致空间复杂度不是线性的。另一种写法是进行垃圾回收，但其实回收完之后马上就要再利用了，不如直接利用。
其余操作和二叉搜索树是基本一致的，只是插入和删除时需要合并两个子节点进行平衡维护。
## 持久化
持久化用路径复制实现，具体来说，修改了某一个节点，就将这个节点拷贝一份。具体实现只需要将 `merge` 函数修改，原本传入 `rt` 以回收垃圾节点，现在由于进行了修改，所以需要得到新的 `rt`，将合并的结果作为返回值即可。
```c++
Node *merge(Node *x, Node *y) {
if (x == nullptr) return y;
if (y == nullptr) return x;
int w = x->sz + y->sz;
if (min(x->sz, y->sz) * 10 >= w * 3) return new_node(Node(x, y));
if (x->sz > y->sz) {
if (x->ls->sz * 10 >= w * 3) return new_node(Node(x->ls, merge(x->rs, y)));
return new_node(Node(merge(x->ls, x->rs->ls), merge(x->rs->rs, y)));
}
if (y->rs->sz * 10 >= w * 3) return new_node(Node(merge(x, y->ls), y->rs));
return new_node(Node(merge(x, y->ls->ls), merge(y->ls->rs, y->rs)));
}
```
比如说插入就这么写，最后将返回的指针记住，这就是这次操作产生版本的根。
```c++
Node *ins(Node *cur, int v) {
if (cur->leaf()) {
auto t = minmax(cur->val, v);
return merge(new_node(t.first), new_node(t.second));
}
if (v <= cur->ls->val) return merge(ins(cur->ls, v), cur->rs);
return merge(cur->ls, ins(cur->rs, v));
}
```
## 文艺平衡树
相较于普通平衡树，区间操作要求支持分裂。比较容易弄出问题的一点是：假如分裂的最左侧是某一个点的右叶子，那么将这分离开之后，会出现其父亲只有一个儿子的情况，此时如果左叶子或右叶子和父亲的信息是重叠的，有一个节点是多余的，需要将这个节点回收，否则可能会 MLE。
另一个问题是，将根分裂之后，由于回收机制，根会被利用来放其它东西，这时候，如果合并的根选择原来的根，就会出问题。所以需要新建一个根来作为新的根。
## 持久化文艺平衡树
也是类似的。写的时候有些地方没下传标记，挂飞了，调了很久。
持久化文艺平衡树需要下传标记，传标记的时候也需要新建节点。