首页 > 代码库 > [模板]洛谷T3369 普通平衡树 链表&递归版、无父指针版Splay
[模板]洛谷T3369 普通平衡树 链表&递归版、无父指针版Splay
结构体node定义：呐...因为不是Treap，所以就不必定义优先级yx了；
这次为了代码简短，总算是把判断子树方向函数（cmp）和节点信息维护函数（maintain）封在了结构体里。
旋转函数rotate：与Treap相比，没有任何变化，就是写得简短了一些。
插入函数insert：Treap时需要对违反堆性质的节点进行上浮的操作现在不需要了，只需同普通BST一样直接插入即可。
插完后，对刚插入的节点执行Splay操作。
删除函数del：针对待删除节点左右子树均非空的情况，Treap做法是将左右子树中优先级较小的上旋，然后递归在子树中删除该节点；
现在用Splay，因为没有优先级，所以就随机将左子树或右子树上旋，然后递归在子树中删除该节点。
删完后，对刚删除的节点执行Splay操作。
伸展函数Splay：这就是重头戏咯~
这个操作的功能是，将某个节点通过旋转移动至指定位置。
实现细节：
1.如果当前节点即为待伸展节点，那么不进行任何操作，直接返回；
2.用变量d1记录待伸展节点相对于当前操作节点的位置，若d1指向的子树为空，那么不进行任何操作，直接返回；
3.用变量d2记录待伸展节点相对于d1指向节点的位置；
4.若d2指向节点为空，或d1指向节点即为待伸展节点，那么直接将d1指向节点上旋，然后返回即可；
5.若d2指向节点非空，那么先递归将待伸展节点伸展至d2指向的位置，再根据情况进行一字型或之字形旋转，将待伸展节点调整至当前层指定位置即可。
求k大函数kth：额。。。这个没想出新的搞法，沿用了原先的写法。
求排名函数rank：将待查询元素伸展至根，则其排名为（左子树元素数+1）。
要特判伸展后左子树为空的情况，直接返回1。
求前驱函数pre：
1.将待查询元素伸展至根；
2.若根节点键值小于待查询值，则直接返回根节点键值；
3.若根节点键值大于等于待查询值，则返回左子树中的最大值（实现方法：将inf伸展至根节点的左子节点处，则左子节点键值即为左子树中的最大值）。
求后继函数succ：与pre同理。
代码如下：
1 #include<cstdio>
2 #include<iostream>
3 #include<cstring>
4 #include<ctime>
5 #include<cstdlib>
6 #include<ctime>
7
8 #include<string>
9 #include<stack>
10 #include<queue>
11 #include<vector>
12 #include<algorithm>
13 #include<map>
14
15 #define inf 2147483647
16
17 using namespace std;
18
19 struct node{
20 int key;
21 int size,num;
22 node *ch[2];
23
24 int cmp(int x){
25 if(x==key)return -1;
26 else return x>key;
27 }
28
29 void maintain(){
30 size=num;
31 if(ch[0]!=NULL)size+=ch[0]->size;
32 if(ch[1]!=NULL)size+=ch[1]->size;
33 }
34 };
35
36 void rotate(node* &,bool);
37 void splay(node* &,int);
38 void insert(node* &,int); //没有自带伸展
39 void del(node* &,int); //没有自带伸展
40
41 int kth(node *,int); //没有自带伸展
42 int rank(int); //依靠伸展实现
43 int pre(int); //依靠伸展实现
44 int succ(int); //依靠伸展实现
45
46 node *root=NULL;
47
48 int n,i;
49
50 int f,x;
51
52 int main(){
53 srand(time(0));
54
55 scanf("%d",&n);
56
57 for(i=1;i<=n;i++){
58 scanf("%d",&f);
59
60 switch(f){
61 case 1:{
62 scanf("%d",&x);
63 insert(root,x);
64 splay(root,x);
65 break;
66 }
67 case 2:{
68 scanf("%d",&x);
69 del(root,x);
70 splay(root,x);
71 break;
72 }
73 case 3:{
74 scanf("%d",&x);
75 printf("%d\n",rank(x));
76 break;
77 }
78 case 4:{
79 scanf("%d",&x);
80 printf("%d\n",kth(root,x));
81 break;
82 }
83 case 5:{
84 scanf("%d",&x);
85 printf("%d\n",pre(x));
86 break;
87 }
88 case 6:{
89 scanf("%d",&x);
90 printf("%d\n",succ(x));
91 break;
92 }
93 }
94 }
95
96 return 0;
97 }
98
99 void rotate(node* &p,bool f){
100 node *t=p->ch[f^1];
101 p->ch[f^1]=t->ch[f];
102 t->ch[f]=p;
103
104 p->maintain();
105 t->maintain();
106
107 p=t;
108 }
109
110 void splay(node* &p,int x){
111 int d1=p->cmp(x);
112
113 if(d1==-1 || p->ch[d1]==NULL)return;
114
115 int d2=p->ch[d1]->cmp(x);
116
117 if(p->ch[d1]->ch[d2]==NULL || d2==-1){
118 rotate(p,d1^1);
119 return;
120 }
121 else{
122 splay(p->ch[d1]->ch[d2],x);
123
124 if(d1==d2){
125 rotate(p,d1^1);
126 rotate(p,d2^1);
127 }
128 else{
129 rotate(p->ch[d1],d2^1);
130 rotate(p,d1^1);
131 }
132 }
133 }
134
135 void insert(node* &p,int x){
136 if(p==NULL){
137 p=(node *)malloc(sizeof(node));
138 p->key=x;
139 p->size=p->num=1;
140 p->ch[0]=p->ch[1]=NULL;
141 return;
142 }
143
144 if(p->key==x){
145 p->size++;
146 p->num++;
147 return;
148 }
149
150 if(x<p->key){
151 insert(p->ch[0],x);
152 p->size++;
153 }
154 else{
155 insert(p->ch[1],x);
156 p->size++;
157 }
158 }
159
160 void del(node* &p,int x){
161 if(p==NULL)return;
162
163 if(p->key==x){
164 if(p->num>1){
165 p->size--;
166 p->num--;
167 return;
168 }
169 else{
170 if(p->ch[0]==NULL){
171 node *t=p;
172 p=p->ch[1];
173 free(t);
174 return;
175 }
176 else if(p->ch[1]==NULL){
177 node *t=p;
178 p=p->ch[0];
179 free(t);
180 return;
181 }
182 else{
183 bool f=rand()&1; //旋转方向
184 rotate(p,f);
185 del(p->ch[f],x);
186 p->size--;
187 }
188 }
189 }
190 else{
191 if(x<p->key)del(p->ch[0],x);
192 else del(p->ch[1],x);
193 p->size--;
194 }
195 }
196
197 int kth(node *p,int x){
198 int s=0;
199
200 if(p->ch[0]!=NULL)s=p->ch[0]->size;
201
202 if(x<=s)return kth(p->ch[0],x);
203 else if(x<=s+p->num)return p->key;
204 else return kth(p->ch[1],x-s-p->num);
205 }
206
207 int rank(int x){
208 splay(root,x);
209
210 if(root->ch[0]==NULL)return 1;
211 else return root->ch[0]->size+1;
212 }
213
214 int pre(int x){
215 splay(root,x);
216
217 if(root->key<x)return root->key;
218 else{
219 if(root->ch[0]==NULL)return -inf;
220 else{
221 splay(root->ch[0],inf);
222 return root->ch[0]->key;
223 }
224 }
225 }
226
227 int succ(int x){
228 splay(root,x);
229
230 if(root->key>x)return root->key;
231 else{
232 if(root->ch[1]==NULL)return inf;
233 else{
234 splay(root->ch[1],-inf);
235 return root->ch[1]->key;
236 }
237 }
238 }
[模板]洛谷T3369 普通平衡树 链表&递归版、无父指针版Splay
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。