洛谷 P1377 [TJOI2011]树的序 正解 题解【笛卡尔树】【二叉树】【栈】

作者: wjyyy 分类: ,,,笛卡尔树,解题报告 发布时间: 2018-06-25 19:19

点击量:19

 

    这个题之前写过一个暴力平衡树的题解,现在讲一讲正解。

 

题目描述

众所周知,二叉查找树的形态和键值的插入顺序密切相关。准确的讲: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^2)\)的时间复杂度,那么我们就要想办法优化它。

 

解法:

   题目的正解叫做笛卡尔树,就是保证了二叉查找树的性质(左孩子<根<右孩子),同时根据分治时堆的性质来控制树的先序遍历。有点像treap,但是给的堆性质的权值并不是随机的,它是为了保证每棵子树的根是最先被插入的,堆的关键值就是插入顺序:第几个被插入的。我们按元素大小(并不是上述堆的关键值)从小到大插入这棵树,维护这个堆。

 

正确性:

   我们对一棵二叉查找树分析,就会发现,同一条链上,越是上面的点,插入的一定就越早。那么我们按插入顺序调整二叉查找树,就不会影响先序遍历的正确性了。调整一个存储插入顺序的小根堆,如同treap,调整的复杂度为O(1)。

 

实现:

   我们在手写二叉堆时,是从最后一层的右下角插入的,我们模仿二叉堆,在最右边插入。而因为堆是只和父亲比较,所以我们维护最右边的一条链,用栈来匹配就行了。如果栈顶不符合堆的性质,出栈并记录下来,直到符合性质或栈空了。如果栈空了就说明此时要以它为根才能保证二叉堆的性质。每次只记录最后一个出栈的,因为我们是从最右边的链上来的,所以把当前点放在符合堆性质的位置,然后根据二叉查找树的性质,将最后一个出栈的元素连在当前元素左边,把当前元素进栈,这样我们就用O(1)的时间调整好了树的先序遍历。

 

(更玄学的做法可以参考树的序 解题报告 – 露迭月

 

Code:

#include<cstdio>
struct node
{
    int v;
    node *ls,*rs;
    node(int v)
    {
        this->v=v;
        ls=NULL;
        rs=NULL;
    }
    node()
    {
        ls=NULL;
        rs=NULL;
    }
};
node *root=NULL;
node *pla[101000];//每个节点的位置
void Rotate(node *&rt)//这个题只出现zag
{
    node *tmp=rt->rs;
    rt->rs=tmp->ls;
    tmp->ls=rt;
    rt=tmp;
    return;
}
int s[101000],top=0;
int num[101000];
int a[101000];
void Insert(int x)
{
    int lst=0;
    while(top&&num[s[top]]>num[x])
    {
        lst=s[top];
        top--;
    }
    node *tmp;
    if(top)
    {
        pla[s[top]]->rs=new node(x);
        tmp=pla[s[top]]->rs;
    }
    else//没有到达根
    {
        root=new node(x);
        tmp=root;
    }
    if(lst!=0)//右下角刚好符合
        tmp->ls=pla[lst];
    s[++top]=x;
    pla[x]=tmp;
}
void pre_ord(node *rt)//打出先序遍历
{
    printf("%d ",rt->v);
    if(rt->ls)
        pre_ord(rt->ls);
    if(rt->rs)
        pre_ord(rt->rs);
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        num[a[i]]=i;
    }
    root=new node(1);
    s[++top]=1;
    pla[1]=root;//建根
    for(int i=2;i<=n;i++)
        Insert(i);
    pre_ord(root);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */