前言:

今天想把之前写的无旋heap讲一下。。。

平衡树是计算机科学中的一类改进的二叉查找树。一般的二叉查找树的查询复杂度是跟目标结点到树根的距离(即深度)有关,因此当结点的深度普遍较大时,查询的均摊复杂度会上升,为了更高效的查询,平衡树应运而生了。它可以利用随机化来保证树的平衡,就是左右子树大小差不多,在查询时可以优化复杂度。。。

比如来看落谷这道普通平衡树的模板题:

您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:

  • 插入 x 数
  • 删除 x 数(若有多个相同的数,因只删除一个)
  • 查询 x 数的排名(排名定义为比当前数小的数的个数 +1+1+1 。若有多个相同的数,因输出最小的排名)
  • 查询排名为 x 的数
  • 求 x 的前驱(前驱定义为小于 x ,且最大的数)
  • 求 x 的后继(后继定义为大于 x ,且最小的数)

时空限制:1000ms,128M

1.n的数据范围: n≤100000

2.每个数的数据范围:[-1000000,10000000]

看起来是不是很简单…..

一看这道题就是数据结构,又正好满足我们平衡树的要求。。。那我们开始讲平衡树。。。

首先我们定义这课树

struct Node
{
    int key,p,size;
    Node *ch[2];
}*root;

key用来存当前点的值,p用来存随机树,size顾名思义存树的大小,而ch则是存儿子(这是一棵二叉树,所以只有两个儿子)。。。

由于我用的是指针,所以我们还要写一个申请指针空间,以及初始化的函数。。。如下。。。

Node *new_node(int x)
{
    Node *y=new Node;
    y->key=x;y->p=rand();
    y->ch[0]=y->ch[1]=NULL;
    y->size=1;
    return y;
}

当然还有我们询问指针对应的值了,为了防止re我又写了两个函数(别问我为什么这么烦,用什么指针,因为是学长教的。。。)

inline int key_of(Node *x)
{
    if(x==NULL)
        return 0;
    else
        return x->key;
}
inline int size_of(Node *x)
{
    if(x==NULL)
        return 0;
    else
        return x->size;
}

然后就到了我们平衡树的关键操作了,他叫merge(表合并),用处是把两棵树合在一起,由于平衡树的中序遍历是原来的串,所以这个merge怎么写就令人深思了,显然我们传入两棵树的根指针,如果其中有一棵树是空的明显可以返回另一颗,如果两棵都不为空,那么我们比较随机化的p值,p在这里的作用就是选择当父亲的树根,我们假设p大的A当父亲,那么我们就把另一棵树B连到当前树A上,然后A树的儿子和树B。。。最后返回树的根,由于指针的作用,就是返回了合并好的树。。。

Node *merge(Node *x,Node *y)
{
    if(x==NULL)
        return y;
    if(y==NULL)
        return x;
    if(x->pp)
    {
        x->ch[1]=merge(x->ch[1],y);
        update(x);
        return x;
    }
    else
    {
        y->ch[0]=merge(x,y->ch[0]);
        update(y);
        return y;
    }
}

然后聪明的你是不是发现了,merge函数里还有一个函数没有定义,叫update,他的作用是更新父亲节点的值。。。在这个题目中他只要更新size就好了,在其他题目中还可以用来更新什么sum之类的值。。。所以很短。。。

inline void update(Node *x)
{
    x->size=size_of(x->ch[0])+size_of(x->ch[1])+1;
}

然后又到了一个关键函数,叫split,他的作用是把一棵树分裂成两棵,由于题目原因,我们既要可以按key值分裂,也可以按照位置分裂,他的过程有点向merge的逆过程。。。比如按照key值分裂,若左儿子的值小于询问,那么我们就去查找右儿子,然后递归下去,由于指针指向地址,我们做的操作可以连接上去打起来也很简单。。。

