一、定义。

1.1 BST

　　二叉搜索树，也称有序二叉树,排序二叉树，是指一棵空树或者具有下列性质的二叉树：

　　① 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

　　② 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

　　③ 任意节点的左、右子树也分别为二叉查找树。

　　④ 没有键值相等的节点。

1.2 AVL Tree

　　平衡二叉树定义(AVL)：它或者是一颗空树，或者具有以下性质的二叉树：它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。

　　平衡因子(bf)：结点的左子树的深度减去右子树的深度。

　　保持平衡是依赖于旋转操作，分为LL, RR, LR, RL四种情况。

　　LL单旋即右旋。

　　

1.3 Splay Tree

　　伸展树的出发点是这样的：考虑到局部性原理（刚被访问的内容下次可能仍会被访问，查找次数多的内容可能下一次会被访问），为了使整个查找时间更小，被查频率高的那些节点应当经常处于靠近树根的位置。这样，很容易得想到以下这个方案：每次查找节点之后对树进行重构，把被查找的节点搬移到树根，这种自调整形式的二叉查找树就是伸展树。每次对伸展树进行操作后，它均会通过旋转的方法把被访问节点旋转到树根的位置。

　　为了将当前被访问节点旋转到树根，我们通常将节点自底向上旋转，直至该节点成为树根为止。“旋转”的巧妙之处就是在不打乱数列中数据大小关系（指中序遍历结果是全序的）情况下，所有基本操作的平摊复杂度仍为O（log n）。

　　伸展树主要有三种旋转操作，分别为单旋转，一字形旋转和之字形旋转。为了便于解释，我们假设当前被访问节点为X，X的父亲节点为Y（如果X的父亲节点存在），X的祖父节点为Z（如果X的祖父节点存在）。这里的单旋与之字形旋转与AVL树是一致的，因此这里只列出Zig-Zig。

　　

 

　　Splay操作可以自底向上也可以自顶向下，我只实现了自底向上的算法，自顶向下以后有机会再补充，因为每次操作都需要把操作的结点翻转到根，所以用Zig-Zig代替单旋，每次上升两层，如果根节点恰好是父节点，则此时只需要一次单旋。

 

二、复杂度分析。

　　AVL无论是在顺序逆序或者随机插入删除的情况下效果都不错，而Splay在按照顺序或者逆序的情况下效果比较好，因为预测准确，而随机则无法预测，所做的Splay操作都是多余的，所以比较慢，AVL 和 Splay 哪个更合适需要具体情况具体分析。

2.1 BST

Algorithm AverageWorst caseSpace O(n)O(n)Search O(log n)O(n)Insert O(log n)O(n)Delete O(log n)O(n)

2.2 AVL Tree

Algorithm AverageWorst caseSpace O(n)O(n)Search O(log n)O(log n)Insert O(log n)O(log n)Delete O(log n)O(log n)

2.3 Splay Tree

Algorithm AverageWorst caseSpace O(n)O(n)Search O(log n)amortized O(log n)Insert O(log n)amortized O(log n)Delete O(log n)amortized O(log n)

 

三、实现。

　　水平有限，写的比较啰嗦，见谅。

