首页 > 代码库 > 《数据结构与算法分析：C语言描述》复习——第四章“树”——伸展树
《数据结构与算法分析：C语言描述》复习——第四章“树”——伸展树
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 // X272 // / 273 // Y C274 // / 275 // A B276 // ----------277 // After rotation:278 // Y279 // / 280 // A X281 // / 282 // B C283 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 // X312 // / 313 // A Y314 // / 315 // B C316 // ----------317 // After rotation:318 // Y319 // / 320 // X C321 // / 322 // A B323 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 // X352 // / 353 // Y D354 // / 355 // Z C356 // / 357 // A B358 // ----------359 // After rotation:360 // Z361 // / 362 // A Y363 // / 364 // B X365 // / 366 // C D367 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 // X404 // / 405 // Y D406 // / 407 // A Z408 // / 409 // B C410 // ----------411 // After rotation:412 // Z413 // / 414 // Y X415 // / \ / 416 // A B C D417 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 // X454 // / 455 // A Y456 // / 457 // Z D458 // / 459 // B C460 // ----------461 // After rotation:462 // Z463 // / 464 // X Y465 // / \ / 466 // A B C D467 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 // X504 // / 505 // A Y506 // / 507 // B Z508 // / 509 // C D510 // ----------511 // After rotation:512 // Z513 // / 514 // Y D515 // / 516 // X C517 // / 518 // A B519 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 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。