平衡树——treap

Treap 简介

　　Treap 是一种二叉查找树。它的结构同时满足二叉查找树（Tree）与堆（Heap）的性质，因此得名。Treap的原理是为每一个节点赋一个随机值使其满足堆的性质，保证了树高期望 O(log2n) ，从而保证了时间复杂度。 
　　Treap 是一种高效的平衡树算法，在常数大小与代码复杂度上好于 Splay。

Treap 的基本操作

　　现在以 BZOJ 3224 普通平衡树为模板题，详细讨论 Treap 的基本操作。

1.基本结构

　　在一般情况下，Treap 的节点需要存储它的左右儿子，子树大小，节点中相同元素的数量（如果没有可以默认为1），自身信息及随机数的值

1 struct sd{
2     int l,r,sz,key,rd,re;
3 }t[100005];

其中 l 为左儿子节点编号， r 为右儿子节点编号， key 为节点数值， sz 为子树大小， rd 为节点的随机值， re为该节点数值的出现次数（目的为将所有数值相同的点合为一个）。

2.关于随机值

　　随机值由 rand() 函数生成， 考虑到 <cstdlib> 库中的 rand() 速度较慢，所以在卡常数的时候建议手写 rand() 函数。

1 inline int rand(){
2     static int seed = 2333;
3     return seed = (int)((((seed ^ 998244353) + 19260817ll) * 19890604ll) % 1000000007);
4 }

其中 seed 为随机种子，可以随便填写。

3.节点信息更新

　　节点信息更新由 update() 函数实现。在每次产生节点关系的修改后，需要更新节点信息（最基本的子树大小，以及你要维护的其他内容）。 
　　时间复杂度 O(1) 。

1 inline void update(int k){
2     t[k].sz = t[l].sz + t[r].sz + t[k].re;
3 }

4.「重要」左旋与右旋

　　左旋与右旋是 Treap 的核心操作，也是 Treap 动态保持树的深度的关键，其目的为维护 Treap 堆的性质。 
　　下面的图片可以让你更好的理解左旋与右旋：

　　这里写图片描述

　　下面具体介绍左旋与右旋操作。左旋与右旋均为变更操作节点与其两个儿子的相对位置的操作。 
　　「左旋」为将作儿子节点代替根节点的位置， 根节点相应的成为左儿子节点的右儿子（满足二叉搜索树的性质）。相应的，之前左儿子节点的右儿子应转移至之前根节点的左儿子。此时，只有之前的根节点与左儿子节点的 sz 发生了变化。所以要 update() 这两个节点。 
　　「右旋」类似于「左旋」，将左右关系相反即可。 
　　时间复杂度 O(1) 。 

 1 void right(int &k)
 2 {
 3     int y=t[k].l;t[k].l=t[y].r;t[y].r=k;
 4     t[y].sz=t[k].sz;
 5     update(k);k=y;
 6 }
 7 void left(int &k)
 8 {
 9     int y=t[k].r;t[k].r=t[y].l;t[y].l=k;
10     t[y].sz=t[k].sz;
11     update(k);k=y;
12 }

5.节点的插入与删除

　　节点的插入与删除是 Treap 的基本功能之一。 
　　「节点的插入」是一个递归的过程，我们从根节点开始，逐个判断当前节点的值与插入值的大小关系。如果插入值小于当前节点值，则递归至左儿子；大于则递归至右儿子；

　　相等则直接在把当前节点数值的出现次数 +1 ，跳出循环即可。如果当前访问到了一个空节点，则初始化新节点，将其加入到 Treap 的当前位置。 
　　「节点的删除」同样是一个递归的过程，不过需要讨论多种情况： 
　　如果插入值小于当前节点值，则递归至左儿子；大于则递归至右儿子。 
　　如果插入值等于当前节点值： 
　　　　若当前节点数值的出现次数大于 1 ，则减一; 
　　　　若当前节点数值的出现次数等于于 1 : 
　　　　　　若当前节点没有左儿子与右儿子，则直接删除该节点（置 0）； 
　　　　　　若当前节点没有左儿子或右儿子，则将左儿子或右儿子替代该节点； 
　　　　　　若当前节点有左儿子与右儿子，则不断旋转 当前节点，并走到当前节点新的对应位置，直到没有左儿子或右儿子为止。 
　　时间复杂度均为 O(log2n) 。 
　　具体实现代码如下：

 1 void inin(int &k,int x)
 2 {
 3     if(k==0)
 4     {
 5         size++;
 6         k=size;t[k].sz=1;
 7         t[k].re=1;
 8         t[k].key=x;
 9         t[k].rd=rand(); 
10         return;
11     }
12     t[k].sz++;
13     if(t[k].key==x) 
14     t[k].re++;
15     else
16     {
17         if(x>t[k].key)
18         {
19             inin(t[k].r,x);
20             if(t[t[k].r].rd<t[k].rd) 
21             left(k);
22         }
23         else
24         {
25             inin(t[k].l,x);
26             if(t[t[k].l].rd<t[k].rd)
27             right(k);
28         }
29     }
30 }
31 void del(int &k,int x)
32 {
33     if(k==0)
34     return;
35     if(t[k].key==x)
36     {
37         if(t[k].re>1)
38         {
39             t[k].re--;
40             t[k].sz--;
41             return;
42         }
43         if(t[k].l*t[k].r==0)
44         k=t[k].l+t[k].r;
45         else
46         {
47             if(t[t[k].l].rd<t[t[k].r].rd)
48             right(k),del(k,x);
49             else
50             left(k),del(k,x);
51         }
52     }
53     else
54     {
55         if(x>t[k].key)
56         {
57             t[k].sz--;
58             del(t[k].r,x);
59         }
60         else
61         {
62             t[k].sz--;
63             del(t[k].l,x);
64         }
65     }
66 }

接下来来一道treap模板题，具体其它操作可在代码中学习，有较详细注释

新手代码可能有点冗长，作为蒟蒻，希望大佬勿喷。

https://www.luogu.org/problemnew/show/P3369

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
using namespace std;
struct sd{
    int l,r,sz,key,rd,re;//树的左，右，大小，关键值，随机权值，重复次数
    //我这里建立的是小根堆，即随机权值小的在上方 
}t[100005];
int size,ans,root;
void update(int k)//每次上浮都要更新树的大小 
{
    t[k].sz=t[t[k].l].sz+t[t[k].r].sz+t[k].re;
}
void right(int &k)//向右旋转，是左子树就右旋 
{
    int y=t[k].l;t[k].l=t[y].r;t[y].r=k;
    t[y].sz=t[k].sz;
    update(k);k=y;
}
void left(int &k)//向左旋转 ，是右子树就左旋 
{
    int y=t[k].r;t[k].r=t[y].l;t[y].l=k;
    t[y].sz=t[k].sz;
    update(k);k=y;
}
void inin(int &k,int x)//插入x
{
    if(k==0)//判断是否到了叶节点，如果是就开始插入X 
    {
        size++;
        k=size;t[k].sz=1;
        t[k].re=1;
        t[k].key=x;
        t[k].rd=rand();//随机权值，保证平衡树的随机性与唯一性，让出题人卡不了 
        return;
    }
    t[k].sz++;//每次向下插入时都要在子树大小加一
    if(t[k].key==x)//如果要插入的数原本就存在，那就直接在这个结点数的重复次数+1. 
    t[k].re++;
    else
    {
        if(x>t[k].key)
        {
            inin(t[k].r,x);//到右子树中去找 
            if(t[t[k].r].rd<t[k].rd)//每次插入后判断是否改变了平衡树堆的性质 
            left(k);
        }
        else
        {
            inin(t[k].l,x);//在左子树中找 
            if(t[t[k].l].rd<t[k].rd)
            right(k);
        }
    }
}
void del(int &k,int x)//删除x
{
    if(k==0)
    return;
    if(t[k].key==x)//找到了目标x就将其下沉 
    {
        if(t[k].re>1)//如果x重复多次出现，只用删除一个，那就不用下沉了，直接将重复次数-1 
        {
            t[k].re--;
            t[k].sz--;
            return;
        }
        if(t[k].l*t[k].r==0)//如果某个子树为空，那就直接将那个子树接到原树上，然后就把原树挤掉了 
        k=t[k].l+t[k].r;
        else
        {
            if(t[t[k].l].rd<t[t[k].r].rd)//为了维持平衡树堆的性质，每次下沉都与随机权值小的交换 
            right(k),del(k,x);
            else
            left(k),del(k,x);
        }
    }
    else//如果还没找到要删除的数，那就继续找呗 
    {
        if(x>t[k].key)
        {
            t[k].sz--;
            del(t[k].r,x);
        }
        else
        {
            t[k].sz--;
            del(t[k].l,x);
        }
    }
}
int rank1(int k,int x)//查找数x的排名
{
    if(k==0)return 0;
    if(t[k].key==x)return t[t[k].l].sz+1;//找到目标数，加上自己与比自己小的（即左子树）的数的个数 
    else
    if(x>t[k].key)
    return t[t[k].l].sz+t[k].re+rank1(t[k].r,x);//一旦在右子树寻找就要，递归回来时就要加上左子树大小 
    else
    return rank1(t[k].l,x);//如果在左子树找的话就不用加了 
}
int rank2(int k,int x)//查找排名为x的数
{
    if(k==0)return 0;
    if(x<=t[t[k].l].sz)//在左子树中找 
    return rank2(t[k].l,x);
    else
    if(x>(t[t[k].l].sz+t[k].re))
    return rank2(t[k].r,x-t[t[k].l].sz-t[k].re);//在右子树中找 
    else
    return t[k].key;//如果既不在左子树，也不在右子树，那就在这个结点上了，就是这个结点的数 
}
void pre(int k,int x)//找前缀 
{
    if(k==0)return;
    if(t[k].key<x)
    {
        ans=k;//每次都更新ans的值，直到找到最值 
        pre(t[k].r,x);
    }
    else
    pre(t[k].l,x);//显然没找到符合要求的，那就继续找 
}
void next(int k,int x)//找后缀 
{
    if(k==0)return;
    if(t[k].key>x)
    {
        ans=k;//与找前缀同理 
        next(t[k].l,x);
    }
    else
    next(t[k].r,x);
}
int main()
{
    srand(time(0));//好像这行代码可加可不加，本来就是只为了使随机数每次不同，至于为何删掉后没影响，我就不知道了 
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int op,x;
        scanf("%d%d",&op,&x);
        if(op==1)
        inin(root,x);
        if(op==2)
        del(root,x);
        if(op==3)
        {
            int res=rank1(root,x);
            printf("%d
",res);
        }
        if(op==4)
        {
            int res=rank2(root,x);
            printf("%d
",res);
        }
        if(op==5)
        {
            pre(root,x);
            printf("%d
",t[ans].key);
        }
        if(op==6)
        {
            next(root,x);
            printf("%d
",t[ans].key);
        }
    }
    return 0;
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/genius777/p/8470579.html