笛卡爾樹簡單介紹
笛卡爾樹又稱笛卡兒樹，在數據結構中屬於二叉樹的一種。
笛卡爾樹結構由Vuillmin在解決範圍搜尋的幾何數據結構問題時提出的，從數列中構造一棵笛卡爾樹可以線性時間完成，需要採用基於棧的算法來找到在該數列中的所有最近小數。由此可知，笛卡爾樹是一種特定的二叉樹數據結構，可由數列構造，在範圍最值查詢、範圍top k查詢（range top k queries）等問題上有廣泛套用。它具有堆的有序性，中序遍歷可以輸出原數列。
可以這么說：笛卡爾樹是一棵二叉樹，樹的每個節點有兩個值，一個為key，一個為value。光看key的話，笛卡爾樹是一棵二叉搜尋樹，每個節點的左子樹的key都比它小，右子樹都比它大；光看value的話，笛卡爾樹有點類似堆，根節點的value是最小（或者最大）的，每個節點的value都比它的子樹要大。
笛卡爾樹定義
無相同元素的數列構造出的笛卡爾樹具有下列性質：
1、結點一一對應於數列元素。即數列中的每個元素都對應於樹中某個唯一結點，樹結點也對應於數列中的某個唯一元素
2、中序遍歷（in-order traverse）笛卡爾樹即可得到原數列。即任意樹結點的左子樹結點所對應的數列元素下標比該結點所對應元素的下標小，右子樹結點所對應數列元素下標比該結點所對應元素下標大。
3、樹結構存在堆序性質，即任意樹結點所對應數值大/小於其左、右子樹內任意結點對應數值
根據堆序性質，笛卡爾樹根結點為數列中的最大/小值，樹本身也可以通過這一性質遞歸地定義：根結點為序列的最大/小值，左、右子樹則對應於左右兩個子序列，其結點同樣為兩個子序列的最大/小值。因此，上述三條性質唯一地定義了笛卡爾樹。若數列中存在重複值，則可用其它排序原則為數列中相同元素排定序列，例如以下標較小的數為較小，便能為含重複值的數列構造笛卡爾樹。
笛卡爾樹的實現
①排序之後直接構造笛卡爾樹的方法：
首先將節點序列按照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。
相關代碼
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;
}
