柒葉灬 的博客

柒葉灬 的博客

笛卡尔树构建

posted on 2019-09-18 15:14:25 | under 算法学习 |

笛卡尔树


笛卡尔树是个二叉树:

满足以下性质:

  1. 是一个堆
  2. 中序遍历是原序列

构建复杂度: $O(n)$

构建步骤:

  1. 维护一个最右边的路径(从根开始一直走右儿子)

  2. 插入的时候寻找第一个能成为当前节点父亲的节点

  3. (1) 如果有这个节点,那么把它的右儿子作为当前节点的左儿子,当前节点成为它的新右儿子

    (2)如果没有,说明当前点是根,那么就把原来的根作为自己的做儿子即可

  4. 将当前点塞入栈中

代码:

struct node{
    int ls,rs,x;
    bool operator <(const node &_)const{
        return x<_.x;
    }
}A[maxn];
for(int i=1;i<=n;i++){
    while(top&&A[i]<A[stk[top]])top--;//找一个满足要求的
    if(!top)A[i].ls=stk[1];//原来的根
    else {
        A[i].ls=A[stk[top]].rs;
        A[stk[top]].rs=i;
    }
    stk[++top]=i;
}

我并不知道笛卡尔树记录父亲的意义何在,

所以就没有记节点的父亲了。

模板题:noip2018d1t1铺设道路 , noip2013积木大赛