在此发个牢骚，为了学这个Treap几乎翻遍了全网的博文，自始至终没有找到几篇全面详尽的、能够深入浅出的分析树堆这一数据结构的博客。仅有寥寥几篇博客讲述了具体操作的思想，对于初学者而言很难理解的一些点并无法在博客中展现出来。遂自己模数据、画图，希望能够通过这篇博客将Treap相关的知识点(包括旋转式、无旋式Treap)彻底弄透彻。如果有初学者难以理解相关的结构理论，也可以作一个比较好的参照资料。
从个人的学习历程来看，Treap这个知识点还是比较重要的，无论是思想还是操作。例如如果将旋转式Treap的基本操作学通，那么学习Splay就会变得十分轻松。因为Splay本身也是一种基于旋转操作对二叉搜索树的平衡进行维持的结构。
⚠ | 全文多图、大量文字警告！ ✨ | 非专业作者，如有错误欢迎指正！ 一、Treap 简介Treap(树堆)是一种弱平衡的搜索树，顾名思义，Treap就是由Tree和Heap(树和堆)两种数据结构组合而成的数据结构。
Treap的每个节点上要额外储存一个值 p r i o r i t y priority priority，代表每个节点的优先级。因此对于每个节点，不仅要满足二叉搜索树的基本性质，还需额外满足父节点的 p r i o r i t y priority priority大于两个子节点的 p r i o r i t y priority priority。实际上，这个 p r i o r i o t y priorioty priorioty值又被称为"修正值"。
但由于 p r i o r i t y priority priority是随机生成的，因此我们一般认为Treap是“期望平衡”的。
我们一般将Treap分为两类：①.旋转式Treap；②.无旋式Treap。我们根据这两种分类对Treap进行详解。
这里我们约定： p r i o r i t y priority priority变量拼写较复杂，在程序中我们统一用 o r d ord ord表示 p r i o r i t y priority priority，对于解释用图中的 k e y key key，实际上就是节点所储存的值 v a l val val，意义相同。
二、旋转式Treap 1.旋转式Treap旋转式Treap是我们日常比较常见的Treap实现形式，其操作的精髓在于"左旋"和"右旋"。
我们在对Treap的介绍中讲到：Treap(树堆)是由Tree(树)和Heap(堆)组成的复合数据结构，因此它必须要满足两种组成成分的性质。同时我们也提到，我们对每个节点额外设置一个属性： p r i o r i t y priority priority，其值为随机赋值。整体结构形成后，每个节点的键值排序方式符合二叉搜索树的性质，同时 p r i o r i t y priority priority的排序方式又遵循小根堆的方式，这在一定程度上避免了二叉搜素树呈现"高瘦"形态甚至退化为链的状态。
旋转式Treap不支持区间操作，但是相比于无旋式Treap效率要高一些。
2.旋转式Treap结构与操作基础我们首先给出一棵已经建立的合法的Treap：
PS：再次声明， p r i o r i t y priority priority值是随机生成的！与键值没有什么关系。
我们对储存结构进行定义：
int lc[x]; //节点x的左孩子
int rc[x]; //节点x的右孩子
int val[x]; //节点x的键值(即为节点的key值)
int ord[x]; //节点x的priority值
int siz[x]; //以节点x为根节点的子树大小
int w[x]; //与节点x键值相同的节点数目
我们首先基于这棵二叉搜索树，对树堆的两种基本操作：右旋和左旋进行讲解。
我们现在假设执行插入操作，节点键值 k e y = 7 key = 7 key=7，随机生成 p r i o r i t y priority priority值为 7 7 7。
我们按照二叉搜索树的方式进行插入：
很明显，插入完成后能够满足二叉搜索树的性质，但是却不满足堆的性质，那么此时便要通过旋转来解决问题。
(1).右旋操作当我们发现当前节点左儿子的 p r i o r i t y priority priority小于自身 p r i o r i t y priority priority的时候，我们可以通过右旋操作解决问题。我们首先通过上面的样例来理解右旋操作的原理：
对于新插入的节点，我们检索其根节点，发现根节点左儿子的 p r i o r i t y priority priority小于自身 p r i o r i t y priority priority，因此执行右旋操作：
我们将左字节点提到根节点作为新的根，原根节点右旋至新根节点的右子节点。
可能这张图片不能完全的表述整个右旋操作的原理，我们用一颗普通二叉树的右旋操作来演示其基本原理：
可以总结一下右旋的步骤：设当前节点 m m m，左子节点 l l l，右子节点 r r r
- 将 l l l提至根节点；
- 原根节点 m m m右旋至右子节点；
- 将原右子节点 r r r给原根节点 m m m。
根据上述步骤旋转完后的树如下所示
显然，现在仍不符合要求。此时对于新插入节点的根节点而言，其右子节点 p r i o r i t y priority priority值大于它本身，因此需要执行左旋操作。
void rrotate(int &root){
int tmp = lc[root];
lc[root] = rc[tmp], rc[tmp] = root;
siz[tmp] = siz[root];
pushup(root);
root = tmp;
}
当我们发现当前节点右儿子的 p r i o r i t y priority priority小于自身 p r i o r i t y priority priority的时候，我们可以通过左旋操作解决问题。
左旋的步骤实际上就是右旋的逆过程，理解了右旋后左旋就容易理解了。
旋转之后：
此时，我们得到的树结构即满足二叉搜索树的性质，且满足堆的性质。
void lrotate(int &root){
int tmp = rc[root];
rc[root] = lc[tmp], lc[tmp] = root;
siz[tmp] = siz[root];
pushup(root);
root = tmp;
}
至此，旋转式Treap的两种基本操作介绍完毕。建立在这两种操作的基础上，我们可以对树的一系列操作进行定义。
3.旋转式Treap操作 (1).插入操作插入节点的操作很简单，正如我们在讲解左旋右旋时所演示的一样。如果已存在同值节点，则节点计数++，如果不存在同值节点，首先随机取一个 p r i o r i t y priority priority值赋给新节点，然后只需要按照二叉搜索树(BST)的步骤找到合适的位置进行插入，并进行回溯，在回溯的过程中判断是否需要进行左旋即可。
void insert(int &root, int x){
if(!root){
sz++, root = sz;
siz[root] = w[root] = 1;
val[root] = x, ord[root] = rand();
return;
}
siz[root]++;
if(val[root] == x) w[root]++;
else if(val[root] 1，则只需要
w
−
−
w--
w−−；如果其
w
=
=
1
w == 1
w==1，则将其通过旋转操作旋到叶节点上，直接删除其与父节点的边即可。
bool del(int &root, int x){
if(!root) return false;
if(val[root] == x){
if(w[root] > 1){ w[root]--, siz[root]--; return true; }
if(!lc[root] || !rc[root]){
root = lc[root] + rc[root];
return true;
}
else if(ord[lc[root]] n;
switch(op){
case 1: insert(rt, n); break;
case 2: del(rt, n); break;
case 3: cout ord ord){
u -> rc = merge(u -> rc, v);
return u;
}
else{
v -> lc = merge(u, v -> lc);
return v;
}
}
至此，无旋式Treap的两种基本操作介绍完毕。建立在这两种操作的基础上，我们可以对树的一系列操作进行定义。
3.无旋式Treap 基本操作
(1).建树(build)
建树操作实现的是将一个具有
n
n
n个节点的序列
{
a
n
}
\{a_n \}
{an}转化为一颗Treap。
可以依次暴力插入这
n
n
n 个节点，每次插入一个权值为
v
v
v 的节点时，将整棵 Treap 按照权值分裂成权值小于等于
v
v
v 的和权值大于
v
v
v 的两部分，然后新建一个权值为
v
v
v 的节点，将两部分和新节点按从小到大的顺序依次合并，单次插入时间复杂度
O
(
log
n
)
O(\log n)
O(logn)，总时间复杂度
O
(
n
log
n
)
O(n\log n)
O(nlogn)。
在某些题目内，可能会有多次插入一段有序序列的操作，这是就需要在
O
(
n
)
O(n)
O(n) 的时间复杂度内完成建树操作。
-
方法一：在递归建树的过程中，每次选取当前区间的中点作为该区间的树根，并对每个节点钦定合适的优先值，使得新树满足堆的性质。这样能保证树高为
O
(
log
n
)
O(\log n)
O(logn)。
-
方法二：在递归建树的过程中，每次选取当前区间的中点作为该区间的树根，然后给每个节点一个随机优先级。这样能保证树高为
O
(
log
n
)
O(\log n)
O(logn)，但不保证其满足堆的性质。这样也是正确的，因为无旋式 Treap 的优先级是用来使 merge 操作更加随机一点，而不是用来保证树高的。
-
方法三：观察到 Treap 是笛卡尔树，利用笛卡尔树的
O
(
n
)
O(n)
O(n) 建树方法即可，用单调栈维护右子树即可。
在本博客中，由于我们采用动态申请内存的方式进行储存，因此建树只需要逐个执行插入操作即可。我们会在文末给出基于数组存储的Treap代码，其中包含建树的代码。
(2).查找出现次数(find)
此部分操作与二叉搜索树一致，直接根据二叉搜索树的性质进行查找即可。
int find(node *root, int key){
if(root == nullptr) return 0;
if(key == root -> val) return 1;
if(key val) return find(root -> lc, key);
else return find(root -> rc, key);
}
(3).插入函数(insert)
插入操作很简单，首先以待插入点为关键值对树进行分裂，然后在树上寻找以该值为权值的点是否已经存在，若不存在则将点合并到一棵树上，再与另一棵树进行合并。
如果记录点权，则需要额外加上权值自增的运算(此处不再演示，与普通的二叉搜索树相同)。
inline void insert(int key){
pii o = split(root, key);
if(!find(root , key)) o.first = merge(o.first, new node(key));
root = merge(o.first, o.second);
}
(4).删除操作(erase)
将具有待删除的关键值的结点从整棵 Treap 中孤立出来（进行两侧分裂操作），删除中间的一段（具有待删除关键值），再将左右两端合并即可。
inline void erase(int key){
pii o = split(root, key - 1);
pii p = split(o.second, key);
delete p.first;
root = merge(o.first, p.second);
}
其余如同查询区间排名等与普通平衡树一样的操作不在此一一列举。
值得一提的是，类似洛谷3391文艺平衡树这样的题目，要求对区间进行操作的题目，需要通过split分理出需要操作的区间，然后在根节点打标记并合并。具体的操作会整理成博客。[TODO:占坑–无旋Treap区间操作]
4.模板总结
#include
#define pii pair
#define mkp(x, y) make_pair(x, y)
using namespace std;
struct node{
int val, cnt, siz, ord;
node *lc, *rc;
node(int v = 0, int c = 1, int s = 1): val(v), ord(c), cnt(1), siz(s), lc(nullptr), rc(nullptr){};
};
pii split(node *root, int key){
if(root == nullptr) return mkp(nullptr, nullptr);
if(key val){
pii o = split(root -> lc, key);
root -> lc = o.second;
return mkp(o.first, root);
}
else{
pii o = split(root -> rc, key);
root -> rc = o.first;
return mkp(root, o.second);
}
}
node *merge(node *u, node *v){
if(u == nullptr) return v;
if(v == nullptr) return u;
if(u -> ord ord){
u -> rc = merge(u -> rc, v);
return u;
}else{
v -> lc = merge(u, v -> lc);
return v;
}
}
int find(node *root, int key){
if(root == nullptr) return 0;
if(key == root -> val) return 1;
if(key val) return find(root -> lc, key);
else return find(root -> rc, key);
}
int count(node *root, int key){ return find(root, key); }
inline void insert(node *root, int key){
pii o = split(root, key);
if(!find(root , key)) o.first = merge(o.first, new node(key));
root = merge(o.first, o.second);
}
inline void erase(node *root, int key){
pii o = split(root, key - 1);
pii p = split(o.second, key);
delete p.first;
root = merge(o.first, p.second);
}
signed main(){
int n = 0; cin >> n;
node *np = new node(11, 6);
node *tmp = new node(6, 12);
np -> lc = tmp;
tmp = new node(4, 17);
np -> lc -> lc = tmp;
tmp = new node(8, 18);
np -> lc -> rc = tmp;
tmp = new node(15, 13);
np -> rc = tmp;
tmp = new node(16, 14);
np -> rc -> rc = tmp;
//insert(np, 7);
pii o = split(np, 7);
node *nc = merge(o.first, o.second);
return 0;
}
这里再附一个基于数组静态存储的无旋式Treap模板
struct fhqTreap{
int ch[maxn][2], key[maxn], rnd[maxn], size[maxn], root, tot;
fhqTreap() { root = tot = 0; }
void clear() { root = tot = 0; }
int node(int v) {
key[++tot] = v; rnd[tot] = rand();
size[tot] = 1;
ch[tot][0] = ch[tot][1] = 0;
return tot;
}
void pushup(int x) { size[x] = size[ch[x][0]] + size[ch[x][1]] + 1; }
void split(int now, int k, int &x, int &y) {
if (!now) x = y = 0; return;
if (key[now]
关注
打赏
![]()
1662600635
查看更多评论
最近更新
- 深拷贝和浅拷贝的区别（重点）
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state，props，refs（你学废了吗）
- 【脚手架VueCLI】从零开始，创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解（含代码）
- 【React】DOM的Diffing算法是什么？以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面？
