笛卡尔树

编辑:公开网互动百科 时间:2019-12-13 05:50:12
编辑 锁定
本词条缺少名片图,补充相关内容使词条更完整,还能快速升级,赶紧来编辑吧!
笛卡尔树结构由Vuillmin在解决范围搜索的几何数据结构问题时提出的,从数列中构造一棵笛卡尔树可以线性时间完成,需要采用基于栈的算法来找到在该数列中的所有最近小数。由此可知,笛卡尔树是一种特定的二叉树数据结构,可由数列构造,在范围最值查询、范围top k查询(range top k queries)等问题上有广泛应用。它具有堆的有序性,中序遍历可以输出原数列。
中文名
笛卡尔树
结    构
Vuillmin在解决范围搜索
又    称
笛卡儿树
属    于
二叉树的一种

笛卡尔树笛卡尔树简单介绍

编辑
笛卡尔树又称笛卡儿树,在数据结构中属于二叉树的一种。
可以这么说:笛卡尔树是一棵二叉树,树的每个节点有两个值,一个为key,一个为value。光看key的话,笛卡尔树是一棵二叉搜索树,每个节点的左子树的key都比它小,右子树都比它大;光看value的话,笛卡尔树有点类似堆,根节点的value是最小(或者最大)的,每个节点的value都比它的子树要小(或者大)。

笛卡尔树笛卡尔树定义

编辑
无相同元素的数列构造出的笛卡尔树具有下列性质:
1、结点一一对应于数列元素。即数列中的每个元素都对应于树中某个唯一结点,树结点也对应于数列中的某个唯一元素
2、中序遍历(in-order traverse)笛卡尔树即可得到原数列。即任意树结点的左子树结点所对应的数列元素下标比该结点所对应元素的下标小,右子树结点所对应数列元素下标比该结点所对应元素下标大。
3、树结构存在堆序性质,即任意树结点所对应数值大(或小)于其左、右子树内任意结点对应数值(即根节点为其子树的最值)
根据堆序性质,笛卡尔树根结点为数列中的最大/小值,树本身也可以通过这一性质递归地定义:根结点为序列的最大/小值,左、右子树则对应于左右两个子序列,其结点同样为两个子序列的最大/小值。因此,上述三条性质唯一地定义了笛卡尔树。若数列中存在重复值,则可用其它排序原则为数列中相同元素排定序列,例如以下标较小的数为较小,便能为含重复值的数列构造笛卡尔树。

笛卡尔树笛卡尔树的实现

编辑

笛卡尔树O(N^2)算法实现

①排序之后直接构造笛卡尔树的方法:
首先将节点序列按照key从小到大排序,然后按照顺序插入节点,注意到排序之后,插入的节点的key值一定是树中最大的,所以只需查找最右端的路径,找到一个节点A[i]的value大于待插入节点的value,同时A[i]->right的value小于待插入节点的value。找到之后,只需将A[i]的right指向待插入的节点,A[i]的right原来指向的节点赋值给待插入节点的left指针。注意到查找最右路径的方向,如果从下到上查找,复杂度比较容易分析O(N)(因为查找过的节点必然会旋转到某个节点的左子节点,因此每个查找过的节点只会被查找一次),如果从上倒下,比较复杂(和最右端的最终的路径长度有关吧),会超过N,甚至更高,可能为O(N^2)。
②利用排序加左旋的方法:
就是一样先排序,然后使用treap插入节点,可以发现,所有的旋转都为左旋。这种方法也TLE了,这种方法有一个很重要的意义,就是分析了上个方法中从上到下扫描的复杂度。因为这两种方法的效率是等价的,都TLE。

笛卡尔树O(N)算法实现

