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

悠悠 2023-01-17 04:43 174阅读 0赞

本文作者封承成，年仅13岁，非常感谢他的投稿。

说起二叉查找树的平衡调整，大家最先想到的一定是红黑树或者AVL树。

其实，能够进行平衡调整的二叉树还有很多种，**树堆（Treap）**就是其中一种。

Treap是什么？

顾名思义，**Treap=Tree+Heap**，**树堆=树+堆**

所以，Treap就一定是树和堆的结合体咯！

恭喜你，你已经掌握Treap的精髓了

那么Treap是怎样把树和堆的优点结合起来的呢？

## Treap的特性 ##

Treap与AVL、红黑树等平衡树本质相同，都是一个**二叉查找树（BST）**。但是作为一个平衡树，它必须要有一个维护树平衡的功能（避免变成一条链）。它的每个节点还有一个随机生成的**优先级**，这些优先级要满足**堆的性质**，以保证这个树**相对**较平衡。

比如说这个

![0ad750a2b15cd8bc2cbb817d300fdaa7.png][]

就是一个Treap树（本质上跟BST没区别）

问题是，在调整（插入、删除元素）Treap树时可能会使得每个节点的优先级不满足**堆的性质**，所以我们要对树进行调整

## Treap的建模 ##

我们考虑用指针的方式建树，一个节点的模型如下：

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种旋转。

### 右旋 ###

![ae9775f4b914a57f1485a5eed386fb1f.png][]

我们假设这个树已经满足二叉查找树的特性，即D<B<E<A<C，我们可以这样旋转

第一步：把A-C边挂到B下面

![d90461a42e41bbaf125329e230fad634.png][]

第二步：把点E挂到A下面

![7bb256e5b9707f670b08483d70c64fcc.png][]

这样旋转，依然保证这个子树满足D<B<E<A<C，还调整了树形。我们把右旋总结为：

> 枢纽（B）拎上来，父（A）兄（C）挂下面，右孩（E）给父亲（A）

**注意：D、C、E都可以表示一个子树**而不仅仅是一个节点

代码如下：

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();
    }

### 左旋 ###

左旋跟右旋差不多一样，把右旋的整个过程反过来就是左旋。也是分两步走：

![3424c560af902b159a728b556e3d4f57.png][]

第一步：

![9478eaf27d845f8ddf7802b9f4c395fc.png][]

第二步：

![cc528026021232b13f654623b2bd1abf.png][]

代码如下：

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`，然后将左旋和右旋写成一个函数：

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`也要更新

### 插入节点 ###

Treap也是一类BST，所以插入的时候我们首先要**遵循BST的插入规则**，**插入之后**再根据优先级判断是否需要旋转。我们以这个树为例（绿色小字是该节点的优先级），我们要在这个树中插入一个8。

![c77bbf98df66192720f0e1ea528d76d1.png][]

当前的目标是在以值为2的节点为根的子树上，插入一个值为8的节点。

而我们发现，8>2，8一定在根的右子树上。

因此，这个问题就变成了在以值为6的节点为根的子树上插入一个值为8的节点。

而我们发现，8>6，8一定在根的右子树上。

这个问题就变成了在以值为9的节点为根的子树上，插入一个值为8的节点。

而我们发现，8<9，8一定在根的左子树上，而9已经是叶子了，可以直接往进塞。

假设这个节点的优先级是5（随机出来的）：

![8d5f0b1dcb40974b7344fdb0eb3df741.png][]

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

![808c15f711605852d117f04b3ac206dd.png][]

显然，旋转以后这依然满足BST的特性。然而，我们 又双叒叕 发现，两个标红的优先级不满足堆的特性了，而且这两个不满足的节点是向右斜的，我们可以对这个子树进行左旋：

![2f89b45f431d9cd9071807acb4172d23.png][]

一次插入就完成啦！

我们总结一下，一步步往下走找到一个合适的位置**满足BST**，然后再一步步往上走进行旋转以满足**堆的特性**。

显然，我们可以用递归来完成这个过程。往下走的部分借助**递**，向上走的部分借助**归**。

