模板四十天之笛卡尔树

左手的ㄟ右手 2021-12-01 11:24 263阅读 0赞

笛卡尔树：

简介

Cartesian Tree 是一种二叉树，每个节点具有两个值 key 和 value。

*  只看key的话，笛卡尔树是一棵二叉搜索树
 *  只看value的话，笛卡尔树是堆（但不一定是完全二叉树）

笛卡尔树用二元组来构造树，利用树的构造过程和构造好的树来解决问题。

构造

下面我们以大根堆为例。利用栈可以实现线性时间构造笛卡尔树。

*  将节点按照key升序排列，依次插入笛卡尔树，每次插入的是当前的最大值，应该在最右链路上查找
 *  为了满足大根堆的性质，val值沿右链是递减的，所以可以把最右侧的链路存入栈中，栈底是根，栈顶是最新节点，从底到顶key递增，val递减
 *  每次插入一个节点时，从顶往底逐个查看，找到第一个val值大于新节点val的节点，那么它就是新节点的父节点，而之前的这些节点，会成为新节点的左子树
 *  由于每个节点最多进栈一次、出栈一次，所以是O(n)的
 *      #include <iostream>
        #include <cstring>
        #include <algorithm>
        using namespace std;
        
        const int MAXN = 1000;
        
        typedef struct node{
            int id;
            int key, val;
            int f, l, r;
        
            bool operator < (node t) const
            {
                return key < t.key;
            }
        } node;
        
        node T[MAXN];
        int stack[MAXN], top;
        
        int create(int n)
        {
            top = 1;
            stack[top] = 1;
            for(int i = 2; i <= n; i++)
            {
                while(top > 0 && T[i].val > T[stack[top]].val) //小根堆则改成小于
                    top --;
                if(top > 0) // 右链中的节点
                {
                    T[i].f = stack[top];
                    T[i].l = T[stack[top]].r;
                    T[T[stack[top]].r].f = i;
                    T[stack[top]].r = i;
                    stack[++top] = i;
                }
                else // 根节点
                {
                    T[stack[1]].f = i;
                    T[i].l = stack[1];
                    stack[++top] = i;
                }
            }
        
            return stack[1];
        }
        
        void show(int i)
        {
            cout << "id: " << T[i].id << " key: " << T[i].key
                 << " val: " << T[i].val << " fa: " << T[T[i].f].key
                 << " l: " << T[T[i].l].key << " r: " << T[T[i].r].key << endl;
        
            if(T[i].l)
            {
                show(T[i].l);
            }
        
            if(T[i].r)
            {
                show(T[i].r);
            }
        }
        
        int main()
        {
            int n;
            scanf("%d", &n);
            memset(T, 0, sizeof(T));
        
            for(int i = 1; i <= n; i++)
            {
                scanf("%d %d", &T[i].key, &T[i].val);
                T[i].id = i;
            }
            
            sort(T + 1, T + n + 1);
            int root = create(n);
            
            show(root);
        
            return 0;
        }
    
    简单模板：
 *      #include<bits/stdc++.h>
        using namespace std; 
        const int N=1e5+10;
        int n,v[N],fa[N],ls[N],rs[N];
        int s[N],top;
        void Tree() 
        {
            for(int i = 1; i <= n; i ++)//从前向后插入 
        	{
                scanf("%d",&v[i]);
                while(top && v[s[top]] > v[i])
                	ls[i] = s[top], top --;//一直向右走，原来的点成为这个点的左子树 
                fa[i] = s[top]; //找到第一个符合 
        		fa[ls[i]] = i; //左子树的父亲也是这个i 
                if(fa[i]) rs[fa[i]] = i;//如果是根节点，那么右子树的根节点也是 
                s[++ top] = i;
            }
        }
        
        小根堆 
        找到第一个权值小于等于自己 ，让这个点成为自己的，原来的点成为这个点的左子树
        top--,左子树的原来父亲就是这个点的父亲
        左子树现在的父亲是自己
        如果左子树原来父亲不为空，原来父亲的右子树使自己 
        入栈 
        
        
        
        
        
        
        
        int create(int n){//按照key的升序
            top = 1; 
            stack[top] = 1; 
            for(int i = 2; i <= n; i++) 
            {
                while(top > 0 && T[i].val < T[stack[top]].val) top --; //找到 第一个比自己小的节点 
                if(top > 0)
                {
                    T[i].f = stack[top];//第一个比自己小的点是父亲 
                    T[i].l = T[stack[top]].r;//父亲的右孩子成为自己的左孩子 
                    T[T[stack[top]].r].f = i;//左孩子的父亲是目前点 
                    T[stack[top]].r = i;// 目前点是父亲的右子树 
                    stack[++top] = i;//入队 
                }
                else 
                {
                    T[stack[1]].f = i;//如果是根节点，那么父亲节点使自己 
                    T[i].l = stack[1];//左孩子也是自己 
                    stack[++top] = i;//入队 
                }
            }
        	return stack[1];
        }
        int create(){
        	top=1;
        	s[top]=1;
        	for(int i=2;i<=n;i++){
        		while(top&&t[s[top]].val>t[i].val)top--;
        		if(top){
        			t[i].f=s[top];
        			t[i].l=t[s[top]].r;
        			t[t[s[top]].r].f=i;
        			t[s[top]].r=i;
        			s[++top]=i;
        		}else{
        			t[s[1]].f=i;
        			t[i].l=s[1];
        			s[++top]=i;			
        		}
        	}
        	return s[1];
        } //建立笛卡尔树之后排序。
    
    模板题目：poj2201
 *      #include<iostream>
        #include<algorithm>
        #include<cstdio>
        #include<cstring>
        using namespace std;
        const int M=51000+50;
        struct Nde{int key,val,id,f,l,r;}t[M];
        struct Node{int f,l,r;}res[M];
        bool cmp(Nde a,Nde b){return a.key<b.key;}
        int n,s[M],top;
        int create(){
        	top=1;
        	s[top]=1;
        	for(int i=2;i<=n;i++){
        		while(top&&t[i].val<t[s[top]].val)top--;
        		if(top){
        			t[i].f=s[top];
        			t[i].l=t[s[top]].r;
        			t[t[s[top]].r].f=i;
        			t[s[top]].r=i;
        		}else{
        			t[s[1]].f=i;
        			t[i].l=s[1];
        		}
        		s[++top]=i;
        	} 
        	return s[1];
        } 
        void dfs(int x,int fa){
        	if(!x)return ;
        	res[t[x].id].f=t[fa].id;
        	res[t[x].id].l=t[t[x].l].id;
        	res[t[x].id].r=t[t[x].r].id;
        	dfs(t[x].l,x);
        	dfs(t[x].r,x);
        }
        int main(){
        	while(scanf("%d",&n)!=EOF){
        		memset(t,0,sizeof(t));
        		memset(res,0,sizeof(res));
        		for(int i=1;i<=n;i++)scanf("%d%d",&t[i].key,&t[i].val),t[i].id=i;
        		sort(t+1,t+n+1,cmp);
        		int root=create();
        		dfs(root,0);
        		printf("YES\n");
        		for(int i=1;i<=n;i++)printf("%d %d %d\n",res[i].f,res[i].l,res[i].r);
        	}
        	return 0;
        }