本文是Splay（伸展树）的后续。

        在介绍Splay时，已经提及了BST的概念。BST在最坏情况下会达到$O(n)$复杂度，于是有各种使其平衡的方法，Treap就是一种，它也属于平衡树，比Splay要更易实现。
        Splay是通过伸展操作来使树的结构随机化，以达到均摊$O(logn)$的复杂度。Treap是通过在维护BST时同时维护堆来实现结构的随机化。
        所谓Treap就是Tree+Heap，故称树堆。
        先来看看Treap的结点结构体定义，和Splay类似：

1
2
3
4
5
6
7
struct Node {
    int v{}, key{}, ch[2]{}, s, num;

    Node() : num(0), s(0) {
        ch[0] = ch[1] = 0;
    }
} node[100005];

        没记录父结点？是的，在Treap中不需要记录父结点信息。
        另外还可以发现多了一个key，key记录这个结点的优先级。刚才已经提到，Treap是树与堆的结合（这里的堆不再是完全二叉树，只要有堆的性质即可），所谓堆的性质就是：所有结点的优先级不得小于其子结点优先级。这当然是大根堆，用小根堆也是可以的，本文中使用大根堆。我们在维护BST的同时还要满足堆的要求。
        key应该如何赋值？在插入一个新结点时，会给它分配一个随机的优先值，这个可以通过rand()函数来实现。从这里就可以看出Treap的原理：通过优先级的随机性来保持树结构的随机性。
        下面的函数，若无特殊说明，函数都采用与Splay中相同的命名。

旋转操作

        Treap中同样有旋转操作。当某结点不满足堆的性质时（比如它的优先级大于父结点），就需要进行一次旋转，将其旋转到父结点的位置。
        Treap中只有左旋和右旋，没有Splay中双旋的概念。

1
2
3
4
void rotate(int &x, int w) {
    int c1 = node[x].ch[w], c2 = node[c1].ch[w ^ 1];
    node[x].ch[w] = c2, node[c1].ch[w ^ 1] = x, node[c1].num = node[x].num, update(x), x = c1;
}

        上面就是旋转函数的定义，它的作用是将编号为x的结点旋转下去，方向为w（1为左旋），这和splay中的旋转上去有所不同。但事实上将子结点旋转上去就是把父结点旋转下来。
        这里有一些值得注意的细节。一处是node[c1].num = node[x].num，这其实就是update(c1)的简略写法。另外还有x=c1，这里巧妙地使用引用来实现我们在Splay中旋转的第三步。

插入操作

        Treap中的插入是基于递归的，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void insert(int &x, int v) {
    if (!x) {//空结点，新建结点
        x = cnt++;
        node[x].v = v, node[x].s = 1, node[x].num = 1, node[x].key = rand();
        node[x].ch[0] = node[x].ch[1] = 0;
        return;
    }
    node[x].num++;//路过的结点都要更新num
    if (node[x].v == v)node[x].s++;//找到直接更新s
    else if (node[x].v < v) {//找右树
        insert(node[x].ch[1], v);
        if (node[node[x].ch[1]].key > node[x].key)rotate(x, 1);//旋转，维护堆的性质
    } else {//找左树
        insert(node[x].ch[0], v);
        if (node[node[x].ch[0]].key > node[x].key)rotate(x, 0);
    }
}

        它的作用是在以结点x为根的子树上插入值为v的结点。
        当x为0时，说明这里是一个空结点，此时新建结点，更新信息，分配优先级。
        另外，所有经过的结点都需要更新num。其次在递归回溯后需要检查堆的性质是否满足，如果不满足就需要旋转来调整。从这里可以看出引用的技巧性。

删除操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void del(int &x, int v) {
    if (!x)return;//空结点无需继续
    if (node[x].v == v) {//找到该结点
        if (node[x].s > 1) node[x].num--, node[x].s--;//直接更新值
        else {//需要删除结点
            if (!node[x].ch[0] && !node[x].ch[1])x = 0;//没有儿子，直接赋值0
            else if (!node[x].ch[0])x = node[x].ch[1];//有右儿子，将右儿子移过来
            else if (!node[x].ch[1])x = node[x].ch[0];//有左儿子，将左儿子移过来
            else if (node[node[x].ch[0]].key < node[node[x].ch[1]].key)rotate(x, 1), del(x, v);//将优先级大的旋转上去，递归
            else rotate(x, 0), del(x, v);
        }
    } else if (node[x].v > v)node[x].num--, del(node[x].ch[0], v);//找左树
    else node[x].num--, del(node[x].ch[1], v);//找右树
}

        Treap的删除操作基于分类讨论，有这几种情况（只考虑完全删除的情况，s自减一不考虑）：

  • 若该结点没有儿子，直接删除
  • 若结点仅有右儿子，则左儿子代替其位置。仅有左儿子同理。
  • 若结点有两个儿子，则将优先级大的一个旋转到该结点位置，再递归进行删除。

        这里的一个易错点是每一个经过的结点需要更新num，但是上面的分类讨论中不需要更新，因为上面的分类讨论过程只是更改了一下树的结构。
        其余的操作与Splay完全相同。