华师一附中OI组

标题: splay步步为营 [打印本页]

---

作者: admin    时间: 2020-4-5 15:45
标题: splay步步为营
SPLAY是信息学奥赛高级数据结构里面一个很重要的内容，可以用来解决好多的实际问题，序列统计，序列翻转等，很多的BST之类的题目都可以用SPLAY来解决。为了学好它，我们步步为营一个个的做。

Splay的基本思想和并查集的有点相似，并查集在进行了查找的时候顺便压缩了路径，这是一个自调整的过程，Splay在查询的时候将这个点想转到根，因为树总在旋转，所以基本可以达到一个平衡。
Splay的精髓在于旋转，这个旋转和treap的有点相似，treap在插入的时候现先只考虑节点的val值，根据BST的特性插入到合适的位置，显然是一个叶节点，然后再比较它的rnd和父节点的rnd，若大了则旋转，这样一次旋转的话它的父亲变成了自己的儿子，它上升了一级，然后递归直到rnd满足要求。而splay的旋转也是一样，基本思想把它旋转到他父亲的位置，逐层向上直到它成为根节点。

上旋一层和treap中几乎是一样的，但是Spaly因为以后涉及到更多的操作，所以结构体中特加了一个fa域。

先来一个最简单的，只有插入和输出的splay，着重写好旋转，为了确保正确，分步手写LR和RR，免得出错。交到LG1097，AC了。基本说明旋转部分没问题。

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. const int inf=9999999;
   
4. const int N=100100;
   
5. struct node
   
6. {
   
7.         int val,cnt;
   
8.         int fa,s[2],sz;  ///s0s1左右儿子
   
9. } a[N];
   
10. int n, tot, root;
    
11. void ArrayPr()   /// 调试监视使用
    
12. {
    
13.         cout<<endl<<"  i ";
    
14.         for (int i=1; i<=tot; i++) cout<<setw(3)<<i;
    
15.         cout<<endl<<"val ";
    
16.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].val;
    
17.         cout<<endl<<"cnt ";
    
18.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].cnt;
    
19.         cout<<endl<<" s0 ";
    
20.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[0];
    
21.         cout<<endl<<" s1 ";
    
22.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[1];
    
23.         cout<<endl<<" sz ";
    
24.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].sz;
    
25.         cout<<endl;
    
26. }
    
27. 
    
28. void BSTPr(int rt)   ///中序输出以rt为根的BST
    
29. {
    
30.         if (a[rt].s[0]>0)  BSTPr(a[rt].s[0]);
    
31.         cout<<a[rt].val<<' '<<a[rt].cnt<<endl;
    
32.         if (a[rt].s[1]>0)  BSTPr(a[rt].s[1]);
    
33. }
    
34. 
    
35. void LR(int rt)/// 左旋 因为有了fa，所以不需要传地址 但是也多了修改fa指针的操作
    
36. {
    
37.         ///cout<<"L\n";
    
38.         int x=a[rt].fa; ///x是rt的爸爸
    
39.         int y=a[x].fa;///y是x的爸爸 rt的爷爷
    
40.         int l=a[rt].s[0]; ///rt的左儿子挂给x当右儿子（本来右儿子是rt）
    
41.         a[x].s[1]=l;
    
42.         if(l!=0) a[l].fa=x;        //这个要注意空节点没有fa
    
43. 
    
44.         a[rt].fa=y; //rt取代了他的爸爸x
    
45.         a[rt].s[0]=x;//rt的原父节点x成为rt 的左儿子
    
46.         if(y!=0)
    
47.                 {
    
48.                         if(x==a[y].s[0])
    
49.                                 a[y].s[0]=rt;
    
50.                         else a[y].s[1]=rt;
    
51.                 }
    
52.         a[x].fa=rt;
    
53. }
    
54. 
    
55. void RR(int rt) /// 同上 右旋
    
