FHQ Treap | 非旋式树堆

Prologue

前置技能

一些定义

  • 树中任意节点的权值都大于或等于其父节点的权值,则称该二叉树满足 “小根堆性质”
  • 二元搜寻树(Binary Search Tree, BST)是一棵空树或具有下列性质的二叉树
    1. 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值
    2. 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值
    3. 任意节点的左、右子树也分别为二叉查找树
    4. 没有键值相等的节点
  • 平衡树是一类改进的 BST ,平衡指所有叶子的深度趋于平衡,更广义的是指在树上所有可能查找的均摊复杂度偏低。

​BST 支持插入、删除、动态查询,均摊复杂度 O(logN)O(\log N) ,看似是非常优秀的数据结构,但只要插入一个有序序列,就可以让 BST 退化为链表,复杂度达到 O(N)O(N) 。因为一般的 BST 的查询复杂度是跟目标结点的深度有关,各种平衡树诞生了。

​常见的平衡树及特点如下:

Feature
Treap 随机赋一个点权,并维持堆性质。基于旋转,代码短,速度快
FHQ Treap 平衡方式同 Treap,但基于分裂与合并,支持区间操作,可持久化
SBT 扩展性一般,代码短,略快于 Treap,单旋会被卡
Splay 常数极大,代码较长,但极其灵活,LCT 前置技能
RB Tree 最快的 BST,功能少,500 行起步,告辞
AVL Tree 速度仅次于 RB Tree,功能少,代码较长
Scapegoat Tree 基于部分重建来保持平衡,KD Tree 前置技能
set / multiset 底层 RB Tree,但没有维护 size 域,故不支持查询排名和第 k 大

FHQ Treap 显然是很香的

构建 FHQ

​BST 的形态不断变化,所以需要链状结构进行存储。拒绝指针,从我做起。

1
2
3
4
5
6
struct uuz {
int l,r;
#define l(x) treap[x].l
#define r(x) treap[x].r
}treap[_];
int rt,e,f,g,fp,siz[_],key[_],val[_];

rt 表示根节点,fp 表示总节点数,siz[] key[] val[] 分别表示每个节点的子树大小、关键码、权值。鬼知道为什么又有结构体又有数组。

由于 cstdlibrand() 效率较低,可以自己写一个 LCG:

1
int random() {static int s=703;return s=int(s*48271LL%2147483647);}

新建节点和普通的 BST 类似,只要再给每个节点赋一个随机权值即可。

1
2
3
4
5
int gene(const int& v) {
key[++fp]=v;
val[fp]=random();
siz[fp]=1;return fp;
}

siz[x] 表示以节点 xx 为根的子树大小,回溯时进行统计即可。

1
2
3
void maintain(const int& p) {
siz[p]=siz[l(p)]+siz[r(p)]+1;
}

基本操作

​分裂。按照关键码进行分裂,最后 xx 是关键码小于或等于 kk 的树的根节点,yy 是关键码大于 kk 的树的根节点。开始时,对引用的 x,yx,y 初值没有要求。对于每一个节点,若其关键码小于或等于给定的 kk,根据 BST 的性质,它的左子树的关键码一定都小于 kk,将它放入 xx,否则将它和它的右子树放入 yy 中。对于剩下的节点,递归进行划分即可。此处的递归传引用非常巧妙,建议在纸上进行模拟。

1
2
3
4
5
6
void split(int p,int k,int& x,int& y) {
if(!p) {x=y=p;return;}
if(key[p]>k) split(l(y=p),k,x,l(p));
else split(r(x=p),k,r(p),y);
maintain(p);
}

合并。进行启发式合并,若 val[x]<val[y] 则保留 xx 的左子树,合并 xx 的右子树和 yy,将得到的树作为 xx 的右子树,否则保留 yy 的右子树,合并 yy 的左子树和 xx,将得到的树作为 yy 的左子树。

1
2
3
4
5
6
int merge(int x,int y) {
if(!x||!y) return x+y;
if(val[x]<val[y]) r(x)=merge(r(x),y),maintain(x);
else l(y)=merge(x,l(y)),maintain(y);
return val[x]<val[y]? x:y;
}

找出排名为 kk 的节点在数组中的位置。查询第 kk 大和普通的 BST 是完全相同的。由于维护了 siz 域,根据 BST 的性质易知左子树的关键码严格小于右子树,所以如果左子树的大小 +1 等于 kk,显然当前节点就是答案。若左子树大小 +1 大于 kk,则第 kk 大的节点一定在左子树中,此时可以直接走到左子树。若左子树大小 +1 小于 kk,则第 kk 大的节点一定是右子树的第 k-siz[l(p)]-1 大的节点。

1
2
3
4
5
6
int sel(int p,int k) {
while(k!=siz[l(p)]+1)
if(k<siz[l(p)]+1) p=l(p);
else k-=siz[l(p)]+1,p=r(p);
return p;
}

进阶操作

​FHQ Treap 基于分裂与合并,所以其它操作都由 split merge 完成。

插入节点。直接按插入的值 vv 进行分裂,把 vv 和分裂出的较小的树合并,再合并两棵树即可。

1
2
3
4
void ins(const int& v) {
split(rt,v,e,f);
rt=merge(merge(e,gene(v)),f);
}

删除节点。先按删除的值 vv 分裂成 e,ge,g 两部分,ee 中最大的关键码为 vv,再对 eev1v-1 分裂,显然 ff 的关键码为 vv,直接合并 ff 的左右儿子,并用新树的根节点更新 ff,然后不断合并把树还原即可。

1
2
3
4
5
void del(const int& v) {
split(rt,v,e,g);split(e,v-1,e,f);
f=merge(l(f),r(f));
rt=merge(merge(e,f),g);
}

查询 rank。先按照 v1v-1 进行分裂,则 ee 包含了所有小于 vv 的节点,siz[e]+1 即为 vv 的 rank。

1
2
3
4
5
6
int rnk(const int& v) {
split(rt,v-1,e,f);
int pos=siz[e]+1;
rt=merge(e,f);
return pos;
}

查询前驱与后继。按 v-1 进行分裂,显然 ee 中的最后一名就是 vv 的前驱,查询后继也类似。

1
2
3
4
5
6
7
8
9
10
11
12
int pre(const int& v) {
split(rt,v-1,e,f);
int pos=sel(e,siz[e]);
rt=merge(e,f);
return pos;
}
int nxt(const int& v) {
split(rt,v,e,f);
int pos=sel(f,1);
rt=merge(e,f);
return pos;
}

Download

本站所有原创内容采用 CC-BY-NC-ND 4.0 International 协议进行许可,附加条款亦可能应用。部分非原创内容版权为 上海アリス幻楽団黄昏フロンティア 等同人创作者所有。

笔记 数据结构

评论

您需要成为穿墙的邪仙以加载 Disqus。