平衡树 - 知识点梳理

_本文中一行代码都没有，因为平衡树的代码变化很大，关键是理解思想，代码根本不重要，需要代码可以看我的提交记录_
平衡树是一种优化过的 BST。BST由于没有保证深度因此每次查询复杂度最坏为 \(O(n)\)，而平衡树通过在中序遍历不改变的情况下对树的结构做一些适当的调整，使每次查询时间复杂度降低，通常为 \(O(\log n)\)。同时，平衡树还支持一定的区间操作，因此在对有序序列操作的题上平衡树一般占优势。当然，平衡树也可以单纯用来维护有序集，并辅助其他算法进行运算。平衡树的空间复杂度通常为线性，因此空间上一般不会太受限。

实现

Van 树之源：BST

这是所有平衡树的基础，本身的用处约等于没有。
BST 的基本性质是：左子节点的所有数都小于根节点，右子节点的所有树都大于根节点。
这样查询时最多只需要走 BST 的深度条边，期望复杂度为 \((\log n)\)，但在特殊情况可以卡成一条链，即深度为 \(n\)，这就是为什么我们需要平衡树。

插入

假设我们在 BST \(x\) 中插入 \(p\)。
若 \(x\) 是空节点，直接将 \(p\) 放在 \(x\) 的位置。
若 \(val_x < p\)，根据性质我们需要将 \(p\) 插入在 \(x\) 的右子节点。递归即可。
若 \(val_x > p\)，相反我们将 \(x\) 插入在 \(x\) 的左子节点。
如果 \(val_x = p\) 插哪边都行。

删除

首先我们先把要删除的节点给删掉。
现在考虑如何填上这个空位。
如果当前节点是叶子节点，那就直接返回。
如果当前节点左右子节点不全有，那我们直接让子节点顶上来就可以了。
如果当前节点左有子节点全有，我们需要从左右子结点中找到一个数 \(x\) 使得 \(x\) 大于剩下左子节点的所有数，小于剩下右子节点的所有数。这样的数有两个：左子树中最大数和右子树中最小数。我们只需要找到这两个树中的一个然后将它顶到空位上来就行了。要找到一棵 BST 的最小/最大节点，根据性质只需要一直往左/右走，走到的节点就是该子树的最小/大节点。

查询排名

假设当前节点为 \(x\)，我们要查询 \(p\) 的排名。
若 \(p < val_x\)，则 \(p\) 一定在 \(x\) 的左子节点中，于是返回 \(p\) 在左子节点中的排名。
若 \(p = val_x\)，则答案直接是 \(size_{{ls}_x} + 1\)。
否则 \(p\) 在 \(x\) 的右子结点中，查询 \(p\) 在右子节点的排名，但要加上 \(size_{{ls}_x} + 1\)。

查询第 k 小

假设当前节点为 \(x\)，我们要查询排名为 \(k\) 的数是哪一个。
若 \(k \le sz_{ls_x}\)，则要查询的数一定在 \(ls_x\) 中。这时到 \(ls_x\) 中查询即可。
若 \(k = sz_{ls_x} + 1\)，则要查询的数是 \(x\)。
否则要查询的数在 \(rs_x\) 中，于是查询 \(rs_x\) 中排名为 \(k - sz_{ls_x} - 1\) 的数。

查询前驱/后继

设 \(x\) 的排名为 \(rank_x\)，排名第 \(k\) 小的数为 \(ranked_x\)。
\(precursor_x = ranked_{rank_x - 1}\)
\(successor_x = ranked_{rank_{x + 1}}\)
注意上面两个公式不完全对称。

知道这些以后，我们就可以入手平衡树了。

平衡定义：对于树中的任意节点，其左节点深度与右节点深度之差不超过 \(1\)。

AVL树

AVL树严格遵循平衡的定义，通过旋转来维护树的平衡。
旋转是一种操作，可以让树变得更加平衡。
在插入或删除时，若不平衡，可以进行旋转操作。