56. {
    
57.         ///cout<<"R\n";
    
58.         int x=a[rt].fa; ///x是rt的爸爸
    
59.         int y=a[x].fa;///y是x的爸爸 rt的爷爷
    
60.         int  r=a[x].s[0]=a[rt].s[1];
    
61.         if(r!=0) a[r].fa=x;
    
62. 
    
63.         a[rt].fa=y; //rt取代了他的爸爸x
    
64.         a[rt].s[1]=x;
    
65.         if(y!=0)
    
66.                 {
    
67.                         if(x==a[y].s[0])
    
68.                                 a[y].s[0]=rt;
    
69.                         else a[y].s[1]=rt;
    
70.                 }
    
71.         a[x].fa=rt;
    
72. }
    
73. 
    
74. void splay(int rt)//伸展操作: 6种情况
    
75. {
    
76.         int x,y;
    
77.         while(a[rt].fa!=0)//反复进行旋转，直至将x节点调整至根部为止
    
78.                 {
    
79.                         x=a[rt].fa;///rt的爸爸
    
80.                         y=a[x].fa;
    
81.                         if(y==0)//在x为根的情况下，若x在左儿子位置，则右旋；否则左旋
    
82.                                 {
    
83.                                         if(rt==a[x].s[0]) RR(rt);
    
84.                                         else LR(rt);
    
85.                                         break;
    
86.                                 }
    
87.                     
    
88.                         if(rt==a[x].s[0])//在x位于左位置的情况下，若x的父节点位于左位置，则分别
    
89.                                 //以x的父节点和x为基准两次右旋；否则以x为基准右旋和左旋
    
90.                                 {
    
91.                                         if(x==a[y].s[0])  ///LLL
    
92.                                                 {
    
93.                                                         RR(x);
    
94.                                                         RR(rt);
    
95.                                                 }
    
96.                                         else  ///LLR
    
97.                                                 {
    
98.                                                         RR(rt);
    
99.                                                         LR(rt);
    
100.                                                 }
     
101.                                 }
     
102.                         else
     
103.                                 {
     
104.                                         if(x==a[y].s[1]) ///RRR
     
105.                                                 {
     
106.                                                         LR(x);
     
107.                                                         LR(rt);
     
108.                                                 }
     
109.                                         else
     
110.                                                 {
     
111.                                                         LR(rt);
     
112.                                                         RR(rt);
     
113.                                                 }
     
114.                                 }
     
115.                 }
     
116.         root=rt;//新根
     
117.         //cout<<rt<<endl;
     
118. }
     
119. void Ins(int rt, int x)   /// 在rt子树中插入x
     
120. {
     
121.         if(rt==0)  /// 新树
     
122.                 {
     
123.                         tot=root=1;
     
124.                         a[1].fa=a[1].s[0]=a[1].s[1]=0;
     
125.                         a[1].val=x;
     
126.                         a[1].cnt=1;
     
127.                 }
     
128.         else if(a[rt].val==x) a[rt].cnt++;
     
129.         else if(a[rt].val<x)
     
130.                 {
     
131.                         if (a[rt].s[1]==0)
     
132.                                 {
     
133.                                         a[rt].s[1]=++tot;
     
134.                                         a[tot].s[0]=a[tot].s[1]=0;
     
135.                                         a[tot].val=x;
     
136.                                         a[tot].fa=rt;
     
137.                                         a[tot].cnt=1;
     
138.                                         splay(tot);
     
139.                                 }
     
140.                         else
     
141.                                 Ins(a[rt].s[1],x);
     
142.                 }
     
143.         else if(a[rt].val>x)
     
144.                 {
     
145.                         if (a[rt].s[0]==0)
     
146.                                 {
     
147.                                         a[rt].s[0]=++tot;
     
148.                                         a[tot].s[0]=a[tot].s[1]=0;
     
149.                                         a[tot].val=x;
     
150.                                         a[tot].fa=rt;
     
151.                                         a[tot].cnt=1;
     
152.                                         splay(tot);
     
153.                                 }
     
154.                         else
     
155.                                 Ins(a[rt].s[0], x);
     
156.                 }
     
157. 
     
158. }
     
159. 
     
160. int main()
     
161. {
     
162.         cin>>n;
     
163.         while(n--)
     
164.                 {
     
165.                         int x;
     
166.                         cin>>x;
     
167.                         Ins(root,x);
     
168. 
     
169.                 }
     
170.         BSTPr(root);
     
171.         return 0;
     
172. }
     
173. 
     
174. /*
     
175. 10
     
176. 1 2 5 8 9 7 6 1 2 9
     
177. */

复制代码

这里写的代码很清晰直观，所以代码量比较大，加之我在里面写了很多的调试和测试语句，显得更长了。但是思路简单，主要是熟悉SPLAY的基本思路和几种旋转。要在纸上配合画图来理解。

---

作者: admin    时间: 2020-4-5 16:19
现在精简这部分的代码，用一个函数R(x)来表示将x向上旋一格，Splay(x,y)表示把x旋到y的位置，便于以后扩展的时候代码写短一点，因为比较复杂，里面加了好多的调试语句。

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. const int inf=9999999;
   
4. const int N=100100;
   
5. struct node
   
6. {
   
7.         int val,cnt;
   
8.         int fa,s[2],sz;  ///s0s1左右儿子
   
9. } a[N];
   
10. int n, tot, root;
    
11. void ArrayPr()   /// 调试监视使用
    
12. {
    
13.         cout<<endl<<"  i ";
    
14.         for (int i=1; i<=tot; i++) cout<<setw(3)<<i;
    
15.         cout<<endl<<"val ";
    
16.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].val;
    
17.         cout<<endl<<"cnt ";
    
18.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].cnt;
    
19.         cout<<endl<<" s0 ";
    
20.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[0];
    
21.         cout<<endl<<" s1 ";
    
22.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[1];
    
23.         cout<<endl<<" fa ";
    
24.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].fa;
    
25.         cout<<endl;
    
26.         int kk;
    
27.         cin>>kk;
    
28. }
    
29. 
    
30. void BSTPr(int rt)   ///中序输出以rt为根的BST
    
31. {
    
32.         if (a[rt].s[0]>0)  BSTPr(a[rt].s[0]);
    
33.         if (a[rt].cnt>0) cout<<a[rt].val<<' '<<a[rt].cnt<<endl;
    
34.         if (a[rt].s[1]>0)  BSTPr(a[rt].s[1]);
    
35. }
    
36. 
    
37. int Son(int x)///判断x是L还是R儿子
    
38. {
    
39.         int y=a[x].fa;
    
40.         return  a[y].s[1]==x;
    
41. }
    
42. void R(int x)
    
43. {
    
44.         int y=a[x].fa;
    
45.         int z=a[y].fa;
    
46.         int k=Son(x);
    
47.         int v=a[x].s[k^1];///v是x另外一边的儿子将要被挂在y下面
    
48.    
    
49.         a[y].s[k]=v,a[v].fa=y;///v挂在y下  要是v=0这里省略了
    
50.         a[z].s[Son(y)]=x,a[x].fa=z;///x挂在z下
    
51.         a[x].s[k^1]=y,a[y].fa=x;///y挂在x下
    
52.         /// 这三步需要画图理解
    
53.   
    
54.         ///cout<<"R"<<k<<endl;///0表示LR 1表示RR
    
55. }
    
56. inline void Splay(int x,int rt=root)  ///把x旋到rt的位置 默认rt是根
    
57. {
    
58.         rt=a[rt].fa;
    
59.         int y,z;
    
60.         while(a[x].fa!=rt)  /// y==rt就到位
    
61.                 {
    
62.                         y=a[x].fa,z=a[y].fa;;
    
63.                         ///ArrayPr();
    
64.                         ///cout<<x<<' '<<y<<' '<<z<<' '<<endl;
    
65. 
    
66.                         if(z!=rt)
    
67.                                 if(Son(x)==Son(y))R(y); /// 一字
    
68.                                 else R(x);
    
69.                         ///ArrayPr();
    
70.                         R(x);
    
71.                         ///ArrayPr();
    
72.                 }
    
73.         ///cout<<"Splay Complete!\n";
    
74.         if(rt==0)root=x;
    
75.         ///检查
    
76.         ///ArrayPr();
    
77.         ///BSTPr(root);
    
78. }
    
79. 
    
80. void Ins(int rt, int x)   /// 在rt子树中插入x
    
81. {
    
82.         if(a[rt].val==x) a[rt].cnt++;
    
83.         else
    
84.                 {
    
85.                         int k=a[rt].val>x;
    
86.                         {
    
87.                                 if (a[rt].s[k^1]==0)
    
88.                                         {
    
89.                                                 a[rt].s[k^1]=++tot;
    
90.                                                 a[tot].s[0]=a[tot].s[1]=0;
    
91.                                                 a[tot].val=x;
    
92.                                                 a[tot].fa=rt;
    
93.                                                 a[tot].cnt=1;
    
94.                                                 Splay(tot,root);
    
95.                                         }
    
96.                                 else
    
97.                                         Ins(a[rt].s[k^1],x);
    
98.                         }
    
99.                 }
    
100. 
     
101. }
     
102. 
     
103. int main()
     
104. {
     
105.         int i;
     
106.         cin>>n;
     
107.         //插入-inf和inf
     
108.         root=1;
     
109.         tot=2;
     
110.         a[1].val=-inf,a[1].s[0]=0,a[1].s[1]=2,a[1].fa=0;
     
111.         a[2].val= inf,a[2].s[0]=0,a[2].s[1]=0,a[2].fa=1;
     
112. 
     
113.         while(n--)
     
114.                 {
     
115.                         int x;
     
116.                         cin>>x;
     
117.                         Ins(root,x);
     
118. 
     
119.                         ///BSTPr(root);
     
120.                 }
     
121.         BSTPr(root);
     
122.         return 0;
     
123. }
     
124. 
     
125. /*
     
126. 10
     
127. 1 2  5  8  9  7  6  1  2 9
     
128. */

复制代码

这个程序我还好久没有写了，以前都是写LR RR那样清晰明了的，现在把他们合N为一，代码段肯定是短了，但是有错的话就很难调出来，你看我的程序里面都保留了我曾经的调试痕迹，体会下我是怎么样步步为营做程序的。

直观的加了-inf和-inf，也用cnt控制了它们的时候输出，交到LG1097，AC了。

---

作者: admin    时间: 2020-4-10 18:01
现在插入和遍历都是正确的，特别检查了旋转，既然LG1097AC了，基本既没有问题，现在添上删除部分，要删除x的话需要先查找到x所在的节点，找到后旋转到根，设为root，然后看它有没有左子树l，有的话，把左子树中的最大节点p，旋转到此节点l的位置，那么这个树l就完全没有右子树了，因为根是最大嘛！然后把root的右子树r作为l的右子树，接到l上，修改下root，新根为l。

1. int Find(int rt,int x)  /// 找到x对应的a[rt]
   
2. {
   
3.         if (rt==0) return 0;
   
4.         if (a[rt].val==x)
   
5.                 {
   
6.                         Splay(rt,root);
   
7.                         return rt;
   
8.                 }
   
9.         int k=a[rt].val<x; /// k=0表示左子树中去1表示去右子树
   
10.         return Find(a[rt].s[k],x);
    
11. }
    
12. void Del(int x) //删除节点
    
13. {
    
14.         int rt=Find(root,x);///找到对应的rt
    
15.         if(rt==0) return;
    
16.         if(a[rt].cnt>1)  a[rt].cnt--;
    
17.         else if(a[rt].s[0]==0) /// 没有左子树
    
18.                 {
    
19.                         root=a[rt].s[1];
    
20.                         a[root].fa=0;
    
21.                 }
    
22.         else
    
23.                 {
    
24.                         int p,l,r;
    
25.                         l=a[rt].s[0];
    
26.                         r=a[rt].s[1];
    
27.                         /// 左子树里面去找最右的儿子
    
28.                         p=l;
    
29.                         while(a[p].s[1]>0) p=a[p].s[1];
    
30.                         Splay(p,l); ///转上来作为根的左子树
    
31.                         /// 因为最大，没有右子树，把他作为新根
    
32.                         a[p].s[1]=r;  ///rt的右儿子接上去
    
33.                         a[r].fa=p;
    
34.                         a[root=p].fa=0;/// 新根
    
35.                         pushup(p);
    
36.                 }
    
37.         ///要不要回收？
    
38. }

复制代码

检查了下这段，把刚才插入的结点无聊的乱序一个个的删除，发现真的都删除了。

---

作者: admin    时间: 2020-4-11 13:21
因为Splay强调了R过程，所以查询排名和Treap有点不同，SPLAY查询的时候带着了旋转。
要想查找x的排名，先要找到x，当找到x的时候，其实x已经被旋到了根，现在只要直接输出左子树下的sz就行了。但是这里我们有两个假节点 +/-inf ，所以真实的排名要调整。

1. int Rank(int x) ///在RT子树中比x小的数 +1
   
2. {
   
3.         int rt=Find(root,x);
   
4.         int l=a[rt].s[0];
   
5.         return a[l].sz;/// 包含那个-inf 所以不需要+1
   
6. }

复制代码

---

作者: admin    时间: 2020-4-23 18:27
至于求前驱和后继，和以前的一样，但是这次我们选择使用非递归的写法，

1. int Pre(int rt, int x)
   
2. {
   
3.         int p=rt, ans;
   
4.         while(p>0)
   
5.                 {
   
6.                         if(x<=a[p].val) p=a[p].s[0];
   
7.                         else
   
8.                                 {
   
9.                                         ans=p;
   
10.                                         p=a[p].s[1];
    
11.                                 }
    
12.                 }
    
13.         return ans;
    
14. }
    
15. int Suc(int rt, int x)
    
16. {
    
17.         int p=rt, ans;
    
18.         while(p>0)
    
19.                 {
    
20.                         if(a[p].val<=x) p=a[p].s[1];
    
21.                         else
    
22.                                 {
    
23.                                         ans = p;
    
24.                                         p=a[p].s[0];
    
25.                                 }
    
26.                 }
    
27.         return ans;
    
28. }

复制代码

---

作者: admin    时间: 2020-4-23 18:36
结合上面所有的代码，3369的做法如下，交上去，顺利AC.

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. const int inf=99999999;
   
4. const int N=100100;
   
5. struct node
   
6. {
   
7.         int val,cnt;
   
8.         int fa,s[2],sz;  ///s0s1左右儿子
   
9. } a[N];
   
10. int n, tot, root;
    
11. void ArrayPr()   /// 调试监视使用
    
12. {
    
13.         cout<<endl<<"  i ";
    
14.         for (int i=1; i<=tot; i++) cout<<setw(3)<<i;
    
15.         cout<<endl<<"val ";
    
16.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].val;
    
17.         cout<<endl<<"cnt ";
    
18.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].cnt;
    
19.         cout<<endl<<" s0 ";
    
20.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[0];
    
21.         cout<<endl<<" s1 ";
    
22.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[1];
    
23.         cout<<endl<<" fa ";
    
24.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].fa;
    
25.         cout<<endl<<" sz ";
    
26.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].sz;
    
27.         cout<<endl;
    
28. }
    
29. 
    
30. void BSTPr(int rt)   ///中序输出以rt为根的BST
    
31. {
    
32.         if (a[rt].s[0]>0)  BSTPr(a[rt].s[0]);
    
33.         if (a[rt].cnt>0) cout<<a[rt].val<<' '<<a[rt].cnt<<endl;
    
34.         if (a[rt].s[1]>0)  BSTPr(a[rt].s[1]);
    
35. }
    
36. void pushdown(int rt)   ///类似线段树网上调整
    
37. {
    
38.         ///暂时无用
    
39. }
    
40. void pushup(int rt)  ///类似线段树网上调整
    
41. {
    
42.         int l=a[rt].s[0], r=a[rt].s[1];
    
43.         a[rt].sz=a[l].sz+a[r].sz+a[rt].cnt;
    
44. }
    
45. int Son(int x)///判断x是L还是R儿子
    
46. {
    
47.         int y=a[x].fa;
    
48.         return  a[y].s[1]==x;
    
49. }
    
50. void R(int x)
    
51. {
    
52.         int y=a[x].fa;
    
53.         int z=a[y].fa;
    
54.         int k=Son(x);
    
55.         int v=a[x].s[k^1];///v是x另外一边的儿子将要被挂在y下面
    
56.         pushdown(x),pushdown(y);///下传
    
57.         a[y].s[k]=v,a[v].fa=y;///v挂在y下  要是v=0这里省略了
    
58.         a[z].s[Son(y)]=x,a[x].fa=z;///x挂在z下
    
59.         a[x].s[k^1]=y,a[y].fa=x;///y挂在x下
    
60.         /// 这三步需要画图理解
    
61.         pushup(y),pushup(x);///上传，注意顺序
    
62. }
    
63. inline void Splay(int x,int rt=root)  ///把x旋到rt的位置 默认rt是根
    
64. {
    
65.         rt=a[rt].fa;
    
66.         int y,z;
    
67.         while(a[x].fa!=rt)  /// y==rt就到位
    
68.                 {
    
69.                         y=a[x].fa,z=a[y].fa;;
    
70.                         if(z!=rt)
    
71.                                 if(Son(x)==Son(y))R(y); /// 一字
    
72.                                 else R(x);
    
73.                         R(x);
    
74.                 }
    
75.         if(rt==0)root=x;
    
76. }
    
77. int Find(int rt,int x)  /// 找到x对应的a[rt]
    
78. {
    
79.         if (a[rt].val==x)
    
80.                 {
    
81.                         Splay(rt,root);
    
82.                         return rt;
    
83.                 }
    
84.         int k=a[rt].val<x; /// k=0表示左子树中去1表示去右子树
    
85.         if (a[rt].s[k]>0)  return Find(a[rt].s[k],x);
    
86.         else return 0;
    
87. }
    
88. void Ins(int rt, int x)   /// 在rt子树中插入x
    
89. {
    
90.         a[rt].sz++;
    
91.         if(a[rt].val==x) a[rt].cnt++;
    
92.         else
    
93.                 {
    
94.                         int k=(a[rt].val<x);/// k=0表示左子树中去1表示去右子树
    
95.                         if (a[rt].s[k]==0)
    
96.                                 {
    
97.                                         a[rt].s[k]=++tot;
    
98.                                         a[tot].s[0]=a[tot].s[1]=0;
    
99.                                         a[tot].val=x;
    
100.                                         a[tot].fa=rt;
     
101.                                         a[tot].cnt=a[tot].sz=1;
     
102.                                         Splay(tot,root);
     
103.                                 }
     
104.                         else
     
105.                                 Ins(a[rt].s[k],x);
     
106.                 }
     
107. 
     
108. }
     
109. void Del(int x) //删除节点
     
110. {
     
111.         int rt=Find(root,x);///找到对应的rt
     
112.         if(rt==0) return;
     
113.         a[rt].sz--;
     
114.         if(a[rt].cnt>1)  a[rt].cnt--;
     
115.         else if(a[rt].s[0]==0) /// 没有左子树
     
116.                 {
     
117.                         root=a[rt].s[1];
     
118.                         a[root].fa=0;
     
119.                 }
     
120.         else
     
121.                 {
     
122.                         int p,l,r;
     
123.                         l=a[rt].s[0];
     
124.                         r=a[rt].s[1];
     
125.                         /// 左子树里面去找最右的儿子
     
126.                         p=l;
     
127.                         while(a[p].s[1]>0) p=a[p].s[1];
     
128.                         Splay(p,l); ///转上来作为根的左子树
     
129.                         /// 因为最大，没有右子树，把他作为新根
     
130.                         a[p].s[1]=r;  ///rt的右儿子接上去
     
131.                         a[r].fa=p;
     
132.                         a[root=p].fa=0;;/// 新根
     
133.                         pushup(p);
     
134.                 }
     
135.         ///要不要回收？
     
136. }
     
