面试官问我：什么是树堆（Treap）？-

沙海

3186
文章

2
评论

2021年4月26日01:18:07Java评论154字数 5603阅读18分40秒阅读模式

摘要

速读摘要

速读摘要文章源自JAVA秀-https://www.javaxiu.com/20528.html

作为一个平衡树，它必须要有一个维护树平衡的功能(避免变成一条链)。当前的目标是在以值为2的节点为根的子树上，插入一个值为8的节点。这个问题就变成了在以值为6的节点为根的子树上插入一个值为8的节点。这个问题就变成了在以值为9的节点为根的子树上，插入一个值为8的节点。我们追到左子树，拿着枪对着它，它还算敬业，要让自己另一个儿子接班后再阵亡。文章源自JAVA秀-https://www.javaxiu.com/20528.html

原文约 2360 字 | 图片 15 张 | 建议阅读 5 分钟 | 评价反馈文章源自JAVA秀-https://www.javaxiu.com/20528.html

面试官问我：什么是树堆（Treap）？

原创封承成程序员小灰文章源自JAVA秀-https://www.javaxiu.com/20528.html

本文作者封承成，年仅13岁，非常感谢他的投稿。文章源自JAVA秀-https://www.javaxiu.com/20528.html

说起二叉查找树的平衡调整，大家最先想到的一定是红黑树或者AVL树。文章源自JAVA秀-https://www.javaxiu.com/20528.html

文章源自JAVA秀-https://www.javaxiu.com/20528.html

其实，能够进行平衡调整的二叉树还有很多种，树堆（Treap）就是其中一种。文章源自JAVA秀-https://www.javaxiu.com/20528.html

Treap是什么？文章源自JAVA秀-https://www.javaxiu.com/20528.html

顾名思义，Treap=Tree+Heap，树堆=树+堆文章源自JAVA秀-https://www.javaxiu.com/20528.html

所以，Treap就一定是树和堆的结合体咯！文章源自JAVA秀-https://www.javaxiu.com/20528.html

恭喜你，你已经掌握Treap的精髓了文章源自JAVA秀-https://www.javaxiu.com/20528.html

那么Treap是怎样把树和堆的优点结合起来的呢？文章源自JAVA秀-https://www.javaxiu.com/20528.html

Treap的特性

Treap与AVL、红黑树等平衡树本质相同，都是一个二叉查找树（BST）。但是作为一个平衡树，它必须要有一个维护树平衡的功能（避免变成一条链）。它的每个节点还有一个随机生成的优先级，这些优先级要满足堆的性质，以保证这个树相对较平衡。文章源自JAVA秀-https://www.javaxiu.com/20528.html

比如说这个文章源自JAVA秀-https://www.javaxiu.com/20528.html

面试官问我：什么是树堆（Treap）？文章源自JAVA秀-https://www.javaxiu.com/20528.html

就是一个Treap树（本质上跟BST没区别）文章源自JAVA秀-https://www.javaxiu.com/20528.html

问题是，在调整（插入、删除元素）Treap树时可能会使得每个节点的优先级不满足堆的性质，所以我们要对树进行调整文章源自JAVA秀-https://www.javaxiu.com/20528.html

Treap的建模

我们考虑用指针的方式建树，一个节点的模型如下：文章源自JAVA秀-https://www.javaxiu.com/20528.html

