[关闭]
@KirinBill 2017-09-18T16:59:07.000000Z 字数 2993 阅读 4154

笛卡尔树学习笔记

学习笔记 数据结构

目录


基础知识

定义

实现

严格说来,笛卡尔树不是一种平衡树,它没有后续的插入等操作,只有建树操作,因此建树后的功能操作通常用Treap实现,我们在此也只讨论建树的实现:
- 笛卡尔树的构造类似左偏树,只是它是“右偏的”;
- 我们先将节点按值升序排列,这样按顺序每次只向树的右侧插入即可;
- 但我们还要维护该树的堆性质(这里小根堆会方便些),所以我们考虑用一个栈维护树最右边的一条链;
- 我们先令节点入栈,即超级根,因为rand()函数值域非负,所以构造小根堆就不需考虑将超级根赋为

  1. 对于一个节点,我们从栈顶开始找,找到第一个小于的节点
  2. 的右子树成为的左子树,成为的右儿子;
  3. 这样栈中之上的节点均不在树的最右边的链上了,所以都将其弹出,并让入栈。
  4. 最后,超级根的右儿子就是真正的根。

以上操作贪心(每次找第一个满足要求的节点)的保证了笛卡尔树的两个性质。同时,每个节点只入栈出栈各1次,瓶颈只在排序,因此复杂度

代码

  1. void build(int n,int val[],int key[]){
  2. static stack<int> stk;
  3. for(int i=1;i<=n;++i){
  4. d[i].val=val[i];
  5. d[i].key=key[i];
  6. d[i].sz=1;
  7. }
  8. sort(d+1,d+n+1);
  9. stk.push(0);
  10. for(int i=1,fa;i<=n;++i){
  11. while(fa=stk.top(),d[fa].key>d[i].key){
  12. upd(fa);
  13. stk.pop();
  14. }
  15. d[i].ls=d[fa].rs;
  16. d[fa].rs=i;
  17. stk.push(i);
  18. }
  19. while(stk.size()>1){
  20. upd(stk.top());
  21. stk.pop();
  22. }
  23. stk.pop();
  24. rt=d[0].rs;
  25. }

应用

构造Treap

练习题:[POJ 1785] Binary Search Heap Construction

代码:

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <utility>
  5. #include <climits>
  6. #include <cctype>
  7. #include <iostream>
  8. #include <stack>
  9. #define val first
  10. #define key second
  11. using std::sort;
  12. using std::pair;
  13. using std::ostream;
  14. using std::cout;
  15. using std::stack;
  16. template<const int MAXN>
  17. class string{
  18. private:
  19. int sz;
  20. char c[MAXN];
  21. public:
  22. string(){};
  23. string(char chr,int cnt){
  24. for(int i=0;i<cnt;++i)
  25. c[i]=chr;
  26. sz=cnt;
  27. }
  28. string& operator+= (char chr){c[sz++]=chr;}
  29. friend bool operator< (const string &a,const string &b){
  30. return strcmp(a.c,b.c)<0;
  31. }
  32. friend ostream& operator<< (ostream &out,const string &a){
  33. printf("%s",a.c);
  34. return out;
  35. }
  36. };
  37. typedef pair<string<20>,int> data;
  38. const int MAXN=50005;
  39. data tmp[MAXN];
  40. struct node{
  41. int ls,rs;
  42. data w;
  43. friend bool operator< (const node &a,const node &b){
  44. return a.w<b.w;
  45. }
  46. };
  47. class CartesianT{
  48. private:
  49. int rt;
  50. node d[MAXN];
  51. void inorder_prt(int u){
  52. putchar('(');
  53. if(d[u].ls) inorder_prt(d[u].ls);
  54. cout<<d[u].w.val;
  55. putchar('/');
  56. printf("%d",d[u].w.key);
  57. if(d[u].rs) inorder_prt(d[u].rs);
  58. putchar(')');
  59. }
  60. public:
  61. void clear(){memset(d,0,sizeof(d));}
  62. void build(int n,data a[]){
  63. static stack<int> stk;
  64. for(int i=1;i<=n;++i)
  65. d[i].w=a[i];
  66. sort(d+1,d+n+1);
  67. stk.push(0);
  68. d[0].w=data(string<20>(CHAR_MAX,20),INT_MAX);
  69. for(int i=1,fa;i<=n;++i){
  70. while(fa=stk.top(),d[fa].w.key<d[i].w.key)
  71. stk.pop();
  72. d[i].ls=d[fa].rs;
  73. d[fa].rs=i;
  74. stk.push(i);
  75. }
  76. while(stk.size()) stk.pop();
  77. rt=d[0].rs;
  78. }
  79. void inorder_prt(){inorder_prt(rt);}
  80. }T;
  81. int main(){
  82. int n;
  83. char c;
  84. while(scanf("%d",&n),n){
  85. T.clear();
  86. memset(tmp,0,sizeof(tmp));
  87. for(int i=1;i<=n;++i){
  88. do{c=getchar();}while(!islower(c));
  89. while(islower(c)){
  90. tmp[i].val+=c;
  91. c=getchar();
  92. }
  93. scanf("%d",&tmp[i].key);
  94. }
  95. T.build(n,tmp);
  96. T.inorder_prt();
  97. putchar('\n');
  98. }
  99. return 0;
  100. }

非旋转式Treap

其实也是用于建树,单独拿出来说是因为用于这种Treap建树是一般性的而不是只用于刚刚说的特殊情况。因为非旋转式Treapist()需要一次split()和两次merge(),常数略大,用笛卡尔树建树比较快。

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注