526互联

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

发布时间 2023-12-11 11:03:04作者: mekdull

平衡树：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\)）可以这么转化为求节点数：

\(k=\sum\limits_{i=1}^{n} [T_i<k]+1\)

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

\(A\le val-1\)

\(A\) 也包含了所有值小于 \(x\) 的节点。所以 \(A.size+1\) 就是我们想要的 \(k\)。

int rnk(int x)//rank可能与内置函数重名
{
    int l,r,res;
    split(rt,x-1,l,r),res=t[l].sz+1,rt=merge(l,r);
    return res;
}

根据排名（k）查询值

分三种情况：

  1. 如果左子树的大小等于 \(k-1\)，那么直接返回 \(cur\) 指向的搜索树中的值就是答案；
  2. 如果左子树大小小于 \(k-1\)，那么答案在右子树里。此时我们把 \(k-1\) 减掉左子树大小之后递归右子树即可；
  3. 如果左子树大小大于 \(k-1\)，那么直接递归左子树。

代码如下：

int kth(int k,int o=rt)
{
    if(t[t[o].l].sz==k-1) return t[o].k;
    if(t[t[o].l].sz<k-1) return kth(k-1-t[t[o].l].sz,t[o].r);
    else return kth(k,t[o].l);
}

查询第一个比 \(val\) 小的节点（前驱）

可以把这个问题转化为，在比 \(\textit{val}\) 小的所有节点中，找出排名最大的。

我们根据 \(\textit{val}\) 来分裂这个 Treap，返回的第一个 Treap 中的节点的值就全部小于 \(\textit{val}\)，然后我们调用 kth 函数找出这个树中值最大的节点。

int pre(int x)
{
    int l,r,res;
    split(rt,x-1,l,r),res=kth(t[l].sz,l),rt=merge(l,r);
    return res;
}

查询第一个比 \(val\) 大的节点（后继）

和上个操作类似，可以把这个问题转化为，在比 \(\textit{val}\) 大的所有节点中，找出排名最大的。

根据 \(\textit{val}\) 分裂后，返回的第二个 Treap 中的所有节点的值就大于 \(\textit{val}\)。

然后我们去查询这个树中排名为 \(1\) 的节点（也就是值最小的节点）的值，就可以成功查到第一个比 \(\textit{val}\) 大的节点。

int nxt(int x)
{
    int l,r,res;
    split(rt,x,l,r),res=kth(1,r),rt=merge(l,r);
    return res;
}

这些就是无旋 Treap 的基础单点操作。当然，它还可以进行区间操作，但在此由于篇幅所限不作讲述。

例题

P3369 【模板】普通平衡树

P6136 【模板】普通平衡树（数据加强版）

这里给出 P6136 的代码，也是无旋 Treap 的完整板子。

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
	return s*w;
}
const int N=2e6+114;
struct node{
    int k,p,sz,l,r;
    node(int k=0,int p=0,int sz=0,int l=0,int r=0):k(k),p(p),sz(sz),l(l),r(r){}
}t[N];
int cnt,n,rt,m,last,ans;
int newnode(int x){return ++cnt,t[cnt]=node(x,rand(),1),cnt;}
int update(int o){return t[o].sz=t[t[o].l].sz+t[t[o].r].sz+1,o;}
void split(int o,int x,int &l,int &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);
}
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);
    return t[r].l=merge(l,t[r].l),update(r);
}
void insert(int x)
{
    int l,r;
    split(rt,x,l,r),rt=merge(merge(l,newnode(x)),r);
}
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);
}
int rnk(int x)
{
    int l,r,res;
    split(rt,x-1,l,r),res=t[l].sz+1,rt=merge(l,r);
    return res;
}
int kth(int k,int o=rt)
{
    if(t[t[o].l].sz==k-1) return t[o].k;
    if(t[t[o].l].sz<k-1) return kth(k-t[t[o].l].sz-1,t[o].r);
    else return kth(k,t[o].l);
}
int pre(int x)
{
    int l,r,res;
    split(rt,x-1,l,r),res=kth(t[l].sz,l),rt=merge(l,r);
    return res;
}
int nxt(int x)
{
    int l,r,res;
    split(rt,x,l,r),res=kth(1,r),rt=merge(l,r);
    return res;
}
signed main()
{
    srand(0);
    n=read(),m=read();
    for(int i=1;i<=n;i++) insert(read());
    while(m--)
    {
        int opt=read(),x=read()^last;
        switch(opt)
        {
            case 1: insert(x);                break;
            case 2: erase(x);                 break;
            case 3: last=rnk(x),ans^=last;    break;
            case 4: last=kth(x),ans^=last;    break;
            case 5: last=pre(x),ans^=last;    break;
            case 6: last=nxt(x),ans^=last;    break;
        }
    }
    printf("%d",ans);
}

参考文章

[1] oi-wiki Treap

[2] FHQ Treap 学习笔记 Charles Wu的博客

关于非旋FHQ Treap的复杂度证明

FHQ-Treap学习笔记 万万没想到 的博客

浅析Treap——平衡树 曦行夜落 的博客