首页 > 其他分享 >平衡树（无旋Treap，范浩强树）学习笔记

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

时间：2023-12-11 11:14:15浏览次数：40  
标签：rt merge int 无旋 Treap textit 范浩强 节点

平衡树：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——平衡树 曦行夜落 的博客

标签：rt,merge,int,无旋,Treap,textit,范浩强,节点
From： https://www.cnblogs.com/mekdull/p/17893896.html

相关文章

  • Treap 学习笔记
    二叉查找树二叉查找树是一棵有点权的二叉树，具有以下几个特征：左孩子的权值小于父亲的权值右孩子的权值大于父亲的权值中序遍历及从小到大排序二叉查找树支持以下几个操作：插入一个数删除一个数找一个数的前驱找一个数的后继询问一个数的排名询问排第几名的数二叉查......
  • Treap
    概述FHQTreap基于Treap发明的“无旋Treap”，代码短，易理解且速度快（在OI算是很优秀的算法了）。FHQTreap核心函数只有两个，分别是分裂和合并。字面意思，就是将某一棵二叉查找树按某种要求分裂成两个或将两个合并成一个。实现变量维护变量名功能root记录所维护......
  • 算法笔记（2）FHQtreap
    原发布于我的个人博客前言FHQtreap绝对是平衡树里最好写，最实用的，他几乎能做所有splay或其它平衡树能做的事，还能可持久化！这篇文章将会介绍FHQtreap的基本操作和维护区间的操作，并附上例题。基本操作FHQtreap的基本操作只有两个，分裂和合并。有些读者可能会问，分裂和合并和平衡树......
  • 【学习笔记】FHQ-Treap
    前置知识：二叉搜索树与二叉堆。1.简介Treap，即Tree+Heap，它的每个结点上存储着一个索引\(key\)和一个值\(val\)，其中索引满足二叉堆的性质，值满足二叉搜索树的性质，且索引是随机的。Treap就是通过上述的性质，使树达到平衡。至于为什么索引是随机的，其实很简单：我们插入的每个数的......
  • Atcoder Beginner Contest 324 G Generate Arrays 题解-Treap
    为了更好的阅读体验，请点击这里题目链接套上平衡树板子就能做的很快的题，然后因为是指针存树，因此交换只需要把序列大小较小的挨个拿出来插到相应的地方即可。复杂度\(O(N\log^2N)\)。但是一定要记住不可以直接使用std::swap交换包含带有指针的类的实例（如代码中的Treap类）！......
  • Treap引入
    前置知识treap是由BST和heap组合而成的数据结构，这一点也体现在它的名字上：treap=tree+heapBST中，每个节点的左儿子都比它小，右儿子都比它大，可以实现有序的遍历，但是可能因为数据特殊的排列方式，而退化为线性heap中，每个父节点都是当前子树内权值最大（或最小）的点。在BST的基础上加一个......
  • BST-Treap名次树指针实现板子 Ver2.0
    为了更好的阅读体验，请点击这里这里只有板子没有原理QWQ可实现1.插入x数2.删除x数(若有多个相同的数，只删除一个)3.查询x数的排名(排名定义为比当前数小的数的个数+1)4.查询排名为x的数5.求x的前驱(前驱定义为小于x，且最大的数)6.求x的后继(后继定义为大于x，且......
  • 弱势无图解FHQ-Treap 及各种乱七八糟的错误方法
    众所周知，FHQ-Treap是一个码量少，可区间翻转，能持久化的treap（只是常熟略大）像我这种蒟蒻，想调处有旋Treap或者Splay肯定要个114514年以下可能以FHQ代表FHQ-Treap（逃前置芝士treap的节点拥有两个权值，一个是值，一个是优先级。优先级满足堆的性质，值满足二叉搜索树的性质。当两个权值相......
  • Treap
    BST\(v_i\)表示点权，\(x\)表示当前点，\(L\)表示左子树，\(R\)表示右子树在普通二叉树的基础上多一个条件对于\(p\inL\)，满足\(v_p\leqv_x\)对于\(q\inR\)，满足\(v_x<v_q\)Treap但是这样如果BST是一条链的话就退化\(O(n)\)，而且很容易卡，考虑TreapTreap就是在普通B......
  • FHQ-Treap 详解
    目录1）FHQ-Treap基本功能理论与实现1.1）FHQ-Treap模型1.2）操作一：分裂（Split）1.3）操作二：合并（Merge）1.4）操作三：插入新节点1.5）删除某个节点1.6）查询某个值的排名1.7）查询排名为\(k\)的值1.8）查询\(x\)的前驱与后继1.9）Endofthisunit2）FHQ-Treap的应用2.1）洛谷P3369END1）FHQ-Treap基本功......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99