如图，在左图中，若 \(dep_{green} > dep_{orange}\)，此时根据平衡定义，该树不平衡。我们需要对它进行旋转。
注意，此操作我们至底而上递归进行，所以 \(dep_{green}\le dep_{blue} + 1\), 即 \(dep_{blue} \ge {dep_orange}\)
由于黄色节点深度较高，我们尝试将其旋转到根节点。
红色节点键值应小于黄色节点，因此应作为黄色节点的左子节点。此时多出来的绿色节点键值应小于黄色节点，但大于红色节点，因此应放到红色节点的右子节点。
原树深度差：\(dep_{green} + 1 - dep_{orange}\)。 现在深度差：\(dep_{green} + 1 - dep_{blue}\)。
因此原树变得更加平衡。现在，原树子节点深度差至多为 \(2\)。如果为 \(2\)，则再旋转一次即可。
AVL树由于完全遵照定义，因此在查询操作中常数非常小且复杂度严格（不能被卡），但同时也因此在每次修改操作时需要较多次数的旋转，因此修改常数较大，所以AVL树在静态问题中表现优秀。

Treap

Treap 不是一种严格平衡的平衡树，但基于随机，形态能够维护，期望复杂度也为 \(O(\log n)\)。相比AVL树，其平衡性虽然不如 AVL 树好，但如果修改次数较多，Treap 的运行时间会比 AVL 树小很多，适合大部分应用。
我们给每个节点定义一个随机值，记为 \(key_i\)。整棵树的 \(key\) 要满足堆的性质，键值要满足 BST 的性质。这样 Treap 的形态相对会比较正常（因此复杂度会较为接近 BST 的期望复杂度，\(O(\log n)\)）。
现在我们考虑如何维护它。

如图，假设 \(key_{orange} > key_{red}\)。
根据堆的定义（此处为大根堆，实际一般为小根堆），我们需要将黄色节点变为根节点，于是我们将黄色节点旋转到根即可，验证发现现在这棵树满足堆性质。（注意因为是一个一个节点操作的，所以最多只会有一个节点不满足堆的性质，因此 \(\max(key_{green}, key_{blue}) \le key_{red}\)）
Treap 的操作方式与 BST 相似，但需要在回溯时判断 \(key\) 是否符合性质。
Treap 是一种较为均衡的平衡树，但深度不完全符合定义，若查询次数较多常数会稍微偏大，但也不会被卡。同时 Treap 码量较大，容易出错，因此不推荐使用。

FHQ Treap

FHQ Treap 原理与 Treap 相同，都是通过维护随机 \(key\) 来达到维持形态的目的，但基于分裂与合并。其优点巨大：码量小，常数小，可持久化占空间最少且最简单，支持分裂合并，因此可以完成一些基于合并的问题，比如一些树上信息统计类问题。这类问题还有一种做法：启发式合并。FHQ Treap 代码量比启发式合并稍微大一些，但是支持直接询问排名，第 \(k\) 小，etc.
FHQ Treap 因为支持分裂和和合并，常规操作可以直接通过分裂合并进行，进一步减小代码量与常数。

分裂

设我们要将 FHQ Treap \(x\) 分为 \(p\)，\(q\) 两个子树，且 \(p\) 中的元素全部 \(< k\)，\(q\) 中的元素全部 \(\ge k\)。
首先先分析 \(x\) 的所属。
情况1：\(x < k\)，则 \(x\) 与 \(ls_x\) 全部属于 \(p\)，于是我们先将 \(x\) 赋值给 \(p\)，然后再单独处理 \(rs_x\)。而对于 \(rs_x\)，将其再分裂为两个子树 \(p_1\)， \(q_1\)， \(p_1\) 中所有数应都比 \(p\)（\(x\)）更大，\(key\) 也比 \(p\) （\(x\)）大，因此应作为 \(p\) 的右子节点，\(q_1\) 则作为 \(q\)。
情况2：\(x \ge k\)，则同理先把 \(x\) 赋值给 \(q\)，再分裂 \(ls_x\) 为 \(p_1\)，\(q_1\)，将 \(q_1\) 作为 \(q\) 的左子节点，将 \(p_1\) 作为 \(p\)。

合并