137. int Rank(int x) ///在RT子树中比x小的数 +1
     
138. {
     
139.         int rt=Find(root,x);
     
140.         int l=a[rt].s[0];
     
141.         return a[l].sz;/// 包含那个-inf 所以不需要+1
     
142. }
     
143. 
     
144. int Getkth(int rt, int x) ///在RT子树中找第k小
     
145. {
     
146.         int l=a[a[rt].s[0]].sz;  /// RT的左儿子下的个数
     
147.         if(l+1<=x && x<=l+a[rt].cnt) return a[rt].val;
     
148.         if(l+1>x) return Getkth(a[rt].s[0], x); ///左儿子里去找
     
149.         if(l+a[rt].cnt<x) return Getkth(a[rt].s[1], x-(l+a[rt].cnt));
     
150. }
     
151. 
     
152. int Pre(int rt, int x)
     
153. {
     
154.         int p=rt, ans;
     
155.         while(p>0)
     
156.                 {
     
157.                         if(x<=a[p].val) p=a[p].s[0];
     
158.                         else
     
159.                                 {
     
160.                                         ans=p;
     
161.                                         p=a[p].s[1];
     
162.                                 }
     
163.                 }
     
164.         return ans;
     
165. }
     
166. int Suc(int rt, int x)
     
167. {
     
168.         int p=rt, ans;
     
169.         while(p>0)
     
170.                 {
     
171.                         if(a[p].val<=x) p=a[p].s[1];
     
172.                         else
     
173.                                 {
     
174.                                         ans = p;
     
175.                                         p=a[p].s[0];
     
176.                                 }
     
177.                 }
     
178.         return ans;
     
179. }
     
180. int main()
     
181. {
     
182.         ///freopen("3369.in","r",stdin);
     
183.         ///freopen("3369.out","w",stdout);
     
184.         int x,opt;
     
185.         cin>>n;
     
186.         //插入-inf和inf
     
187.         root=1;
     
188.         tot=2;
     
189.         a[1].val=-inf,a[1].s[0]=0,a[1].s[1]=2,a[1].fa=0;
     
190.         a[2].val= inf,a[2].s[0]=0,a[2].s[1]=0,a[2].fa=1;
     
191.         a[1].sz=2,a[2].sz=1;
     
192.         a[1].cnt=a[2].cnt=1;
     
193. 
     
194.         while(n--)
     
195.                 {
     
196.                         cin>>opt>>x;
     
197.                         if(opt==1) Ins(root, x);
     
198.                         if(opt==2) Del(x);
     
199.                         if(opt==3) cout<<Rank(x)<<endl;
     
200.                         if(opt==4) cout<<Getkth(root, x+1)<<endl;
     
201.                         if(opt==5) cout<<a[Pre(root, x)].val<<endl;
     
202.                         if(opt==6) cout<<a[Suc(root, x)].val<<endl;
     
203.                 }
     
204.         return 0;
     
205. }
     
206. /*
     
207. 40
     
208. 1 3 7 5 9 2 8 4 6 0
     
209. 11 13 17 15 19 12 18 14 16 10
     
210. 31 33 37 35 39 32 38 34 36 30
     
211. 11 13 17 15 19 12 18 14 16 10
     
212. */
     

复制代码

---

作者: admin    时间: 2020-4-24 13:04
上面的例子是SPLAY的一个应用，就是把某个点旋转到根，在查询的过程中总在转动的话这棵树的平衡性不会太差，所以可以当AVL来用。还有一个更牛的应用就是伸展操作，把
在学这个的时候要注意转换一下思想，把区间的下标当做树的节点。
一个典型的简单应用基础题是P3391 文艺平衡树 http://hsyit.cn/forum.php?mod=viewthread&tid=69341

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2