\u8fd9\u91cc\u6211\u4eec\u4ecb\u7ecdBinary Search Tree\u7684\u5347\u7ea7\u7248\uff0cAVL\u3002\u76f8\u6bd4\u4e8eBST\uff0cAVL\u8981\u6c42\u4e86\u5bf9\u4e8e\u6bcf\u4e2a\u8282\u70b9\u5176\u5de6\u53f3\u5b50\u6811\u7684\u5dee\u81f3\u591a\u4e3aLimit\uff08\u81ea\u5df1\u8bbe\u5b9a\uff09\uff0c\u8fd9\u91cc\u7684Limit\u4e00\u822c\u90091\uff08\u4ece0\u8ba1\u7b97\u9ad8\u5ea6\uff09\uff0c\u5373\u4fdd\u8bc1\u5b83\u662f\u4e00\u9897\u5e73\u8861\u4e8c\u53c9\u6811\u3002\n AVL\u6811\u7684\u64cd\u4f5c\u548cBST\u57fa\u672c\u4e00\u81f4\uff0c\u53ea\u9700\u8981\u5728\u5220\u9664\u3001\u63d2\u5165\u8fd4\u56de\u524d\u8c03\u7528\u4e00\u6b21balance()\uff0c\u4f7f\u5f97\u5b83\u4eceBST\u65cb\u8f6c\u4e3aAVL\u3002<\/p>\n
template<typename elemType>\nvoid Avl<elemType>::Insert(const elemType& ele, Node<elemType>*& node)\n{\n \/\/ \u6709\u7a7a\u4f4d\u63d2\n if (!node)\n {\n node = new Node<elemType>(ele, nullptr, nullptr);\n }\n \/\/ \u8fd9\u4e2a\u7a7a\u4f4d\u6709\u4eba\u4e86\uff0c\u548c\u4ed6\u6bd4\u8f83\u4e0b\uff0c\u6309\u4e00\u5b9a\u6392\u5e8f\u51c6\u5219\u9009\u62e9\u5de6\u53f3\uff0c\u8fd9\u91cc\u4ee5 < \u4e3a\u6392\u5e8f\u51c6\u5219\u3002\n else if (ele < node->element)\n {\n this->Insert(ele, node->left);\n }\n else if (node->element < ele)\n {\n this->Insert(ele, node->right);\n }\n\n this->Balance(node);\n}<\/code><\/pre>\n2.2 \u5220\u9664<\/h3>\ntemplate<typename elemType>\nvoid Avl<elemType>::Remove_val(const elemType& ele, Node<elemType>*& node)\n{\n if (!node) return;\n\n \/\/ \u4e0d\u662f\u76ee\u6807\uff0c\u6bd4\u8f83\n if (ele < node->element)\n this->Remove_val(ele, node->left);\n else if (ele > node->element)\n this->Remove_val(ele, node->left);\n \/\/ \u627e\u5230\u76ee\u6807\n else if (node->left && node->right) \/\/ \u88ab\u5220\u9664\u76ee\u6807\u6709\u4e24\u4e2a\u8282\u70b9\n {\n \/\/ \u53ef\u66ff\u6362\u5de6\u5b50\u6811\u7684\u6700\u5927\u503c\u3001\u53f3\u5b50\u6811\u7684\u6700\u5c0f\u503c\uff08\u4e2d\u5e8f\u5411\u91cf\u7684\u4e24\u4e2a\u70b9\uff0c\u9009\u4e00\uff09\n node->element = this->FindMin(node->right)->element;\n \/\/ \u66f4\u65b0\u5220\u9664\u76ee\u6807\n Remove_val(node->element, node->right);\n }\n else \/\/ \u88ab\u5220\u9664\u76ee\u6807\u53ea\u6709\u4e00\u4e2a\u8282\u70b9\u6216\u65e0\u8282\u70b9\n {\n Node<elemType>* oldOne = node;\n node = (node->left) ?\n node->left :\n node->right;\n delete oldOne;\n }\n\n Balance(node);\n}<\/code><\/pre>\n\u4e09\u3001\u65cb\u8f6c\u4e0e\u5e73\u8861<\/h2>\n3.1 \u65cb\u8f6c<\/h3>\n AVL\u7684\u65cb\u8f6c\u53ef\u4ee5\u5206\u4e3a\u4e24\u79cd\uff0c\u5355\u65cb\u548c\u53cc\u9009\u3002\u5bf9\u4e8e\u5de6\u53f3\u5b50\u6811\u7684\u65cb\u8f6c\u5176\u662f\u5bf9\u79f0\u7684\u3002<\/p>\n3.1.1 \u5de6\u5b50\u6811\u5355\u65cb<\/h4>\nSingle Rotate with Left<\/strong> \/\/ LL<\/strong>\n \u73b0\u5728\u6211\u4eec\u6709\u5982\u4e0b\u7684\u4e00\u4e2a\u4e8c\u53c9\u6811\uff0c\u5176\u8282\u70b9violate\u662f\u8fdd\u53cd\u4e86AVL\u8981\u6c42\u7684\u8282\u70b9\uff0c\u5176\u9ad8\u5ea6\u66f4\u9ad8\u7684\u4e00\u8fb9\u6765\u81eaviolate\u7684\u5de6\u5b50\u6811\uff0c\u6211\u4eec\u79f0\u4e4b\u4e3aviolateLeft\u3002\u6211\u4eec\u67e5\u770bviolateLeft\u7684\u5de6\u53f3\u5b50\u6811\u9ad8\u5ea6\u60c5\u51b5\uff0c\u53d1\u73b0violateLeft\u7684\u5de6\u8fb9\u6bd4\u53f3\u8fb9\u9ad8\uff0c\u5219\u5176\u4e3aLL\u60c5\u51b5\uff0c\u6216\u79f0Single Rotate with Left\u3002\n\u56fe1\uff1aLL\u5355\u65cb<\/figcaption><\/figure><\/p >\n \u56fe1\uff1aLL\u5355\u65cb[\/caption]<\/p><\/noscript>\n \u53d8\u6362\u64cd\u4f5c\uff1a<\/p>\n\nviolate->left = violateLeft->right;<\/li>\nviolateLeft->right = violate;<\/li>\nviolate = violateLeft; \/\/ \u66f4\u65b0\u6839\u8282\u70b9<\/li>\n<\/ol>\n<\/noscript> \u56fe3\uff1aLL\u53d8\u6362<\/figcaption><\/figure>\n RR\u7684\u53d8\u6362\u540c\u7406\uff0c\u4e0b\u9762\u662fLL\u4ee3\u7801\u5c55\u793a\uff1a<\/p>\n\/* ===== Function 07 : LL ===== *\/\ntemplate<typename elemType>\nvoid Avl<elemType>::LL(Node<elemType>*& violate)\n{\n Node<elemType>* violateLeft = violate->left;\n\n \/\/ \u4ea4\u6362\u8282\u70b9\n violate->left = violateLeft->right;\n violateLeft->right = violate;\n\n \/\/ \u9ad8\u5ea6\u66f4\u65b0\n violate->height = std::max(Height(violate->left), Height(violate->right)) + 1;\n violateLeft->height = std::max(Height(violateLeft->left), violate->height) + 1;\n\n violate = violateLeft;\n}<\/code><\/pre>\n3.1.2 \u5de6\u5b50\u6811\u53cc\u65cb<\/h4>\nDouble Rotate with Left<\/strong> \/\/ LR<\/strong>\n \u540c\u6837\u662f\u4e0a\u9762\u7684\u56fe\uff0c\u4e0d\u8fc7\u8fd9\u6b21\u6700\u9ad8\u70b9\u6765\u81eaviolate->left->right\uff0c\u6240\u4ee5\u8fd9\u662f\u4e00\u6b21\u53cc\u65cb\u3002\u5bf9\u4e8eLR\u53cc\u65cb\uff0c\u6211\u4eec\u5148\u5bf9(voilate->left)\u4f7f\u7528RR\u5355\u65cb\uff0c\u518d\u5bf9(violate)\u4f7f\u7528LL\u5355\u65cb\u3002\n\u56fe3\uff1aLR\u53cc\u9009<\/figcaption><\/figure><\/p >\n \u56fe3\uff1aLR\u53cc\u9009[\/caption]<\/p><\/noscript>\n \u53d8\u6362\u64cd\u4f5c\uff1a<\/p>\n\nRR(violate->left);<\/li>\nLL(violate);<\/li>\n<\/ol>\n<\/noscript> \u56fe4\uff1aLR\u53d8\u6362<\/figcaption><\/figure>\n \u4ee3\u7801\u793a\u4f8b\uff1a<\/p>\n\/* ===== Function 09 : LR ===== *\/\ntemplate<typename elemType>\nvoid Avl<elemType>::LR(Node<elemType>*& violate)\n{\n RR(violate->left);\n LL(violate);\n}<\/code><\/pre>\n3.2 \u5e73\u8861<\/h3>\n \u6211\u4eec\u6bcf\u6267\u884c\u4e00\u6b21\u63d2\u5165\u3001\u5220\u9664\u64cd\u4f5c\uff0c\u5c31\u5bf9\u5f53\u524d\u8282\u70b9\u6267\u884c\u4e00\u6b21balance()\u3002\n \u5224\u65ad\u65b9\u6cd5\u5982\u4e0b\uff0cL\u8868\u793a\u5f53\u524d\u8282\u70b9\u7684\u5de6\u5b50\u6811\uff0cLL\u8868\u793a\u5f53\u524d\u8282\u70b9\u5de6\u5b50\u6811\u7684\u5de6\u5b50\u6811\u3002<\/p>\n\nL - R > \u9650\u5236\nLL > LR\nLL();\nLL < LR\nLR();<\/li>\nR - L < \u9650\u5236\nRR > RL\nRR();\nRR < RL\nRL();<\/li>\n\u66f4\u65b0\u9ad8\u5ea6<\/li>\n<\/ol>\n \u4ee3\u7801\u793a\u4f8b\uff1a<\/p>\n\/* ===== Function 11 : \u5e73\u8861 ===== *\/\ntemplate<typename elemType>\nvoid Avl<elemType>::Balance(Node<elemType>*& node)\n{\n if (!node) return;\n\n \/\/ \u5de6\u9ad8\n if (Height(node->left) - Height(node->right) >= 2)\n {\n if (Height(node->left->left) >= Height(node->left->right))\n {\n LL(node);\n }\n else\n {\n LR(node);\n }\n }\n \/\/ \u53f3\u9ad8\n else if (Height(node->right) - Height(node->left) >= 2)\n {\n if (Height(node->right->right) >= Height(node->right->right))\n {\n RR(node);\n }\n else\n {\n RL(node);\n }\n }\n\n \/\/ \u66f4\u65b0\u9ad8\u5ea6\n node->height = std::max(Height(node->left), Height(node->right)) + 1;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u4e00\u3001\u5f15\u8a00 \u8fd9\u91cc\u6211\u4eec\u4ecb\u7ecdBinary Search Tree\u7684\u5347\u7ea7\u7248\uff0cAVL\u3002\u76f8\u6bd4\u4e8eBST\uff0cAVL\u8981\u6c42\u4e86\u5bf9\u4e8e …<\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[60],"tags":[],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/643"}],"collection":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/comments?post=643"}],"version-history":[{"count":8,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/643\/revisions"}],"predecessor-version":[{"id":651,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/643\/revisions\/651"}],"wp:attachment":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/media?parent=643"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/categories?post=643"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/tags?post=643"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
template<typename elemType>\nvoid Avl<elemType>::Remove_val(const elemType& ele, Node<elemType>*& node)\n{\n if (!node) return;\n\n \/\/ \u4e0d\u662f\u76ee\u6807\uff0c\u6bd4\u8f83\n if (ele < node->element)\n this->Remove_val(ele, node->left);\n else if (ele > node->element)\n this->Remove_val(ele, node->left);\n \/\/ \u627e\u5230\u76ee\u6807\n else if (node->left && node->right) \/\/ \u88ab\u5220\u9664\u76ee\u6807\u6709\u4e24\u4e2a\u8282\u70b9\n {\n \/\/ \u53ef\u66ff\u6362\u5de6\u5b50\u6811\u7684\u6700\u5927\u503c\u3001\u53f3\u5b50\u6811\u7684\u6700\u5c0f\u503c\uff08\u4e2d\u5e8f\u5411\u91cf\u7684\u4e24\u4e2a\u70b9\uff0c\u9009\u4e00\uff09\n node->element = this->FindMin(node->right)->element;\n \/\/ \u66f4\u65b0\u5220\u9664\u76ee\u6807\n Remove_val(node->element, node->right);\n }\n else \/\/ \u88ab\u5220\u9664\u76ee\u6807\u53ea\u6709\u4e00\u4e2a\u8282\u70b9\u6216\u65e0\u8282\u70b9\n {\n Node<elemType>* oldOne = node;\n node = (node->left) ?\n node->left :\n node->right;\n delete oldOne;\n }\n\n Balance(node);\n}<\/code><\/pre>\n\u4e09\u3001\u65cb\u8f6c\u4e0e\u5e73\u8861<\/h2>\n3.1 \u65cb\u8f6c<\/h3>\n AVL\u7684\u65cb\u8f6c\u53ef\u4ee5\u5206\u4e3a\u4e24\u79cd\uff0c\u5355\u65cb\u548c\u53cc\u9009\u3002\u5bf9\u4e8e\u5de6\u53f3\u5b50\u6811\u7684\u65cb\u8f6c\u5176\u662f\u5bf9\u79f0\u7684\u3002<\/p>\n3.1.1 \u5de6\u5b50\u6811\u5355\u65cb<\/h4>\nSingle Rotate with Left<\/strong> \/\/ LL<\/strong>\n \u73b0\u5728\u6211\u4eec\u6709\u5982\u4e0b\u7684\u4e00\u4e2a\u4e8c\u53c9\u6811\uff0c\u5176\u8282\u70b9violate\u662f\u8fdd\u53cd\u4e86AVL\u8981\u6c42\u7684\u8282\u70b9\uff0c\u5176\u9ad8\u5ea6\u66f4\u9ad8\u7684\u4e00\u8fb9\u6765\u81eaviolate\u7684\u5de6\u5b50\u6811\uff0c\u6211\u4eec\u79f0\u4e4b\u4e3aviolateLeft\u3002\u6211\u4eec\u67e5\u770bviolateLeft\u7684\u5de6\u53f3\u5b50\u6811\u9ad8\u5ea6\u60c5\u51b5\uff0c\u53d1\u73b0violateLeft\u7684\u5de6\u8fb9\u6bd4\u53f3\u8fb9\u9ad8\uff0c\u5219\u5176\u4e3aLL\u60c5\u51b5\uff0c\u6216\u79f0Single Rotate with Left\u3002\n\u56fe1\uff1aLL\u5355\u65cb<\/figcaption><\/figure><\/p >\n \u56fe1\uff1aLL\u5355\u65cb[\/caption]<\/p><\/noscript>\n \u53d8\u6362\u64cd\u4f5c\uff1a<\/p>\n\nviolate->left = violateLeft->right;<\/li>\nviolateLeft->right = violate;<\/li>\nviolate = violateLeft; \/\/ \u66f4\u65b0\u6839\u8282\u70b9<\/li>\n<\/ol>\n<\/noscript> \u56fe3\uff1aLL\u53d8\u6362<\/figcaption><\/figure>\n RR\u7684\u53d8\u6362\u540c\u7406\uff0c\u4e0b\u9762\u662fLL\u4ee3\u7801\u5c55\u793a\uff1a<\/p>\n\/* ===== Function 07 : LL ===== *\/\ntemplate<typename elemType>\nvoid Avl<elemType>::LL(Node<elemType>*& violate)\n{\n Node<elemType>* violateLeft = violate->left;\n\n \/\/ \u4ea4\u6362\u8282\u70b9\n violate->left = violateLeft->right;\n violateLeft->right = violate;\n\n \/\/ \u9ad8\u5ea6\u66f4\u65b0\n violate->height = std::max(Height(violate->left), Height(violate->right)) + 1;\n violateLeft->height = std::max(Height(violateLeft->left), violate->height) + 1;\n\n violate = violateLeft;\n}<\/code><\/pre>\n3.1.2 \u5de6\u5b50\u6811\u53cc\u65cb<\/h4>\nDouble Rotate with Left<\/strong> \/\/ LR<\/strong>\n \u540c\u6837\u662f\u4e0a\u9762\u7684\u56fe\uff0c\u4e0d\u8fc7\u8fd9\u6b21\u6700\u9ad8\u70b9\u6765\u81eaviolate->left->right\uff0c\u6240\u4ee5\u8fd9\u662f\u4e00\u6b21\u53cc\u65cb\u3002\u5bf9\u4e8eLR\u53cc\u65cb\uff0c\u6211\u4eec\u5148\u5bf9(voilate->left)\u4f7f\u7528RR\u5355\u65cb\uff0c\u518d\u5bf9(violate)\u4f7f\u7528LL\u5355\u65cb\u3002\n\u56fe3\uff1aLR\u53cc\u9009<\/figcaption><\/figure><\/p >\n \u56fe3\uff1aLR\u53cc\u9009[\/caption]<\/p><\/noscript>\n \u53d8\u6362\u64cd\u4f5c\uff1a<\/p>\n\nRR(violate->left);<\/li>\nLL(violate);<\/li>\n<\/ol>\n<\/noscript> \u56fe4\uff1aLR\u53d8\u6362<\/figcaption><\/figure>\n \u4ee3\u7801\u793a\u4f8b\uff1a<\/p>\n\/* ===== Function 09 : LR ===== *\/\ntemplate<typename elemType>\nvoid Avl<elemType>::LR(Node<elemType>*& violate)\n{\n RR(violate->left);\n LL(violate);\n}<\/code><\/pre>\n3.2 \u5e73\u8861<\/h3>\n \u6211\u4eec\u6bcf\u6267\u884c\u4e00\u6b21\u63d2\u5165\u3001\u5220\u9664\u64cd\u4f5c\uff0c\u5c31\u5bf9\u5f53\u524d\u8282\u70b9\u6267\u884c\u4e00\u6b21balance()\u3002\n \u5224\u65ad\u65b9\u6cd5\u5982\u4e0b\uff0cL\u8868\u793a\u5f53\u524d\u8282\u70b9\u7684\u5de6\u5b50\u6811\uff0cLL\u8868\u793a\u5f53\u524d\u8282\u70b9\u5de6\u5b50\u6811\u7684\u5de6\u5b50\u6811\u3002<\/p>\n\nL - R > \u9650\u5236\nLL > LR\nLL();\nLL < LR\nLR();<\/li>\nR - L < \u9650\u5236\nRR > RL\nRR();\nRR < RL\nRL();<\/li>\n\u66f4\u65b0\u9ad8\u5ea6<\/li>\n<\/ol>\n \u4ee3\u7801\u793a\u4f8b\uff1a<\/p>\n\/* ===== Function 11 : \u5e73\u8861 ===== *\/\ntemplate<typename elemType>\nvoid Avl<elemType>::Balance(Node<elemType>*& node)\n{\n if (!node) return;\n\n \/\/ \u5de6\u9ad8\n if (Height(node->left) - Height(node->right) >= 2)\n {\n if (Height(node->left->left) >= Height(node->left->right))\n {\n LL(node);\n }\n else\n {\n LR(node);\n }\n }\n \/\/ \u53f3\u9ad8\n else if (Height(node->right) - Height(node->left) >= 2)\n {\n if (Height(node->right->right) >= Height(node->right->right))\n {\n RR(node);\n }\n else\n {\n RL(node);\n }\n }\n\n \/\/ \u66f4\u65b0\u9ad8\u5ea6\n node->height = std::max(Height(node->left), Height(node->right)) + 1;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u4e00\u3001\u5f15\u8a00 \u8fd9\u91cc\u6211\u4eec\u4ecb\u7ecdBinary Search Tree\u7684\u5347\u7ea7\u7248\uff0cAVL\u3002\u76f8\u6bd4\u4e8eBST\uff0cAVL\u8981\u6c42\u4e86\u5bf9\u4e8e …<\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[60],"tags":[],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/643"}],"collection":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/comments?post=643"}],"version-history":[{"count":8,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/643\/revisions"}],"predecessor-version":[{"id":651,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/643\/revisions\/651"}],"wp:attachment":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/media?parent=643"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/categories?post=643"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/tags?post=643"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
AVL\u7684\u65cb\u8f6c\u53ef\u4ee5\u5206\u4e3a\u4e24\u79cd\uff0c\u5355\u65cb\u548c\u53cc\u9009\u3002\u5bf9\u4e8e\u5de6\u53f3\u5b50\u6811\u7684\u65cb\u8f6c\u5176\u662f\u5bf9\u79f0\u7684\u3002<\/p>\n
Single Rotate with Left<\/strong> \/\/ LL<\/strong>\n \u73b0\u5728\u6211\u4eec\u6709\u5982\u4e0b\u7684\u4e00\u4e2a\u4e8c\u53c9\u6811\uff0c\u5176\u8282\u70b9violate\u662f\u8fdd\u53cd\u4e86AVL\u8981\u6c42\u7684\u8282\u70b9\uff0c\u5176\u9ad8\u5ea6\u66f4\u9ad8\u7684\u4e00\u8fb9\u6765\u81eaviolate\u7684\u5de6\u5b50\u6811\uff0c\u6211\u4eec\u79f0\u4e4b\u4e3aviolateLeft\u3002\u6211\u4eec\u67e5\u770bviolateLeft\u7684\u5de6\u53f3\u5b50\u6811\u9ad8\u5ea6\u60c5\u51b5\uff0c\u53d1\u73b0violateLeft\u7684\u5de6\u8fb9\u6bd4\u53f3\u8fb9\u9ad8\uff0c\u5219\u5176\u4e3aLL\u60c5\u51b5\uff0c\u6216\u79f0Single Rotate with Left\u3002\n\u56fe1\uff1aLL\u5355\u65cb<\/figcaption><\/figure><\/p >\n \u56fe1\uff1aLL\u5355\u65cb[\/caption]<\/p><\/noscript>\n \u53d8\u6362\u64cd\u4f5c\uff1a<\/p>\n\nviolate->left = violateLeft->right;<\/li>\nviolateLeft->right = violate;<\/li>\nviolate = violateLeft; \/\/ \u66f4\u65b0\u6839\u8282\u70b9<\/li>\n<\/ol>\n<\/noscript> \u56fe3\uff1aLL\u53d8\u6362<\/figcaption><\/figure>\n RR\u7684\u53d8\u6362\u540c\u7406\uff0c\u4e0b\u9762\u662fLL\u4ee3\u7801\u5c55\u793a\uff1a<\/p>\n\/* ===== Function 07 : LL ===== *\/\ntemplate<typename elemType>\nvoid Avl<elemType>::LL(Node<elemType>*& violate)\n{\n Node<elemType>* violateLeft = violate->left;\n\n \/\/ \u4ea4\u6362\u8282\u70b9\n violate->left = violateLeft->right;\n violateLeft->right = violate;\n\n \/\/ \u9ad8\u5ea6\u66f4\u65b0\n violate->height = std::max(Height(violate->left), Height(violate->right)) + 1;\n violateLeft->height = std::max(Height(violateLeft->left), violate->height) + 1;\n\n violate = violateLeft;\n}<\/code><\/pre>\n3.1.2 \u5de6\u5b50\u6811\u53cc\u65cb<\/h4>\nDouble Rotate with Left<\/strong> \/\/ LR<\/strong>\n \u540c\u6837\u662f\u4e0a\u9762\u7684\u56fe\uff0c\u4e0d\u8fc7\u8fd9\u6b21\u6700\u9ad8\u70b9\u6765\u81eaviolate->left->right\uff0c\u6240\u4ee5\u8fd9\u662f\u4e00\u6b21\u53cc\u65cb\u3002\u5bf9\u4e8eLR\u53cc\u65cb\uff0c\u6211\u4eec\u5148\u5bf9(voilate->left)\u4f7f\u7528RR\u5355\u65cb\uff0c\u518d\u5bf9(violate)\u4f7f\u7528LL\u5355\u65cb\u3002\n\u56fe3\uff1aLR\u53cc\u9009<\/figcaption><\/figure><\/p >\n \u56fe3\uff1aLR\u53cc\u9009[\/caption]<\/p><\/noscript>\n \u53d8\u6362\u64cd\u4f5c\uff1a<\/p>\n\nRR(violate->left);<\/li>\nLL(violate);<\/li>\n<\/ol>\n<\/noscript> \u56fe4\uff1aLR\u53d8\u6362<\/figcaption><\/figure>\n \u4ee3\u7801\u793a\u4f8b\uff1a<\/p>\n\/* ===== Function 09 : LR ===== *\/\ntemplate<typename elemType>\nvoid Avl<elemType>::LR(Node<elemType>*& violate)\n{\n RR(violate->left);\n LL(violate);\n}<\/code><\/pre>\n3.2 \u5e73\u8861<\/h3>\n \u6211\u4eec\u6bcf\u6267\u884c\u4e00\u6b21\u63d2\u5165\u3001\u5220\u9664\u64cd\u4f5c\uff0c\u5c31\u5bf9\u5f53\u524d\u8282\u70b9\u6267\u884c\u4e00\u6b21balance()\u3002\n \u5224\u65ad\u65b9\u6cd5\u5982\u4e0b\uff0cL\u8868\u793a\u5f53\u524d\u8282\u70b9\u7684\u5de6\u5b50\u6811\uff0cLL\u8868\u793a\u5f53\u524d\u8282\u70b9\u5de6\u5b50\u6811\u7684\u5de6\u5b50\u6811\u3002<\/p>\n\nL - R > \u9650\u5236\nLL > LR\nLL();\nLL < LR\nLR();<\/li>\nR - L < \u9650\u5236\nRR > RL\nRR();\nRR < RL\nRL();<\/li>\n\u66f4\u65b0\u9ad8\u5ea6<\/li>\n<\/ol>\n \u4ee3\u7801\u793a\u4f8b\uff1a<\/p>\n\/* ===== Function 11 : \u5e73\u8861 ===== *\/\ntemplate<typename elemType>\nvoid Avl<elemType>::Balance(Node<elemType>*& node)\n{\n if (!node) return;\n\n \/\/ \u5de6\u9ad8\n if (Height(node->left) - Height(node->right) >= 2)\n {\n if (Height(node->left->left) >= Height(node->left->right))\n {\n LL(node);\n }\n else\n {\n LR(node);\n }\n }\n \/\/ \u53f3\u9ad8\n else if (Height(node->right) - Height(node->left) >= 2)\n {\n if (Height(node->right->right) >= Height(node->right->right))\n {\n RR(node);\n }\n else\n {\n RL(node);\n }\n }\n\n \/\/ \u66f4\u65b0\u9ad8\u5ea6\n node->height = std::max(Height(node->left), Height(node->right)) + 1;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u4e00\u3001\u5f15\u8a00 \u8fd9\u91cc\u6211\u4eec\u4ecb\u7ecdBinary Search Tree\u7684\u5347\u7ea7\u7248\uff0cAVL\u3002\u76f8\u6bd4\u4e8eBST\uff0cAVL\u8981\u6c42\u4e86\u5bf9\u4e8e …<\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[60],"tags":[],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/643"}],"collection":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/comments?post=643"}],"version-history":[{"count":8,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/643\/revisions"}],"predecessor-version":[{"id":651,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/643\/revisions\/651"}],"wp:attachment":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/media?parent=643"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/categories?post=643"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/tags?post=643"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\u53d8\u6362\u64cd\u4f5c\uff1a<\/p>\n
RR\u7684\u53d8\u6362\u540c\u7406\uff0c\u4e0b\u9762\u662fLL\u4ee3\u7801\u5c55\u793a\uff1a<\/p>\n
\/* ===== Function 07 : LL ===== *\/\ntemplate<typename elemType>\nvoid Avl<elemType>::LL(Node<elemType>*& violate)\n{\n Node<elemType>* violateLeft = violate->left;\n\n \/\/ \u4ea4\u6362\u8282\u70b9\n violate->left = violateLeft->right;\n violateLeft->right = violate;\n\n \/\/ \u9ad8\u5ea6\u66f4\u65b0\n violate->height = std::max(Height(violate->left), Height(violate->right)) + 1;\n violateLeft->height = std::max(Height(violateLeft->left), violate->height) + 1;\n\n violate = violateLeft;\n}<\/code><\/pre>\n3.1.2 \u5de6\u5b50\u6811\u53cc\u65cb<\/h4>\nDouble Rotate with Left<\/strong> \/\/ LR<\/strong>\n \u540c\u6837\u662f\u4e0a\u9762\u7684\u56fe\uff0c\u4e0d\u8fc7\u8fd9\u6b21\u6700\u9ad8\u70b9\u6765\u81eaviolate->left->right\uff0c\u6240\u4ee5\u8fd9\u662f\u4e00\u6b21\u53cc\u65cb\u3002\u5bf9\u4e8eLR\u53cc\u65cb\uff0c\u6211\u4eec\u5148\u5bf9(voilate->left)\u4f7f\u7528RR\u5355\u65cb\uff0c\u518d\u5bf9(violate)\u4f7f\u7528LL\u5355\u65cb\u3002\n\u56fe3\uff1aLR\u53cc\u9009<\/figcaption><\/figure><\/p >\n \u56fe3\uff1aLR\u53cc\u9009[\/caption]<\/p><\/noscript>\n \u53d8\u6362\u64cd\u4f5c\uff1a<\/p>\n\nRR(violate->left);<\/li>\nLL(violate);<\/li>\n<\/ol>\n<\/noscript> \u56fe4\uff1aLR\u53d8\u6362<\/figcaption><\/figure>\n \u4ee3\u7801\u793a\u4f8b\uff1a<\/p>\n\/* ===== Function 09 : LR ===== *\/\ntemplate<typename elemType>\nvoid Avl<elemType>::LR(Node<elemType>*& violate)\n{\n RR(violate->left);\n LL(violate);\n}<\/code><\/pre>\n3.2 \u5e73\u8861<\/h3>\n \u6211\u4eec\u6bcf\u6267\u884c\u4e00\u6b21\u63d2\u5165\u3001\u5220\u9664\u64cd\u4f5c\uff0c\u5c31\u5bf9\u5f53\u524d\u8282\u70b9\u6267\u884c\u4e00\u6b21balance()\u3002\n \u5224\u65ad\u65b9\u6cd5\u5982\u4e0b\uff0cL\u8868\u793a\u5f53\u524d\u8282\u70b9\u7684\u5de6\u5b50\u6811\uff0cLL\u8868\u793a\u5f53\u524d\u8282\u70b9\u5de6\u5b50\u6811\u7684\u5de6\u5b50\u6811\u3002<\/p>\n\nL - R > \u9650\u5236\nLL > LR\nLL();\nLL < LR\nLR();<\/li>\nR - L < \u9650\u5236\nRR > RL\nRR();\nRR < RL\nRL();<\/li>\n\u66f4\u65b0\u9ad8\u5ea6<\/li>\n<\/ol>\n \u4ee3\u7801\u793a\u4f8b\uff1a<\/p>\n\/* ===== Function 11 : \u5e73\u8861 ===== *\/\ntemplate<typename elemType>\nvoid Avl<elemType>::Balance(Node<elemType>*& node)\n{\n if (!node) return;\n\n \/\/ \u5de6\u9ad8\n if (Height(node->left) - Height(node->right) >= 2)\n {\n if (Height(node->left->left) >= Height(node->left->right))\n {\n LL(node);\n }\n else\n {\n LR(node);\n }\n }\n \/\/ \u53f3\u9ad8\n else if (Height(node->right) - Height(node->left) >= 2)\n {\n if (Height(node->right->right) >= Height(node->right->right))\n {\n RR(node);\n }\n else\n {\n RL(node);\n }\n }\n\n \/\/ \u66f4\u65b0\u9ad8\u5ea6\n node->height = std::max(Height(node->left), Height(node->right)) + 1;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u4e00\u3001\u5f15\u8a00 \u8fd9\u91cc\u6211\u4eec\u4ecb\u7ecdBinary Search Tree\u7684\u5347\u7ea7\u7248\uff0cAVL\u3002\u76f8\u6bd4\u4e8eBST\uff0cAVL\u8981\u6c42\u4e86\u5bf9\u4e8e …<\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[60],"tags":[],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/643"}],"collection":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/comments?post=643"}],"version-history":[{"count":8,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/643\/revisions"}],"predecessor-version":[{"id":651,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/643\/revisions\/651"}],"wp:attachment":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/media?parent=643"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/categories?post=643"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/tags?post=643"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
Double Rotate with Left<\/strong> \/\/ LR<\/strong>\n \u540c\u6837\u662f\u4e0a\u9762\u7684\u56fe\uff0c\u4e0d\u8fc7\u8fd9\u6b21\u6700\u9ad8\u70b9\u6765\u81eaviolate->left->right\uff0c\u6240\u4ee5\u8fd9\u662f\u4e00\u6b21\u53cc\u65cb\u3002\u5bf9\u4e8eLR\u53cc\u65cb\uff0c\u6211\u4eec\u5148\u5bf9(voilate->left)\u4f7f\u7528RR\u5355\u65cb\uff0c\u518d\u5bf9(violate)\u4f7f\u7528LL\u5355\u65cb\u3002\n\u56fe3\uff1aLR\u53cc\u9009<\/figcaption><\/figure><\/p >\n \u56fe3\uff1aLR\u53cc\u9009[\/caption]<\/p><\/noscript>\n \u53d8\u6362\u64cd\u4f5c\uff1a<\/p>\n\nRR(violate->left);<\/li>\nLL(violate);<\/li>\n<\/ol>\n<\/noscript> \u56fe4\uff1aLR\u53d8\u6362<\/figcaption><\/figure>\n \u4ee3\u7801\u793a\u4f8b\uff1a<\/p>\n\/* ===== Function 09 : LR ===== *\/\ntemplate<typename elemType>\nvoid Avl<elemType>::LR(Node<elemType>*& violate)\n{\n RR(violate->left);\n LL(violate);\n}<\/code><\/pre>\n3.2 \u5e73\u8861<\/h3>\n \u6211\u4eec\u6bcf\u6267\u884c\u4e00\u6b21\u63d2\u5165\u3001\u5220\u9664\u64cd\u4f5c\uff0c\u5c31\u5bf9\u5f53\u524d\u8282\u70b9\u6267\u884c\u4e00\u6b21balance()\u3002\n \u5224\u65ad\u65b9\u6cd5\u5982\u4e0b\uff0cL\u8868\u793a\u5f53\u524d\u8282\u70b9\u7684\u5de6\u5b50\u6811\uff0cLL\u8868\u793a\u5f53\u524d\u8282\u70b9\u5de6\u5b50\u6811\u7684\u5de6\u5b50\u6811\u3002<\/p>\n\nL - R > \u9650\u5236\nLL > LR\nLL();\nLL < LR\nLR();<\/li>\nR - L < \u9650\u5236\nRR > RL\nRR();\nRR < RL\nRL();<\/li>\n\u66f4\u65b0\u9ad8\u5ea6<\/li>\n<\/ol>\n \u4ee3\u7801\u793a\u4f8b\uff1a<\/p>\n\/* ===== Function 11 : \u5e73\u8861 ===== *\/\ntemplate<typename elemType>\nvoid Avl<elemType>::Balance(Node<elemType>*& node)\n{\n if (!node) return;\n\n \/\/ \u5de6\u9ad8\n if (Height(node->left) - Height(node->right) >= 2)\n {\n if (Height(node->left->left) >= Height(node->left->right))\n {\n LL(node);\n }\n else\n {\n LR(node);\n }\n }\n \/\/ \u53f3\u9ad8\n else if (Height(node->right) - Height(node->left) >= 2)\n {\n if (Height(node->right->right) >= Height(node->right->right))\n {\n RR(node);\n }\n else\n {\n RL(node);\n }\n }\n\n \/\/ \u66f4\u65b0\u9ad8\u5ea6\n node->height = std::max(Height(node->left), Height(node->right)) + 1;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u4e00\u3001\u5f15\u8a00 \u8fd9\u91cc\u6211\u4eec\u4ecb\u7ecdBinary Search Tree\u7684\u5347\u7ea7\u7248\uff0cAVL\u3002\u76f8\u6bd4\u4e8eBST\uff0cAVL\u8981\u6c42\u4e86\u5bf9\u4e8e …<\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[60],"tags":[],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/643"}],"collection":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/comments?post=643"}],"version-history":[{"count":8,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/643\/revisions"}],"predecessor-version":[{"id":651,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/643\/revisions\/651"}],"wp:attachment":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/media?parent=643"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/categories?post=643"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/tags?post=643"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\u4ee3\u7801\u793a\u4f8b\uff1a<\/p>\n
\/* ===== Function 09 : LR ===== *\/\ntemplate<typename elemType>\nvoid Avl<elemType>::LR(Node<elemType>*& violate)\n{\n RR(violate->left);\n LL(violate);\n}<\/code><\/pre>\n3.2 \u5e73\u8861<\/h3>\n \u6211\u4eec\u6bcf\u6267\u884c\u4e00\u6b21\u63d2\u5165\u3001\u5220\u9664\u64cd\u4f5c\uff0c\u5c31\u5bf9\u5f53\u524d\u8282\u70b9\u6267\u884c\u4e00\u6b21balance()\u3002\n \u5224\u65ad\u65b9\u6cd5\u5982\u4e0b\uff0cL\u8868\u793a\u5f53\u524d\u8282\u70b9\u7684\u5de6\u5b50\u6811\uff0cLL\u8868\u793a\u5f53\u524d\u8282\u70b9\u5de6\u5b50\u6811\u7684\u5de6\u5b50\u6811\u3002<\/p>\n\nL - R > \u9650\u5236\nLL > LR\nLL();\nLL < LR\nLR();<\/li>\nR - L < \u9650\u5236\nRR > RL\nRR();\nRR < RL\nRL();<\/li>\n\u66f4\u65b0\u9ad8\u5ea6<\/li>\n<\/ol>\n \u4ee3\u7801\u793a\u4f8b\uff1a<\/p>\n\/* ===== Function 11 : \u5e73\u8861 ===== *\/\ntemplate<typename elemType>\nvoid Avl<elemType>::Balance(Node<elemType>*& node)\n{\n if (!node) return;\n\n \/\/ \u5de6\u9ad8\n if (Height(node->left) - Height(node->right) >= 2)\n {\n if (Height(node->left->left) >= Height(node->left->right))\n {\n LL(node);\n }\n else\n {\n LR(node);\n }\n }\n \/\/ \u53f3\u9ad8\n else if (Height(node->right) - Height(node->left) >= 2)\n {\n if (Height(node->right->right) >= Height(node->right->right))\n {\n RR(node);\n }\n else\n {\n RL(node);\n }\n }\n\n \/\/ \u66f4\u65b0\u9ad8\u5ea6\n node->height = std::max(Height(node->left), Height(node->right)) + 1;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u4e00\u3001\u5f15\u8a00 \u8fd9\u91cc\u6211\u4eec\u4ecb\u7ecdBinary Search Tree\u7684\u5347\u7ea7\u7248\uff0cAVL\u3002\u76f8\u6bd4\u4e8eBST\uff0cAVL\u8981\u6c42\u4e86\u5bf9\u4e8e …<\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[60],"tags":[],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/643"}],"collection":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/comments?post=643"}],"version-history":[{"count":8,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/643\/revisions"}],"predecessor-version":[{"id":651,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/643\/revisions\/651"}],"wp:attachment":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/media?parent=643"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/categories?post=643"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/tags?post=643"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\u6211\u4eec\u6bcf\u6267\u884c\u4e00\u6b21\u63d2\u5165\u3001\u5220\u9664\u64cd\u4f5c\uff0c\u5c31\u5bf9\u5f53\u524d\u8282\u70b9\u6267\u884c\u4e00\u6b21balance()\u3002\n \u5224\u65ad\u65b9\u6cd5\u5982\u4e0b\uff0cL\u8868\u793a\u5f53\u524d\u8282\u70b9\u7684\u5de6\u5b50\u6811\uff0cLL\u8868\u793a\u5f53\u524d\u8282\u70b9\u5de6\u5b50\u6811\u7684\u5de6\u5b50\u6811\u3002<\/p>\n
\/* ===== Function 11 : \u5e73\u8861 ===== *\/\ntemplate<typename elemType>\nvoid Avl<elemType>::Balance(Node<elemType>*& node)\n{\n if (!node) return;\n\n \/\/ \u5de6\u9ad8\n if (Height(node->left) - Height(node->right) >= 2)\n {\n if (Height(node->left->left) >= Height(node->left->right))\n {\n LL(node);\n }\n else\n {\n LR(node);\n }\n }\n \/\/ \u53f3\u9ad8\n else if (Height(node->right) - Height(node->left) >= 2)\n {\n if (Height(node->right->right) >= Height(node->right->right))\n {\n RR(node);\n }\n else\n {\n RL(node);\n }\n }\n\n \/\/ \u66f4\u65b0\u9ad8\u5ea6\n node->height = std::max(Height(node->left), Height(node->right)) + 1;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u4e00\u3001\u5f15\u8a00 \u8fd9\u91cc\u6211\u4eec\u4ecb\u7ecdBinary Search Tree\u7684\u5347\u7ea7\u7248\uff0cAVL\u3002\u76f8\u6bd4\u4e8eBST\uff0cAVL\u8981\u6c42\u4e86\u5bf9\u4e8e …<\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[60],"tags":[],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/643"}],"collection":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/comments?post=643"}],"version-history":[{"count":8,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/643\/revisions"}],"predecessor-version":[{"id":651,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/643\/revisions\/651"}],"wp:attachment":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/media?parent=643"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/categories?post=643"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/tags?post=643"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\u4e00\u3001\u5f15\u8a00 \u8fd9\u91cc\u6211\u4eec\u4ecb\u7ecdBinary Search Tree\u7684\u5347\u7ea7\u7248\uff0cAVL\u3002\u76f8\u6bd4\u4e8eBST\uff0cAVL\u8981\u6c42\u4e86\u5bf9\u4e8e …<\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[60],"tags":[],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/643"}],"collection":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/comments?post=643"}],"version-history":[{"count":8,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/643\/revisions"}],"predecessor-version":[{"id":651,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/643\/revisions\/651"}],"wp:attachment":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/media?parent=643"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/categories?post=643"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/tags?post=643"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
![\"\u56fe2\"](\"https:\/\/cdn.swordofmorning.com\/SwordofMorning\/Article%20Images\/pgexamDataStructer\/05\/AVL_LL_ing.png\")
![\"\u56fe3\"](\"https:\/\/cdn.jsdelivr.net\/gh\/moezx\/cdn@3.0.2\/img\/svg\/loader\/trans.ajax-spinner-preloader.svg\")
![\"\u56fe3\"](\"https:\/\/cdn.swordofmorning.com\/SwordofMorning\/Article%20Images\/pgexamDataStructer\/05\/AVL_LR.png\")
![\"\u56fe4\"](\"https:\/\/cdn.swordofmorning.com\/SwordofMorning\/Article%20Images\/pgexamDataStructer\/05\/AVL_LR_ing.png\")
![\"\u56fe1\"](\"https:\/\/cdn.swordofmorning.com\/SwordofMorning\/Article%20Images\/pgexamDataStructer\/05\/AVL_LL.png\")