1 #include <iostream> 2 using namespace std; 3 // Binery Search Tree Node 4 class BSTreeNode { 5 public: 6 int data; 7 BSTreeNode* leftChild; 8 BSTreeNode* rightChild; 9 BSTreeNode(int value): data(value), leftChild(NULL), rightChild(NULL){} 10 }; 11 // AVL Tree Node 12 class AVLTreeNode { 13 public: 14 int data; 15 // The height of node 16 int height; 17 AVLTreeNode* leftChild; 18 AVLTreeNode* rightChild; 19 AVLTreeNode(int value): data(value), height(0), leftChild(NULL), rightChild(NULL){} 20 }; 21 // Splay Tree Node 22 class SplayTreeNode { 23 public: 24 int data; 25 // The pointer to parent 26 SplayTreeNode* parent; 27 SplayTreeNode* leftChild; 28 SplayTreeNode* rightChild; 29 SplayTreeNode(int value): data(value), parent(NULL), leftChild(NULL), rightChild(NULL){} 30 }; 31 // Preorder traversal 32 void previsit(SplayTreeNode* T){ 33 if(T){ 34 cout<<T->data<<' '; 35 previsit(T->leftChild); 36 previsit(T->rightChild); 37 } 38 39 } 40 // Preorder traversal 41 void previsit(BSTreeNode* T){ 42 if(T!=NULL){ 43 cout<<T->data<<' '; 44 previsit(T->leftChild); 45 previsit(T->rightChild); 46 } 47 } 48 // Preorder traversal 49 void previsit(AVLTreeNode* T){ 50 if(T){ 51 cout<<T->data<<' '; 52 previsit(T->leftChild); 53 previsit(T->rightChild); 54 } 55 56 } 57 // Find the minimun element 58 BSTreeNode* BSTreeFindMin(BSTreeNode* T) { 59 if (T == NULL) { 60 return NULL; 61 } else if (T->leftChild == NULL) { 62 return T; 63 } else { 64 return BSTreeFindMin(T->leftChild); 65 } 66 } 67 // Insert operation of Binery Search Tree 68 BSTreeNode* BSTreeInsert(int value, BSTreeNode* T) { 69 if (T == NULL) { 70 T = new BSTreeNode(value); 71 } else { 72 // If value is smaller than element 73 if (value < T->data) { 74 T->leftChild = BSTreeInsert(value, T->leftChild); 75 } 76 // If value is larger than element 77 else if (value > T->data) { 78 T->rightChild = BSTreeInsert(value, T->rightChild); 79 } 80 } 81 return T; 82 } 83 // Delete operation of Binery Search Tree 84 BSTreeNode* BSTreeDelete(int value, BSTreeNode* T) { 85 if (T == NULL) { 86 return NULL; 87 } 88 // If value is smaller than element 89 else if (value < T->data) { 90 T->leftChild = BSTreeDelete(value, T->leftChild); 91 } 92 // If value is larger than element 93 else if (value > T->data) { 94 T->rightChild = BSTreeDelete(value, T->rightChild); 95 } 96 // If value is equal to element 97 else { 98 if (T->leftChild && T->rightChild) { 99 // Two children 100 BSTreeNode* tmp = BSTreeFindMin(T->rightChild); 101 T->data = tmp->data; 102 //delete tmp; 103 T->rightChild = BSTreeDelete(T->data, T->rightChild); 104 } else { 105 // One or no child 106 if (T->leftChild) { 107 T = T->leftChild; 108 } else if (T->rightChild) { 109 T = T->rightChild; 110 } else { 111 T = NULL; 112 } 113 } 114 } 115 return T; 116 } 117 // Get the height of AVL Tree 118 int getHeight(AVLTreeNode* T) { 119 if (T == NULL) { 120 return -1; 121 } else { 122 return T->height; 123 } 124 } 125 // Get the larger one element 126 int Max(int x, int y) { 127 return (x > y) ? x : y; 128 } 129 // LL Rotation 130 AVLTreeNode* SingleRotateWithLeft(AVLTreeNode* K2) { 131 AVLTreeNode* K1; 132 133 K1 = K2->leftChild; 134 K2->leftChild = K1->rightChild; 135 K1->rightChild = K2; 136 137 // Update the height of node 138 K2->height = Max(getHeight(K2->leftChild), getHeight(K2->rightChild)) + 1; 139 K1->height = Max(getHeight(K1->leftChild), getHeight(K1->rightChild)) + 1; 140 return K1; 141 } 142 // RR Rotation 143 AVLTreeNode* SingleRotateWithRight(AVLTreeNode* K2) { 144 AVLTreeNode* K1; 145 146 K1 = K2->rightChild; 147 K2->rightChild = K1->leftChild; 148 K1->leftChild = K2; 149 150 // Update the height of node 151 K2->height = Max(getHeight(K2->leftChild), getHeight(K2->rightChild)) + 1; 152 K1->height = Max(getHeight(K1->leftChild), getHeight(K1->rightChild)) + 1; 153 return K1; 154 } 155 // LR Rotation 156 AVLTreeNode* DoubleRotateWithLeft(AVLTreeNode* K3) { 157 K3->leftChild = SingleRotateWithRight(K3->leftChild); 158 return SingleRotateWithLeft(K3); 159 } 160 // RL Rotation 161 AVLTreeNode* DoubleRotateWithRight(AVLTreeNode* K3) { 162 K3->rightChild = SingleRotateWithLeft(K3->rightChild); 163 return SingleRotateWithRight(K3); 164 } 165 // Find the minimum element 166 AVLTreeNode* AVLTreeFindMin(AVLTreeNode* T) { 167 if (T == NULL) { 168 return NULL; 169 } else if (T->leftChild == NULL) { 170 return T; 171 } else { 172 return AVLTreeFindMin(T->leftChild); 173 } 174 } 175 // Insert operation of AVL Tree 176 AVLTreeNode* AVLTreeInsert(int value, AVLTreeNode* T) { 177 if (T == NULL) { 178 T = new AVLTreeNode(value); 179 return T; 180 } else { 181 // If value is smaller than element 182 if (value < T->data) { 183 T->leftChild = AVLTreeInsert(value, T->leftChild); 184 // If the balance is broken 185 if (getHeight(T->leftChild) - getHeight(T->rightChild) == 2) { 186 if (value < T->leftChild->data) { 187 // LL Rotation 188 T = SingleRotateWithLeft(T); 189 } else { 190 // LR Rotation 191 T = DoubleRotateWithLeft(T); 192 } 193 } 194 } 195 // If value is larger than element 196 else if (value > T->data) { 197 T->rightChild = AVLTreeInsert(value, T->rightChild); 198 // If the balance is broken 199 if (getHeight(T->rightChild) - getHeight(T->leftChild) == 2) { 200 if (value > T->rightChild->data) { 201 // RR Rotation 202 T = SingleRotateWithRight(T); 203 } else { 204 // RL Rotation 205 T = DoubleRotateWithRight(T); 206 } 207 } 208 } 209 210 // Update the height of node 211 if (T) { 212 T->height = Max(getHeight(T->leftChild), getHeight(T->rightChild)) + 1; 213 } 214 return T; 215 } 216 } 217 // Delete operation of AVL Tree 218 AVLTreeNode* AVLTreeDelete(int value, AVLTreeNode* T) { 219 if (T == NULL) { 220 return NULL; 221 } else { 222 // If value is smaller than element 223 if (value < T->data) { 224 T->leftChild = AVLTreeDelete(value, T->leftChild); 225 // If the balance is broken 226 if (getHeight(T->rightChild) - getHeight(T->leftChild) == 2) { 227 // Delete is similar to insert 228 // We can assume the unbalance is caused by insert an element 229 if (getHeight(T->rightChild->rightChild) >= getHeight(T->rightChild->leftChild)) { 230 // RR Rotation 231 T = SingleRotateWithRight(T); 232 } else { 233 // RL Rotation 234 T = DoubleRotateWithRight(T); 235 } 236 } 237 } 238 // If value is larger than element 239 else if (value > T->data) { 240 T->rightChild = AVLTreeDelete(value, T->rightChild); 241 // If the balance is broken 242 if (getHeight(T->leftChild) - getHeight(T->rightChild) == 2) { 243 // Delete is similar to insert 244 // We can assume the unbalance is caused by insert an element 245 if (getHeight(T->leftChild->leftChild) >= getHeight(T->leftChild->rightChild)) { 246 // LL Rotation 247 T = SingleRotateWithLeft(T); 248 } else { 249 // LR Rotation 250 T = DoubleRotateWithLeft(T); 251 } 252 } 253 } 254 // If value is equal to element 255 else { 256 if (T->leftChild && T->rightChild) { 257 // Two children 258 AVLTreeNode* tmp = AVLTreeFindMin(T->rightChild); 259 T->data = tmp->data; 260 //delete tmp; 261 T->rightChild = AVLTreeDelete(T->data, T->rightChild); 262 } else { 263 // One or no child 264 if (T->leftChild) { 265 T = T->leftChild; 266 } else if (T->rightChild) { 267 T = T->rightChild; 268 } else { 269 T = NULL; 270 } 271 } 272 } 273 } 274 275 // Update the height of node 276 if (T) { 277 T->height = Max(getHeight(T->leftChild), getHeight(T->rightChild)) + 1; 278 } 279 return T; 280 } 281 // LL Rotation of Splay Tree 282 SplayTreeNode* SplaySingleRotateWithLeft(SplayTreeNode* K2) { 283 // It is similar to AVL Tree 284 // But we must update the parent of node 285 SplayTreeNode* K1 = K2->leftChild; 286 SplayTreeNode* P = K2->parent; 287 K2->leftChild = K1->rightChild; 288 if(K2->leftChild){ 289 K2->leftChild->parent = K2; 290 } 291 K1->rightChild = K2; 292 K1->rightChild->parent = K1; 293 K1->parent = P; 294 if (P != NULL) { 295 if (P->leftChild == K2) { 296 P->leftChild = K1; 297 } else { 298 P->rightChild = K1; 299 } 300 } 301 return K1; 302 } 303 // RR Rotation of Splay Tree 304 SplayTreeNode* SplaySingleRotateWithRight(SplayTreeNode* K2) { 305 // It is similar to AVL Tree 306 // But we must update the parent of node 307 SplayTreeNode* K1 = K2->rightChild; 308 SplayTreeNode* P = K2->parent; 309 K2->rightChild = K1->leftChild; 310 if(K2->rightChild){ 311 K2->rightChild->parent = K2; 312 } 313 K1->leftChild = K2; 314 if(K1->leftChild){ 315 K1->leftChild->parent = K1; 316 } 317 318 K1->parent = P; 319 if (P != NULL) { 320 if (P->leftChild == K2) { 321 P->leftChild = K1; 322 } else { 323 P->rightChild = K1; 324 } 325 } 326 return K1; 327 } 328 // LR Rotation 329 SplayTreeNode* SplayDoubleRotateWithLeft(SplayTreeNode* K3) { 330 K3->leftChild = SplaySingleRotateWithRight(K3->leftChild); 331 return SplaySingleRotateWithLeft(K3); 332 } 333 // RL Rotation 334 SplayTreeNode* SplayDoubleRotateWithRight(SplayTreeNode* K3) { 335 K3->rightChild = SplaySingleRotateWithLeft(K3->rightChild); 336 return SplaySingleRotateWithRight(K3); 337 } 338 // L-Zig-Zig 339 SplayTreeNode* ZigZigWithLeft(SplayTreeNode* K3) { 340 SplayTreeNode* parent = K3->parent; 341 SplayTreeNode* K2 = K3->leftChild; 342 SplayTreeNode* K1 = K2->leftChild; 343 344 K3->leftChild = K2->rightChild; 345 if (K2->rightChild != NULL) { 346 K3->leftChild->parent = K3; 347 } 348 K2->rightChild = K3; 349 K2->rightChild->parent = K2; 350 K2->leftChild = K1->rightChild; 351 if (K1->rightChild != NULL) { 352 K2->leftChild->parent = K2; 353 } 354 K1->rightChild = K2; 355 K1->rightChild->parent = K1; 356 K1->parent = parent; 357 if (parent != NULL) { 358 if (parent->leftChild == K3) { 359 parent->leftChild = K1; 360 } else { 361 parent->rightChild = K1; 362 } 363 } 364 return K1; 365 } 366 // R-Zig-Zig 367 SplayTreeNode* ZigZigWithRight(SplayTreeNode* K3) { 368 SplayTreeNode* parent = K3->parent; 369 SplayTreeNode* K2 = K3->leftChild; 370 SplayTreeNode* K1 = K2->leftChild; 371 372 K3->rightChild = K2->leftChild; 373 if (K2->leftChild != NULL) { 374 K3->rightChild->parent = K3; 375 } 376 K2->leftChild = K3; 377 K2->leftChild->parent = K2; 378 K2->rightChild = K1->leftChild; 379 if (K1->leftChild != NULL) { 380 K2->rightChild->parent = K2; 381 } 382 K1->leftChild = K2; 383 K1->leftChild->parent = K1; 384 K1->parent = parent; 385 if (parent != NULL) { 386 if (parent->leftChild == K3) { 387 parent->leftChild = K1; 388 } else { 389 parent->rightChild = K1; 390 } 391 } 392 return K1; 393 } 394 // Insert operation of Splay Tree without Splay 395 // It is similar to insert operation of Binery Search Tree 396 SplayTreeNode* PreInsert(int value, SplayTreeNode* T) { 397 if (T == NULL) { 398 T = new SplayTreeNode(value); 399 } else { 400 if (value < T->data) { 401 T->leftChild = PreInsert(value, T->leftChild); 402 // Update the parent of node 403 T->leftChild->parent = T; 404 } else if (value > T->data) { 405 T->rightChild = PreInsert(value, T->rightChild); 406 // Update the parent of node 407 T->rightChild->parent = T; 408 } 409 } 410 return T; 411 } 412 // Find the maximum element 413 SplayTreeNode* SplayTreeFindMax(SplayTreeNode* T) { 414 if (T == NULL) { 415 return NULL; 416 } else if (T->rightChild == NULL) { 417 return T; 418 } else { 419 return SplayTreeFindMax(T->rightChild); 420 } 421 } 422 // Find the minimum element 423 SplayTreeNode* SplayTreeFindMin(SplayTreeNode* T) { 424 if (T == NULL) { 425 return NULL; 426 } else if (T->leftChild == NULL) { 427 return T; 428 } else { 429 return SplayTreeFindMin(T->leftChild); 430 } 431 } 432 // Find the element and return the node 433 SplayTreeNode* Find(int value, SplayTreeNode* T) { 434 if (T == NULL) { 435 return NULL; 436 } else if (T->data == value) { 437 return T; 438 } else if (T->data > value) { 439 return Find(value, T->leftChild); 440 } else { 441 return Find(value, T->rightChild); 442 } 443 } 444 // Splay operation of Splay Tree 445 SplayTreeNode* Splay(int value, SplayTreeNode* T) { 446 SplayTreeNode* K = Find(value, T); 447 // Parent node 448 SplayTreeNode* P = NULL; 449 // Grandparent node 450 SplayTreeNode* GP = NULL; 451 // If node doesn't exist 452 if (K == NULL) { 453 return T; 454 } 455 // Do rotation until K arrives at root or is the child of root 456 while (T->leftChild != K && T->rightChild != K) { 457 P = K->parent; 458 // Break the loop if just need single rotation 459 if(P==NULL||P->parent==NULL){ 460 break; 461 } 462 GP = P->parent; 463 if (GP->leftChild == P && P->leftChild == K) { 464 // L-Zig-Zig 465 ZigZigWithLeft(GP); 466 } else if (GP->leftChild == P && P->rightChild == K) { 467 // LR Rotation 468 SplayDoubleRotateWithLeft(GP); 469 } else if (GP->rightChild == P && P->leftChild == K) { 470 // RL Rotation 471 SplayDoubleRotateWithRight(GP); 472 } else if (GP->rightChild == P && P->rightChild == K) { 473 // R-Zig-Zig 474 ZigZigWithRight(GP); 475 } 476 // Return the new root if GP == T 477 if(GP == T){ 478 return K; 479 } 480 } 481 if (T->leftChild == K) { 482 // LL Rotation 483 T = SplaySingleRotateWithLeft(T); 484 } else if (T->rightChild == K) { 485 // RR Rotation 486 T = SplaySingleRotateWithRight(T); 487 } 488 return T; 489 } 490 // Insert operation of Splay Tree 491 SplayTreeNode* SplayTreeInsert(int value, SplayTreeNode* T) { 492 // First insert the element just like Binery Search Tree 493 T = PreInsert(value, T); 494 // Then do the Splay 495 T = Splay(value, T); 496 } 497 // Splay operation of Splay Tree 498 SplayTreeNode* Splay(SplayTreeNode* node, SplayTreeNode* T) { 499 SplayTreeNode* K = node; 500 // Parent node 501 SplayTreeNode* P = NULL; 502 // Grandparent node 503 SplayTreeNode* GP = NULL; 504 // If node doesn't exist 505 if(K == NULL){ 506 return T; 507 } 508 // Do rotation until K arrives at root or is the child of root 509 while (T->leftChild != K && T->rightChild != K) { 510 P = K->parent; 511 // Break the loop if just need single rotation 512 if(P==NULL||P->parent==NULL){ 513 break; 514 } 515 GP = P->parent; 516 if (GP->leftChild == P && P->leftChild == K) { 517 // L-Zig-Zig 518 ZigZigWithLeft(GP); 519 } else if (GP->leftChild == P && P->rightChild == K) { 520 // LR Rotation 521 SplayDoubleRotateWithLeft(GP); 522 } else if (GP->rightChild == P && P->leftChild == K) { 523 // RL Rotation 524 SplayDoubleRotateWithRight(GP); 525 } else if (GP->rightChild == P && P->rightChild == K) { 526 // R-Zig-Zig 527 ZigZigWithRight(GP); 528 } 529 // Return the new root if GP == T 530 if(GP == T){ 531 return K; 532 } 533 } 534 if (T->leftChild == K) { 535 // LL Rotation 536 T = SplaySingleRotateWithLeft(T); 537 } else if (T->rightChild == K) { 538 // RR Rotation 539 T = SplaySingleRotateWithRight(T); 540 } 541 return T; 542 } 543 // Delete operation of Splay Tree 544 SplayTreeNode* SplayTreeDelete(int value, SplayTreeNode* T) { 545 // If T is NULL 546 if (!T) { 547 return NULL; 548 } 549 // First do the Splay operation 550 T = Splay(value, T); 551 // Leftchild of root 552 SplayTreeNode* L = T->leftChild; 553 // Rightchild of root 554 SplayTreeNode* R = T->rightChild; 555 // If the tree doesn't have rightchild 556 if(R==NULL){ 557 R = L; 558 if (L) { 559 R->parent = NULL; 560 } 561 } 562 else{ 563 R->parent = NULL; 564 // Find the minimum element of R 565 R = Splay(SplayTreeFindMin(R), R); 566 R-> leftChild = L; 567 if(L){ 568 L->parent = R; 569 } 570 } 571 // Delete the element 572 delete T; 573 return R; 574 }

 

转载于:https://www.cnblogs.com/lyf520/p/8684293.html