{"id":541,"date":"2021-06-15T07:43:23","date_gmt":"2021-06-14T23:43:23","guid":{"rendered":"http:\/\/120.55.184.7\/?p=541"},"modified":"2025-04-16T00:44:23","modified_gmt":"2025-04-15T16:44:23","slug":"541","status":"publish","type":"post","link":"https:\/\/beijian99.top\/?p=541","title":{"rendered":"AVL\u5e73\u8861\u6811"},"content":{"rendered":"\n

AVL\u6811\u662f\u4e00\u79cd\u81ea\u5e73\u8861\u4e8c\u53c9\u641c\u7d22\u6811\uff0c\u901a\u8fc7\u65cb\u8f6c\u64cd\u4f5c\u4fdd\u6301\u6811\u7684\u5e73\u8861\uff0c\u786e\u4fdd\u67e5\u627e\u3001\u63d2\u5165\u548c\u5220\u9664\u64cd\u4f5c\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO(log n)\u3002<\/p>\n\n\n\n

AVL\u6811\u7684\u6838\u5fc3\u539f\u7406<\/h2>\n\n\n\n

AVL\u6811\u7684\u5173\u952e\u7279\u6027\u662f\u6bcf\u4e2a\u8282\u70b9\u7684\u5e73\u8861\u56e0\u5b50\uff08\u5de6\u5b50\u6811\u9ad8\u5ea6 – \u53f3\u5b50\u6811\u9ad8\u5ea6\uff09\u7edd\u5bf9\u503c\u4e0d\u8d85\u8fc71\u3002\u5f53\u63d2\u5165\u6216\u5220\u9664\u8282\u70b9\u5bfc\u81f4\u5e73\u8861\u56e0\u5b50\u7edd\u5bf9\u503c\u8d85\u8fc71\u65f6\uff0c\u9700\u8981\u901a\u8fc7\u56db\u79cd\u65cb\u8f6c\u64cd\u4f5c\u6765\u6062\u590d\u5e73\u8861\uff1a<\/p>\n\n\n\n

    \n
  1. \u5de6\u65cb\uff08RR\u65cb\u8f6c\uff09<\/strong>\uff1a\u5904\u7406\u53f3\u5b50\u6811\u6bd4\u5de6\u5b50\u6811\u9ad82\u4e14\u53f3\u5b50\u6811\u7684\u53f3\u5b50\u6811\u66f4\u9ad8\u7684\u60c5\u51b5<\/li>\n\n\n\n
  2. \u53f3\u65cb\uff08LL\u65cb\u8f6c\uff09<\/strong>\uff1a\u5904\u7406\u5de6\u5b50\u6811\u6bd4\u53f3\u5b50\u6811\u9ad82\u4e14\u5de6\u5b50\u6811\u7684\u5de6\u5b50\u6811\u66f4\u9ad8\u7684\u60c5\u51b5<\/li>\n\n\n\n
  3. \u5de6\u53f3\u53cc\u65cb\uff08LR\u65cb\u8f6c\uff09<\/strong>\uff1a\u5148\u5bf9\u5de6\u5b50\u8282\u70b9\u5de6\u65cb\uff0c\u518d\u5bf9\u5f53\u524d\u8282\u70b9\u53f3\u65cb<\/li>\n\n\n\n
  4. \u53f3\u5de6\u53cc\u65cb\uff08RL\u65cb\u8f6c\uff09<\/strong>\uff1a\u5148\u5bf9\u53f3\u5b50\u8282\u70b9\u53f3\u65cb\uff0c\u518d\u5bf9\u5f53\u524d\u8282\u70b9\u5de6\u65cb<\/li>\n<\/ol>\n\n\n\n

    C++\u5b9e\u73b0\u4ee3\u7801<\/h2>\n\n\n
    \n#include <iostream>\n#include <algorithm>\n\n\/\/ AVL\u6811\u8282\u70b9\u7ed3\u6784\nstruct AVLNode {\n    int key;\n    AVLNode* left;\n    AVLNode* right;\n    int height;\n\n    AVLNode(int k) : key(k), left(nullptr), right(nullptr), height(1) {}\n};\n\nclass AVLTree {\nprivate:\n    AVLNode* root;\n\n    \/\/ \u83b7\u53d6\u8282\u70b9\u9ad8\u5ea6\n    int height(AVLNode* node) {\n        return node ? node->height : 0;\n    }\n\n    \/\/ \u8ba1\u7b97\u5e73\u8861\u56e0\u5b50\n    int getBalance(AVLNode* node) {\n        return node ? height(node->left) - height(node->right) : 0;\n    }\n\n    \/\/ \u53f3\u65cb\u64cd\u4f5c\n    AVLNode* rightRotate(AVLNode* y) {\n        AVLNode* x = y->left;\n        AVLNode* T2 = x->right;\n\n        \/\/ \u6267\u884c\u65cb\u8f6c\n        x->right = y;\n        y->left = T2;\n\n        \/\/ \u66f4\u65b0\u9ad8\u5ea6\n        y->height = std::max(height(y->left), height(y->right)) + 1;\n        x->height = std::max(height(x->left), height(x->right)) + 1;\n\n        return x;\n    }\n\n    \/\/ \u5de6\u65cb\u64cd\u4f5c\n    AVLNode* leftRotate(AVLNode* x) {\n        AVLNode* y = x->right;\n        AVLNode* T2 = y->left;\n\n        \/\/ \u6267\u884c\u65cb\u8f6c\n        y->left = x;\n        x->right = T2;\n\n        \/\/ \u66f4\u65b0\u9ad8\u5ea6\n        x->height = std::max(height(x->left), height(x->right)) + 1;\n        y->height = std::max(height(y->left), height(y->right)) + 1;\n\n        return y;\n    }\n\n    \/\/ \u63d2\u5165\u8282\u70b9\u8f85\u52a9\u51fd\u6570\n    AVLNode* insert(AVLNode* node, int key) {\n        \/\/ 1. \u6267\u884c\u6807\u51c6BST\u63d2\u5165\n        if (!node) return new AVLNode(key);\n\n        if (key < node->key)\n            node->left = insert(node->left, key);\n        else if (key > node->key)\n            node->right = insert(node->right, key);\n        else \/\/ \u4e0d\u5141\u8bb8\u91cd\u590d\u952e\n            return node;\n\n        \/\/ 2. \u66f4\u65b0\u8282\u70b9\u9ad8\u5ea6\n        node->height = 1 + std::max(height(node->left), height(node->right));\n\n        \/\/ 3. \u83b7\u53d6\u5e73\u8861\u56e0\u5b50\u68c0\u67e5\u662f\u5426\u5e73\u8861\n        int balance = getBalance(node);\n\n        \/\/ \u5982\u679c\u4e0d\u5e73\u8861\uff0c\u67094\u79cd\u60c5\u51b5\n\n        \/\/ \u5de6\u5de6\u60c5\u51b5\n        if (balance > 1 && key < node->left->key)\n            return rightRotate(node);\n\n        \/\/ \u53f3\u53f3\u60c5\u51b5\n        if (balance < -1 && key > node->right->key)\n            return leftRotate(node);\n\n        \/\/ \u5de6\u53f3\u60c5\u51b5\n        if (balance > 1 && key > node->left->key) {\n            node->left = leftRotate(node->left);\n            return rightRotate(node);\n        }\n\n        \/\/ \u53f3\u5de6\u60c5\u51b5\n        if (balance < -1 && key < node->right->key) {\n            node->right = rightRotate(node->right);\n            return leftRotate(node);\n        }\n\n        return node;\n    }\n\n    \/\/ \u67e5\u627e\u6700\u5c0f\u8282\u70b9\n    AVLNode* minValueNode(AVLNode* node) {\n        AVLNode* current = node;\n        while (current->left)\n            current = current->left;\n        return current;\n    }\n\n    \/\/ \u5220\u9664\u8282\u70b9\u8f85\u52a9\u51fd\u6570\n    AVLNode* deleteNode(AVLNode* root, int key) {\n        \/\/ 1. \u6267\u884c\u6807\u51c6BST\u5220\u9664\n        if (!root) return root;\n\n        if (key < root->key)\n            root->left = deleteNode(root->left, key);\n        else if (key > root->key)\n            root->right = deleteNode(root->right, key);\n        else {\n            \/\/ \u8282\u70b9\u6709\u4e00\u4e2a\u6216\u6ca1\u6709\u5b50\u8282\u70b9\n            if (!root->left || !root->right) {\n                AVLNode* temp = root->left ? root->left : root->right;\n\n                \/\/ \u6ca1\u6709\u5b50\u8282\u70b9\u7684\u60c5\u51b5\n                if (!temp) {\n                    temp = root;\n                    root = nullptr;\n                } else \/\/ \u4e00\u4e2a\u5b50\u8282\u70b9\u7684\u60c5\u51b5\n                    *root = *temp; \/\/ \u590d\u5236\u975e\u7a7a\u5b50\u8282\u70b9\u5185\u5bb9\n\n                delete temp;\n            } else {\n                \/\/ \u8282\u70b9\u6709\u4e24\u4e2a\u5b50\u8282\u70b9\uff1a\u83b7\u53d6\u4e2d\u5e8f\u540e\u7ee7\uff08\u53f3\u5b50\u6811\u7684\u6700\u5c0f\u503c\uff09\n                AVLNode* temp = minValueNode(root->right);\n\n                \/\/ \u590d\u5236\u4e2d\u5e8f\u540e\u7ee7\u7684\u6570\u636e\u5230\u5f53\u524d\u8282\u70b9\n                root->key = temp->key;\n\n                \/\/ \u5220\u9664\u4e2d\u5e8f\u540e\u7ee7\n                root->right = deleteNode(root->right, temp->key);\n            }\n        }\n\n        \/\/ \u5982\u679c\u6811\u53ea\u6709\u4e00\u4e2a\u8282\u70b9\u5219\u8fd4\u56de\n        if (!root) return root;\n\n        \/\/ 2. \u66f4\u65b0\u5f53\u524d\u8282\u70b9\u7684\u9ad8\u5ea6\n        root->height = 1 + std::max(height(root->left), height(root->right));\n\n        \/\/ 3. \u83b7\u53d6\u5e73\u8861\u56e0\u5b50\u68c0\u67e5\u662f\u5426\u5e73\u8861\n        int balance = getBalance(root);\n\n        \/\/ \u5982\u679c\u4e0d\u5e73\u8861\uff0c\u67094\u79cd\u60c5\u51b5\n\n        \/\/ \u5de6\u5de6\u60c5\u51b5\n        if (balance > 1 && getBalance(root->left) >= 0)\n            return rightRotate(root);\n\n        \/\/ \u5de6\u53f3\u60c5\u51b5\n        if (balance > 1 && getBalance(root->left) < 0) {\n            root->left = leftRotate(root->left);\n            return rightRotate(root);\n        }\n\n        \/\/ \u53f3\u53f3\u60c5\u51b5\n        if (balance < -1 && getBalance(root->right) <= 0)\n            return leftRotate(root);\n\n        \/\/ \u53f3\u5de6\u60c5\u51b5\n        if (balance < -1 && getBalance(root->right) > 0) {\n            root->right = rightRotate(root->right);\n            return leftRotate(root);\n        }\n\n        return root;\n    }\n\n    \/\/ \u4e2d\u5e8f\u904d\u5386\u8f85\u52a9\u51fd\u6570\n    void inorder(AVLNode* node) {\n        if (node) {\n            inorder(node->left);\n            std::cout << node->key << " ";\n            inorder(node->right);\n        }\n    }\n\n    \/\/ \u524d\u5e8f\u904d\u5386\u8f85\u52a9\u51fd\u6570\n    void preorder(AVLNode* node) {\n        if (node) {\n            std::cout << node->key << " ";\n            preorder(node->left);\n            preorder(node->right);\n        }\n    }\n\npublic:\n    AVLTree() : root(nullptr) {}\n\n    \/\/ \u63d2\u5165\u8282\u70b9\n    void insert(int key) {\n        root = insert(root, key);\n    }\n\n    \/\/ \u5220\u9664\u8282\u70b9\n    void deleteKey(int key) {\n        root = deleteNode(root, key);\n    }\n\n    \/\/ \u4e2d\u5e8f\u904d\u5386\n    void inorder() {\n        inorder(root);\n        std::cout << std::endl;\n    }\n\n    \/\/ \u524d\u5e8f\u904d\u5386\n    void preorder() {\n        preorder(root);\n        std::cout << std::endl;\n    }\n\n    \/\/ \u67e5\u627e\u8282\u70b9\n    AVLNode* search(int key) {\n        AVLNode* current = root;\n        while (current) {\n            if (key < current->key)\n                current = current->left;\n            else if (key > current->key)\n                current = current->right;\n            else\n                return current;\n        }\n        return nullptr;\n    }\n};\n\n\/\/ \u6d4b\u8bd5\u4ee3\u7801\nint main() {\n    AVLTree tree;\n\n    \/\/ \u6d4b\u8bd5\u63d2\u5165\n    tree.insert(10);\n    tree.insert(20);\n    tree.insert(30);\n    tree.insert(40);\n    tree.insert(50);\n    tree.insert(25);\n\n    std::cout << "\u524d\u5e8f\u904d\u5386: ";\n    tree.preorder(); \/\/ \u5e94\u663e\u793a\u5e73\u8861\u540e\u7684\u6811\u7ed3\u6784\n\n    std::cout << "\u4e2d\u5e8f\u904d\u5386: ";\n    tree.inorder(); \/\/ \u5e94\u663e\u793a\u6709\u5e8f\u5e8f\u5217\n\n    \/\/ \u6d4b\u8bd5\u5220\u9664\n    tree.deleteKey(20);\n    std::cout << "\u5220\u966420\u540e\u7684\u4e2d\u5e8f\u904d\u5386: ";\n    tree.inorder();\n\n    \/\/ \u6d4b\u8bd5\u67e5\u627e\n    AVLNode* found = tree.search(30);\n    if (found)\n        std::cout << "\u627e\u5230\u8282\u70b930\\n";\n    else\n        std::cout << "\u672a\u627e\u5230\u8282\u70b930\\n";\n\n    return 0;\n}\n<\/pre><\/div>\n\n\n
    \u4ee3\u7801\u89e3\u6790<\/h2>\n\n\n\n
      \n
    1. \u8282\u70b9\u7ed3\u6784<\/strong>\uff1aAVLNode<\/code>\u5305\u542b\u952e\u503c\u3001\u5de6\u53f3\u5b50\u8282\u70b9\u6307\u9488\u548c\u9ad8\u5ea6\u4fe1\u606f\u3002<\/li>\n\n\n\n
    2. \u65cb\u8f6c\u64cd\u4f5c<\/strong>\uff1a
      \u2022 rightRotate<\/code>\u5904\u7406LL\u4e0d\u5e73\u8861\u60c5\u51b5
      \u2022 leftRotate<\/code>\u5904\u7406RR\u4e0d\u5e73\u8861\u60c5\u51b5
      \u2022 \u7ec4\u5408\u4f7f\u7528\u5904\u7406LR\u548cRL\u4e0d\u5e73\u8861\u60c5\u51b5<\/li>\n\n\n\n
    3. \u63d2\u5165\u64cd\u4f5c<\/strong>\uff1a
      \u2022 \u6267\u884c\u6807\u51c6BST\u63d2\u5165
      \u2022 \u66f4\u65b0\u8282\u70b9\u9ad8\u5ea6
      \u2022 \u68c0\u67e5\u5e73\u8861\u56e0\u5b50\u5e76\u8fdb\u884c\u5fc5\u8981\u7684\u65cb\u8f6c<\/li>\n\n\n\n
    4. \u5220\u9664\u64cd\u4f5c<\/strong>\uff1a
      \u2022 \u6267\u884c\u6807\u51c6BST\u5220\u9664
      \u2022 \u66f4\u65b0\u8282\u70b9\u9ad8\u5ea6
      \u2022 \u68c0\u67e5\u5e73\u8861\u56e0\u5b50\u5e76\u8fdb\u884c\u5fc5\u8981\u7684\u65cb\u8f6c<\/li>\n\n\n\n
    5. \u904d\u5386\u64cd\u4f5c<\/strong>\uff1a\u63d0\u4f9b\u4e2d\u5e8f\u548c\u524d\u5e8f\u904d\u5386\u65b9\u6cd5<\/li>\n\n\n\n
    6. \u67e5\u627e\u64cd\u4f5c<\/strong>\uff1a\u6807\u51c6BST\u67e5\u627e\u5b9e\u73b0<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"
      AVL\u6811\u662f\u4e00\u79cd\u81ea\u5e73\u8861\u4e8c\u53c9\u641c\u7d22\u6811\uff0c\u901a\u8fc7\u65cb\u8f6c\u64cd\u4f5c\u4fdd\u6301\u6811\u7684\u5e73\u8861\uff0c\u786e\u4fdd\u67e5\u627e\u3001\u63d2\u5165\u548c\u5220\u9664\u64cd\u4f5c\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO(log n […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"categories":[4],"tags":[126],"class_list":["post-541","post","type-post","status-publish","format-standard","hentry","category-algorithm","tag-126"],"_links":{"self":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts\/541","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=541"}],"version-history":[{"count":4,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts\/541\/revisions"}],"predecessor-version":[{"id":546,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts\/541\/revisions\/546"}],"wp:attachment":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=541"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=541"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=541"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}