![洛谷P3369【模板】普通平衡树](/img/boat-7040754_1920.jpg)
洛谷P3369【模板】普通平衡树
![](https://picx.zhimg.com/v2-9e83e1fd23eccdb98450679841a3a4bc_xll.jpg)
#数据结构 #平衡树 #题解
题目来源
请读者先自行阅读题目
概述
我们现在要对一个数列进行在线的加入、删除、查询功能,如果每加入一个数就对这串数进行排序是很明显不现实的,这样的时间复杂度是
那今天呢我们来讲一种可以说是最好写的平衡树——Treap,这是一种重量平衡树。注意这里讲的是无旋式Treap,也就是FHQ Treap,相较于旋转式的Treap,它更好写,效率也更高。我瞎说的,其实老师就没有讲旋转的Treap
数据结构
如果不了解BST(Binary Search Tree)的同学可以趋势了离开了。
如果人品差到极致的同学其实 也没必要活着了 也可以离开了(要是真能差到极致我也是佩服)
Treap的基本原理:
- 每个节点有两个数据,一个是存储值的,一个是存储优先级的
- Treap = Tree + Heap
是什么意思呢,就是对于每个新建的结点赋予一个随机的优先级,然后最后让这个二叉树既满足堆的性质又满足二叉平衡树的性质,可以证明,这两个参数的加持下只能够形成一个唯一的Treap (如果你说两个结点优先级都一样,好吧你赢了)。证明的话小学生都会,我就不说了
由于这样的随机性,它的时间复杂度期望也是
然后我们回到它的具体实现上,这个地方就能体现FHQ Treap的高明之处了。
我们先来看看FHQ Treap结点的定义:
1 | //本文章是由指针实现的数据结构 |
FHQ Treap有两个基本操作:Merge 和 Split 。Merge就是将两个FHQ Treap合在一起,Split也就是从一个地方分开,能做到把前几个数和后几个数(比n小的和比n大的分开是一个道理)分成两个树(BST中序遍历不就是本来的序列吗,这样就相当于把原本的序列切成两半然后再形成两个平衡树)。这两个操作是互逆的。
接下来讲操作(本文使用小根堆实现)
Merge(u, v)
假设现在要合并这两棵树(一个结点左边是值,右边是优先级):
FHQ Treap合并的思路是这样的,首先我们严格要求左边这棵树点值的最大值必须要小于右边这棵树点值的最小值,这样就能保证每次操作都能把一棵树完全放到另一棵树的一边。
合并的过程是递归的,从两个点的根结点开始,如果u的优先级比v的小,那么u肯定是v这个树的父节点,又因为u中所有结点都是小于v中的,所以v肯定全部都在u的右儿子中,因此我们将u的右儿子与v合并。反之则将u与v的左儿子合并,很好理解。如果最后有一边是空了,那么返回另一个就行。
具体操作如下
所以v在u的右子树上,将递归到u的右子树与v合并 所以右边的树在上面,这个子树的根就是 ,然后继续递归 的那棵树和 的左子树
这里将
和 连接起来了是方便理解与观看,实际更新儿子是在子树递归完后更新的(具体见后面的代码)
然后我们继续合并这两个子树,由于优先级
然后另外一个树变成空节点了,于是直接连接
于是我们成功合并了两棵子树!
接下来我们来看看代码:
1 | //需要u小于v |
Split(u, v, l, r)
ValSplit
我们首先来讲按值来分裂。
由于画图对逻辑上理解好像并没有什么帮助,反而是递归更能让人理解其运行的内在逻辑,所以我不画图了。
绝对不是因为我懒!!!
什么是分裂呢,前面已经说过了,近视的同学回去再找找。
我们想现在要把一个完整的Treap从中间拆成两个树,我们就倒着想合并的过程(这里不太好用语言描述,请读者自己想象)。
而我们伟大的先辈FHQ同志就是这么想的,我从点
那我们继续想,接下来只需要将
这里可以简化一下,直接将
上代码:
1 | void valsplit(node* u, int v, node* &l, node* &r) { |
RankSplit
函数名字都是我瞎取的
这次不是按值来分树,而是按排名(或者说数量)来分。
这时就要用到
看代码:
1 | void RankSplit(node* u, int k, node* &l, node* &r) { |
SuperMerge(u, v)
在学会了merge和split后你是否希望做到merge任意两个Treap呢?(反正我还没遇到过)
merge只能u小于v的原因是要将一个完全放到另一个的一边的子树里。但是现在你学会了split,是否可以使用split来实现supermerge呢?
见代码:
1 | node* SuperMerge(node* u, node* v) { |
kthn(u, k)
现在我们写最后一个基础函数,也是最简单最容易理解的一个,求第k小的数。
我们现在有siz也知道了怎么递归,我们其实可以自己写出kthn函数
(我当时就是自己写出来的求第k小函数,和使用较广方法的一样)
代码如下:
1 | int kthn(node* u, int k) { |
具体操作
基础函数和对Treap的合并分裂都学会了,我们来看看这道题。
插入
插入比较简单,我们新建一个结点,将其看作是一个一个大小的Treap,然后将现有的Treap按新结点的值分开再从中间插进去合并即可。
1 | void insert(int x) { |
删除
通过分裂操作,我们可以将小于
真是天才的做法!
1 | inline void del(int x) { |
查询排名
看代码自己理解
1 | void getrank(int x) { |
查询排名为 的数
更简单了,直接用
求 的前趋
只需要将小于
代码:
1 | void lema(int x) { //less than max 什么神奇Chinglish |
求 的后继
更简单了,同前趋
1 | void grmi(int x) { // greater min |
后记
对于Treap,我们需要一种递归思维。我们不能只通过图去理解整个流程,递归是一种方式,我们要用函数式的思想去理解,它是一种规律的操作而不是一种过程。只有当你真正理解了这种规律,你就可以说你对这种数据结构了如指掌了。
嘎嘎嘎嘎嘎,写的太多了,累啊累啊累啊
- 标题: 洛谷P3369【模板】普通平衡树
- 作者: 混氏新子
- 创建于 : 2023-03-26 21:23:55
- 更新于 : 2023-09-24 19:16:37
- 链接: https://blog.huasushis.cn/2023/洛谷P3369【模板】普通平衡树/
- 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。