洛谷 P1377 [TJOI2011]树的序 暴力数据结构做法 题解【树的遍历】【splay】

作者: wjyyy 分类: splay,数据结构,,解题报告 发布时间: 2018-06-19 21:20

点击量:21

 

   这个题正解不是平衡树,不过可以拿平衡树优化一下常数,\(O(NlogN)\)就能过了。

 

题目描述

众所周知,二叉查找树的形态和键值的插入顺序密切相关。准确的讲:1、空树中加入一个键值k,则变为只有一个结点的二叉查找树,此结点的键值即为k;2、在非空树中插入一个键值k,若k小于其根的键值,则在其左子树中插入k,否则在其右子树中插入k。

我们将一棵二叉查找树的键值插入序列称为树的生成序列,现给出一个生成序列,求与其生成同样二叉查找树的所有生成序列中字典序最小的那个,其中,字典序关系是指对两个长度同为n的生成序列,先比较第一个插入键值,再比较第二个,依此类推。

输入输出格式

输入格式:

第一行,一个整数,n,表示二叉查找树的结点个数。第二行,有n个正整数,k1到kn,表示生成序列,简单起见,k1~kn为一个1到n的排列。

 

输出格式:

一行,n个正整数,为能够生成同样二叉查找树的所有生成序列中最小的。

输入输出样例

输入样例#1:
4
1 3 4 2
输出样例#1:
1 3 2 4

说明

对于20%的数据,n ≤ 10。

 

对于50%的数据,n ≤ 100。

 

对于100%的数据,n ≤ 100,000。

 

   这个题正解是\(O(N)\)桶排,或者\(O(NlogN)\)的快排后拿笛卡尔树\(O(N)\)建树,综合复杂度\(O(NlogN)\)。

 

   而平衡树套用了BST的一种性质,就是某数在插入前(第一个数跳过),要么它的前驱和后继的深度是不同的,要么它没有前驱(此时前驱深度定为0),要么它没有后继(此时后继深度定为0);这时候它一定会被插入为较深的那一个的孩子(下面给出证明)。因此我们只需要存每个点的节点地址,就可以用平衡树求出前驱和后继从而直接访问较深节点并插入。

 

    上述命题证明:如果遍历过程两个节点都要经过(即在根节点的同侧),那么会去到较深的点。因为经过较浅的那个节点时,那个节点会把它继续向下插入,直到找到较深的另一个点,这是BST的插入性质。如果遍历过程不同时经过这两个点(前驱和后继),则不会出现分属两树的情况,因为此时的根节点比前驱大,比后继小,那么前驱和后继求的就是不合法的,因此不会出现这种情况。原命题得证。

 

   伸展树在这里会用到的功能不算多,所以敲起来比较方便也比较迅速。因此在想不到正解而splay可做时,就最好先打个splay上去咯。(说不定平衡树是正解啊蛤蛤蛤

 

Code:

#include<cstdio>
#include<cstring>
#define Root spl::root
#define RooT BST::root
int dpt[101000];//深度
namespace spl//开两个namespace可以用两个node(起名综合症)
{
struct node
{
    int key;
    node *s[2];
    node(int key)
    {
        this->key=key;
        s[0]=NULL;
        s[1]=NULL;
    }
    node()
    {
        s[0]=NULL;
        s[1]=NULL;
    }
    int getd(int x)
    {
        if(x==key)
            return -1;
        return x>key;
    }
};
node *root=NULL;
void Rotate(node *&rt,int d)
{
    node *tmp=rt->s[d];
    rt->s[d]=tmp->s[d^1];
    tmp->s[d^1]=rt;
    rt=tmp;
    return;
}
void splay(node *&rt,int x)
{
    int d1=rt->getd(x);
    if(d1==-1)
        return;
    int d2=rt->s[d1]->getd(x);
    if(d2==-1)
    {
        Rotate(rt,d1);
        return;
    }
    splay(rt->s[d1]->s[d2],x);
    if(d1==d2)
    {
        Rotate(rt,d1);
        Rotate(rt,d1);
        return;
    }
    else
    {
        Rotate(rt->s[d1],d2);
        Rotate(rt,d1);
        return;
    }
}
void Insert(node *&rt,int x)
{
    if(!rt)
    {
        rt=new node(x);
        return;
    }
    Insert(rt->s[rt->getd(x)],x);//没有重复元素
    return;
}
//也没有删除
int getm(node *rt,int d)
{
    if(!rt->s[d])
        return rt->key;
    return getm(rt->s[d],d);
}
}
namespace BST
{
struct node
{
    int v;
    node *ls,*rs;
    node(int v)
    {
        this->v=v;
        ls=NULL;
        rs=NULL;
    }
    node()
    {
        ls=NULL;
        rs=NULL;
    }
}*root=NULL;
node *pla[101000];//存这个节点的指针地址
void Insert(node *&rt,int x,int d)//记得计算深度
{
    if(!rt)
    {
        dpt[x]=d;
        rt=new node(x);
        pla[x]=rt;
        return;
    }
    if(x<rt->v)
        Insert(rt->ls,x,d+1);
    else
        Insert(rt->rs,x,d+1);
    return;
}
void pre_ord(node *rt)
{
    printf("%d ",rt->v);
    if(rt->ls)
        pre_ord(rt->ls);
    if(rt->rs)
        pre_ord(rt->rs);
}
}
using BST::pla;

int main()
{
    memset(dpt,0,sizeof(dpt));
    memset(pla,NULL,sizeof(pla));
    int n,a;
    scanf("%d",&n);
    scanf("%d",&a);
    spl::Insert(Root,a);//第一个是构造根节点要特判
    BST::Insert(RooT,a,1);

    int p,s;//p是pre前驱,s是suc后继
    for(int i=2;i<=n;i++)
    {
        scanf("%d",&a);
        spl::Insert(Root,a);
        spl::splay(Root,a);
        p=0;//这里注意置0,否则下面用到s和p就会GG(紊乱)
        s=0;
        if(Root->s[0])
            p=getm(Root->s[0],1);
        if(Root->s[1])
            s=getm(Root->s[1],0);
        if(dpt[p]>dpt[s])
            BST::Insert(pla[p],a,1);
        else
            BST::Insert(pla[s],a,1);
    }
    BST::pre_ord(RooT);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */