平衡树（无旋Treap，范浩强树）学习笔记

mekdull · 2023-11-14 20:32:37 · 个人记录

平衡树：YYDS

以下是常见的平衡树/要用平衡树实现的算法：

• Treap（有旋/无旋）
• Splay树
• WBLT（Weight Balanced Leafy Tree，重量平衡线段树）
• SBT（Size Balanced Tree，陈启峰树）
• AVL树
• B树 、B+树
• 笛卡尔树
• 红黑树 、左偏红黑树 、AA树
• 替罪羊树 \to K-D Tree（k-Dimension Tree）
• LT（Leafy Tree，平衡线段树）
• 2-3树 、2-3-4树
• ······

（平衡树能整出的花活真TM多）可见，平衡树在计算机科学中是一种非常重要的数据结构。

其中，在 NOIP 考试范围内的有：

1. Treap（有旋/无旋）
2. Splay树
3. 笛卡尔树

在这之中，我认为无旋 Treap（范浩强树）在 OI 中的应用最为重要与广泛。所以，这篇笔记主要记录范浩强树的实现。（绝对不是因为时间紧迫所以只学了无旋 Treap）

前置知识：二叉搜索树

二叉搜索树是一种二叉树的树形数据结构，其定义如下：

1.空树是二叉搜索树。

2.若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。

3.若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。

4.二叉搜索树的左右子树均为二叉搜索树。^{[1]}

二叉搜索树上的基本操作所花费的时间与这棵树的高度成正比。对于一个有 n 个结点的二叉搜索树中，这些操作的最优时间复杂度为 O(\log n)，最坏为 O(n)。随机构造这样一棵二叉搜索树的期望高度为 O(\log n)。

在给朴素搜索树插入一个新节点时，我们需要从这个搜索树的根节点开始递归，如果新节点比当前节点小，那就向左递归，反之亦然。最后当发现当前节点没有子节点时，就根据新节点的值的大小，让新节点成为当前节点的左或右子节点。^{[1]}

如果新插入的节点的值是随机的，那这个朴素搜索树的形状会非常的「胖」。也就是说，每一层的节点比较多。若如此，那么它可以达到我们期望的复杂度。这里放一张图来表示一下随机情况下期望得到的满二叉树，其深度为 log(n)：

但是它可以被卡成最坏复杂度。

如果我们有序地（如输入一个单增的序列）给一个朴素的搜索树插入节点，那这棵树就会变得非常 “瘦长” 。由于每次插入的节点都比前面的大，所以都被安排到右儿子上了。

那这就跟一条链（实际上是一个链表）一样了，所有操作复杂度都退化为 O(n)，然后就会 T 飞。

引用一张 oi-wiki 上的图来表示这棵可怜的树：

这棵树中，节点 1 到节点 5 权值递增。

怎么解决呢？Treap 给出了一个 比米奇妙妙屋还要妙的 解法。

Treap

Treap（树堆）是一种 弱平衡 的 二叉搜索树。它同时符合二叉搜索树和堆的性质，名字也因此为 tree（树）和 heap（堆）的组合。^{[1]}

根据定义，我们可以得出它的一些基本性质：

1.左子节点的值（ \textit{val} ）比父节点大

2.右子节点的值（ \textit{val} ）比父节点小（当然这也是可以反过来的）

3.子节点值（ \textit{priority} ）比父节点大或小（取决于是小根堆还是大根堆）^{[1]}

前两个是二叉平衡树的性质，后一个是堆的性质。

声明：以下若没有特殊说明，使用的都是小根堆，包括最后的代码板子。

不难看出，如果用的是同一个值，那这两种数据结构的性质是矛盾的，所以我们再在搜索树的基础上，引入一个给堆的值 \textit{priority}。对于 \textit{val} 值，我们维护搜索树的性质，对于 \textit{priority} 值，我们维护堆的性质。其中 \textit{priority} 这个值是随机给出的。^{[1]}

那么，Treap 要怎么解决二叉搜索树的问题呢？

关键就在 Treap 中的那个堆。

Treap 通过随机化的 \textit{priority} 属性，以及维护堆性质的过程，「打乱」了节点的插入顺序。从而让二叉搜索树达到了理想的复杂度，避免了退化成链的问题。^{[1]}

Treap 有较为严格的复杂度证明（看这里），每一次操作都是 O(logn)的。

总之，你永远可以相信 Treap 的力量。

现在，就到了平衡树的一个关键了：如何维护平衡。

