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

点击量：183

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

目录

题目描述

众所周知，二叉查找树的形态和键值的插入顺序密切相关。准确的讲：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;
}