treap模版_bartender模板

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46，售后保障稳定

之前我们讲到二叉搜索树，从二叉搜索树到2-3树到红黑树到B-树。
二叉搜索树的主要问题就是其结构与数据相关，树的深度可能会很大，Treap树就是一种解决二叉搜索树可能深度过大的另一种数据结构。

Treap

Treap=Tree+Heap。Treap本身是一棵二叉搜索树，它的左子树和右子树也分别是一个Treap，和一般的二叉搜索树不同的是，
Treap纪录一个额外的数据，就是优先级。Treap在以关键码构成二叉搜索树的同时，还满足堆的性质。
这些优先级是是在结点插入时，随机赋予的，Treap根据这些优先级满足堆的性质。这样的话，Treap是有一个随机附加域满足堆的性质的二叉搜索树，其结构
相当于以随机数据插入的二叉搜索树。其基本操作的期望时间复杂度为O(logn)。相对于其他的平衡二叉搜索树，Treap的特点是实现简单，且能基本实现随机平衡的结构。

Treap维护堆性质的方法
只用到了旋转，只需要两种旋转，编程复杂度比Splay要小一些。

插入 

给节点随机分配一个优先级，先和二叉搜索树的插入一样，先把要插入的点插入到一个叶子上，然后
跟维护堆一样，如果当前节点的优先级比根大就旋转，如果
当前节点是根的左儿子就右旋，如果当前节点是根的右儿子就左旋。

下面图解旋转操作：

由于旋转是O(1)的，最多进行h次（h是树的高度），插入的复杂度是O(h)的，在期望情况下h=O(logn)，所以它的期望复杂度是O(logn)。 

 

下面我们以一个
实例来图解Treap的插入过程，看完之后你一定对Treap的插入了然于胸。

删除

删除一个节点有两种方式，可以像删除二叉树节点那样删除一个节点，也可以像删除堆中节点那样删除。

1、用二叉搜索树的方式删除

先在二叉查找树中找到要删除的节点的位置,然后根据节点分以下情况:


情况一:
该节点是
叶节点(没有非空子节 点的节点),直接把节点删除即可。

情况二：

该节点是
链节点(只有一个非空子节点的节点),为了删除这个节点而不影响它的子树,需要把它的子节点代替它的位置,然后把它删除。

关于查找最小值：
基本方法就是从子树的根节点开始, 如果左子节点不为空,那么就访问左子节点,直到左子节点为空,当前节点就是该子树的最 小值节点。删除它只需用它的右子节点代替它本身。

2、用堆的方式删除

因为Treap满足堆性质，所以只需要把要删除的节点旋转到叶节点上，然后直接删除就可以了。
具体的方法：
如果该节点的左子节点的优先级小于右子节点的优先级，右旋该节点,使该节点降为右子树的根节点，然后访问右子树的根节点,继续操作；

反之，左旋该节点,使该节点降为左子树的根节点，然后访问左子树的根节点，继续操作，直到变成可以直接删除的节点。
（即：让小优先级的结点旋到上面，满足堆的性质）

删除最多进行O(h)次旋转，期望复杂度是O(logn)。

查找

和一般的二叉搜索树一样，但是由于Treap的随机化结构，Treap中查找的期望复杂度是O(logn)。 

对比 

与 Splay树 相比:

Splay 和 BST 一样,不需要维护任何附加域,比 Treap 在空间上有节约。但 Splay 在查找时也会调整结构,这使得 Splay 灵活性稍有欠缺。
Splay 的查找插入删除等基本操作的时间复杂度为均摊O(logN)而非期望。可以故意构造出使 Splay 变得很慢的数据。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<queue>
#include<vector>
#include<climits>
#include<string>
#include<cstdlib>
#include<set>
#include<stack>
#include<map>
#include<bitset>
#include<ctime>
using namespace std;
typedef int ll;
typedef unsigned long long ull;
inline ll read()
{
    char k=0;char ls;ls=getchar();for(;ls<'0'||ls>'9';k=ls,ls=getchar());
    ll x=0;for(;ls>='0'&&ls<='9';ls=getchar())x=x*10+ls-'0';
    if(k=='-')x=0-x;return x;
}
struct E{
    ll lc,rc;//左右孩子
    ll s,sum;//权值和随机数
    ll fa;//父亲
    ll size;//子节点大小
    ll js;//该节点元素计数
}t[1000050];
ll w;
ll size;
ll root;

inline ll find(ll s)//查找
{
    if(size==0)
        return 0;
    ll now=root;
    while(now)
    {
        if(t[now].s==s)
            return now;
        if(s<t[now].s)
        {
            now=t[now].lc;
            continue;
        }
        if(s>t[now].s)
        {
            now=t[now].rc;
            continue;
        }
    }
    return 0;
}

ll maxn()//最大值
{
    ll now=root;
    while(1)
    {
        if(t[now].rc==0)
            return now;
        now=t[now].rc;
    }
}

ll minn()//最小值
{
    ll now=root;
    while(1)
    {
        if(t[now].lc==0)
            return now;
        now=t[now].lc;
    }
}

void update(ll x)//更新平衡树尺寸
{
    ll now=root;
    while(1)
    {
        --t[now].size;
        if(now==x)return;
        if(t[x].s<t[now].s)
        {
            now=t[now].lc;
            continue;
        }
        if(t[x].s>t[now].s)
        {
            now=t[now].rc;
            continue;
        }
    }
    return;
}

void zig(ll x)//左旋
{
    t[t[x].fa].size-=t[t[x].rc].size;
    t[t[x].fa].size-=t[x].js;
    t[x].size+=t[t[t[x].fa].lc].size;
    t[x].size+=t[t[x].fa].js;
    if(root==t[x].fa)
        root=x;
    ll ff=t[t[x].fa].fa;
    t[t[x].fa].fa=x;
    if(ff!=0)
    {
        if(t[ff].lc==t[x].fa)
            t[ff].lc=x;
        if(t[ff].rc==t[x].fa)
            t[ff].rc=x;
    }
    if(t[x].lc!=0)
        t[t[x].lc].fa=t[x].fa;
    t[t[x].fa].rc=t[x].lc;
    t[x].lc=t[x].fa;
    t[x].fa=ff;
    return;
}

void zag(ll x)//右旋
{
    t[t[x].fa].size-=t[t[x].lc].size;
    t[t[x].fa].size-=t[x].js;
    t[x].size+=t[t[t[x].fa].rc].size;
    t[x].size+=t[t[x].fa].js;
    if(root==t[x].fa)
        root=x;
    ll ff=t[t[x].fa].fa;
    t[t[x].fa].fa=x;
    if(ff!=0)
    {
        if(t[ff].lc==t[x].fa)
            t[ff].lc=x;
        if(t[ff].rc==t[x].fa)
            t[ff].rc=x;
    }
    if(t[x].rc!=0)
        t[t[x].rc].fa=t[x].fa;
    t[t[x].fa].lc=t[x].rc;
    t[x].rc=t[x].fa;
    t[x].fa=ff;
    return;
}

void strike_off(ll x)//删除指定下标
{
    while(t[x].lc!=0||t[x].rc!=0)
    {
        if(t[x].lc!=0&&t[x].rc==0)
        {zag(t[x].lc);continue;}
        
        if(t[x].rc!=0&&t[x].lc==0)
        {zig(t[x].rc);continue;}
        
        if(t[x].lc!=0&&t[x].rc!=0)
        {
            if(t[t[x].lc].sum<t[t[x].rc].sum)
                zag(t[x].lc);
            else
                zig(t[x].rc);
        }
    }
    update(x);
    if(t[x].fa!=0)
    {
        if(t[t[x].fa].lc==x)
            t[t[x].fa].lc=0;
        if(t[t[x].fa].rc==x)
            t[t[x].fa].rc=0;
    }
    --size;
    if(size==0)
        root=0;
    return;
}

void delete_(ll s)//删除指定数字
{
    ll x=find(s);
    if(x==0)
        return;
    if(t[x].js>1)
    {
        --t[x].js;
        --size;
        update(x);
        return;
    }
    else
        strike_off(x);
    return;
}

void insert(ll s)//插入
{
    ++size;
    t[++w].s=s;
    t[w].sum=rand()%1000050;
    t[w].size=1;
    t[w].js=1;
    if(size==1)
    {
        root=w;
        return;
    }
    ll pre=root;
    ll now=root;
    while(now!=0)
    {
        if(s==t[now].s)
        {
            ++t[now].size;
            ++t[now].js;
            --w;
            return;
        }
        if(s<t[now].s)
        {
            ++t[now].size;
            pre=now;
            now=t[now].lc;
            continue;
        }
        if(s>t[now].s)
        {
            ++t[now].size;
            pre=now;
            now=t[now].rc;
            continue;
        }
    }
    if(s<t[pre].s)
        t[pre].lc=w;
    if(s>t[pre].s)
        t[pre].rc=w;
    t[w].fa=pre;
    
    while(t[w].sum<t[t[w].fa].sum)
    {
        if(t[t[w].fa].lc==w)
        {
            zag(w);
            continue;
        }
        if(t[t[w].fa].rc==w)
        {
            zig(w);
            continue;
        }
    }
    return;
}

int main()
{
    srand(19981017);
    return 0;
}

Jetbrains全家桶1年46，售后保障稳定