[关闭]
@zzzc18 2017-06-20T09:28:57.000000Z 字数 3391 阅读 574

Splay

Splay


模板:普通平衡树
洛谷3369

Splay即为伸展树,本体就是一个排序二叉树,主要通过节点的父子关系改变而进行旋转,从而使得二叉树尽量平衡;
核心部分即为splay和rotate,代码中对此有清晰的讨论

  1. #include<cstdio>
  2. #include<algorithm>
  3. #define MAXN 100009
  4. using namespace std;
  5. int n;
  6. class SP{
  7. public:
  8. struct T{
  9. int ls,rs,fa,sz,num,val;
  10. };
  11. int root;int size;
  12. T tree[MAXN];
  13. void DEBUG(int k){
  14. if(k==0)return;
  15. DEBUG(tree[k].ls);
  16. printf("No. %2d:val=%d|ls=%d|rs=%d|fa=%d|sz=%d|num=%d\n",k,tree[k].val,tree[k].ls,tree[k].rs,tree[k].fa,tree[k].sz,tree[k].num);
  17. DEBUG(tree[k].rs);
  18. }
  19. int max_t(int x){
  20. int k=x;
  21. while(x){
  22. k=x;
  23. x=tree[x].rs;
  24. }
  25. return k;
  26. }
  27. int min_t(int x){
  28. int k=x;
  29. while(x){
  30. k=x;
  31. x=tree[x].ls;
  32. }
  33. return k;
  34. }
  35. int Find(int k,int x){
  36. if(k==0)return 0;
  37. if(tree[k].val==x)
  38. return k;
  39. else if(tree[k].val<x)
  40. return Find(tree[k].rs,x);
  41. else
  42. return Find(tree[k].ls,x);
  43. }
  44. void update(int x){
  45. tree[x].sz=tree[tree[x].ls].sz+tree[tree[x].rs].sz+tree[x].num;
  46. }
  47. void rotate_l(int x){
  48. int flag=0;
  49. int y=tree[x].fa,z=tree[y].fa,p=tree[x].ls;
  50. if(tree[z].rs==y)flag=0;
  51. else flag=1;
  52. if(z==0)
  53. flag=-1;
  54. tree[x].ls=y;
  55. tree[y].rs=p;
  56. if(flag==0)tree[z].rs=x;
  57. else if(flag==1) tree[z].ls=x;
  58. else root=x;
  59. tree[x].fa=z;
  60. tree[y].fa=x;
  61. tree[p].fa=y;
  62. update(y);
  63. update(x);
  64. }
  65. void rotate_r(int x){
  66. int flag=0;
  67. int y=tree[x].fa,z=tree[y].fa,p=tree[x].rs;
  68. if(tree[z].rs==y)flag=0;
  69. else flag=1;
  70. if(z==0)
  71. flag=-1;
  72. tree[y].ls=p;
  73. tree[x].rs=y;
  74. if(flag==0)tree[z].rs=x;
  75. else if(flag==1) tree[z].ls=x;
  76. else root=x;
  77. tree[x].fa=z;
  78. tree[p].fa=y;
  79. tree[y].fa=x;
  80. update(y);
  81. update(x);
  82. }
  83. void splay(int x,int to,int type){
  84. int y,z;
  85. to=tree[to].fa;
  86. if(type==1)
  87. x=Find(root,x);
  88. while(tree[x].fa!=to){
  89. y=tree[x].fa;z=tree[y].fa;
  90. if(z==to){
  91. if(tree[y].ls==x)rotate_r(x);
  92. else rotate_l(x);
  93. }
  94. else{
  95. if(tree[z].ls==y && tree[y].ls==x){
  96. rotate_r(y);
  97. rotate_r(x);
  98. }
  99. else if(tree[z].ls==y && tree[y].rs==x)
  100. rotate_l(x),rotate_r(x);
  101. else if(tree[z].rs==y && tree[y].rs==x)
  102. rotate_l(y),rotate_l(x);
  103. else if(tree[z].rs==y && tree[y].ls==x)
  104. rotate_r(x),rotate_l(x);
  105. update(z);
  106. }
  107. }
  108. if(to==0)root=x;
  109. }
  110. void insert(int &k,int v,int father){
  111. if(k==0){
  112. k=++size;
  113. tree[k].val=v;
  114. tree[k].fa=father;
  115. tree[k].num=tree[k].sz=1;
  116. return;
  117. }
  118. tree[k].sz++;
  119. if(tree[k].val==v)
  120. tree[k].num++;
  121. else if(tree[k].val<v)
  122. insert(tree[k].rs,v,k);
  123. else
  124. insert(tree[k].ls,v,k);
  125. }
  126. void del(int x){
  127. int p=0;
  128. if(!Find(root,x))return;
  129. splay(x,root,1);
  130. x=Find(root,x);
  131. if(tree[x].num>1){
  132. tree[x].num--;
  133. return;
  134. }
  135. if(tree[x].ls*tree[x].rs==0)root=tree[x].ls+tree[x].rs;
  136. else{
  137. p=max_t(tree[x].ls);
  138. tree[p].rs=tree[x].rs;
  139. tree[tree[x].rs].fa=p;
  140. root=tree[x].ls;
  141. }
  142. tree[root].fa=0;
  143. while(p!=0){
  144. update(p);
  145. p=tree[p].fa;
  146. }
  147. }
  148. int n2r(int x){
  149. splay(x,root,1);
  150. return tree[tree[root].ls].sz+1;
  151. }
  152. int r2n(int x){
  153. int now=root;
  154. while(1){
  155. int minused=tree[now].num+tree[tree[now].ls].sz;
  156. if(x>tree[tree[now].ls].sz && x<=minused)
  157. break;
  158. if(x<=tree[tree[now].ls].sz)
  159. now=tree[now].ls;
  160. else{
  161. x-=minused;
  162. now=tree[now].rs;
  163. }
  164. }
  165. splay(now,root,0);
  166. return tree[now].val;
  167. }
  168. int pred(int x){
  169. int re;
  170. insert(root,x,0);
  171. splay(x,root,1);
  172. if(tree[root].ls==0)
  173. re=0;
  174. else
  175. re=tree[max_t(tree[root].ls)].val;
  176. del(x);
  177. return re;
  178. }
  179. int succ(int x){
  180. int re;
  181. insert(root,x,0);
  182. splay(x,root,1);
  183. if(tree[root].rs==0)
  184. re=0;
  185. else
  186. re=tree[min_t(tree[root].rs)].val;
  187. del(x);
  188. return re;
  189. }
  190. }Splay;
  191. int main(){
  192. freopen("splay.in","r",stdin);
  193. freopen("splay.out","w",stdout);
  194. scanf("%d",&n);
  195. int i;
  196. for(i=1;i<=n;i++){
  197. int opt,x;
  198. scanf("%d%d",&opt,&x);
  199. if(opt==1)
  200. Splay.insert(Splay.root,x,0);
  201. else if(opt==2)
  202. Splay.del(x);
  203. else if(opt==3)
  204. printf("%d\n",Splay.n2r(x));
  205. else if(opt==4)
  206. printf("%d\n",Splay.r2n(x));
  207. else if(opt==5)
  208. printf("%d\n",Splay.pred(x));
  209. else if(opt==6)
  210. printf("%d\n",Splay.succ(x));
  211. //printf("----------DEBUG------------\norderNo.%d root:%d\n",i,Splay.root),Splay.DEBUG(Splay.root);
  212. }
  213. return 0;
  214. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注