这份代码来自于以前的Wikipedia,遇到这份代码也许是缘分吧,虽然实现上十分的冗长(好多好多的废话),但是也正因为如此这份代码展示了伸展树操作的每一个细节,尽管没什么实用价值,但是拿来理解splay是很好的。我自己抄了一遍同时加上了注释。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 |
// // SplayTree.cpp // playground // // Created by Adam Chang on 2015/4/11. // Copyright (c) 2015年 Adam Chang. All rights reserved. // //C Implementation in reference of http://en.wikipedia.org/w/index.php?title=Splay_tree&oldid=533723000 //NON-Recursive Elementary #include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> using namespace std; struct node{ int data; node *left; node *right; node *parent; }; struct node *rotate_left(struct node *pivot,struct node *root){ struct node *x; x = pivot->right; //reassign x's left child to pivot's right child slot pivot->right = x->left; if (x->left != NULL) { x->left->parent = pivot; } //reverse the parential relation between x and pivot x->left = pivot; if (pivot->parent != NULL) { if (pivot == pivot->parent->left) { pivot->parent->left = x; }else{ pivot->parent->right = x; } } x->parent = pivot->parent; pivot->parent = x; //return value for the splay func to change the tree root if (pivot == root) { //pivot is the original root,after rotate x become the new root return x; }else{ return root; } } struct node *rotate_right(struct node *pivot,struct node *root){ //x is pivot's left child struct node *x; x = pivot->left; //assign x's right child to pivot's left child slot pivot->left = x -> right; if (x->right != NULL) { x->right->parent = pivot; } //reverse the parental relationship between x and pivot x->right = pivot; if (pivot->parent != NULL) { if (pivot == pivot->parent->right) { pivot->parent->right = x; }else { pivot->parent->left = x; } } x->parent = pivot->parent; pivot->parent = x; //the return value is for the splay func to change the tree root if (pivot == root) { //pivot is the original root,after rotate x become the new root return x; }else{ return root; } } void splay(struct node *x,struct node *root){ //x is root,no operation required if (x == root) { return; }else if(x->parent == root){ //single rotation required if (x == x->parent->left) { //x on the root's left,let root be the pivot and throw the x onto the root pos root = rotate_right(root, root); }else{ //conversely root = rotate_left(root, root); } }else { //complex situation,multiple rotation required node *p,*g;//p:parent node g:grandparent node p = x->parent; g = p->parent; if (x == p->left && p == g->left) { //double right rotation root = rotate_right(g, root); root = rotate_right(p, root); }else if(x == p->right && p == g->right){ //double left rotation root = rotate_left(g, root); root = rotate_left(p, root); }else if(x == p->left && p == g->right){ //perform right-left(zagzig) rotation root = rotate_right(p, root); root = rotate_left(g, root); }else if(x == p->right && p == g->left){ //perform left-right(zigzag) rotation root = rotate_left(p, root); root = rotate_right(g, root); } //when in complex situation,the splay cannot terminate only after once,use recursion here. splay(x, root); } } struct node *insert(struct node *root,int value){ struct node *temp1,*temp2,*par; if (root == NULL) { //given subtree root doesn't exist,create one and return this new subroot for splay. root = (struct node *)malloc(sizeof(struct node)); if (root != NULL) { root->data = value; root->parent = NULL; root->left = NULL; root->right = NULL; }else{ //handle memory exception printf("MEMORY ALLOCATION EXCEPTION\n"); exit(0); } }else{ temp2 = root; while (temp2 != NULL) { //iteriate until we find a good place to place the new node temp1 = temp2;//save current node as the target node(or its place)'s parent if (temp2->data > value) { temp2 = temp2->left; }else if(temp2->data < value){ temp2 = temp2->right; }else{ //temp2->data==value no need to instert,just return this node //(we don't accept nodes with same key),in this case insert becomes search return temp2; } } if (temp1->data > value) { par = temp1;//par is now the target's parent temp1->left = (struct node *)malloc(sizeof(struct node)); temp1 = temp1->left;//temp1 is now the target node if (temp1 != NULL) { temp1->data = value; temp1->parent = par; temp1->left = NULL; temp1->right = NULL; }else{ //handle memory exception printf("MEMORY ALLOCATION EXCEPTION\n"); exit(0); } }else{ //only repeating itself(REFACTORIZATION REQUIRED) par = temp1;//par is now the target's parent temp1->right = (struct node *)malloc(sizeof(struct node)); temp1 = temp1->right;//temp1 is now the target node if (temp1 != NULL) { temp1->data = value; temp1->parent = par; temp1->left = NULL; temp1->right = NULL; }else{ //handle memory exception printf("MEMORY ALLOCATION EXCEPTION\n"); exit(0); } } } splay(temp1, root);//splay the newly inserted node to root position return temp1;//this func. returns the pointer of newly inserted node for futher ops. } struct node *lookup(struct node *root,int value){ struct node *temp1,*temp2; if (root != NULL) { temp1 = root;//temp2 is the target pos for return,temp1 is only for iteration temp2 = temp1; while (temp1 != NULL) { temp2 = temp1; if (temp1->data > value) { temp1 = temp1->left; }else if(temp1->data < value){ temp1 = temp1->right; }else{ return temp1;//already found,just return it. } } return temp2;//didn't find the node but we find it's parent(assuming the node exists),return the parent; }else{ printf("ROOT NULL EXCEPTION\n"); exit(0); } } struct node *successor(struct node *x){ //get the assuming node's right subtree's leftmost child struct node *temp1,*temp2; temp1 = temp2 = x->right; while (temp1 != NULL) { temp2 = temp1; temp1 = temp1->left; } return temp2; } struct node *remove(struct node *root,int value){ struct node *x,*y,*s;//y is the new root after removal x = lookup(root, value); if (x->data == value) { //we have located the node matched for remove if (x->left == NULL && x->right == NULL) { if (x == root) { //special judge to avoid root fault y = root = NULL;//if root is leaf,simply make NULL the new root }else{ //if the node for remove is a leaf y = x->parent; if (x == (y->right)) { y->right = NULL; }else{ y->left = NULL; }//unlink x from its parent } }else if(x->left != NULL && x->right == NULL){ if (x == root) {//root fault prevention x->left->parent = NULL;//x's lch becomes the new root y = x->left; root = x->left; }else{ //if the node for removal only have left child y = x->parent; if (x == y->left) { x->left->parent = y;//relink the child y->left = x->left; }else{ x->left->parent = y;//relink y->right = x->left; } } }else if(x->left == NULL && x->right != NULL){ if(x == root) { //avoid root fault x->right->parent=NULL;//x's rch becomes the new root y=x->right; root=x->right; } else { //if the node to remove only have right child y = x->parent; //we just repeat ourself as above... if (x == y->left) { x->right->parent = y; y->left = x->right; }else{ x->right->parent = y; y->right = x->right; } } }else{ //if the node for removal have both childs if (x == root) { s = successor(x);//find successor(rch's leftmost node) if (s == x->right) { //if successor is right at x's rch y = s; s->parent = NULL;//make s the new root,relink x's lch x->left->parent = s; s->left = x->left; root = s; }else{ y = s->parent;//s's parent should be the new root after splay if (s->right != NULL) { s->right->parent = y;//relink s's rch to s's parent(because s goes to root) y->left = s->right; }else{ y->left = NULL;//unlink s's parent's lch } s->parent = NULL;//s is now the new root x->right->parent = s;//relink x->left->parent = s; s->right = x->right; s->left = x->left; root = s; } }else{ y = x->parent; if (x == y->left) { s = successor(x); //find x's right's leftmost to replace x if (s != x->right) { y = s->parent; if (s->right != NULL) { //if the successor have right child s->right->parent = y;//relink its right child to x's parent(s goes to x's parent's left) y->left = s->right; }else{ y->left = NULL; } s->parent = s->parent;//the relink proccess can be better understood by illustration x->right->parent = s; x->left->parent = s; s->right = x->right; s->left = x->left; x->parent->left = s; }else{ y = s; s->parent = x->parent; x->left->parent = s; s->left = x->left; x->parent->left = s; } }else{ s = successor(x);//we are repeating if (s != x->right) { y = s->parent; if (s->right != NULL) { s->right->parent = y; y->left = s->right; }else{ y->left = NULL; } s->parent = x->parent; s->right->parent = s; x->left->parent = s; s->right = x->right; s->left = x->left; x->parent->right = s; }else{ y = s; s->parent = x->parent; s->left->parent = s; s->left = x->left; x->parent->right = s; } } } } free(x);//destroy and free splay(y, root);//splay y to the new root's position return y; }else{ splay(x, root);//found nothing to delete,but still we should splay return x; } } int main(){ return 0; } |