平衡树初步

David_Mercury · 2023-07-09 17:28:00 · 个人记录

一、总述

前面在基本数据结构中提到，数组支持 O(1) 查找排名对应数，O(n) 修改序列；链表支持 O(n) 查找排名对应数，O(1) 修改序列。那么，平衡树就综合了二者，是一种支持 O(\log_2 n) 查找与修改序列的一种树形结构。

以下我们从二叉查找树谈起，介绍几种平衡树。

二、二叉查找树

1. 概念

二叉查找树是一种满足“BST 性质”的二叉树。

2. 思想

BST 性质即为：对于树上任意一个节点，满足它自身关键码不小于左孩子关键码，不大于右孩子关键码。此时可以发现，对于二叉查找树的中序遍历即为一个关键码不严格单调递增的序列。

这样，我们就能够通过对该 BST 进行维护，来维护一个序列了。

为什么选择树形结构？我认为，树形结构具有链表的优点：易于删除、插入；但同时，也平衡了链表深度过深的问题。

3. 实现

二叉查找树只是平衡树的基础，我们并不会在考场上直接使用。略过。

三、Treap

1. 概念

\text{Treap} = \text{Tree} + \text{Heap}

Treap 是一种同时满足 BST 性质与堆性质的树形结构。是一种平衡树。

2. 思想

可以发现，二叉查找树是很有局限性的。在插入随机数据时，效率可以达到 O(\log_2 n)；但当插入比如说一个有序序列时，它就会退化为一条链，复杂度为 O(n)。这种左右子树大小相差很大的 BST 被称为“不平衡的”。

可以发现，同一个序列的 BST 的样貌是不唯一的。因此就想，如何通过某些手段来使它变得平衡。

Treap 采用的一种改变 BST 样貌的手段叫做旋转：

右旋 zig：左孩子成为父亲节点，父亲节点成为右孩子，左孩子原本的右孩子成为父亲节点的左孩子。

左旋 zag：右孩子成为父亲节点，父亲节点成为左孩子，右孩子原本的左孩子成为父亲节点的右孩子。

现在的问题是什么时候旋转可以使得 BST 变平衡。既然随机的二叉查找树平衡概率很大，就引入一个随机化的想法：为每个节点新增一个随机权值，使随机权值满足“堆性质”。很神奇啊，BST 性质和这个堆性质不会产生矛盾，因为一个决定左右，一个决定上下。

3. 实现

模板题：P3369 【模板】普通平衡树

先谈最基本的节点数值储存。一个权值 val，一个随机权值 dat，左右子节点编号 l,r，与该权值重合元素个数 cnt，size 该子树 cnt 之和。

操作分为几种。

• 新建节点。在此时附上随机权值。

• 自底向上更新信息（cnt, size）。

• 建树。注意建两个额外节点，值为正无穷、负无穷，可避免越界。

• 根据排名找元素。主要根据与左子树的 size 的关系来判断向左向右递归。若需要往右子树递归，要将目标 rank 变为 rank-size(l)-1，因为右子树所有节点的排名都在左子树与根节点之后。

• 根据大小找排名。按照中序遍历性质来判断向左向右递归。

• 旋转。已经说了。

• 插入。先检索到它应在位置。有相同元素则 cnt 增加，否则新建节点。回溯时，判断是否需要旋转子树，并更新信息。

• 找前驱 / 后继。以前驱为例，如果当前节点权值大于目标，更新答案，往左递归；如果小于等于，就往右走。

• 删除。若有重复，减少 cnt；否则就将节点向下旋转（过程中注意比较左右子树随机权值大小），直到旋到叶子节点，直接删除。回溯要更新信息。

4. 应用

模板题已经覆盖了它的大部分功能了，还是挺强大的。它大部分时候会作为一道题的中间步骤出现，仅仅关于它的题目一般思维难度不高，只是考验码力。而且，它的码量这么大，最好还是别写，STL set、multiset 基本可以代替（其实我不会 set）。

四、FHQ Treap

1. 概念

又称为无旋 Treap，因为它是一种基于分裂而非旋转的 Treap。功能上，它也比 Treap 强大许多。

2. 思想

为什么要分裂呢？可以发现，把这棵树裂成权值一大一小两半，自然地就可以为新节点腾出插入空间，也可以很轻松地删除一个中间节点。

两种分裂方式：按权值 / 排名。

以按权值为例。我们先定义分裂出的两棵树 lt, rt。对于当前节点，若其权值小于目标权值，那么它应该放在 lt；同时，它的左子树也全都小于权值，那么就可以一下子放入 lt；接着就向右子树递归即可。大于目标权值同理。

那么放进去以后，应该接在 lt, rt 的哪里呢？还是以 lt 为例。明显地，先接入的节点权值更小，因此当接入 lt 的最右端。

分裂过程之所以能达到 O(\log_2 n) 这么高效，得亏了左子树全都小于父节点这一性质。

合并呢？显然，lt, rt 两棵子树的左右，也就是 BST 性质已经区分好了。我们只需要关心如何合并可以满足堆性质。若关于随机权值， lt 的根节点大于 rt 的根节点，lt 根节点就可以确定为父亲，继续把 rt 与 lt 的右子树递归继续合并即可。

3. 实现

分裂与合并两个重要工具已经说完了。而平衡树应具有的其他功能，都可以通过两种分裂与合并的组合实现，就只提一点：对一个元素进行操作时，把它当作一棵子树裂出来 / 合进去。

4. 应用

刚刚提到 FHQ 的应用是很广的。它不但可以做 Treap 能做的所有事，还可以对一个无序序列进行操作，对一段数进行插入删除，甚至可以作为线段树来使用。唯一的缺点可能是常数较 Treap 更大。

• P4008 [NOI2003] 文本编辑器

比较典型的用 FHQ 来处理无序序列的题目。

• P3391 【模板】文艺平衡树

这种特殊的区间操作可以联想到灵活的 FHQ。巧妙的点在于引入了线段树的延迟标记思想。

• P2596 [ZJOI2006] 书架

将编号这一不变量就固定为书的下标。这时尽管知道它的子节点，它的位置依旧一无所知。所以我们就设法找到排名。接下来的问题全部被转化为知道排名问题，就迎刃而解了。

• P2042 [NOI2005] 维护数列

FHQ 典型应用大杂烩。这里面有 FHQ 做线段树的用法。