定义
所谓笛卡尔树,就是将给定的个二元组建成一棵树。使得如果只关注,那么这是一个堆。如果只关注,那么这是一棵二叉搜索树。
有没有很像。
与不同的是,笛卡尔树是可以在时间内构建的。而且如果给定key,那么是可以被卡成一条链的。
构造
以小根堆为例。
借助栈来完成。先按照val从小到大排序。然后用栈维护出最右边的一条链。即
显然,这条链上的val是自上到下递增的。key也是自上到下递增的。
因为已经按照val排好序了,所以当我们往这棵树里插入点的时候,权值一定是当前最大的了。所以插入的这个点要么是最右下的一个点,要么就是根并且其他所有的点都在左子树上。
然后考虑,只要沿着最右边这条链自下而上找到第一个小于当前点的点。将当前点变为他的右儿子,并且将这个点原来的右儿子变为当前点的右儿子。
如图(标号表示key),现在要往里面插入一个6。最右边的链中,从下往上找到第一个比6小的点为5。然后将5的右子树变为6的左子树。6变为5的右儿子。变成这样。
如果所有点的key都比要插入的点小的话,那就直接把整棵树变为插入点的左子树就行了。
代码
<a href="http://poj.org/problem?id=2201">Poj2201</a>
/* * @Author: wxyww * @Date: 2019-06-05 15:06:45 * @Last Modified time: 2019-06-05 20:14:23 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> using namespace std; typedef long long ll; const int N = 100000 + 100; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } struct node { int id,key,val,ls,rs,pre; }TR[N]; int top,sta[N]; bool cmp(node A,node B) { return A.val < B.val; } bool cmp2(node A,node B) { return A.id < B.id; } int main() { // freopen("a.txt","r",stdin); // int n; // while(~scanf("%d",&n)) { int n = read(); for(int i = 1;i <= n;++i) { TR[i].id = i;TR[i].val = read();TR[i].key = read(); TR[i].pre = TR[i].ls = TR[i].rs = 0; } sort(TR + 1,TR + n + 1,cmp); top = 0;memset(sta,0,sizeof(sta)); // sta[++top] = 1; for(int i = 1;i <= n;++i) { int k = top; while(top && TR[i].key < TR[sta[top]].key) --top; if(top) { TR[i].pre = sta[top]; TR[TR[sta[top]].rs].pre = i; TR[i].ls = TR[sta[top]].rs; TR[sta[top]].rs = i; } else { TR[sta[1]].pre = i; TR[i].ls = sta[1]; } sta[++top] = i; } for(int i = 1;i <= n;++i) TR[i].ls = TR[TR[i].ls].id,TR[i].rs = TR[TR[i].rs].id,TR[i].pre = TR[TR[i].pre].id; sort(TR + 1,TR + n + 1,cmp2); puts("YES"); for(int i = 1;i <= n;++i) printf("%d %d %d\n",TR[i].pre,TR[i].ls,TR[i].rs); // } return 0; }