void split_k(Node *now,Node *&x,Node *&y,int k)
{
    if(now==NULL)
    {
        x=NULL,y=NULL;
        return;
    }
    if(size_of(now->ch[0])+1ch[1],now->ch[1],y,k-size_of(now->ch[0])-1);
    }
    else
    {
        y=now;
        split_k(now->ch[0],x,now->ch[0],k);
    }
    update(now);
}
void split_key(Node *now,Node *&x,Node *&y,int key)
{
    if(now==NULL)
    {
        x=NULL,y=NULL;
        return;
    }
    if(key_of(now)ch[1],now->ch[1],y,key);
    }
    else
    {
        y=now;
        split_key(now->ch[0],x,now->ch[0],key);
    }
    update(now);
}

主要的函数都打完了,下面就开始打各类操作了,因为太简单我就举个例子。。。

比如你要合并两棵树:

root=merge(x,y)//x,y都要是一棵定义过得树

比如你以k值要分裂一颗树:

split_key(root,x,y,k);//这里的x,y与上面的同理。。。

然后就讲完了。。。现在贴一个全代码:

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=1e7+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
namespace FastIO 
{
    template inline void read(tp &x) 
    {
        x=0; register char c=getchar(); register bool f=0;
        for(;c'9';f|=(c=='-'),c = getchar());
        for(;c>='0'&&c<='9';x=(x<<3)+(x<p=rand();
        y->ch[0]=y->ch[1]=NULL;
        y->size=1;
        return y;
    }
    inline int key_of(Node *x)
    {
        if(x==NULL)
            return 0;
        else
            return x->key;
    }
    inline int size_of(Node *x)
    {
        if(x==NULL)
            return 0;
        else
            return x->size;
    }
    inline void update(Node *x)
    {
        x->size=size_of(x->ch[0])+size_of(x->ch[1])+1;
    }
    Node *merge(Node *x,Node *y)
    {
        if(x==NULL)
            return y;
        if(y==NULL)
            return x;
        if(x->pp)
        {
            x->ch[1]=merge(x->ch[1],y);
            update(x);
            return x;
        }
        else
        {
            y->ch[0]=merge(x,y->ch[0]);
            update(y);
            return y;
        }
    }
    void split_k(Node *now,Node *&x,Node *&y,int k)
    {
        if(now==NULL)
        {
            x=NULL,y=NULL;
            return;
        }
        if(size_of(now->ch[0])+1ch[1],now->ch[1],y,k-size_of(now->ch[0])-1);
        }
        else
        {
            y=now;
            split_k(now->ch[0],x,now->ch[0],k);
        }
        update(now);
    }
    void split_key(Node *now,Node *&x,Node *&y,int key)
    {
        if(now==NULL)
        {
            x=NULL,y=NULL;
            return;
        }
        if(key_of(now)ch[1],now->ch[1],y,key);
        }
        else
        {
            y=now;
            split_key(now->ch[0],x,now->ch[0],key);
        }
        update(now);
    }
    Node *x,*y,*z,*w,*q,*p;
}
using namespace Treap;
int T;
int main() 
{
    scanf("%d",&T);
    for(int i=1;i<=T;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        switch(l)
        {
            case 1:
                split_key(root,x,y,r);
                x=merge(x,new_node(r));
                root=merge(x,y);
                break;
            case 2:
                split_key(root,x,y,r);
                split_key(x,z,w,r-1);
                split_k(w,q,p,1);delete q;
                z=merge(z,p);
                root=merge(z,y);
                break;
            case 3:
                split_key(root,x,y,r-1);
                printf("%d\n",size_of(x)+1);
                root=merge(x,y);
                break;
            case 4:
                split_k(root,x,y,r);
                split_k(x,z,w,r-1);
                printf("%d\n",key_of(w));
                x=merge(z,w);
                root=merge(x,y);
                break;
            case 5:
                split_key(root,x,y,r-1);
                split_k(x,z,w,size_of(x)-1);
                printf("%d\n",key_of(w));
                x=merge(z,w);
                root=merge(x,y);
                break;
            case 6:
                split_key(root,x,y,r);
                split_k(y,z,w,1);
                printf("%d\n",key_of(z));
                y=merge(z,w);
                root=merge(x,y);
                break;
        }
    }
    return 0;
}

哈哈哈,讲完了,你可以点关注了。。。
溜了溜了。。。

Leave A Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注