我们来写一下代码，这里可能有点难理解，好好看注释：

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();
    }

### 删除节点 ###

删除节点与插入节点的**顺序基本一样**。都是**先下后上**。

我们还是举一个例子，我们要删除值为6的节点：

![3f2b6e82ddd7d21e10c4a0f097277b87.png][]

当前的目标就是在以值为2的节点为根的子树中删除值为6的节点

因为6>2，所以目标节点一定在根的右子树上，这个问题就变为，

在以值为6的节点为根的子树中删除值为6的节点

很好！我们已经找到目标节点了。皇帝驾崩了，大皇子顶上！

我们可以让树旋转使得**优先级较大**的儿子替换掉父亲（目标节点）

在这里我们给6这个子树进行**左旋**

![adf22d0b2fb69a4bda3d668383fef1e3.png][]

但是我们要删的节点跑了，我们要**继续追杀**！

我们追到左子树，拿着枪对着它，它还算敬业，要让自己另一个儿子接班后再阵亡。

作为一个善良的人，我们只好应允它的请求，再它给转！

![d10b6123443557c1cca32016e4ed8eac.png][]

这时候，6已经没有拖延时间的借口了，我们直接祝它清明节快乐，删掉它吧！

![4478583538d2c3ec572643a42220798f.png][]

显然删完之后，这个树依然满足Treap树的特性。

话不多说，直接上代码：

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一样，所以直接贴代码了

#### 查询排名 ####

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;
    }

或是

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;
    }

或是

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)`

#### 查询后继 ####

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)`

## 总结 ##

Treap不算是一个**标准**的平衡树。但因为它完美地结合了树和堆的特性，使得它常数比AVL小，无论是在竞赛中还是在开发应用中都有**比较好**的效果，因此常用来代替AVL树。

同时，我们也可以从中学到一点：两种不同的算法可以通过巧妙的方法**优势互补**，从而达到更好的效果。在实际开发中我们如果能运用这个方法，一定能得到不小的成效。

[0ad750a2b15cd8bc2cbb817d300fdaa7.png]: /images/20221022/549917218af949b9b8af1139f0e75bda.png
[ae9775f4b914a57f1485a5eed386fb1f.png]: /images/20221022/93a0e66ebf7945b08ce72810d000b3da.png
[d90461a42e41bbaf125329e230fad634.png]: /images/20221022/33e727682194443cae0cc8f4e2a83dab.png
[7bb256e5b9707f670b08483d70c64fcc.png]: /images/20221022/b9da313d92064a419a809237c0c1f873.png
[3424c560af902b159a728b556e3d4f57.png]: /images/20221022/ac935ba4c21c4c498c1bb6f4b05dcf9e.png
[9478eaf27d845f8ddf7802b9f4c395fc.png]: /images/20221022/dfa03c5c56294d6c9f5c9165e035711d.png
[cc528026021232b13f654623b2bd1abf.png]: /images/20221022/831492508c5041d3a6d2dffb868713bb.png
[c77bbf98df66192720f0e1ea528d76d1.png]: /images/20221022/b2419aa7410b4eac95cf9cca7b8e83e1.png
[8d5f0b1dcb40974b7344fdb0eb3df741.png]: /images/20221022/42081cc321644f258477580170427620.png
[808c15f711605852d117f04b3ac206dd.png]: /images/20221022/26c6efc0ca8f421887a8e99f2fea6d6c.png
[2f89b45f431d9cd9071807acb4172d23.png]: /images/20221022/ea8f60a4dab34acd981a941cbc765632.png
[3f2b6e82ddd7d21e10c4a0f097277b87.png]: /images/20221022/50adc794b27c4e78bf30c1a9bcc8e742.png
[adf22d0b2fb69a4bda3d668383fef1e3.png]: /images/20221022/8df0636cbb9b42e395fa50a1018bb65a.png
[d10b6123443557c1cca32016e4ed8eac.png]: /images/20221022/04633558b95d43b8afdf8a3a4f797e7c.png
[4478583538d2c3ec572643a42220798f.png]: /images/20221022/f0c51d61789f459982d12e70b1050aa4.png