笛卡尔树以及treap-zoj_2243

笛卡尔树以及treap---zoj_2243

??????? zoj_2243笛卡尔树的构造，开始被topcoder上的教程吸引去看这题。题目中说这种数据结构叫treap然后就按照treap的insert加上左旋右旋去做了，结果果断TLE。然后网上找了一下关于笛卡尔树的资料，发现了一些问题的端倪。

?????? 首先，treap和笛卡尔树从形式上来说是完全一样的，即是一颗二叉搜索树和二叉堆的结合（不是严格意义上的二叉堆，因为二叉堆是一颗完全二叉树，而treap不是）。但是他们的目的也许不太一样。treap更大的意义在于为了维持BST的平衡型而找到的一种随即化构造的方案。在treap中，insert的时候节点的value值是随机生成的。因此在逐个insert节点的时候能够保证treap的统计意义上的平衡。然而，笛卡尔树的目的更多是为了rmq问题和LCA问题的转化。

???????其次，我们可以看到，在zoj_2243中，如果使用treap,按照题意一个个插如节点，随即化就被打破了，judge系统的数据也许不随机，从而导致treap的链化，弱化了平衡性，理想的NlogN的复杂度，可能退化到N^2，导致最后的TLE（可能左旋右旋操作的消耗也对应能有所影响）.

?????? 最后，找到了一种排序之后直接构造笛卡尔树的方法。首先将节点序列按照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。

?????? 最后，同样的题ZOJ是5M的，POJ是2M的，我用了从上到下2.5S，从下到上0.6S。

代码zoj_2243

#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;}

?