天天看点

数据结构-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:

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

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

​右旋​

​​和​

​左旋​

​进行讲解。

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

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

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

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

(1).右旋操作

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

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

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

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

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

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

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

  1. 将提至根节点;
  2. 原根节点右旋至右子节点;
  3. 将原右子节点给原根节点。

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

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

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

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

(2).左旋操作

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

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

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

旋转之后:

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

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

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,我们可以知道:关键操作都建立在左旋和右旋的基础之上;相似的,对于无旋式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)​

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

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

  1. 判断所指向的节点是否为空;
  2. 将当前节点所指向的值与给定的值进行比较:
  • 如果,则说明所指向的节点及其右子树全部属于第二个Treap,同时向左子树继续分裂;
  • 如果,则说明所指向的节点及其左子树全部属于第一个Treap,同时向右子树继续分裂。

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

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

我们从根结点开始检索:

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

第一次:,因此可以判断当前指向的节点及右子树应该属于第二个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)​

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

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

  1. 指针判空:如果指针为空,则返回;如果指针为空,则返回指针;
  2. 若的根结点的小于的,那么即为新根结点,应与的右子树合并;反之,则作为新根结点,然后让与

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

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

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

函数入口​

​node * new_tree = merge(u, v);​

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

​merge(u, v -> lc)​

​;

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

​merge(u -> rc, v)​

​;

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

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

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

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

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;      

继续阅读