笛卡尔树的线性构建方法及其正确性

╰半橙微兮° 2023-08-17 17:47 79阅读 0赞

前排提醒：本文所有代码都可以当做伪代码看，因为我懒得编译。

## 从https://courses.csail.mit.edu/6.851/spring12/lectures/里找到的技术。 ##

笛卡尔树，可用来查询一维区间最小值（目前我只会这个也只知道这个），方法是求标号为区间左端点及区间右端点的最近公共祖先，它的值即所求。

笛卡尔树以序列为基础建立，满足堆性质（update on 2019.7.13），但有一点，它的节点之间的父子关系并不和它的节点标号有直接关系，且将此树前序遍历可得到原序列。

--------------------

较好理解的\\(nlogn\\)接近\\(n^2\\)的建立方法

过程看代码啦

int build_tree(int l,int r) //在l-r这个区间建立一颗笛卡尔树，返回根节点的标号 { if(l>r) return 0;//数组存储树的父子关系，0即NULL if(l==r) return l; int p=l,Min_val=a[p]; //p记录区间最小值在原序列的下标，Min_val记录最小值, a数组存储原序列 for(int i=l+1;i<=r;++i) if(a[i]<Min_val) p=i,Min_val=a[i]; lc[p]=build_tree(l,p-1);//lc[i]:标号为i的节点的左子树根节点的标号 rc[p]=build_tree(p+1,r);//rc[i]:标号为i的节点的右子树根节点的标号 return p; } int root=build(1,n);//n是序列长度

--------------------

线性建立方法，复杂度不会证明，原文没有给出，但可以证明是和上面的超慢做法有一样的效果。（即满足小顶堆性质和前序遍历得到原序列性质）

描述：若想在一段序列建立笛卡尔树，从序列的左端点到序列的右端点遍历，每遍历到一个元素，将此元素从树的最右端点(原文译为右脊，我理解为此前最后插入的元素所在节点)开始插入，如果当前关注的节点的数值比要插入的节点的数值大，则将关注点放在当前关注节点的父节点上，否则将关注点的右儿子变成插入点的左儿子，插入点则变成关注点的右儿子。(当然，若根节点也比此元素大，那么之前的整棵树都是这个元素的左子树了。）

描述结束，约好的证明如下：

1.首先，当序列长度为1时，性质们显然是成立的。

2.接着，若此时遍历到序列的第\\(k(1<k \\leq n，n为序列长度)\\)个元素，前\\(k-1\\)个元素所形成的树满足性质们。

那么将第\\(k\\)个元素按照上述建立方法插入时，假定将关注点放到第\\(d\\)个元素时，\\(val(d)<=val(k)\\)，

那么\\(d\\)的右子树\\(R\\)就成为了\\(k\\)的左子树，\\(k\\)成为\\(d\\)的新的右子树。

\\(R\\)在插入\\(k\\)之前的意义是"\\(d+1到k-1\\)的所有元素"，

故将\\(R\\)变成\\(k\\)的左子树时，在中序遍历下，\\(1到d\\)会被照常遍历，作为\\(k\\)的左子树，\\(R\\)，即"\\(d+1到k-1\\)的所有元素"

会在元素\\(1到d\\)按顺序遍历之后，\\(k\\)被遍历之前，按顺序被遍历。

那么插入过程中是否也保持了笛卡尔树小根堆的性质呢？答案是肯定的，

因为子树\\(R\\)比节点\\(k\\)大，节点\\(k\\)比节点\\(d\\)小，而插入过程中被改变父子关系的节点也就仅有它们三个而已。

到此，解释完毕，关于构建的详细方法可以参考一下我的代码：

int Right_node=0,root,a[],fa[],lc[],rc[]; //a数组储存原序列，其余见名知意 Right_node=root=1; //初始化为序列的第一个元素，从第二个元素开始插入 void insert_tree(int k)//k是待插入序列元素的标号 { int now=Right_node;//初始化关注节点 // while(a[now]>a[k]&&now)//爬升过程 { now=fa[now]; } // if(now==0) lc[k]=root,root=k;//k节点设为根节点 else lc[k]=rc[now],rc[now]=k;//在树中插入k // Right_node=k;//更新，便于下次插入。 return; }

完结撒花，写了一小时了，累死qwq

转载于:https://www.cnblogs.com/tztqwq/p/11172517.html