设我们要将 FHQ Treap \(x\) 与 \(y\) 合并。
首先先考虑将哪个节点作为根节点。显然应该把 \(key\) 更小的节点作为根节点，于是如果 \(key_x > key_y\)，swap(x, y)。
然后考虑我们应该将 \(y\) 放在 \(ls_x\) 还是 \(rs_x\)，这显然由 \(y\) 的键值决定。若 \(val_x > val_y\)，则将 \(y\) 与 \(ls_x\) 进行合并，否则将 \(y\) 与 \(rs_x\) 进行合并。
\(x\) 即为合并完树的根节点。

插入

我们直接把新插入的节点看成一棵树，然后将它与原树合并。

删除

设我们要删除 \(x\)。
我们把原树分成 \(3\) 棵树：\(l\) 中所有键值都 \(< x\)，\(t\) 中所有键值都 \(= x\)，\(r\) 中所有键值都 \(> x\)。
这样我们要从 \(t\) 中删除一个元素，最简单的方法是 \(t \leftarrow merge(ls_t, rs_t)\)。
然后我们在顺次将 \(l\)，\(t\)，\(r\) 合并即可。

查询排名

查询排名相当于找到比当前数小的树的个数再加一，自然而然地想到分裂。
设我们要查询 \(k\) 的排名。
我们将原树分裂为 \(l\)，\(r\)，关键字为 \(k\)。
答案即为 \(size_l + 1\)。
查询完再将树合并回去即可。

查询第 k 小

这个操作没有捷径，必须使用普通 BST 的方法进行查询。

查询前驱/后继

还是使用那个公式。

FHQ Treap 优点很多。但有一个缺点：FHQ Treap 树的形态容易发生变化，所以比较难维护区间信息，维护区间信息一般选取 Treap 或者 Splay。（但可持久化除外，因为其他平衡树写可持久化更难）

Splay

Splay 也是一种基于旋转的平衡树，但不需要维护键值，是所有平衡树除了替罪羊树以外最无脑的一种（做法相对较暴力）。它的复杂度基于热度查询，常数不大，但在进行拓展时复杂度容易伪（因为不是所有的操作操作完都适合 Splay），所以拓展时能不使用 Splay 就使用其他的，因为 Splay 出锅率最大。话虽如此，Splay 的拓展应用很多，其中就包括著名的 Link Cut Tree。

核心操作：Splay

一般情况下，当我们对一个节点进行完操作之后我们会将这个节点旋转到根。这就是所谓的 Splay 操作，也就是热度查询的机制。
当然不是所有的情况都适合splay。
适合进行 Splay 的操作：

• 查询类操作
• 需要 Splay 的节点较为集中的操作

不适合进行 Splay 的操作：

• 需要 Splay 的节点深度明显大于平均深度的操作
• Splay 完还需要进行大量修改的操作
• 进行非常频繁的操作（比如pushdown）
• 和树的具体形态有关的操作

Splay 的其他操作与 BST 无异。

Splay 因为复杂度容易出锅，代码量大，所以能不用尽量用其他的平衡树代替，但 Splay 拓展方法很多，比如文艺平衡树。

替罪羊树

最暴力的平衡树，码量一般。优点是完全不需要脑子，复杂度不容易伪，几乎不会错，但缺点也很明显：常数大。
替罪羊树不是一种完全平衡的树，但它保证左右节点的大小差别不会很大，变相限制了深度。
操作方式很简单，如果左节点大小与右节点大小的比值超过了 \(\dfrac{1}{\alpha}\) 或低于 \(\alpha\) 则直接将当前树所有节点排序后重建。

总结

平衡树是对 BST 的一种优化，BST 因为树的形态不确定所以复杂度没有保证，而平衡树通过维持树的形态将复杂度控制在 \(O(\log n)\)。平时写平衡树尽量用 FHQ Treap 或替罪羊树，而对于查询操作较多的题如果想要优化常数可以考虑 AVL 树，普通优化常数一般用 Treap。Splay 无论如何都尽量少用，但 Splay 的拓展性最好，可以解决很多 Leafy Tree 或者线段树解决不了的区间问题，使用时注意在合适的时间 Splay，避免被卡。