typedef struct Node {    Node(int v) {        val = v, cnt = size = 1, fac = rand();        lson = rson = NULL;    }    //  值  个数  子树大小 优先级    int val, cnt, size, fac;    // 元素有可能重复，所以用cnt记有多少个    //     左儿子 右儿子    Node *lson, *rson;    // 每次更改后更新以这个节点的为根的字数大小    inline void push_up() {        size = cnt;        if (lson != NULL) size += lson->size;        if (rson != NULL) size += rson->size;    }}* Tree;inline int size(Tree t) { return t == NULL ? 0 : t->size; }inline Tree init() {    Tree rt = new Node(Inf);    rt->lson = new Node(-Inf);    rt->fac = -Inf, rt->lson->fac = -Inf;    rt->push_up();    return rt;}

Treap的操作

我们为了保证Treap树在改变后优先级依然能够满足堆的性质，我们需要在它满足二叉查找树的前提下进行旋转使得它的优先级形成一个堆。Treap的好处就在于它只有2种旋转。文章源自JAVA秀-https://www.javaxiu.com/20528.html

右旋

面试官问我：什么是树堆（Treap）？文章源自JAVA秀-https://www.javaxiu.com/20528.html

我们假设这个树已经满足二叉查找树的特性，即D<B<E<A<C，我们可以这样旋转文章源自JAVA秀-https://www.javaxiu.com/20528.html

第一步：把A-C边挂到B下面文章源自JAVA秀-https://www.javaxiu.com/20528.html

面试官问我：什么是树堆（Treap）？文章源自JAVA秀-https://www.javaxiu.com/20528.html

文章源自JAVA秀-https://www.javaxiu.com/20528.html

第二步：把点E挂到A下面文章源自JAVA秀-https://www.javaxiu.com/20528.html

面试官问我：什么是树堆（Treap）？文章源自JAVA秀-https://www.javaxiu.com/20528.html

文章源自JAVA秀-https://www.javaxiu.com/20528.html

这样旋转，依然保证这个子树满足D<B<E<A<C，还调整了树形。我们把右旋总结为：文章源自JAVA秀-https://www.javaxiu.com/20528.html

枢纽（B）拎上来，父（A）兄（C）挂下面，右孩（E）给父亲（A）文章源自JAVA秀-https://www.javaxiu.com/20528.html

注意：D、C、E都可以表示一个子树而不仅仅是一个节点文章源自JAVA秀-https://www.javaxiu.com/20528.html

代码如下：文章源自JAVA秀-https://www.javaxiu.com/20528.html

inline void right_rotate(Tree &a) {    Tree b = a->lson;    a->lson = b->rson, b->rson = a, a = b;    a->rson->push_up(), a->push_up();}

左旋

左旋跟右旋差不多一样，把右旋的整个过程反过来就是左旋。也是分两步走：文章源自JAVA秀-https://www.javaxiu.com/20528.html

面试官问我：什么是树堆（Treap）？文章源自JAVA秀-https://www.javaxiu.com/20528.html

第一步：文章源自JAVA秀-https://www.javaxiu.com/20528.html

面试官问我：什么是树堆（Treap）？文章源自JAVA秀-https://www.javaxiu.com/20528.html

第二步：文章源自JAVA秀-https://www.javaxiu.com/20528.html

面试官问我：什么是树堆（Treap）？文章源自JAVA秀-https://www.javaxiu.com/20528.html

代码如下：文章源自JAVA秀-https://www.javaxiu.com/20528.html

inline void right_rotate(Tree &a) {    Tree b = a->lson;    a->lson = b->rson, b->rson = a, a = b;    a->rson->push_up(), a->push_up();}

网上也有博文将lson和rson写成一个数组son，然后将左旋和右旋写成一个函数：文章源自JAVA秀-https://www.javaxiu.com/20528.html

inline void rotate(Tree &a, int f) {    Tree b = a->son[f^1];    a->son[f^1] = b->son[f], b->son[f] = a, a = b;    a->rson->push_up(), b->push_up();}

注意左旋、右旋中的代码传的参数a需要传引用，因为最后a也要更新文章源自JAVA秀-https://www.javaxiu.com/20528.html

插入节点

Treap也是一类BST，所以插入的时候我们首先要遵循BST的插入规则，插入之后再根据优先级判断是否需要旋转。我们以这个树为例（绿色小字是该节点的优先级），我们要在这个树中插入一个8。文章源自JAVA秀-https://www.javaxiu.com/20528.html

面试官问我：什么是树堆（Treap）？文章源自JAVA秀-https://www.javaxiu.com/20528.html

当前的目标是在以值为2的节点为根的子树上，插入一个值为8的节点。文章源自JAVA秀-https://www.javaxiu.com/20528.html

而我们发现，8>2，8一定在根的右子树上。文章源自JAVA秀-https://www.javaxiu.com/20528.html

因此，这个问题就变成了在以值为6的节点为根的子树上插入一个值为8的节点。文章源自JAVA秀-https://www.javaxiu.com/20528.html

而我们发现，8>6，8一定在根的右子树上。文章源自JAVA秀-https://www.javaxiu.com/20528.html

这个问题就变成了在以值为9的节点为根的子树上，插入一个值为8的节点。文章源自JAVA秀-https://www.javaxiu.com/20528.html

而我们发现，8<9，8一定在根的左子树上，而9已经是叶子了，可以直接往进塞。文章源自JAVA秀-https://www.javaxiu.com/20528.html

假设这个节点的优先级是5（随机出来的）：文章源自JAVA秀-https://www.javaxiu.com/20528.html

面试官问我：什么是树堆（Treap）？文章源自JAVA秀-https://www.javaxiu.com/20528.html

很明显，两个标红的优先级不满足大顶堆的特性（即儿子的优先级大于父亲的了），而且这两个节点是向左斜的，那么我们就要对这个节点进行右旋。因为两个节点都没有额外的儿子，所以一步完成：文章源自JAVA秀-https://www.javaxiu.com/20528.html

面试官问我：什么是树堆（Treap）？文章源自JAVA秀-https://www.javaxiu.com/20528.html

显然，旋转以后这依然满足BST的特性。然而，我们又双叒叕发现，两个标红的优先级不满足堆的特性了，而且这两个不满足的节点是向右斜的，我们可以对这个子树进行左旋：文章源自JAVA秀-https://www.javaxiu.com/20528.html

面试官问我：什么是树堆（Treap）？文章源自JAVA秀-https://www.javaxiu.com/20528.html

一次插入就完成啦！文章源自JAVA秀-https://www.javaxiu.com/20528.html

我们总结一下，一步步往下走找到一个合适的位置满足BST，然后再一步步往上走进行旋转以满足堆的特性。文章源自JAVA秀-https://www.javaxiu.com/20528.html

显然，我们可以用递归来完成这个过程。往下走的部分借助递，向上走的部分借助归。文章源自JAVA秀-https://www.javaxiu.com/20528.html

我们来写一下代码，这里可能有点难理解，好好看注释：文章源自JAVA秀-https://www.javaxiu.com/20528.html

inline void ins(Tree &rt, int val) {    if (rt == NULL) {rt = new Node(val); return;}    if (rt->val == val) rt->cnt++; // 已经有这个点了    else if (rt->val > val) {        // 如果这个节点的值大了就跑到左子树        ins(rt->lson, val);        // 因为只更改了左子树，只用判断自己和左子树的优先级        if (rt->fac < rt->lson->fac) right_rotate(rt);    }    else {        // 如果这个节点的值小了就跑到右子树        ins(rt->rson, val);        if (rt->fac < rt->rson->fac) left_rotate(rt);    }    rt->push_up();}

删除节点

删除节点与插入节点的顺序基本一样。都是先下后上。文章源自JAVA秀-https://www.javaxiu.com/20528.html

我们还是举一个例子，我们要删除值为6的节点：文章源自JAVA秀-https://www.javaxiu.com/20528.html

面试官问我：什么是树堆（Treap）？文章源自JAVA秀-https://www.javaxiu.com/20528.html

当前的目标就是在以值为2的节点为根的子树中删除值为6的节点文章源自JAVA秀-https://www.javaxiu.com/20528.html

因为6>2，所以目标节点一定在根的右子树上，这个问题就变为，文章源自JAVA秀-https://www.javaxiu.com/20528.html

在以值为6的节点为根的子树中删除值为6的节点文章源自JAVA秀-https://www.javaxiu.com/20528.html

很好！我们已经找到目标节点了。皇帝驾崩了，大皇子顶上！文章源自JAVA秀-https://www.javaxiu.com/20528.html

我们可以让树旋转使得优先级较大的儿子替换掉父亲（目标节点）文章源自JAVA秀-https://www.javaxiu.com/20528.html

在这里我们给6这个子树进行左旋文章源自JAVA秀-https://www.javaxiu.com/20528.html

面试官问我：什么是树堆（Treap）？文章源自JAVA秀-https://www.javaxiu.com/20528.html

但是我们要删的节点跑了，我们要继续追杀！文章源自JAVA秀-https://www.javaxiu.com/20528.html

我们追到左子树，拿着枪对着它，它还算敬业，要让自己另一个儿子接班后再阵亡。文章源自JAVA秀-https://www.javaxiu.com/20528.html

作为一个善良的人，我们只好应允它的请求，再它给转！文章源自JAVA秀-https://www.javaxiu.com/20528.html

面试官问我：什么是树堆（Treap）？文章源自JAVA秀-https://www.javaxiu.com/20528.html

这时候，6已经没有拖延时间的借口了，我们直接祝它清明节快乐，删掉它吧！文章源自JAVA秀-https://www.javaxiu.com/20528.html

面试官问我：什么是树堆（Treap）？文章源自JAVA秀-https://www.javaxiu.com/20528.html

显然删完之后，这个树依然满足Treap树的特性。文章源自JAVA秀-https://www.javaxiu.com/20528.html

话不多说，直接上代码：文章源自JAVA秀-https://www.javaxiu.com/20528.html

inline void del(Tree &rt, int val) {    if (rt == NULL) return; // 没找到    if (rt->val == val) {        // 找到这个节点了        if (rt->cnt > 1) {rt->cnt--, rt->push_up(); return;}        // 它有孩子        if (rt->lson != NULL || rt->rson != NULL) {            // 重点            if (rt->rson == NULL || rt->lson != NULL && rt->lson->fac > rt->rson->fac)                right_rotate(rt), del(rt->rson, val);            else left_rotate(rt), del(rt->lson, val);        }        else {delete rt; rt = NULL; return;} // 手动gc    }    else if (rt->val > val) del(rt->lson, val);    else del(rt->rson, val);    rt->push_up();}

查询

查询分好几种，因为Treap跟普通BST一样，所以直接贴代码了文章源自JAVA秀-https://www.javaxiu.com/20528.html

查询排名

inline int qry_rank(Tree p, int val) { // 询问有多少个数小于等于val（也就相当于查询排名）    int rank = 0;    while (p != NULL)        if (p->val == val) return size(p->lson) + rank;        else if (p->val > val) p = p->lson;        else rank += size(p->lson) + p->cnt, p = p->rson;    return rank;}

或是文章源自JAVA秀-https://www.javaxiu.com/20528.html

inline int qry_rank(Tree p, int val) {    if (p->val == val) return size(p->lson);    if (p->val > val) return qry_rank(p->lson, val);    return qry_rank(p->rson, val) + size(p->lson) + p->cnt;}

查询数值

inline int qry_value(Tree p, int rank) {    while (p != NULL && rank)        if (size(p->lson) > rank) p = p->lson;        else if (size(p->lson)+p->cnt >= rank) return p->val;        else rank -= size(p->lson)+p->cnt, p = p->rson;}

或是文章源自JAVA秀-https://www.javaxiu.com/20528.html

inline int qry_value(Tree p, int rank) {    if (size(p->lson) >= rank) return qry_value(p->rson, rank);    if (size(p->lson)+p->cnt >= rank) return p->val;    return qry_value(p->lson, rank-size(p->lson)-p->cnt);}

查询前驱

inline int qry_pre(Tree p, int val) {    int pre = 0;    while (p != NULL)        if (p->val < val) pre = p->val, p = p->rson;        else p = p->lson;    return pre;}

或者直接qry_value(qry_rank(p, val)-1)文章源自JAVA秀-https://www.javaxiu.com/20528.html

查询后继

inline int qry_suf(Tree p, int val) {    int suf = 0;    while (p != NULL)        if (p->val > val) suf = p->val, p = p->lson;        else p = p->rson;    return suf;}

或者直接qry_value(qry_rank(p, val)+1)文章源自JAVA秀-https://www.javaxiu.com/20528.html