2014.06.15 20:42
简介：
伸展树是一种介于普通二叉搜索树和AVL树之间的，比较平衡的一种二叉搜索树。它不像AVL树那样总是高度平衡，虽然单次操作的就可能耗费O(n)时间，但连续M次基本操作的时间复杂度能做到O(M * log(N))，M当然不能和1太接近。这种复杂度叫做均摊复杂度，英文叫amortiized complexity。当我学这门课的时候，这个概念我根本不理解，伸展树我也没有动手写过。后来在多个编程题目中的算法分析中，逐渐明白了均摊复杂度的意义。伸展树的一大特点，就是每次要访问一个节点，一定要想办法把它弄到根节点。这个办法，就是“旋转”。如果你明白AVL树的旋转，这个自然也不必多说了。不过，伸展树除了左单旋转、右单旋转、左右双旋转、右左双旋转之外，还用到了左左双旋转，右右双旋转。AVL旋转是为了恢复树的平衡，伸展树的旋转则是为了把一个节点一直旋转到根节点。在我费劲力气实现了AVL树之后，我以为能通过删掉很多代码把它变成伸展树，结果除了不再记录树的高度之外，我没删掉多少代码，还额外增加了两个旋转。事实证明伸展树也是个好想但不好写的结构。
图示：
照理说增删改查都应该给出图示，但我只想用图示说明一个节点是如何被旋转到根节点的。旋转不是为了恢复平衡，但旋转的确可以让一棵树变得更平衡，这也是伸展树高效率的关键——越旋转越平衡。
实现：
1 // My implementation for splay tree, modified from my avl tree. 2 #include <iostream> 3 #include <string> 4 #include <vector> 5 using namespace std; 6 7 struct TreeNode { 8 int val; 9 TreeNode *left; 10 TreeNode *right; 11 TreeNode *parent; 12 TreeNode(int _val): val(_val), left(nullptr), right(nullptr), parent(nullptr) {}; 13 }; 14 15 class SplayTree { 16 public: 17 SplayTree() { 18 m_root = nullptr; 19 } 20 21 bool empty() { 22 return m_root == nullptr; 23 } 24 25 void clear() { 26 _deleteTree(m_root); 27 } 28 29 void insertNode(const int &val) { 30 if (m_root == nullptr) { 31 m_root = new TreeNode(val); 32 return; 33 } 34 35 TreeNode *ptr = _findNode(val); 36 37 if (val == ptr->val) { 38 return; 39 } 40 41 if (val < ptr->val) { 42 ptr->left = new TreeNode(val); 43 ptr->left->parent = ptr; 44 ptr = ptr->left; 45 } else { 46 ptr->right = new TreeNode(val); 47 ptr->right->parent = ptr; 48 ptr = ptr->right; 49 } 50 _splayNode(ptr); 51 } 52 53 void deleteNode(const int &val) { 54 if (m_root == nullptr) { 55 return; 56 } 57 58 TreeNode *par, *cur; 59 60 cur = _findNode(val); 61 if (cur == nullptr || cur->val != val) { 62 return; 63 } 64 // the node is splayed to the root, cur must be m_root. 65 par = cur->parent; 66 67 TreeNode *ptr; 68 69 if (cur->left != nullptr) { 70 ptr = _shiftLeft(cur); 71 return; 72 } 73 74 if (cur->right != nullptr) { 75 ptr = _shiftRight(cur); 76 return; 77 } 78 79 if (par == nullptr) { 80 delete cur; 81 m_root = nullptr; 82 } else if (val < par->val) { 83 delete cur; 84 par->left = nullptr; 85 } else { 86 delete cur; 87 par->right = nullptr; 88 } 89 } 90 91 void updateNode(const int &old_val, const int &new_val) { 92 deleteNode(old_val); 93 insertNode(new_val); 94 } 95 96 bool contains(const int &val) { 97 TreeNode *ptr = _findNode(val); 98 return ptr == nullptr ? false : ptr->val == val ? true : false; 99 } 100 101 string preorderTraversal() { 102 string result; 103 _preorderTraversalRecursive(m_root, result); 104 return result; 105 } 106 107 string inorderTraversal() { 108 string result; 109 _inorderTraversalRecursive(m_root, result); 110 return result; 111 } 112 113 string postorderTraversal() { 114 string result; 115 _postorderTraversalRecursive(m_root, result); 116 return result; 117 } 118 119 ~SplayTree() { 120 clear(); 121 } 122 private: 123 TreeNode *m_root; 124 125 void _deleteTree(TreeNode *&root) { 126 if (root == nullptr) { 127 return; 128 } 129 _deleteTree(root->left); 130 _deleteTree(root->right); 131 delete root; 132 root = nullptr; 133 } 134 135 TreeNode* _findNode(const int &val) { 136 TreeNode *ptr; 137 138 ptr = m_root; 139 while (ptr != nullptr) { 140 if (val == ptr->val) { 141 return ptr; 142 } 143 if (val < ptr->val) { 144 if (ptr->left != nullptr) { 145 ptr = ptr->left; 146 } else { 147 return ptr; 148 } 149 } else { 150 if (ptr->right != nullptr) { 151 ptr = ptr->right; 152 } else { 153 return ptr; 154 } 155 } 156 } 157 if (ptr->val == val) { 158 _splayNode(ptr); 159 return m_root; 160 } 161 162 return ptr; 163 } 164 165 void _preorderTraversalRecursive(const TreeNode *root, string &result) { 166 result.push_back(‘{‘); 167 if (root == nullptr) { 168 // ‘#‘ represents NULL. 169 result.push_back(‘#‘); 170 } else { 171 result.append(to_string(root->val)); 172 _preorderTraversalRecursive(root->left, result); 173 _preorderTraversalRecursive(root->right, result); 174 } 175 result.push_back(‘}‘); 176 } 177 178 void _inorderTraversalRecursive(const TreeNode *root, string &result) { 179 result.push_back(‘{‘); 180 if (root == nullptr) { 181 // ‘#‘ represents NULL. 182 result.push_back(‘#‘); 183 } else { 184 _inorderTraversalRecursive(root->left, result); 185 result.append(to_string(root->val)); 186 _inorderTraversalRecursive(root->right, result); 187 } 188 result.push_back(‘}‘); 189 } 190 191 void _postorderTraversalRecursive(const TreeNode *root, string &result) { 192 result.push_back(‘{‘); 193 if (root == nullptr) { 194 // ‘#‘ represents NULL. 195 result.push_back(‘#‘); 196 } else { 197 _postorderTraversalRecursive(root->left, result); 198 _postorderTraversalRecursive(root->right, result); 199 result.append(to_string(root->val)); 200 } 201 result.push_back(‘}‘); 202 } 203 204 TreeNode *_shiftLeft(TreeNode *root) { 205 TreeNode *cur, *par; 206 207 // root and root->left is guaranteed to be non-empty. 208 par = root; 209 cur = par->left; 210 211 while (cur->right != nullptr) { 212 par = cur; 213 cur = cur->right; 214 } 215 root->val = cur->val; 216 217 if (cur->left != nullptr) { 218 return _shiftLeft(cur); 219 } 220 221 if (cur->right != nullptr) { 222 return _shiftRight(cur); 223 } 224 225 if (cur == par->left) { 226 delete par->left; 227 par->left = nullptr; 228 } else { 229 delete par->right; 230 par->right = nullptr; 231 } 232 233 return par; 234 } 235 236 TreeNode *_shiftRight(TreeNode *root) { 237 TreeNode *cur, *par; 238 239 // root and root->right is guaranteed to be non-empty. 240 par = root; 241 cur = par->right; 242 243 while (cur->left != nullptr) { 244 par = cur; 245 cur = cur->left; 246 } 247 root->val = cur->val; 248 249 if (cur->left != nullptr) { 250 return _shiftLeft(cur); 251 } 252 253 if (cur->right != nullptr) { 254 return _shiftRight(cur); 255 } 256 257 if (cur == par->left) { 258 delete par->left; 259 par->left = nullptr; 260 } else { 261 delete par->right; 262 par->right = nullptr; 263 } 264 265 return par; 266 } 267 268 void _singleRotationLeft(TreeNode *cur) { 269 // Subtree A is deeper than subtree B. 270 // Before rotation: 271 // X 272 // / 273 // Y C 274 // / 275 // A B 276 // ---------- 277 // After rotation: 278 // Y 279 // / 280 // A X 281 // / 282 // B C 283 TreeNode *par = cur->parent; 284 TreeNode *B; 285 TreeNode *X, *Y; 286 287 X = cur; 288 Y = cur->left; 289 B = Y->right; 290 291 Y->right = X; 292 X->parent = Y; 293 X->left = B; 294 if (B != nullptr) { 295 B->parent = Y; 296 } 297 298 if (par == nullptr) { 299 m_root = Y; 300 } else if (par->left == cur) { 301 par->left = Y; 302 } else { 303 par->right = Y; 304 } 305 Y->parent = par; 306 } 307 308 void _singleRotationRight(TreeNode *cur) { 309 // Subtree C is deeper than subtree B. 310 // Before rotation: 311 // X 312 // / 313 // A Y 314 // / 315 // B C 316 // ---------- 317 // After rotation: 318 // Y 319 // / 320 // X C 321 // / 322 // A B 323 TreeNode *par = cur->parent; 324 TreeNode *B; 325 TreeNode *X, *Y; 326 327 X = cur; 328 Y = cur->right; 329 B = Y->left; 330 331 Y->left = X; 332 X->parent = Y; 333 X->right = B; 334 if (B != nullptr) { 335 B->parent = X; 336 } 337 338 if (par == nullptr) { 339 m_root = Y; 340 } else if (par->left == cur) { 341 par->left = Y; 342 } else { 343 par->right = Y; 344 } 345 Y->parent = par; 346 } 347 348 void _doubleRotationLeftLeft(TreeNode *cur) { 349 // This is only for splay tree, not AVL. 350 // Before rotation: 351 // X 352 // / 353 // Y D 354 // / 355 // Z C 356 // / 357 // A B 358 // ---------- 359 // After rotation: 360 // Z 361 // / 362 // A Y 363 // / 364 // B X 365 // / 366 // C D 367 TreeNode *par = cur->parent; 368 TreeNode *B, *C; 369 TreeNode *X, *Y, *Z; 370 371 X = cur; 372 Y = X->left; 373 Z = Y->left; 374 B = Z->right; 375 C = Y->right; 376 377 Z->right = Y; 378 Y->parent = Z; 379 Y->right = X; 380 X->parent = Y; 381 Y->left = B; 382 if (B != nullptr) { 383 B->parent = Y; 384 } 385 X->left = C; 386 if (C != nullptr) { 387 C->parent = X; 388 } 389 390 if (par == nullptr) { 391 m_root = Z; 392 } else if (par->left == cur) { 393 par->left = Z; 394 } else { 395 par->right = Z; 396 } 397 Z->parent = par; 398 } 399 400 void _doubleRotationLeftRight(TreeNode *cur) { 401 // Subtree Z is deeper than subtree A. Single rotation won‘t work, so let‘s use this one instead. 402 // Before rotation: 403 // X 404 // / 405 // Y D 406 // / 407 // A Z 408 // / 409 // B C 410 // ---------- 411 // After rotation: 412 // Z 413 // / 414 // Y X 415 // / \ / 416 // A B C D 417 TreeNode *par = cur->parent; 418 TreeNode *B, *C; 419 TreeNode *X, *Y, *Z; 420 421 X = cur; 422 Y = X->left; 423 Z = Y->right; 424 B = Z->left; 425 C = Z->right; 426 427 Z->left = Y; 428 Y->parent = Z; 429 Z->right = X; 430 X->parent = Z; 431 Y->right = B; 432 if (B != nullptr) { 433 B->parent = X; 434 } 435 X->left = C; 436 if (C != nullptr) { 437 C->parent = X; 438 } 439 440 if (par == nullptr) { 441 m_root = Z; 442 } else if (par->left == cur) { 443 par->left = Z; 444 } else { 445 par->right = Z; 446 } 447 Z->parent = par; 448 } 449 450 void _doubleRotationRightLeft(TreeNode *cur) { 451 // Subtree Z is deeper than subtree D. Single rotation won‘t work, so let‘s use this one instead. 452 // Before rotation: 453 // X 454 // / 455 // A Y 456 // / 457 // Z D 458 // / 459 // B C 460 // ---------- 461 // After rotation: 462 // Z 463 // / 464 // X Y 465 // / \ / 466 // A B C D 467 TreeNode *par = cur->parent; 468 TreeNode *B, *C; 469 TreeNode *X, *Y, *Z; 470 471 X = cur; 472 Y = X->right; 473 Z = Y->left; 474 B = Z->left; 475 C = Z->right; 476 477 Z->left = X; 478 X->parent = Z; 479 Z->right = Y; 480 Y->parent = Z; 481 X->right = B; 482 if (B != nullptr) { 483 B->parent = X; 484 } 485 Y->left = C; 486 if (C != nullptr) { 487 C->parent = Y; 488 } 489 490 if (par == nullptr) { 491 m_root = Z; 492 } else if (par->left == cur) { 493 par->left = Z; 494 } else { 495 par->right = Z; 496 } 497 Z->parent = par; 498 } 499 500 void _doubleRotationRightRight(TreeNode *cur) { 501 // This is only for splay tree, not AVL. 502 // Before rotation: 503 // X 504 // / 505 // A Y 506 // / 507 // B Z 508 // / 509 // C D 510 // ---------- 511 // After rotation: 512 // Z 513 // / 514 // Y D 515 // / 516 // X C 517 // / 518 // A B 519 TreeNode *par = cur->parent; 520 TreeNode *B, *C; 521 TreeNode *X, *Y, *Z; 522 523 X = cur; 524 Y = X->right; 525 Z = Y->right; 526 B = Y->left; 527 C = Z->left; 528 529 Z->left = Y; 530 Y->parent = Z; 531 Y->left = X; 532 X->parent = Y; 533 X->right = B; 534 if (B != nullptr) { 535 B->parent = X; 536 } 537 Y->right = C; 538 if (C != nullptr) { 539 C->parent = Y; 540 } 541 542 if (par == nullptr) { 543 m_root = Z; 544 } else if (par->left == cur) { 545 par->left = Z; 546 } else { 547 par->right = Z; 548 } 549 Z->parent = par; 550 } 551 552 void _splayNode(TreeNode *cur) { 553 if (m_root == nullptr || cur == nullptr) { 554 return; 555 } 556 557 TreeNode *par, *grand; 558 559 while (cur != nullptr && cur->parent != nullptr) { 560 par = cur->parent; 561 grand = par->parent; 562 if (grand == nullptr) { 563 if (par->left == cur) { 564 _singleRotationLeft(par); 565 } else { 566 _singleRotationRight(par); 567 } 568 return; 569 } 570 if (grand->left == par) { 571 if (par->left == cur) { 572 _doubleRotationLeftLeft(grand); 573 } else { 574 _doubleRotationLeftRight(grand); 575 } 576 } else { 577 if (par->left == cur) { 578 _doubleRotationRightLeft(grand); 579 } else { 580 _doubleRotationRightRight(grand); 581 } 582 } 583 } 584 } 585 }; 586 587 int main() 588 { 589 SplayTree tree; 590 591 tree.clear(); 592 tree.insertNode(1); 593 cout << tree.preorderTraversal() << endl; 594 tree.insertNode(2); 595 cout << tree.preorderTraversal() << endl; 596 tree.insertNode(3); 597 cout << tree.preorderTraversal() << endl; 598 tree.insertNode(4); 599 cout << tree.preorderTraversal() << endl; 600 tree.insertNode(5); 601 cout << tree.preorderTraversal() << endl; 602 tree.insertNode(6); 603 cout << tree.preorderTraversal() << endl; 604 // until now the tree is skewed. 605 // look at this step. 606 tree.insertNode(-1); 607 cout << tree.preorderTraversal() << endl; 608 tree.deleteNode(6); 609 cout << tree.preorderTraversal() << endl; 610 tree.deleteNode(5); 611 cout << tree.preorderTraversal() << endl; 612 tree.deleteNode(4); 613 cout << tree.preorderTraversal() << endl; 614 tree.deleteNode(3); 615 cout << tree.preorderTraversal() << endl; 616 tree.deleteNode(2); 617 cout << tree.preorderTraversal() << endl; 618 tree.deleteNode(1); 619 cout << tree.preorderTraversal() << endl; 620 621 return 0; 622 }