平衡树
建议在清楚二叉搜索树的所有操作之后食用本文。本文将略过部分基础知识
本文主要会讲到4中较常用的平衡树：
-
Treap
-
FHQ-Treap（无旋Treap）
-
Splay
-
WBLT
其实WBLT不怎么常用，但是我个人最喜欢用
我将会在另一篇文章中讲述其他的平衡树，如AVL，红黑树，替罪羊树等。
可持久化我还会放在另一篇文章中讲述，敬请期待。
Treap
Treap也就是 Tree + Heap，在满足二叉搜索树的前提下，通过维护二叉堆的性质来保证其复杂度不会太大，一般我们认为是
先声明一点名词：
-
权值：也就是数据，每一个结点保存的数据。
-
优先度：用于维护二叉堆性质，是新建结点的时候随机生成的。
图中我会以二元组的形式给出，格式为
权值，优先度我一般习惯用大根堆，且优先度为非负数，这样要方便一点
这是一颗很简单的树，我们现在来考虑各种操作。
不过，我还是给出树的声明：
其他的树定义类似！
typedef unsigned int uint;
template<int N = 1e5 + 3>
class Treap {
private:
int lc[N], rc[N]; // 左右节点
uint pri[N]; // 优先度，定义为非负整数！
int val[N]; // 权值
int cnt[N]; // 计数器
int siz[N]; // 以当前结点为根的子树的结点个数（用于查找kth和rank）
int root, usage; // 根节点和使用的结点个数
// int fa[N]; // 记录父亲结点，如果需要的话
public:
// ...
}
旋转
这里我们记住一张图即可：
从左到右是右旋，从右到左是左旋。
可以发现，这种旋转并不会改变中序遍历的结果（不会影响二叉搜索树的性质）。但是可以影响二叉堆的性质。所以我们可以以此维护二叉堆的性质。
由于我们需要改变 q 或者 p 父节点对其的指向，我们采用引用的方式修改父节点。
后面的Splay也会有旋转的操作，但是两者需要的旋转方式不一样。
这里是将子节点旋转到当前结点
p上，而splay中的旋转在实现的时候是把当前节点p转到父结点上，别混淆了！
void leftRotate(int &p) { // 定义左旋操作
int q = rc[p];
rc[p] = lc[q], lc[q] = p;
p = q; // 更新父节点对此结点的信息
update(lc[p]), update(p); // 更新结点信息。p已经改变过了！
}
void rightRotate(int &p) { // 定义右旋操作，与上面类似，只是变化了一下lc和rc！
int q = lc[p];
lc[p] = rc[q], rc[q] = p, p = q;
update(rc[p]), update(p);
}
是不是该说一下
update是个啥？直接看代码吧：
void update(p) { siz[p] = siz[lc[p]] + siz[rc[p]] + cnt[p]; }
插入
与二叉搜索树的插入类似。如果遇到已经插入过的结点可以选择新建结点，或者增加标记（++cnt[p]），这里选择后者。
我们先来看新建结点的过程：
int newNode(int x, uint prio = 0) {
++usage;
lc[usage] = rc[usage] = 0;
pri[usage] = prio ? prio : rand();
val[usage] = x;
cnt[usage] = siz[usage] = 1;
return usage;
}
这只是新建一个空结点的操作而已……接下来我们才涉及到插入部分。
新建结点的操作每一种树都很类似，注意灵活修改！
首先我们还是正常的插入，例如我们在刚开始的例子的基础上插入了 (6, 8)
那么根据二叉搜索树的插入方式，插入后应该如下：
很明显，此时不满足二叉堆的性质，我们需要通过旋转的方法来维护。
不难得知，我们需要对 (7, 7) 做一次右旋操作，以使 (6, 8) 成为 (7, 7) 的父节点，从而满足二叉堆的性质。
结果如下：
接着，由于我们一定是在最底部插入的结点，所以我们只需要在回溯的时候一路向上维护二叉堆的性质即可。
代码如下：
void insert(int &p, int x) { // 由于旋转操作需要来自父节点的引用，新建节点也是！
if (!p) {
p = newNode(x); // 新建结点
return;
}
if (val[p] == x) { // 有相同结点，增加引用即可
++cnt[p], ++siz[p];
return;
} else if (val[p] > x) { // 进入左树
insert(lc[p], x);
if (pri[p] < pri[lc[p]]) rightRotate(p); // 维护二叉堆性质
} else { // 进入右树
insert(rc[p], x);
if (pri[p] < pri[rp[p]]) leftRotate(p);
}
update(p); // 更新信息
}
删除
首先我们先找到需要修改的结点：
void remove(int &p, int x) {
if (!p) return; // 没有找到要删除的结点
if (x != val[p]) {
remove(x < val[p] ? lc[p] : rc[p], x), update(p);
return;
}
// TODO
}
然后我们考虑两种情况：
-
如果计数大于1，那么我们减少计数，结束即可：
if (cnt[p] > 1) { --cnt[p], --siz[p]; return; } -
如果计数等于1，那么我们不断再保证二叉堆的性质的情况下不断向下旋转。直到没有子节点，那么我们可以直接
p = 0，删除即可。if (lc[p] || rc[p]) { if (rc[p] == 0 || pri[lc[p]] > pri[rc[p]]) { rightRotate(p), remove(rp[p], val); } else { leftRotate(p), remove(lc[p], val); } } else { p = 0; }
依据逻辑把三个部分合起来即可。
其他操作
例如查找第k大，获取某个数的排名，获取前驱或者后驱。
和二叉搜索树的方法一致，这里就不过多讲述了。
代码链接
此处采用的是另一种写法！注意甄别！ LinkFHQ-Treap
首先我们了解一下这个东西和普通的Treap有啥不同：
-
FHQ-Treap基于分裂和合并的操作，代替了旋转，使得可持久化更为容易
-
操作相对简单，时间复杂度的阶没有变化，还是
O ( log n ) " role="presentation">，但是常数要大一点
我们先来看最重要的分裂部分
分裂
分裂有两种形式
-
按权值
v分裂：将小于等于v的所有节点分裂为一棵树，大于v的放在一棵树 -
按排名
k分裂：将前k个数放在一棵树，其他的放在另一颗树。
两者十分类似，代码几乎一模一样，所以这里只细述按权值分裂。
我们还是拿最初的那张图为例子来讲：
假如我们要按权值 4 分裂，也就相当于分成如下两棵树：
按权值 3 分裂，也就相当于分成如下两棵树：
蓝色的表示新建的边，红色的表示断开的边
似乎有点感觉了？我们来细谈分裂的全过程
约定此处红色为左树（权值小于等于
v），蓝色为右树（权值大于v），绿色为下一步进入的结点
x结点指新入的结点需要拼接到的位置，y同样
这里以按权值 3 分裂为例子：
肯定是从根节点开始，明显，根节点的权值
接下来我们判断结点 (3, 8)，明显，节点的权值 (4, 6)
同样的判断，将 (4, 6) 放置在蓝树
下一步的结点为空，结束分裂。
通过观察，我们可以发现分裂后树的相对形态没有改变，所以我们可以尝试着直接在原树上直接分裂，避免复制结点的操作。
在我的代码中，
sync和其他人写的pushdown是一样的，只是我不习惯如此写……所以使用sync代替pushdown，使用update代替pushup……
哦，对了，忘了说，这部分的代码似乎没有验证过…… 总代码详见：FHQ-Treap
代码如下：
void splitByVal(int p, int v, int &x, int &y) {
if (!p) return (void)(x = y = 0);
// sync(p); // 如果需要，下传标记！！
if (val[p] <= v)
x = p, splitByVal(rc[p], v, rc[p], y);
else
y = p, splitByVal(lc[p], v, x, lc[p]);
update(p);
}
而按照排名分裂十分类似，这里直接给出代码：
void splitByRank(int p, int k, int &x, int &y) {
if (!p) return (void)(x = y = 0);
// sync(p); // 如果需要，下传标记！！
if (siz[lc[p]] < k)
x = p, splitByRank(rc[p], k - siz[lc[p]] - cnt[p], rc[p], y);
else
y = p, splitByRank(lc[p], k, x, lc[p]);
update(p);
}
合并
由于我们保证了左树的最大值一定不大于右树的最大值，所以我们只需要考虑优先度即可。
那么我们来演示上面分裂后的两棵树合并的过程。
此时 x, y 为左树和右树的当前结点。返回的是合并后的结点编号。
首先，y 的优先度较大，那么此时 y 作为父节点，转而合并 x 和 y 的左子树，作为 y 的左子树：
此时 x 的优先度较大，所以此时 x 作为父节点，合并 x 的右子树和 y，作为 x 的右子树。
此时 x 为空，直接接上即可。
至此，合并完成。
合并会遇到的两种情况这里都涉及到了，那么我们来看代码：
int merge(int x, int y) {
if (!x | !y) return x | y;
// sync(x), sync(y); // if need
if (pri[x] > pri[y]) {
rc[x] = merge(rc[x], y);
return update(x), x;
} else {
lc[y] = merge(x, lc[y]);
return update(y), y;
}
return -1; // NEVER REACH!
}
其他操作
其他操作很容易通过分裂和合并的操作完成，这里讲述思路即可。
-
插入：新建一个结点作为单独的一棵树，将原树按权值分裂，三者合并即可。
void insert(int &root, int v) { int p = newNode(v); int x(0), y(0); splitByVal(root, v, x, y); root = merge(merge(x, p), y); } -
删除：分裂成三棵树，中间的树结点的权值全部为
v，分别合并即可。void remove(int &root, int v) { int x(0), y(0), z(0), tmp(0); splitByVal(root, v - 1, x, tmp); // 分裂为 < v 和 >= v 的两棵树 splitByVal(tmp, v, y, z); // 再分裂为 = v 和 > v 的两棵树 // 以此避免判断没有v的情况 root = merge(merge(x, lc[y]), merge(rc[y], z)); } -
第
k大：按排名分裂即可。 -
查询排名：按权值分裂（为
< x " role="presentation"> 和≥ x " role="presentation"> 的两棵树），使用左树的大小即可。 -
前驱或者后驱：分裂即可……
整体代码我就不给了，核心就这些了。
Splay
伸展树，由Tarjan（对，就是他）在1985年发明。它与正常的平衡树不同，不能保证每一次的操作在
Splay最大的特点是每次对一个结点进行操作（读取，或者修改）之后，都会把他转到根节点上。
旋转
我们先来看旋转操作。
还是要记住上面给出的旋转的图，这样方便于理解。这里就不细讲了。
注意和Treap的旋转操作区分开来，这里的旋转是将当前结点旋转到其父节点的位置！
// 0 表示是父节点的左子节点，1表示为右子节点
#define side(x) ((x) == rc[fa[(x)]])
// 利用 side 获取对应的子节点
#define ch(x, k) ((k) ? rc[x] : lc[x])
// rotate x to it's fathers position!
void rotate(int x) {
int y = fa[x], z = fa[y], k = side(x);
ch(y, k) = ch(x, k ^ 1);
if (ch(x, k ^ 1)) fa[ch(x, k ^ 1)] = y;
ch(x, k ^ 1) = y, fa[y] = x, fa[x] = z;
if (z) ch(z, y == rc[z]) = x;
update(y), update(x);
}
在Splay的实现中，
update操作没有变化，还是siz[p] = siz[lc[p]] + siz[rc[p]] + cnt[p]
伸展
伸展是Splay最最核心的操作，也就是把一个结点旋转到根节点（或者其他地方）。
但是仅仅是一路把当前结点向上旋转就可以了吗？并不是的。
如果仅仅是一路向上，那么会有上图的结果，此时我们只需要来回不断地操作，就可以卡成单次
对于每一次旋转我们分类讨论：
-
旋转一次可以到达目的地：直接旋转即可。
-
至少需要两次旋转：
-
当前结点与其父节点为同侧：先转父节点，再转子节点。
-
不同侧，直接两次向上转即可。
-
那么通过这个规则，我们就可以得到这样一张图：
是不是矮了一点 _
我们可以理解为通过这种规则旋转，每次至多可以减少二分之一的高度，最终下来，高度可以保证在
O ( log n ) " role="presentation"> 的样子。
所以，伸展的核心代码就可以写出来了：
target指的是向上不停转之后的最终父节点是什么，注意！
void splay(int x, int target) {
// sync if need!
// for (int i = x; i; i = fa[i]) stack[++top] = i;
// while (top) sync(stack[top--]);
while (fa[x] != target) {
int y = fa[x], z = fa[y];
if (z != target) rotate(side(x) == side(y) ? y : x);
rotate(x);
}
if (!target) root = x;
}
其他操作
删除操作非常特殊，后文里会讲，还有，记得每一次无论是查找还是修改什么的，记得把目标节点Splay到根！！！
大部分和二叉搜索树一样。这里不细讲了。
不过这里建议一下Splay的写法细节：
-
写两个辅助函数，一个用于寻找对于排名的结点，一个用于寻找对于值的结点，都是返回的结点编号。
int _findVal(int v) { int cur = root; while (cur) { // sync(cur); // if need if (val[cur] == v) return cur; else if (v < val[cur]) cur = lc[cur]; else cur = rc[cur]; } return cur; // 0 for not found! } // return the node index of the kth element int _findKth(int k) { int cur = root; while (cur) { // sync(cur); // if need if (siz[lc[cur]] >= k) cur = lc[cur]; else if (siz[lc[cur]] + 1 == k) return cur; else k -= siz[lc[cur]] + 1, cur = rc[cur]; } return cur; } -
其他的操作都一定程度上可以基于这两个操作（或者这两个操作的变换）。例如
remove。具体操作看注释void remove(int v) { int p = _findVal(v); if (!p) return; splay(p, 0); // 转到根节点 if (--cnt[p]) return update(p), (void)0; // 减少计数即可 // 如果只有一个子节点，直接作为根节点即可。 if (!(lc[p] && rc[p])) { root = lc[p] | rc[p]; fa[root] = 0; // 不需要更新！ return; } // 否则寻找后驱 int nxt = rc[p]; // sync(nxt); // if need while (lc[nxt]) nxt = lc[nxt]/*, sync(nxt) */; // 将后驱转到p的右节点的位置 splay(nxt, p); // 此时 lc[nxt] 一定为空，考虑二叉搜索树的性质 // 所以我们直接把nxt作为根节点，连接原本p的左子树即可。 lc[nxt] = lc[p]; update(root = fa[lc[p]] = nxt); // 更新信息 }
其实主要是一些奇怪的操作需要……可恶。
WBLT
这是我最喜欢用的一种平衡树，而且借鉴FHQ-Treap的思路，可以实现类似的操作，这类似的操作这里不细讲。本文只讲述基本。
定义：
-
叶节点：没有子节点的节点。
-
内节点：有子节点的节点。
WBLT全称是 Weight Balanced Tree，有一点类似于 Size Balanced Tree，只是WBLT是一种 Leafy Tree，只有叶节点（没有子节点的结点）保存有信息。而其他的内节点都是用于辅助搜索的。
而且WBLT的每一个节点要么是满的，要么是空的。或者说要么左右儿子都有，要么都没有。再或者说内节点既有左节点也有右节点。这使得操作非常方便……
那么内节点如何辅助搜索？在WBLT中，内节点存储的是右节点的值。
语言描述太罗嗦，我们还是直接上图：
结构还是挺一目了然的。
真正保存着信息的其实只有红色圈起来的节点。
不难看出，总共有9个节点，总而言之，如果有
搜索
这或许是唯一一个需要从搜索开始讲述的平衡树了
例如我们需要搜索值 3，那么搜索路径应该是这样的。
由于WBLT内节点保存信息的特性，我们进入下一个节点可以分如下情况讨论：
-
到达叶子节点：如果当前节点的值等于所需节点的值，那么搜索成功，否则，没有搜到。
-
在内节点上：如果左子节点的值大于等于目标值，则进入左子树，否则进入右子树。
其实看图不难发现，当前节点的值就是当前子树中的最大值，所以可以进行上述操作。
这个规则同样适用于其他的操作！请务必画下来试一下！
维护平衡
当然还是需要用到旋转的操作。
别忘了那张图！！！
但是在WBLT中旋转的实现又不一样了。
因为内节点并没有保存实际的信息，所以我们只需要 swap 三次，update 两次即可。
对了，我好像还没有讲过
update。在WBLT中，有所变化：
void update(int p) { if (lc[p]) { // 防止更新叶节点 // sync(p) // if need siz[p] = siz[lc[p]] + siz[rc[p]]; val[p] = val[rc[p]]; } }
为了减少代码，采用了一点奇技淫巧：
#define ch(p, k) (k ? rc[p] : lc[p])
// k 0 left to here, k 1 right to her
// k是0则将左子节点旋转到此处，否则右节点旋转到此处。
// 但是这里没有旋转，只是交换节点而已，简化操作。
void rotate(int p, int k) {
int q = ch(p, k); // sync(q); // sync if need
if (!p || !q) return;
swap(lc[q], rc[q]), swap(lc[p], rc[p]);
swap(ch(q, k ^ 1), ch(p, k));
fa[ch(p, k)] = p, fa[ch(q, k ^ 1)] = q;
update(q), update(p);
}
那么我们考虑如何维护平衡：
其实一般来说，
WBLT常数本来就小，所以不需要那么严谨的旋转也可以很好的通过很多题。// 非严谨写法！！！ void fix(int p) { const int ratio = 2; if (siz[lc[p]] * ratio < siz[rc[p]]) rotate(p, 1); // 左子树太大 if (siz[rc[p]] * ratio < siz[lc[p]]) rotate(p, 0); // 右子树太大 }
但是为了严谨，肯定不能就这么水过去，万一有人卡WBLT的常呢？？
所以我们还是要稍微严谨一点。
这一部分感谢大佬的文章：抛弃随机，保持理性——Leafy Tree 到 WBLT - 听风响，闻虫鸣。 - 洛谷博客
在WBLT中，平衡是加权的（并不是严格平衡的），一般来说，我们令平衡因子为
那么节点 x 平衡意味着
不难发现，
如果所有节点都满足加权平衡，则这棵树是加权平衡的，并且其高度满足
那么应该如何旋转？很明显，在非严谨写法中已经体现出了雏形了：哪一棵子树大就把那一棵子树转上来。
但是观察上图可以知道 b 所在的子树相对位置是不会变的，也就是说如果
所以此时我们应该把 b 向上转一下，然后再进行类似的维护。
这里讲的相对感性，更严谨的证明请参考上面给出的文章
操作类似于：
相当于把 b 阉割成俩，然后分别和 a, c 在一起……
所以我们可以得出如下代码：
#define ch(p, k) (k ? rc[p] : lc[p])
void fix(int p, double ratio = 0.29) {
int d;
if (siz[lc[p]] < siz[p] * ratio) d = 1;
else if (siz[rc[p]] < siz[p] * ratio) d = 0;
else return;
int q = ch(p, d);
if (siz[ch(q, d)] < siz[p] * ratio) rotate(q, d ^ 1);
rotate(p, d);
}
插入
还是以上图为例。不妨假设我们需要插入 3，那么自然我们到了原来 3 所在的节点。那么我们如何变成两个呢？
很明显，将当前节点作为父节点，左右节点分别为当前节点的值和新增的值。
记得保证左节点不大于右节点的值
然后回溯更新即可。
void insert(int x) {
if (!root) {
root = newNode(x, 0);
return;
}
int cur = root;
while (true) {
// sync(cur); // if needed
if (!lc[cur]) { // new node down here!
int y = val[cur];
if (x > y) swap(x, y); // make sure x < y
// 第二个参数是将其父节点设为cur！和Treap的newNode声明不一样了
lc[cur] = newNode(x, cur), rc[cur] = newNode(y, cur);
break;
}
cur = (x > val[lc[cur]]) ? rc[cur] : lc[cur];
}
while (cur) {
update(cur), fix(cur);
cur = fa[cur];
}
}
删除
我们还是先找到要删除的值所对应的节点吧（任意一个）。
那么我们用其兄弟节点直接替代其父节点即可。
兄弟节点指的是其父节点的另一个子节点
听着很简答吧。在纸上画一下先！！
参考代码：
// 这一块的代码未经编译验证！！可能会有问题
void copyFrom(int p, int q) {
lc[p] = lc[q], rc[p] = rc[q];
fa[lc[p]] = fa[rc[p]] = p;
val[p] = val[q], siz[p] = siz[q];
}
void remove(int p, int x) {
if (!p) return;
if (val[lc[p]] >= x) {
if (siz(lc[p]) == 1 && val[lc[p]] == val) {
// _del(rc[p]), _del(lc[p]); 标记回收节点，如果需要的话（记得别清空，copyFrom需要用！）
copyFrom(p, lc[p]);
} else {
remove(lc[p], val), update(p), fix(p);
}
} else {
if (siz(rp) == 1 && val(rp) == val) {
// _del(lp), _del(rp);
copyFrom(p, rc[p]);
} else {
remove(rc[p], val), update(p), fix(p);
}
}
}
当然，你也可以写成非递归的形式，这里就不展示了。
其他操作
其实我觉得其他操作都很简单，不想多说，掌握了二叉搜索树的算法，应该自然就会了。
这里就直接展示部分基础操作的代码吧。
// 统计所有 < x 的值的个数，也可以用于获取排名
int count(int x) {
int cur(root), cnt(0);
while (cur) {
if (siz[cur] == 1) return cnt;
else if (val[lc[cur]] >= val) cur = lc[cur];
else cnt += siz[lc[cur]], cur = rc[cur];
}
}
int kth(int k) {
int cur(root);
while (cur) {
if (siz[cur] == 1) return k == 1 ? val[cur] : -1; // -1: not found!
else if (siz[lc[cur]] >= k) cur = lc[cur];
else k -= siz[lc[cur]], cur = lc[cur];
}
}
int getpre(int val) {
return kth(count(val));
}
int getpost(int val) {
return kth(count(val + 1) + 1);
}
到这里，你应该学会了四种在OI中较为常用的平衡树了吧。
那么模板题肯定可以用四种方法过了吧：
哦，文艺平衡树啊，并不是一种平衡树，它可以通过FHQ-Treap或者Splay实现，拓展的WBLT也可以实现（只是这里没有讲）。
不过可以给出参考代码：FHQ-Treap 文艺平衡树
附赠各种树速度比较（基于正常平衡树随机数据的操作）：
Splay < FHQ-Treap < Treap < WBLT < Better-Optimized FHQ-Treap
+ ?? 阳寿随机种子Treap
更加优化的Treap参考：treap怎样跑得更快 - zx2003 的博客 - 洛谷博客