我们将要将A的元素依次插入笛卡尔树C。每次插入都可能使树的形态发生变化。为了在O(N)的时间内完成整个插入过程,考虑C的右链,即根结点、根结点的右儿子、根结点的右儿子的右儿子……组成的链。注意这些元素的下标和值都是递增的。下标最大,即将要插入的元素A[i]一定是新树右链的最后一个元素。原来的右链中,值比A[i]大的元素在新树中不再属于右链,这些元素组成的链成为A[i]的左子树的右链;原来右链中的其它元素加上A[i]组成了新的右链。初看起来,寻找分界点的最佳方法是O(logN)时间的二分查找;但是对于整个过程来说,O(NlogN)的时间复杂度不是最优的。关键在于一旦一个元素比A[i]大,它就从右链中被永久地移除了。如果按照从后到前的顺序判断一个元素是否大于A[i],则每次插入的时间复杂度为O(k+1),k为本次插入中移除的右链元素个数。因为每个元素最多进出右链各一次,所以整个过程的时间复杂度为O(N)。
用一个栈结构维护右链元素的下标,上述过程可以很容易地实现。(见下面代码部分)[1] 

笛卡尔树相关代码

编辑

笛卡尔树c++代码

#include<iostream>
#include<cstdio>
#include<string>
#include<string.h>
#include<algorithm>
using namespace std;
class treap_node
{
public:
string label;
int p;
treap_node* left;
treap_node* right;
treap_node()
{
left=NULL;
right=NULL;
}
};
class treap
{
public:
treap_node*root;
treap()
{
root=NULL;
}
void treap_left_rotate(treap_node*&a)
{
treap_node*b=a->right;
a->right=b->left;
b->left=a;
a=b;
}
void treap_right_rotate(treap_node*&a)
{
treap_node*b=a->left;
a->left=b->right;
b->right=a;
a=b;
}
void treap_insert(treap_node*&a,string label,int p)
{
if(!a)
{
a=new treap_node;
a->label=label;
a->p=p;
}
else if(label<a->label)
{
treap_insert(a->left,label,p);
if(a->left->p>a->p)
treap_right_rotate(a);
}
else
{
treap_insert(a->right,label,p);
if(a->right->p>a->p)
treap_left_rotate(a);
}
}
void plist(treap_node*a)
{
if(a!=NULL)
{
cout<<"(";
plist(a->left);
cout<<a->label<<"/"<<a->p;
plist(a->right);
cout<<")";
}
}
};
int num;
treap_node n[50001];
bool cmp(const treap_node&n1,const treap_node&n2)
{
return n1.label<n2.label;
}
void insertN(treap_node*&p)
{
for(int i=0;i<num;i++)
{
treap_node* pre=NULL;
treap_node* tmp=p;
while(tmp!=NULL&&tmp->p>n[i].p)
{
pre=tmp;
tmp=tmp->right;
}
if(pre==NULL)
{
treap_node* node=new treap_node;
node->label=n[i].label;
node->p=n[i].p;
p=node;
p->left=tmp;
}
else
{ treap_node* node=new treap_node;
node->label=n[i].label;
node->p=n[i].p;
pre->right=node;
node->left=tmp;
}
}
return;
}
int main()
{
freopen("e:\\zoj\\zoj_2243.txt","r",stdin);
while(cin>>num&&num)
{
treap* p=new treap;
getchar();
for(int i=0;i<num;i++)
{
char c[1000];
int pi;
scanf("%[^/]s",c);
scanf("/%d",&pi);
getchar();
string str;
str.append(c);
treap_node node;
node.label=str;
node.p=pi;
n[i]=node;
//p->treap_insert(p->root,str,pi);
}
sort(n,n+num,cmp);
//for(int i=0;i<num;i++)
// p->treap_insert(p->root,n[i].label,n[i].p);
insertN(p->root);
p->plist(p->root);
cout<<endl;
}
return 0;
}

笛卡尔树O(N)算法代码

void computeTree(int A[MAXN], int N, int T[MAXN])
//T[i]储存每个结点的父结点(左右子树是无所谓的)
{
int st[MAXN], i, k, top = -1;
//从空栈开始
//第i步,我们将A[i]插入栈中
for (i = 0; i < N; i++)
{
//找到第一个小于等于A[i]的元素
k = top;
while (k >= 0 && A[st[k]] > A[i]) k--;
//如上述,更改树的结构
if (k != -1) T[i] = st[k];
if (k < top) T[st[k + 1]] = i;
//将A[i]插入栈中,并移除所有更大的元素
st[++k] = i;
top = k;
}
//栈中的第一个元素就是树根,没有父节点
T[st[0]] = -1;
}

参考资料
词条标签:
计算机学