在这里，Treap 分裂成了两派：一派用旋转维护，称为 有旋 Treap ；另一派就是这篇笔记的重点，它使用 分裂 与 合并 两个操作来维护，这就是所谓的 无旋 Treap，即 范浩强树。

相比于有旋的，无旋的优势在于代码实现简单，可以方便地进行区间操作。缺点则是常数较大，但一般我们不会在意这些常数。（况且我们还有一些虽然不常用但确实可行的优化）^{[2]}

无旋 Treap

下面逐一介绍无旋 Treap 的基本操作。

分裂（split）

注：这里的分裂方式是按值分裂，事实上还可以按排名分裂，两种方法的效果一样。

分裂过程接受两个参数：根指针 \textit{cur}、关键值 \textit{key}。结果为将根指针指向的 Treap 分裂为两个 Treap，第一个 Treap 所有结点的值（\textit{val}）小于等于 \textit{key}，第二个 Treap 所有结点的值大于 \textit{key}。

该过程首先判断 \textit{key} 是否小于 \textit{cur} 的值，若小于，则说明 \textit{cur} 及其右子树全部大于 \textit{key}，属于第二个 Treap。当然，也可能有一部分的左子树的值大于 \textit{key}，所以还需要继续向左子树递归地分裂。对于大于 \textit{key} 的那部分左子树，我们把它作为 \textit{cur} 的左子树，这样，整个 \textit{cur} 上的节点都是大于 \textit{key} 的。^{[1]}

为了方便理解，这里引用一张 oi-wiki 上的图表示 cur<key 时的分裂： 示例代码：

int update(int o){return t[o].sz=t[t[o].l].sz+t[t[o].r].sz+1,o;}//update用于更新size
void split(int o,int x,int &l,int &r)//o即上文中的cur，x即key，l和r是左右端点。
{
    if(o==0) return l=0,r=0,void();
    if(t[o].k<=x) l=o,split(t[o].r,x,t[o].r,r);
    else r=o,split(t[o].l,x,l,t[o].l);
    update(o);
}

合并

因为需要合并的两个 Treap 已经有序，所以我们在合并的时候只需要考虑把哪个树「放在上面」，把哪个「放在下面」，也就是是需要判断将哪个一个树作为子树。

显然，根据堆的性质（再次提醒：我们采用的是小根堆），我们需要把 \textit{priority} 小的放在上面。

同时，我们还需要满足搜索树的性质，所以若 l 的根结点的 \textit{priority} 小于 r 的，那么 l 即为新根结点，并且 r 因为值比 l 更大，应与 r 的右子树合并；反之，则 r 作为新根结点，然后因为 l 的值比 r 小，与 r 的左子树合并。

int merge(int l,int r)
{
    if(l==0||r==0) return l+r;
    if(t[l].p<=t[r].p) return t[l].r=merge(t[l].r,r),update(l);//p即priority
    return t[r].l=merge(l,t[r].l),update(r);
}

插入

为了插入一个关键码为 x 的节点，我们把整棵树分裂成不大于/大于 x 的两棵树 A,B，然后直接申请一个新的节点。最后将新节点与 A 和 B 合并即可。

申请节点的代码如下：

int newnode(int x)
{
    ++cnt;
    t[cnt]=node(x,rand(),1);
    return cnt;
}

一个优化是，在将 A 分裂成小于/等于 x 的两棵树，若等于 x 的那棵树为空，则增加其数量与子树大小，反之则增加节点数与子树大小。这个优化可以减少节点的浪费，对代码有常数级的复杂度提升。

伪代码如下：

p <- split(x-1)
if p.size=0 do：
    newnode(x)
else do:
    p.size++
    cnt++

但一般为了简便，我们不经常采用这个小优化。下面是不采用优化的代码：

void insert(int x)
{
    int l,r;
    split(rt,x,l,r),rt=merge(merge(l,newnode(x)),r);
}

删除

删除操作也使用和插入操作相似的方法，找到值和 \textit{x} 相等的节点，并且删除它。

void erase(int x)
{
    int l,r,p;
    split(rt,x,l,r),split(l,x-1,l,p);
    p=merge(t[p].l,t[p].r),rt=merge(merge(l,p),r);
}

根据值查询排名

首先，求排名（k）可以这么转化为求节点数：

所以我们根据 \textit{val} - 1 分裂当前树，那么分裂后的第一个树中的全体节点 A 就符合: