数据结构-Treap(树堆) 详解

😊 | Powered By HeartFireY | Balanced Search Tree::Treap

📕 | 需要的前导知识：平衡二叉搜索树(BST)

在此发个牢骚，为了学这个Treap几乎翻遍了全网的博文，自始至终没有找到几篇全面详尽的、能够深入浅出的分析树堆这一数据结构的博客。仅有寥寥几篇博客讲述了具体操作的思想，对于初学者而言很难理解的一些点并无法在博客中展现出来。遂自己模数据、画图，希望能够通过这篇博客将Treap相关的知识点(包括旋转式、无旋式Treap)彻底弄透彻。如果有初学者难以理解相关的结构理论，也可以作一个比较好的参照资料。

从个人的学习历程来看，Treap这个知识点还是比较重要的，无论是思想还是操作。例如如果将旋转式Treap的基本操作学通，那么学习Splay就会变得十分轻松。因为Splay本身也是一种基于旋转操作对二叉搜索树的平衡进行维持的结构。

⚠ | 全文多图、大量文字警告！

✨ | 非专业作者，如有错误欢迎指正！

一、Treap 简介

Treap(树堆)是一种弱平衡的搜索树，顾名思义，Treap就是由Tree和Heap(树和堆)两种数据结构组合而成的数据结构。

Treap的每个节点上要额外储存一个值，代表每个节点的优先级。因此对于每个节点，不仅要满足二叉搜索树的基本性质，还需额外满足父节点的大于两个子节点的。实际上，这个值又被称为"修正值"。

但由于是随机生成的，因此我们一般认为Treap是“期望平衡”的。

我们一般将Treap分为两类：①.旋转式Treap；②.无旋式Treap。我们根据这两种分类对Treap进行详解。

这里我们约定：变量拼写较复杂，在程序中我们统一用表示，对于解释用图中的，实际上就是节点所储存的值，意义相同。

二、旋转式Treap

1.旋转式Treap

旋转式Treap是我们日常比较常见的Treap实现形式，其操作的精髓在于"左旋"和"右旋"。

我们在对Treap的介绍中讲到：Treap(树堆)是由Tree(树)和Heap(堆)组成的复合数据结构，因此它必须要满足两种组成成分的性质。同时我们也提到，我们对每个节点额外设置一个属性：，其值为随机赋值。整体结构形成后，每个节点的键值排序方式符合二叉搜索树的性质，同时的排序方式又遵循小根堆的方式，这在一定程度上避免了二叉搜素树呈现"高瘦"形态甚至退化为链的状态。

旋转式Treap不支持区间操作，但是相比于无旋式Treap效率要高一些。

2.旋转式Treap结构与操作基础

我们首先给出一棵已经建立的合法的Treap：

PS：再次声明，值是随机生成的！与键值没有什么关系。

我们对储存结构进行定义：

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键值相同的节点数目

我们首先基于这棵二叉搜索树，对树堆的两种基本操作：

右旋

和

左旋

进行讲解。

我们现在假设执行插入操作，节点键值，随机生成值为。

我们按照二叉搜索树的方式进行插入：

很明显，插入完成后能够满足二叉搜索树的性质，但是却不满足堆的性质，那么此时便要通过旋转来解决问题。

(1).右旋操作

当我们发现当前节点左儿子的小于自身的时候，我们可以通过右旋操作解决问题。我们首先通过上面的样例来理解右旋操作的原理：

对于新插入的节点，我们检索其根节点，发现根节点左儿子的小于自身，因此执行右旋操作：

我们将左字节点提到根节点作为新的根，原根节点右旋至新根节点的右子节点。

可能这张图片不能完全的表述整个右旋操作的原理，我们用一颗普通二叉树的右旋操作来演示其基本原理：

可以总结一下右旋的步骤：设当前节点，左子节点，右子节点

将提至根节点；
原根节点右旋至右子节点；
将原右子节点给原根节点。

根据上述步骤旋转完后的树如下所示

显然，现在仍不符合要求。此时对于新插入节点的根节点而言，其右子节点值大于它本身，因此需要执行左旋操作。

void rrotate(int &root){
    int tmp = lc[root];
    lc[root] = rc[tmp], rc[tmp] = root;
    siz[tmp] = siz[root];
    pushup(root);
    root = tmp;
}

(2).左旋操作

当我们发现当前节点右儿子的小于自身的时候，我们可以通过左旋操作解决问题。

左旋的步骤实际上就是右旋的逆过程，理解了右旋后左旋就容易理解了。

旋转之后：

此时，我们得到的树结构即满足二叉搜索树的性质，且满足堆的性质。

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).插入操作

插入节点的操作很简单，正如我们在讲解左旋右旋时所演示的一样。如果已存在同值节点，则节点计数++，如果不存在同值节点，首先随机取一个值赋给新节点，然后只需要按照二叉搜索树(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] < x){
        insert(rc[root], x);
        if(ord[rc[root]] < ord[root]) lrotate(root);
    }
    else{
        insert(lc[root], x);
        if(ord[lc[root]] < ord[root]) rrotate(root);
    }
}

(2).删除操作

删除同二叉搜索树一样，我们需要先检索到待删节点，如果其，则只需要；如果其，则将其通过旋转操作旋到叶节点上，直接删除其与父节点的边即可。

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]] < ord[rc[root]]){
            rrotate(root);
            return del(root, x);
        }
        else{
            lrotate(root);
            return del(root, x);
        }
    }
    else if(val[root] < x){
        bool flag = del(rc[root], x);
        if(flag) siz[root]--;
        return flag;
    }
    else{
        bool flag = del(lc[root], x);
        if(flag) siz[root]--;
        return flag;
    }
}

(3).查询给定元素的排名

这部分与普通的二叉搜素树完全相同，具体步骤参考二叉搜索树的查询步骤。

int queryrnk(int root, int x){
    if(!root) return 0;
    if(val[root] == x) return siz[lc[root]] + 1;
    else if(x > siz[lc[root]] + w[root]) return siz[lc[root]] + w[root] + queryrnk(rc[root], x);
    else return queryrnk(lc[root], x);
}

(4).查询给定排名的元素

同样，与普通二叉搜索树相同。

int querynum(int root, int x){
    if(!root) return 0;
    if(x <= siz[lc[root]]) return querynum(lc[root], x);
    else if(x > siz[lc[root]] + w[root]) return querynum(rc[root], x - siz[lc[root]] - w[root]);
    else return val[root];
}

(5).查询后继、前驱

int ans = 0;
void querypre(int root, int x){
    if(!root) return;
    if(val[root] < x) ans = root, querypre(rc[root], x);
    else querypre(lc[root], x);
}
void querysub(int root, int x){
    if(!root) return;
    if(val[root] > x) ans = root, querysub(lc[root], x);
    else querysub(rc[root], x);
}

4.模板

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 10;
int lc[MAXN], rc[MAXN], val[MAXN], ord[MAXN], siz[MAXN], w[MAXN],
int sz = 0, rt = 0;

inline int Rand(){
    static unsigned long long r = 2333;     //static不能少，r的初值可以自己定
    return (r *= 233333) %= 2147483647;     //每次r乘上的数也可以自己定
}

inline void pushup(int x) { siz[x] = siz[lc[x]] + siz[rc[x]] + w[x]; }

void lrotate(int &root){
    int tmp = rc[root];
    rc[root] = lc[tmp], lc[tmp] = root;
    siz[tmp] = siz[root];
    pushup(root);
    root = tmp;
}

void rrotate(int &root){
    int tmp = lc[root];
    lc[root] = rc[tmp], rc[tmp] = root;
    siz[tmp] = siz[root];
    pushup(root);
    root = tmp;
}

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] < x){
        insert(rc[root], x);
        if(ord[rc[root]] < ord[root]) lrotate(root);
    }
    else{
        insert(lc[root], x);
        if(ord[lc[root]] < ord[root]) rrotate(root);
    }
}

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]] < ord[rc[root]]){
            rrotate(root);
            return del(root, x);
        }
        else{
            lrotate(root);
            return del(root, x);
        }
    }
    else if(val[root] < x){
        bool flag = del(rc[root], x);
        if(flag) siz[root]--;
        return flag;
    }
    else{
        bool flag = del(lc[root], x);
        if(flag) siz[root]--;
        return flag;
    }
}

int queryrnk(int root, int x){
    if(!root) return 0;
    if(val[root] == x) return siz[lc[root]] + 1;
    else if(x > siz[lc[root]] + w[root]) return siz[lc[root]] + w[root] + queryrnk(rc[root], x);
    else return queryrnk(lc[root], x);
}

int querynum(int root, int x){
    if(!root) return 0;
    if(x <= siz[lc[root]]) return querynum(lc[root], x);
    else if(x > siz[lc[root]] + w[root]) return querynum(rc[root], x - siz[lc[root]] - w[root]);
    else return val[root];
}

int ans = 0;
void querypre(int root, int x){
    if(!root) return;
    if(val[root] < x) ans = root, querypre(rc[root], x);
    else querypre(lc[root], x);
}
void querysub(int root, int x){
    if(!root) return;
    if(val[root] > x) ans = root, querysub(lc[root], x);
    else querysub(rc[root], x);
}

signed main(){
    int op = 0, n = 0; cin >> op >> n;
    switch(op){
        case 1: insert(rt, n); break;
        case 2: del(rt, n); break;
        case 3: cout << queryrnk(rt, n) << endl;
        case 4: cout << querynum(rt, n) << endl;
        case 5: querypre(rt, n); cout << ans << endl; break;
        case 6: querysub(rt, n); cout << ans << endl; break;
    }
    return 0;
}

三、无旋式Treap

1.无旋式Treap 简介

无旋式Treap，即无旋转操作的Treap，他有两种核心操作：分裂、合并。也正是其操作方式的特性使其具有支持维护序列和可持久化等特性。因此我们可以用封装的无旋式Treap实现类似C++STL中

set

的效果。

优点

：支持可持久化，操作种类多(支持区间操作)

缺点

：相比于Splay要慢很多，且相比于旋转式Treap也要慢一些。

2.无旋式Treap结构与操作基础

无旋式Treap结构与选旋转式Treap相同：既满足二叉搜索树的性质，同时又满足堆的性质。我们继续以旋转式Treap中的样例来对无旋式Treap进行讲解：

对于旋转式Treap，我们可以知道：关键操作都建立在左旋和右旋的基础之上；相似的，对于无旋式Treap，其基本操作都建立在分裂和合并的基础上，我们首先对这两种操作进行讲解：

我们首先对储存结构进行定义：

struct node{
    int val, ord, cnt, siz;
    node *lc, *rc;
    node(int v = 0, int c = 1, int s = 1): val(v), cnt(c), siz(s), lc(nullptr), rc(nullptr){};
}

(1).分裂操作(split)

对无旋式Treap执行分裂操作有两种含义，即按照权值进行分裂或按照排名进行分裂。我们首先来讲解按照权值分裂：

所谓按照权值分裂即：将跟指针指向的Treap分裂为两个，第一个Treap所有节点的权值小于等于给定值，第二个Treap所有节点的权值大于等于给定值。

定义操作

pair<node *, node*> split(node *root, int key)

为分裂操作，其中为根指针，为给定键值。

那么操作的大致思路如下：

判断所指向的节点是否为空；
将当前节点所指向的值与给定的值进行比较：

如果，则说明所指向的节点及其右子树全部属于第二个Treap，同时向左子树继续分裂；
如果，则说明所指向的节点及其左子树全部属于第一个Treap，同时向右子树继续分裂。

根据上述两个条件判断递归向左子树分裂or右子树分裂，并继续递归分裂子树，待子树分裂完成后按刚刚的判断情况连接的左子树或右子树到递归分裂所得的子树中。

我们通过具体的例子来理解这个操作：以样例所示Treap为例，指定进行分裂。

我们从根结点开始检索：

第一次：，因此可以判断当前指向的节点及右子树应该属于第二个Treap，向左子树分裂；

第二次：，因此可以判断当前指向的节点及其左子树全部属于第一个Treap，向右子树分裂；

第三次，，因此可以判断当前指向的节点及其右子树全部属于第二个Treap，此时分裂到叶子节点，无法继续分裂，分裂操作到此终止。

最终，上述二叉树分裂为两棵二叉树：

理解上述过程之后，我们可以写出分裂过程的代码：

pii split(node *root, int key){
    if(root == nullptr)  return mkp(nullptr, nullptr);
    if(key < root -> 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);
    }
}

对于按照排名(权值)进行分裂的类型，实际上与按照权值进行分裂的操作十分相似，仅仅是在左右子树递归的参数上进行了一点修改：即进入左右子树时，对应递归分裂排名的变化。

(2).合并(merge)

必须满足中所有结点的关键值小于等于中所有结点的关键值。因为两个Treap已经有序，我们只需要考虑来决定哪个 Treap 应与另一个Treap的儿子合并。

定义操作

node *merge(node *u, node *v)

，其中和均为待合并的树根指针。

那么操作的大致思路如下：

指针判空：如果指针为空，则返回；如果指针为空，则返回指针；
若的根结点的小于的，那么即为新根结点，应与的右子树合并；反之，则作为新根结点，然后让与

不难发现，这样合并所得的树依然满足

我们依然通过样例来对这个过程进行展示：在先前的分裂操作中，我们得到了两棵子树，设其根节点指针分别为。

函数入口

