首页 > 代码库 > 《数据结构与算法分析：C语言描述》复习——第四章“树”——AVL树
《数据结构与算法分析：C语言描述》复习——第四章“树”——AVL树
2014.06.15 16:22
简介：
AVL树是一种高度平衡的二叉搜索树，其命名源自于联合发明算法的三位科学家的名字的首字母。此处“平衡”的定义是：任意节点的左右子树的高度相差不超过1。有了这个平衡的性质，使得AVL树的高度H总是接近log(N)，因此各种增删改查的操作的复杂度能够保证在对数级别。没有bad case是AVL树与普通的二叉搜索树的最大区别。为了实现平衡性质，我们需要记录每个节点的高度（或者平衡因子）来检测不平衡的情况。为了修正高度不平衡，需要用到“旋转”的方法，分为单旋转和双旋转，左右总共四种旋转。下面的图解会给出旋转的示意，这个是AVL树的关键算法。AVL树看起来特简单，但你动手写写就知实现一棵AVL树有多麻烦。如果你能用200行写出能增删改查的AVL树，请留言给我点提示。我花了一天想思路，并犹豫要不要放弃。又花了一天写代码和自测。终于用500多行代码写完了自己的第一棵AVL树。如果面试里需要平衡查找结构，你最好试试树堆或者跳表，千万别想AVL或者伸展树。不需要自己写的话，还是<map>吧。
图示：
一棵平衡的二叉树：
查找不涉及数据的修改，因此和普通二叉搜索树完全一样：
插入21之后，树的平衡被破坏了，而且不止一个点出现了不平衡：
当平衡被破坏之后，需要从第一个不平衡的地方开始旋转，然后逐层往上继续修正。此处给出一次旋转之后的结果：
一次旋转不一定能修复N个不平衡的节点，因此要从第一个不平衡的节点往上检查所有需要修复的节点。
下面给出四种旋转的示意图，代码的注释中也有类似的示意，以便读者能够直观地想象旋转中发生的变形（数据结构最大的魅力，就在于它们动起来比变形金刚的花样还多）。
左单旋转：
右单旋转：
左右双旋转：
右左双旋转：
实现：
为了向上检查，我引入了parent指针指向二叉树节点的父节点。为了检查平衡状况，我是用了height成员表示树的高度。虽然平衡因子好像更规范，但当时尝试用平衡因子的时候思路始终理不清楚，所以选择了高度作为依据。下面的实现中其实有不少代码是供测试用的，比如三种遍历。这些debug代码对于学习AVL树有帮助作用，如果你有兴趣可以自己运行查看结果。
插入和删除都会影响树的平衡性，因此对于发生变动的节点，需要更新其高度，以便检测平衡性并进行旋转。AVL树的删除挺难想的，需要在草稿纸上比划半天才能想明白。
请看代码。
1 // My implementation for avl tree. 2 #include <iostream> 3 #include <string> 4 #include <vector> 5 using namespace std; 6 7 struct TreeNode { 8 int val; 9 int height; 10 TreeNode *left; 11 TreeNode *right; 12 TreeNode *parent; 13 TreeNode(int _val): val(_val), height(1), left(nullptr), right(nullptr), parent(nullptr) {}; 14 }; 15 16 class AVLTree { 17 public: 18 AVLTree() { 19 m_root = nullptr; 20 } 21 22 bool empty() { 23 return m_root == nullptr; 24 } 25 26 void clear() { 27 _deleteTree(m_root); 28 } 29 30 void insertNode(const int &val) { 31 if (m_root == nullptr) { 32 m_root = new TreeNode(val); 33 return; 34 } 35 36 TreeNode *ptr = _findNode(val); 37 38 if (val == ptr->val) { 39 return; 40 } 41 42 if (val < ptr->val) { 43 ptr->left = new TreeNode(val); 44 ptr->left->parent = ptr; 45 } else if (val > ptr->val) { 46 ptr->right = new TreeNode(val); 47 ptr->right->parent = ptr; 48 } 49 50 int hl, hr; 51 TreeNode *ptr2; 52 while (ptr != nullptr) { 53 ptr2 = ptr->parent; 54 _getHeight(ptr); 55 hl = _height(ptr->left); 56 hr = _height(ptr->right); 57 switch(hl - hr) { 58 case -2: 59 switch (_height(ptr->right->left) - _height(ptr->right->right)) { 60 case -1: 61 _singleRotationRight(ptr); 62 break; 63 case +1: 64 _doubleRotationRightLeft(ptr); 65 break; 66 } 67 break; 68 case +2: 69 switch (_height(ptr->left->left) - _height(ptr->left->right)) { 70 case -1: 71 _doubleRotationLeftRight(ptr); 72 break; 73 case +1: 74 _singleRotationLeft(ptr); 75 break; 76 } 77 break; 78 } 79 ptr = ptr2; 80 } 81 } 82 83 void deleteNode(const int &val) { 84 if (m_root == nullptr) { 85 return; 86 } 87 88 TreeNode *par, *cur; 89 90 cur = _findNode(val); 91 if (cur == nullptr || cur->val != val) { 92 return; 93 } 94 par = cur->parent; 95 96 TreeNode *ptr; 97 do { 98 if (cur->left != nullptr) { 99 ptr = _shiftLeft(cur);100 break;101 }102 103 if (cur->right != nullptr) {104 ptr = _shiftRight(cur);105 break;106 }107 108 if (par == nullptr) {109 delete cur;110 m_root = nullptr;111 } else if (val < par->val) {112 delete cur;113 par->left = nullptr;114 } else {115 delete cur;116 par->right = nullptr;117 }118 ptr = par;119 } while (0);120 121 int hl, hr;122 TreeNode *ptr2;123 while (ptr != nullptr) {124 ptr2 = ptr->parent;125 _getHeight(ptr);126 hl = _height(ptr->left);127 hr = _height(ptr->right);128 switch(hl - hr) {129 case -2:130 switch (_height(ptr->right->left) - _height(ptr->right->right)) {131 case -1:132 _singleRotationRight(ptr);133 break;134 case +1:135 _doubleRotationRightLeft(ptr);136 break;137 }138 break;139 case +2:140 switch (_height(ptr->left->left) - _height(ptr->left->right)) {141 case -1:142 _doubleRotationLeftRight(ptr);143 break;144 case +1:145 _singleRotationLeft(ptr);146 break;147 }148 break;149 }150 ptr = ptr2;151 }152 }153 154 void updateNode(const int &old_val, const int &new_val) {155 deleteNode(old_val);156 insertNode(new_val);157 }158 159 bool contains(const int &val) {160 TreeNode *ptr = _findNode(val);161 return ptr == nullptr ? false : ptr->val == val ? true : false;162 }163 164 string preorderTraversal() {165 string result;166 _preorderTraversalRecursive(m_root, result);167 return result;168 }169 170 string inorderTraversal() {171 string result;172 _inorderTraversalRecursive(m_root, result);173 return result;174 }175 176 string postorderTraversal() {177 string result;178 _postorderTraversalRecursive(m_root, result);179 return result;180 }181 182 ~AVLTree() {183 clear();184 }185 private:186 TreeNode *m_root;187 188 void _deleteTree(TreeNode *&root) {189 if (root == nullptr) {190 return;191 }192 _deleteTree(root->left);193 _deleteTree(root->right);194 delete root;195 root = nullptr;196 }197 198 TreeNode* _findNode(const int &val) {199 TreeNode *ptr;200 201 ptr = m_root;202 while (ptr != nullptr) {203 if (val == ptr->val) {204 return ptr;205 }206 if (val < ptr->val) {207 if (ptr->left != nullptr) {208 ptr = ptr->left;209 } else {210 return ptr;211 }212 } else {213 if (ptr->right != nullptr) {214 ptr = ptr->right;215 } else {216 return ptr;217 }218 }219 }220 return ptr;221 }222 223 void _preorderTraversalRecursive(const TreeNode *root, string &result) {224 result.push_back(‘{‘);225 if (root == nullptr) {226 // ‘#‘ represents NULL.227 result.push_back(‘#‘);228 } else {229 result.append(to_string(root->val));230 _preorderTraversalRecursive(root->left, result);231 _preorderTraversalRecursive(root->right, result);232 }233 result.push_back(‘}‘);234 }235 236 void _inorderTraversalRecursive(const TreeNode *root, string &result) {237 result.push_back(‘{‘);238 if (root == nullptr) {239 // ‘#‘ represents NULL.240 result.push_back(‘#‘);241 } else {242 _inorderTraversalRecursive(root->left, result);243 result.append(to_string(root->val));244 _inorderTraversalRecursive(root->right, result);245 }246 result.push_back(‘}‘);247 }248 249 void _postorderTraversalRecursive(const TreeNode *root, string &result) {250 result.push_back(‘{‘);251 if (root == nullptr) {252 // ‘#‘ represents NULL.253 result.push_back(‘#‘);254 } else {255 _postorderTraversalRecursive(root->left, result);256 _postorderTraversalRecursive(root->right, result);257 result.append(to_string(root->val));258 }259 result.push_back(‘}‘);260 }261 262 TreeNode *_shiftLeft(TreeNode *root) {263 TreeNode *cur, *par;264 265 // root and root->left is guaranteed to be non-empty.266 par = root;267 cur = par->left;268 269 while (cur->right != nullptr) {270 par = cur;271 cur = cur->right;272 }273 root->val = cur->val;274 275 if (cur->left != nullptr) {276 return _shiftLeft(cur);277 }278 279 if (cur->right != nullptr) {280 return _shiftRight(cur);281 }282 283 if (cur == par->left) {284 delete par->left;285 par->left = nullptr;286 } else {287 delete par->right;288 par->right = nullptr;289 }290 291 return par;292 }293 294 TreeNode *_shiftRight(TreeNode *root) {295 TreeNode *cur, *par;296 297 // root and root->right is guaranteed to be non-empty.298 par = root;299 cur = par->right;300 301 while (cur->left != nullptr) {302 par = cur;303 cur = cur->left;304 }305 root->val = cur->val;306 307 if (cur->left != nullptr) {308 return _shiftLeft(cur);309 }310 311 if (cur->right != nullptr) {312 return _shiftRight(cur);313 }314 315 if (cur == par->left) {316 delete par->left;317 par->left = nullptr;318 } else {319 delete par->right;320 par->right = nullptr;321 }322 323 return par;324 }325 326 int _max(const int &x, const int &y) {327 return x > y ? x : y;328 }329 330 int _height(const TreeNode *ptr) {331 return ptr == nullptr ? 0 : ptr->height;332 }333 334 void _getHeight(TreeNode *ptr) {335 if (ptr == nullptr) {336 return;337 }338 ptr->height = _max(_height(ptr->left), _height(ptr->right)) + 1;339 }340 341 void _singleRotationLeft(TreeNode *cur) {342 // Subtree A is deeper than subtree B.343 // Before rotation:344 // X345 // / 346 // Y C347 // / 348 // A B349 // ----------350 // After rotation:351 // Y352 // / 353 // A X354 // / 355 // B C356 TreeNode *par = cur->parent;357 TreeNode *B;358 TreeNode *X, *Y;359 360 X = cur;361 Y = cur->left;362 B = Y->right;363 364 Y->right = X;365 X->parent = Y;366 X->left = B;367 if (B != nullptr) {368 B->parent = Y;369 }370 371 if (par == nullptr) {372 m_root = Y;373 } else if (par->left == cur) {374 par->left = Y;375 } else {376 par->right = Y;377 }378 Y->parent = par;379 380 _getHeight(X);381 _getHeight(Y);382 _getHeight(par);383 }384 385 void _singleRotationRight(TreeNode *cur) {386 // Subtree C is deeper than subtree B.387 // Before rotation:388 // X389 // / 390 // A Y391 // / 392 // B C393 // ----------394 // After rotation:395 // Y396 // / 397 // X C398 // / 399 // A B400 TreeNode *par = cur->parent;401 TreeNode *B;402 TreeNode *X, *Y;403 404 X = cur;405 Y = cur->right;406 B = Y->left;407 408 Y->left = X;409 X->parent = Y;410 X->right = B;411 if (B != nullptr) {412 B->parent = X;413 }414 415 if (par == nullptr) {416 m_root = Y;417 } else if (par->left == cur) {418 par->left = Y;419 } else {420 par->right = Y;421 }422 Y->parent = par;423 424 _getHeight(X);425 _getHeight(Y);426 _getHeight(par);427 }428 429 void _doubleRotationLeftRight(TreeNode *cur) {430 // Subtree Z is deeper than subtree A. Single rotation won‘t work, so let‘s use this one instead.431 // Before rotation:432 // X433 // / 434 // Y D435 // / 436 // A Z437 // / 438 // B C439 // ----------440 // After rotation:441 // Z442 // / 443 // Y X444 // / \ / 445 // A B C D446 TreeNode *par = cur->parent;447 TreeNode *B, *C;448 TreeNode *X, *Y, *Z;449 450 X = cur;451 Y = X->left;452 Z = Y->right;453 B = Z->left;454 C = Z->right;455 456 Z->left = Y;457 Y->parent = Z;458 Z->right = X;459 X->parent = Z;460 Y->right = B;461 if (B != nullptr) {462 B->parent = X;463 }464 X->left = C;465 if (C != nullptr) {466 C->parent = X;467 }468 469 if (par == nullptr) {470 m_root = Z;471 } else if (par->left == cur) {472 par->left = Z;473 } else {474 par->right = Z;475 }476 Z->parent = par;477 478 _getHeight(X);479 _getHeight(Y);480 _getHeight(Z);481 _getHeight(par);482 }483 484 void _doubleRotationRightLeft(TreeNode *cur) {485 // Subtree Z is deeper than subtree D. Single rotation won‘t work, so let‘s use this one instead.486 // Before rotation:487 // X488 // / 489 // A Y490 // / 491 // Z D492 // / 493 // B C494 // ----------495 // After rotation:496 // Z497 // / 498 // X Y499 // / \ / 500 // A B C D501 TreeNode *par = cur->parent;502 TreeNode *B, *C;503 TreeNode *X, *Y, *Z;504 505 X = cur;506 Y = X->right;507 Z = Y->left;508 B = Z->left;509 C = Z->right;510 511 Z->left = X;512 X->parent = Z;513 Z->right = Y;514 Y->parent = Z;515 X->right = B;516 if (B != nullptr) {517 B->parent = X;518 }519 Y->left = C;520 if (C != nullptr) {521 C->parent = Y;522 }523 524 if (par == nullptr) {525 m_root = Z;526 } else if (par->left == cur) {527 par->left = Z;528 } else {529 par->right = Z;530 }531 Z->parent = par;532 533 _getHeight(X);534 _getHeight(Y);535 _getHeight(Z);536 _getHeight(par);537 }538 };539 540 int main()541 {542 AVLTree avl;543 544 // test for single rotation545 avl.insertNode(1);546 cout << avl.preorderTraversal() << endl;547 avl.insertNode(2);548 cout << avl.preorderTraversal() << endl;549 avl.insertNode(3);550 cout << avl.preorderTraversal() << endl;551 avl.insertNode(4);552 cout << avl.preorderTraversal() << endl;553 avl.insertNode(5);554 cout << avl.preorderTraversal() << endl;555 avl.insertNode(6);556 cout << avl.preorderTraversal() << endl;557 avl.insertNode(7);558 cout << avl.preorderTraversal() << endl;559 avl.insertNode(8);560 cout << avl.preorderTraversal() << endl;561 avl.insertNode(9);562 cout << avl.preorderTraversal() << endl;563 cout << endl;564 565 // test for double rotation566 avl.clear();567 avl.insertNode(3);568 cout << avl.preorderTraversal() << endl;569 avl.insertNode(1);570 cout << avl.preorderTraversal() << endl;571 avl.insertNode(2);572 cout << avl.preorderTraversal() << endl;573 cout << endl;574 575 // test for deletion, left576 avl.clear();577 avl.insertNode(3);578 cout << avl.preorderTraversal() << endl;579 avl.insertNode(2);580 cout << avl.preorderTraversal() << endl;581 avl.insertNode(4);582 cout << avl.preorderTraversal() << endl;583 avl.insertNode(1);584 cout << avl.preorderTraversal() << endl;585 avl.deleteNode(3);586 cout << avl.preorderTraversal() << endl;587 avl.deleteNode(2);588 cout << avl.preorderTraversal() << endl;589 avl.deleteNode(4);590 cout << avl.preorderTraversal() << endl;591 cout << endl;592 593 // test for deletion, right594 avl.clear();595 avl.insertNode(2);596 cout << avl.preorderTraversal() << endl;597 avl.insertNode(1);598 cout << avl.preorderTraversal() << endl;599 avl.insertNode(3);600 cout << avl.preorderTraversal() << endl;601 avl.insertNode(4);602 cout << avl.preorderTraversal() << endl;603 avl.deleteNode(2);604 cout << avl.preorderTraversal() << endl;605 avl.deleteNode(1);606 cout << avl.preorderTraversal() << endl;607 avl.deleteNode(3);608 cout << avl.preorderTraversal() << endl;609 cout << endl;610 611 return 0;612 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。