node * new_tree = merge(u, v);

第一次，①.判断和均为非空指针 ②.指向节点的，指向节点的，则应该作为新根节点，与的左子树执行合并，执行

merge(u, v -> lc)

；

第二次，①.判断和均为非空指针 ②.指向节点的，指向节点的，则应该作为新根节点，与的右子树执行合并，执行

merge(u -> rc, v)

；

第三次，①.判断为空指针，则返回指针，此后逐层返回。

如此，两个树就重新合并在了一起。

根据上述样例的理解，我们可以写出合并操作的代码：

node *merge(node *u, node *v){
    if(u == nullptr) return v;
    if(v == nullptr) return u;
    if(u -> ord < v -> ord){
        u -> rc = merge(u -> rc, v);
        return u;
    }
    else{
        v -> lc = merge(u, v -> lc);
        return v;
    }
}

至此，无旋式Treap的两种基本操作介绍完毕。建立在这两种操作的基础上，我们可以对树的一系列操作进行定义。

3.无旋式Treap 基本操作

(1).建树(build)

建树操作实现的是将一个具有个节点的序列转化为一颗Treap。

可以依次暴力插入这个节点，每次插入一个权值为的节点时，将整棵 Treap 按照权值分裂成权值小于等于的和权值大于的两部分，然后新建一个权值为的节点，将两部分和新节点按从小到大的顺序依次合并，单次插入时间复杂度，总时间复杂度。

在某些题目内，可能会有多次插入一段有序序列的操作，这是就需要在

方法一：在递归建树的过程中，每次选取当前区间的中点作为该区间的树根，并对每个节点钦定合适的优先值，使得新树满足堆的性质。这样能保证树高为。
方法二：在递归建树的过程中，每次选取当前区间的中点作为该区间的树根，然后给每个节点一个随机优先级。这样能保证树高为，但不保证其满足堆的性质。这样也是正确的，因为无旋式 Treap 的优先级是用来使 merge 操作更加随机一点，而不是用来保证树高的。
方法三：观察到 Treap 是笛卡尔树，利用笛卡尔树的

在本博客中，由于我们采用动态申请内存的方式进行储存，因此建树只需要逐个执行插入操作即可。我们会在文末给出基于数组存储的Treap代码，其中包含建树的代码。

(2).查找出现次数(find)

此部分操作与二叉搜索树一致，直接根据二叉搜索树的性质进行查找即可。

int find(node *root, int key){
    if(root == nullptr) return 0;
    if(key == root -> val) return 1;
    if(key < root -> 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);
}

其余如同查询区间排名等与普通平衡树一样的操作不在此一一列举。

4.模板总结

#include <bits/stdc++.h>
#define pii pair<node *, node *>
#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 < root -> 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 < v -> 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 < root -> 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;
}

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] <= k) {
            x = now;
            split(ch[now][1], k, ch[now][1], y);
        } else {
            y = now;
            split(ch[now][0], k, x, ch[now][0]);
        }
        pushup(now);
    }
    int merge(int x, int y) {
        if (x == 0 || y == 0) return x + y;
        if (rnd[x] < rnd[y]) {
            ch[x][1] = merge(ch[x][1], y);
            pushup(x); return x;
        } else {
            ch[y][0] = merge(x, ch[y][0]);
            pushup(y); return y;
        }
    }
    void insert(int v) {
        int x = 0, y = 0;
        split(root, v, x, y);
        root = merge(merge(x, node(v)), y);
    }
    void del(int v) {
        int x = 0, y = 0, z = 0;
        split(root, v, x, z);
        split(x, v - 1, x, y);
        y = merge(ch[y][0], ch[y][1]);
        root = merge(merge(x, y), z);
    }
    int find(int v) {
        int x = 0, y = 0;
        split(root, v - 1, x, y);
        int ans = size[x] + 1;
        root = merge(x, y);
        return ans;
    }
    int findx(int now, int rank) {
        while (1) {
            if (size[ch[now][0]] >= rank) now = ch[now][0];
            else if (size[ch[now][0]] + 1 == rank) return key[now];
            else {
                rank -= size[ch[now][0]] + 1;
                now = ch[now][1];
            }
        }
    }
    int prev(int v) {
        int x = 0, y = 0; 
        split(root, v - 1, x, y);
        int ans = findx(x, size[x]);
        root = merge(x, y);
        return ans;
    }
    int succ(int v) {
        int x = 0, y = 0;
        split(root, v, x, y);
        int ans = findx(y, 1);
        root = merge(x, y);
        return ans;
    }
}f;