{"id":78117,"date":"2026-02-26T08:11:32","date_gmt":"2026-02-26T00:11:32","guid":{"rendered":"https:\/\/www.wsisp.com\/helps\/78117.html"},"modified":"2026-02-26T08:11:32","modified_gmt":"2026-02-26T00:11:32","slug":"avl%e6%a0%91%e7%9a%84%e5%ae%9e%e7%8e%b0","status":"publish","type":"post","link":"https:\/\/www.wsisp.com\/helps\/78117.html","title":{"rendered":"AVL\u6811\u7684\u5b9e\u73b0"},"content":{"rendered":"

\u4e00.AVL\u6811\u7684\u6982\u5ff5\u4e0e\u7ed3\u6784<\/h2>\n

1.AVL\u6811\u7684\u6982\u5ff5<\/h2>\n

1.1.\u4e3a\u4ec0\u4e48\u7528AVL\u6811<\/p>\n

\u539f\u56e0：\u666e\u901a\u7684\u4e8c\u53c9\u641c\u7d22\u6811（BST）\u5728\u63d2\u5165\u6709\u5e8f\u6570\u636e（\u5982 1， 2， 3， 4， 5）\u65f6，\u4f1a\u53d8\u6210\u4e00\u4e2a\u53ea\u6709\u53f3\u5b69\u5b50\u7684\u957f\u94fe，\u6b64\u65f6\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u67e5\u627e\u6548\u7387\u5c31\u4eceO(log N)\u9000\u5316\u5230O(N)，\u4f46\u662fAVL \u6811：\u901a\u8fc7\u65cb\u8f6c\u673a\u5236，\u5f3a\u5236\u4fdd\u8bc1\u5de6\u53f3\u5b50\u6811\u9ad8\u5ea6\u5dee\u4e0d\u8d85\u8fc7 1，\u4f7f\u5f97\u6811\u9ad8\u59cb\u7ec8\u7ef4\u6301\u5728O(log N)\u3002<\/p>\n

1.2.AVL\u6811\u7684\u6982\u5ff5<\/p>\n

\u6982\u5ff5：AVL\u662f\u2f00\u9897\u7a7a\u6811，\u6216\u8005\u5177\u5907\u4e0b\u5217\u6027\u8d28\u7684\u2f06\u53c9\u641c\u7d22\u6811：\u5b83\u7684\u5de6\u53f3\u2f26\u6811\u90fd\u662fAVL\u6811，\u4e14\u5de6\u53f3\u2f26\u6811\u7684\u9ad8\u5ea6\u5dee（\u5e73\u8861\u56e0\u5b50）\u7684\u7edd\u5bf9\u503c\u4e0d\u8d85\u8fc71\u3002<\/p>\n

\u4f8b\u5982：\"\"<\/p>\n

\u6ce8\u610f：\u4e0a\u9762\u7684\u6bcf\u4e00\u4e2a\u6570\u4e0a\u7684\u6570\u5b57\u5c31\u662f\u5e73\u8861\u56e0\u5b50<\/p>\n

\u7279\u70b9：AVL\u6811\u5b9e\u73b0\u8fd9\u2fa5\u6211\u4eec\u5f15\u2f0a\u2f00\u4e2a\u5e73\u8861\u56e0\u2f26(balancefactor)\u7684\u6982\u5ff5，\u6bcf\u4e2a\u7ed3\u70b9\u90fd\u6709\u2f00\u4e2a\u5e73\u8861\u56e0\u2f26，\u4efb\u4f55\u7ed3\u70b9\u7684\u5e73\u8861\u56e0\u5b50\u7b49\u4e8e\u53f3\u2f26\u6811\u7684\u9ad8\u5ea6\u51cf\u53bb\u5de6\u5b50\u6811\u7684\u9ad8\u5ea6，\u4e5f\u5c31\u662f\u8bf4\u4efb\u4f55\u7ed3\u70b9\u7684\u5e73\u8861\u56e0\u2f26\u7b49\u4e8e0\/1\/-1， AVL\u6811\u5e76\u4e0d\u662f\u5fc5\u987b\u8981\u5e73\u8861\u56e0\u2f26，\u4f46\u662f\u6709\u4e86\u5e73\u8861\u56e0\u2f26\u53ef\u4ee5\u66f4\u2f45\u4fbf\u6211\u4eec\u53bb\u8fdb\u2f8f\u89c2\u5bdf\u548c\u63a7\u5236\u6811\u662f\u5426\u5e73\u8861， \u5c31\u50cf\u2f00\u4e2a\u2edb\u5411\u6807\u2f00\u6837\u3002<\/p>\n

\u95ee：\u4e3a\u4ec0\u4e48AVL\u6811\u662f\u9ad8\u5ea6\u5e73\u8861\u641c\u7d22\u2f06\u53c9\u6811，\u8981\u6c42\u9ad8\u5ea6\u5dee\u4e0d\u8d85\u8fc71，\u2f7d\u4e0d\u662f\u9ad8\u5ea6\u5dee\u662f0\u5462？0\u4e0d\u662f\u66f4\u597d\u7684\u5e73\u8861\u5417？<\/p>\n

\u539f\u56e0：0\u4e0d\u662f\u66f4\u597d\u7684\u5e73\u8861\u5417？\u753b\u753b\u56fe\u5206\u6790\u6211\u4eec\u53d1\u73b0，\u4e0d\u662f\u4e0d\u60f3\u8fd9\u6837\u8bbe\u8ba1，\u800c\u662f\u6709\u4e9b\u60c5\u51b5\u662f\u505a\u4e0d\u5230\u9ad8\u5ea6\u5dee\u662f0\u7684，\u6bd4\u5982\u2f00\u68f5\u6811\u662f2\u4e2a\u7ed3\u70b9，4\u4e2a\u7ed3\u70b9\u7b49\u60c5\u51b5\u4e0b，\u9ad8\u5ea6\u5dee\u6700\u597d\u5c31\u662f1，\u65e0\u6cd5\u505a\u5230\u9ad8\u5ea6\u5dee\u662f0\u3002<\/p>\n

\u6548\u7387：AVL\u6811\u6574\u4f53\u7ed3\u70b9\u6570\u91cf\u548c\u5206\u5e03\u548c\u5b8c\u5168\u4e8c\u53c9\u6811\u7c7b\u4f3c，\u9ad8\u5ea6\u53ef\u4ee5\u63a7\u5236\u5728 ，\u90a3\u4e48\u589e\u5220\u67e5\u6539\u7684\u6548\u7387\u4e5f\u53ef \u4ee5\u63a7\u5236\u5728O(logN) ，\u76f8\u6bd4\u4e8c\u53c9\u641c\u7d22\u6811\u6709\u4e86\u672c\u8d28\u7684\u63d0\u5347\u3002<\/p>\n

\"\"<\/p>\n

\u4f46\u662f\u5982\u679c\u6811\u957f\u6210\u8fd9\u6837，\u5c31\u4e0d\u662fAVL\u6811，\u6b64\u65f6\u5c31\u9700\u8981\u901a\u8fc7\u65cb\u8f6c\u4f7f\u5176\u53d8\u6210AVL\u6811\u3002<\/p>\n

2.AVL\u6811\u7684\u7ed3\u6784<\/h3>\n

\u9996\u5148\u6211\u4eec\u5b9a\u4e49\u4e24\u4e2a\u6587\u4ef6，\u4e00\u4e2a\u4e3aAVLTree.h，\u53e6\u4e00\u4e2a\u4e3aAVL_Test.cpp<\/p>\n

\u5728AVLTree.h\u4e2d，\u6211\u4eec\u5148\u5b9e\u73b0\u6bcf\u4e00\u4e2a\u8282\u70b9，\u4f8b\u5982：<\/p>\n

#include<iostream>
\n#include<assert.h>
\n#include<vector>
\nusing namespace std;
\ntemplate<class K,class V>
\nstruct AVLTNode
\n{
\npair<K, V> _kv;
\nAVLTNode<K, V>* _left;
\nAVLTNode<K, V>* _right;
\n\/\/parent\u6307\u9488\u7528\u4e8e\u540e\u7eed\u66f4\u65b0\u5e73\u8861\u56e0\u5b50
\nAVLTNode<K, V>* _parent;
\nint _bf;
\n\/\/\u6784\u9020\u51fd\u6570
\nAVLTNode(const pair<K,V>& kv)
\n:_kv(kv)
\n,_left(nullptr)
\n,_right(nullptr)
\n,_parent(nullptr)
\n,_bf(0)
\n{}
\n};<\/p>\n

\u89e3\u91ca：\u5176\u4e2d\u7684pair<K, V> _kv;\u4e0d\u9700\u8981\u6211\u4eec\u53bb\u5b9e\u73b0，AVLTNode<K, V>* _left;AVLTNode<K, V>* _right;\u4e0e\u641c\u7d22\u4e8c\u53c9\u6811\u7c7b\u4f3c，AVLTNode<K, V>* _parent;\u4e2d\u7684parent\u6307\u9488\u7528\u4e8e\u540e\u7eed\u66f4\u65b0\u5e73\u8861\u56e0\u5b50<\/p>\n

_bf\u7528\u4e8e\u8bb0\u5f55\u5e73\u8861\u56e0\u5b50<\/p>\n

template<class K, class V>
\nclass AVLTree
\n{
\n typedef AVLTreeNode<K, V> Node;
\npublic:
\n \/\/…
\nprivate:
\n Node* _root = nullptr;
\n};<\/p>\n

\u8fd9\u4e2a\u5c31\u4e3a\u6811\u7684\u5927\u6846\u67b6<\/p>\n

\u4e8c.AVL\u6811\u7684\u63d2\u5165（\u96be\u70b9）<\/h3>\n

1.\u63d2\u5165\u5927\u6982\u8fc7\u7a0b<\/h2>\n

1.1.\u8fc7\u7a0b<\/p>\n

<1>. \u63d2\u5165\u2f00\u4e2a\u503c\u6309\u2f06\u53c9\u641c\u7d22\u6811\u89c4\u5219\u8fdb\u884c\u63d2\u2f0a\u3002 <\/p>\n

<2>. \u65b0\u589e\u7ed3\u70b9\u4ee5\u540e，\u53ea\u4f1a\u5f71\u54cd\u7956\u5148\u7ed3\u70b9\u7684\u9ad8\u5ea6，\u4e5f\u5c31\u662f\u53ef\u80fd\u4f1a\u5f71\u54cd\u90e8\u5206\u7956\u5148\u7ed3\u70b9\u7684\u5e73\u8861\u56e0\u5b50，\u6240\u4ee5\u66f4\u65b0 \u4ece\u65b0\u589e\u7ed3\u70b9->\u6839\u7ed3\u70b9\u8def\u5f84\u4e0a\u7684\u5e73\u8861\u56e0\u5b50，\u5b9e\u9645\u4e2d\u6700\u574f\u60c5\u51b5\u4e0b\u8981\u66f4\u65b0\u5230\u6839，\u6709\u4e9b\u60c5\u51b5\u66f4\u65b0\u5230\u4e2d\u95f4\u5c31\u53ef\u4ee5\u505c\u6b62\u4e86，\u5177\u4f53\u60c5\u51b5\u6211\u4eec\u4e0b\u9762\u518d\u8be6\u7ec6\u5206\u6790\u3002 <\/p>\n

<3>. \u66f4\u65b0\u5e73\u8861\u56e0\u5b50\u8fc7\u7a0b\u4e2d\u6ca1\u6709\u51fa\u73b0\u95ee\u9898，\u5219\u63d2\u5165\u7ed3\u675f\u3002<\/p>\n

<4>. \u66f4\u65b0\u5e73\u8861\u56e0\u5b50\u8fc7\u7a0b\u4e2d\u51fa\u73b0\u4e0d\u5e73\u8861，\u5bf9\u4e0d\u5e73\u8861\u5b50\u6811\u65cb\u8f6c，\u65cb\u8f6c\u540e\u672c\u8d28\u8c03\u5e73\u8861\u7684\u540c\u65f6，\u672c\u8d28\u964d\u4f4e\u4e86\u5b50\u6811 \u7684\u9ad8\u5ea6，\u4e0d\u4f1a\u518d\u5f71\u54cd\u4e0a\u2f00\u5c42，\u6240\u4ee5\u63d2\u5165\u7ed3\u675f\u3002<\/p>\n

1.2.\u5e73\u8861\u56e0\u5b50\u66f4\u65b0<\/p>\n

1.2.1.\u66f4\u65b0\u539f\u5219：<\/p>\n

\u2022 \u5e73\u8861\u56e0\u5b50=\u5de6\u5b50\u6811\u9ad8\u5ea6-\u5de6\u5b50\u6811\u9ad8\u5ea6（\u4e5f\u53ef\u4ee5\u5de6\u5b50\u6811\u9ad8\u5ea6-\u53f3\u5b50\u6811\u9ad8\u5ea6，\u53d6\u51b3\u4e8e\u81ea\u5df1）\u3002<\/p>\n

\u2022 \u53ea\u6709\u5b50\u6811\u9ad8\u5ea6\u53d8\u5316\u624d\u4f1a\u5f71\u54cd\u5f53\u524d\u7ed3\u70b9\u5e73\u8861\u56e0\u5b50\u3002<\/p>\n

\u2022 \u63d2\u2f0a\u7ed3\u70b9，\u4f1a\u589e\u52a0\u9ad8\u5ea6，\u6240\u4ee5\u65b0\u589e\u7ed3\u70b9\u5728parent\u7684\u53f3\u5b50\u6811，parent\u7684\u5e73\u8861\u56e0\u5b50++，\u65b0\u589e\u7ed3\u70b9\u5728 parent\u7684\u5de6\u5b50\u6811，parent\u5e73\u8861\u56e0\u5b50– <\/p>\n

\u2022 parent\u6240\u5728\u5b50\u6811\u7684\u9ad8\u5ea6\u662f\u5426\u53d8\u5316\u51b3\u5b9a\u4e86\u662f\u5426\u4f1a\u7ee7\u7eed\u5f80\u4e0a\u66f4\u65b0\u3002<\/p>\n

1.2.2.\u66f4\u65b0\u505c\u6b62\u6761\u4ef6： <\/p>\n

\u2022 \u66f4\u65b0\u540eparent\u7684\u5e73\u8861\u56e0\u5b50\u7b49\u4e8e0，\u8bf4\u660e\u66f4\u65b0\u4e2dparent\u7684\u5e73\u8861\u56e0\u5b50\u53d8\u5316\u4e3a-1->0\u6216\u80051->0，\u8bf4\u660e\u66f4\u65b0\u524d parent\u5b50\u6811\u2f00\u8fb9\u9ad8\u2f00\u8fb9\u4f4e，\u65b0\u589e\u7684\u7ed3\u70b9\u63d2\u5165\u5728\u4f4e\u7684\u90a3\u8fb9，\u63d2\u5165\u540eparent\u6240\u5728\u7684\u5b50\u6811\u9ad8\u5ea6\u4e0d\u53d8，\u4e0d\u4f1a\u5f71\u54cdparent\u7684\u7236\u4eb2\u7ed3\u70b9\u7684\u5e73\u8861\u56e0\u5b50，\u66f4\u65b0\u7ed3\u675f\u3002<\/p>\n

\u4f8b\u5982：3\u4e3a\u6839\u7684\u5b50\u6811\u9ad8\u5ea6\u4e0d\u53d8，\u4e0d\u4f1a\u5f71\u54cd\u4e0a\u2f00\u5c42，\u66f4\u65b0\u7ed3\u675f\"\"<\/p>\n

\u2022 \u66f4\u65b0\u540eparent\u7684\u5e73\u8861\u56e0\u5b50\u7b49\u4e8e1\u6216-1，\u66f4\u65b0\u524d\u66f4\u65b0\u4e2dparent\u7684\u5e73\u8861\u56e0\u5b50\u53d8\u5316\u4e3a0->1\u6216\u80050->-1，\u8bf4 \u660e\u66f4\u65b0\u524dparent\u5b50\u6811\u4e24\u8fb9\u2f00\u6837\u9ad8，\u65b0\u589e\u7684\u63d2\u2f0a\u7ed3\u70b9\u540e，parent\u6240\u5728\u7684\u5b50\u6811\u2f00\u8fb9\u9ad8\u2f00\u8fb9\u4f4e，parent\u6240 \u5728\u7684\u5b50\u6811\u7b26\u5408\u5e73\u8861\u8981\u6c42，\u4f46\u662f\u9ad8\u5ea6\u589e\u52a0\u4e861，\u4f1a\u5f71\u54cdparent\u7684\u7236\u4eb2\u7ed3\u70b9\u7684\u5e73\u8861\u56e0\u2f26，\u6240\u4ee5\u8981\u7ee7\u7eed\u5411\u4e0a\u66f4\u65b0\u3002<\/p>\n

\u4f8b\u5982：1\u4e3a\u6839\u7684\u5b50\u6811\u9ad8\u5ea6\u6539\u53d8，\u5f71\u54cd\u4e0a\u2f00\u5c42，\u66f4\u65b0\u7ee7\u7eed，\u4f7fcur=parent，parent=parent->_parent\"\"<\/p>\n

\u2022 \u66f4\u65b0\u540eparent\u7684\u5e73\u8861\u56e0\u2f26\u7b49\u4e8e2\u6216-2，\u66f4\u65b0\u524d\u66f4\u65b0\u4e2dparent\u7684\u5e73\u8861\u56e0\u2f26\u53d8\u5316\u4e3a1->2\u6216\u8005-1->-2，\u8bf4 \u660e\u66f4\u65b0\u524dparent\u5b50\u6811\u2f00\u8fb9\u9ad8\u2f00\u8fb9\u4f4e，\u65b0\u589e\u7684\u63d2\u5165\u7ed3\u70b9\u5728\u9ad8\u7684\u90a3\u8fb9，parent\u6240\u5728\u7684\u5b50\u6811\u9ad8\u7684\u90a3\u8fb9\u66f4\u9ad8\u4e86，\u7834\u574f\u4e86\u5e73\u8861，parent\u6240\u5728\u7684\u5b50\u6811\u4e0d\u7b26\u5408\u5e73\u8861\u8981\u6c42，\u9700\u8981\u65cb\u8f6c\u5904\u7406，\u65cb\u8f6c\u7684\u76ee\u6807\u6709\u4e24\u4e2a：1\u3001\u628a parent\u5b50\u6811\u65cb\u8f6c\u5e73\u8861\u30022\u3001\u964d\u4f4eparent\u2f26\u6811\u7684\u9ad8\u5ea6，\u6062\u590d\u5230\u63d2\u2f0a\u7ed3\u70b9\u4ee5\u524d\u7684\u9ad8\u5ea6\u3002\u6240\u4ee5\u65cb\u8f6c\u540e\u4e5f\u4e0d \u9700\u8981\u7ee7\u7eed\u5f80\u4e0a\u66f4\u65b0，\u63d2\u5165\u7ed3\u675f\u3002<\/p>\n

\u4f8b\u5982：\u66f4\u65b0\u523010\u7ed3\u70b9，\u5e73\u8861\u56e0\u5b50\u4e3a2，10\u6240\u5728\u7684\u5b50\u6811\u5df2\u7ecf\u4e0d\u5e73\u8861，\u9700\u8981\u65cb\u8f6c\u5904\u7406\"\"<\/p>\n

\u2022 \u4e0d\u65ad\u66f4\u65b0，\u66f4\u65b0\u5230\u6839，\u6839\u7684\u5e73\u8861\u56e0\u5b50\u662f1\u6216-1\u4e5f\u505c\u6b62\u4e86\u3002<\/p>\n

\u4f8b\u5982：\"\"<\/p>\n

\u90a3\u4e48\u63d2\u5165\u7684\u4ee3\u7801\u5c31\u53ef\u4ee5\u8fd9\u6837\u5199：<\/p>\n

bool Insert(const pair<K, V>& kv)
\n{
\nif (_root == nullptr)
\n{
\n_root = new Node(kv);
\nreturn true;
\n}<\/p>\n

Node* parent = nullptr;
\nNode* cur = _root;
\nwhile (cur)
\n{
\nif (cur->_kv.first < kv.first)
\n{
\nparent = cur;
\ncur = cur->_right;
\n}
\nelse if (cur->_kv.first > kv.first)
\n{
\nparent = cur;
\ncur = cur->_left;
\n}
\nelse
\n{
\nreturn false;
\n}
\n}
\ncur = new Node(kv);
\nif (parent->_kv.first < kv.first)
\n{
\nparent->_right = cur;
\n}
\nelse
\n{
\nparent->_left = cur;
\n}
\ncur->_parent = parent;<\/p>\n

while (parent)
\n{
\n \/\/\u66f4\u65b0\u5e73\u8861\u56e0\u5b50
\nif (parent->_left == cur)
\n{
\nparent->_bf–;
\n}
\nelse
\n{
\nparent->_bf++;
\n}
\n \/\/\u67e5\u627e\u66f4\u65b0\u5e73\u8861\u56e0\u5b50\u540e，\u8981\u65cb\u8f6c\u7684\u8282\u70b9
\nif (parent->_bf == 0)
\n{
\nbreak;
\n}
\nelse if (parent->_bf == 1 || parent->_bf == -1)
\n{
\ncur = parent;
\nparent = parent->_parent;
\n}
\nelse if (parent->_bf == 2 || parent->_bf == -2)
\n{
\nif (parent->_bf == -2 && cur->_bf == -1)
\n{
\nRotate_Right(parent);
\n}
\nelse if (parent->_bf == 2 && cur->_bf == 1)
\n{
\nRotate_Left(parent);
\n}
\nelse if (parent->_bf == -2 && cur->_bf == 1)
\n{
\nRotate_Left_Right(parent);
\n}
\nelse if (parent->_bf == 2 && cur->_bf == -1)
\n{
\nRotate_Right_Left(parent);
\n}
\nelse
\n{
\nassert(false);
\n}
\nbreak;
\n}
\nelse
\n{
\nassert(false);
\n}
\n}
\nreturn true;
\n}<\/p>\n

\u89e3\u91ca：\u5176\u5b9e\u524d\u9762\u7684\u4ee3\u7801\u5c31\u662f\u5bfb\u627e\u8981\u63d2\u5165\u8282\u70b9\u7684\u5730\u65b9，\u6ca1\u6709\u627e\u5230，\u5c31\u8fd4\u56defalse，\u627e\u5230\u4e86，\u5c31\u63d2\u5165\u8282\u70b9，\u800ccur->_parent = parent;\u5c31\u7528\u4e8e\u6307\u5411cur\u81ea\u5df1\u7684\u7236\u4eb2\u8282\u70b9，\u7136\u540e\u5728parent\u5faa\u73af\u4e2d，\u5148\u66f4\u65b0\u5e73\u8861\u56e0\u5b50，\u518d\u5224\u65ad\u66f4\u65b0\u540e\u7684\u5e73\u8861\u56e0\u5b50\u662f\u5426\u6ee1\u8db3\u66f4\u65b0\u505c\u6b62\u6761\u4ef6，\u6ee1\u8db3\u505c\u6b62\u6761\u4ef6\u5c31\u505c\u6b62\u66f4\u65b0，\u4e0d\u6ee1\u8db3\u505c\u6b62\u6761\u4ef6\u5c31\u7ee7\u7eed\u5411\u4e0a\u66f4\u65b0，\u5982\u679c\u9047\u5230parent->_bf\u7684\u7edd\u5bf9\u503c\u5927\u4e8e1，\u5c31\u9700\u8981\u65cb\u8f6c（Rotate）\u3002<\/p>\n

2.\u65cb\u8f6c<\/h3>\n

\u89c4\u5219：<\/p>\n

<1>. \u4fdd\u6301\u641c\u7d22\u6811\u7684\u89c4\u5219 <\/p>\n

<2>. \u8ba9\u65cb\u8f6c\u7684\u6811\u4ece\u4e0d\u6ee1\u8db3\u53d8\u5e73\u8861，\u5176\u6b21\u964d\u4f4e\u65cb\u8f6c\u6811\u7684\u9ad8\u5ea6<\/p>\n

\u65cb\u8f6c\u603b\u5171\u5206\u4e3a\u56db\u79cd，\u5de6\u5355\u65cb\/\u53f3\u5355\u65cb\/\u5de6\u53f3\u53cc\u65cb\/\u53f3\u5de6\u53cc\u65cb\u3002<\/p>\n

\u6ce8\u610f：\u4e0b\u9762\u7684\u56fe\u4e2d，\u6709\u4e9b\u7ed3\u70b9\u6211\u4eec\u7ed9\u7684\u662f\u5177\u4f53\u503c，\u598210\u548c5\u7b49\u7ed3\u70b9，\u8fd9\u91cc\u662f\u4e3a\u4e86\u65b9\u4fbf\u8bb2\u89e3，\u5b9e\u9645\u4e2d\u662f\u4ec0 \u4e48\u503c\u90fd\u53ef\u4ee5，\u53ea\u8981\u5927\u5c0f\u5173\u7cfb\u7b26\u5408\u641c\u7d22\u6811\u7684\u6027\u8d28\u5373\u53ef\u3002<\/p>\n

2.1.\u53f3\u5355\u65cb<\/h2>\n

\u2022 \u672c\u56fe1\u5c55\u793a\u7684\u662f10\u4e3a\u6839\u7684\u6811，\u6709a\/b\/c\u62bd\u8c61\u4e3a\u4e09\u68f5\u9ad8\u5ea6\u4e3ah\u7684\u5b50\u6811(h>=0)，a\/b\/c\u5747\u7b26\u5408AVL\u6811\u7684\u8981 \u6c42\u300210\u53ef\u80fd\u662f\u6574\u68f5\u6811\u7684\u6839，\u4e5f\u53ef\u80fd\u662f\u2f00\u4e2a\u6574\u68f5\u6811\u4e2d\u5c40\u90e8\u7684\u5b50\u6811\u7684\u6839\u3002\u8fd9\u91cca\/b\/c\u662f\u9ad8\u5ea6\u4e3ah\u7684\u2f26\u6811， \u662f\u2f00\u79cd\u6982\u62ec\u62bd\u8c61\u8868\u793a，\u4ed6\u4ee3\u8868\u4e86\u6240\u6709\u53f3\u5355\u65cb\u7684\u573a\u666f，\u5b9e\u9645\u53f3\u5355\u65cb\u5f62\u6001\u6709\u5f88\u591a\u79cd，\u5177\u4f53\u56fe2\/\u56fe3\/\u56fe4\/ \u56fe5\u8fdb\u2f8f\u4e86\u8be6\u7ec6\u63cf\u8ff0\u3002<\/p>\n

\u2022 \u5728a\u5b50\u6811\u4e2d\u63d2\u5165\u2f00\u4e2a\u65b0\u7ed3\u70b9，\u5bfc\u81f4a\u5b50\u6811\u7684\u9ad8\u5ea6\u4eceh\u53d8\u6210h+1，\u4e0d\u65ad\u5411\u4e0a\u66f4\u65b0\u5e73\u8861\u56e0\u2f26，\u5bfc\u81f410\u7684\u5e73\u8861\u56e0\u5b50\u4ece-1\u53d8\u6210-2，10\u4e3a\u6839\u7684\u6811\u5de6\u53f3\u9ad8\u5ea6\u5dee\u8d85\u8fc71，\u8fdd\u53cd\u5e73\u8861\u89c4\u5219\u300210\u4e3a\u6839\u7684\u6811\u5de6\u8fb9\u592a\u9ad8\u4e86，\u9700\u8981 \u5f80\u53f3\u8fb9\u65cb\u8f6c，\u63a7\u5236\u4e24\u68f5\u6811\u7684\u5e73\u8861\u3002 <\/p>\n

\u2022 \u65cb\u8f6c\u6838\u5fc3\u6b65\u9aa4，\u56e0\u4e3a5<b\u5b50\u6811\u7684\u503c<10，\u4e3a\u5c06b\u53d8\u621010\u7684\u5de6\u5b50\u6811，10\u53d8\u62105\u7684\u53f3\u5b50\u6811，5\u53d8\u6210\u8fd9\u68f5\u6811\u65b0 \u7684\u6839，\u7b26\u5408\u641c\u7d22\u6811\u7684\u89c4\u5219，\u63a7\u5236\u4e86\u5e73\u8861，\u540c\u65f6\u8fd9\u68f5\u7684\u9ad8\u5ea6\u6062\u590d\u5230\u4e86\u63d2\u5165\u4e4b\u524d\u7684h+2，\u7b26\u5408\u65cb\u8f6c\u539f \u5219\u3002\u5982\u679c\u63d2\u5165\u4e4b\u524d10\u6574\u68f5\u6811\u7684\u2f00\u4e2a\u5c40\u90e8\u5b50\u6811，\u65cb\u8f6c\u540e\u4e0d\u4f1a\u518d\u5f71\u54cd\u4e0a\u4e00\u5c42，\u63d2\u5165\u7ed3\u675f\u4e86\u3002<\/p>\n

\u4f8b\u5982：\u8fd9\u4e2a\u62bd\u8c61\u4f8b\u5b50\"\"<\/p>\n

\u89e3\u91ca：\u5728\u8fd9\u4e2a\u56fe\u4e2d，a,b,c\u7684\u9ad8\u5ea6\u5fc5\u987b\u5b58\u5728\u4e14\u76f8\u7b49，\u5982\u679cb\u7684\u9ad8\u5ea6\u6bd4a\u5c0f1，\u5c31\u4f1a\u5bfc\u81f4\u5728a\u5904\u63d2\u5165\u65f6，5\u7684\u5e73\u8861\u56e0\u5b50\u53d8\u4e3a-2，\u90a3\u4e48\u8981\u65cb\u8f6c\u7684\u5c31\u4e0d\u662f10\u8fd9\u4e2a\u8282\u70b9，\u5982\u679cc\u7684\u9ad8\u5ea6\u6bd4a\u548cb\u5c0f1，\u5c31\u4f1a\u5bfc\u81f4\u63d2\u5165\u524d\u5c31\u4e0d\u6ee1\u8db3AVL\u6811，\u6240\u4ee5\u4e5f\u4e0d\u6ee1\u8db3\u63d2\u5165\u6761\u4ef6，\u6ee1\u8db3a,b,c\u7684\u9ad8\u5ea6\u5fc5\u987b\u5b58\u5728（\u9ad8\u5ea6>=0）\u4e14\u76f8\u7b49\u540e，\u6211\u4eec\u57285（parent）\u7684\u53f3\u8fb9a\u63d2\u5165\u4e00\u4e2a\u8282\u70b9，\u4f1a\u5bfc\u81f45\u7684\u5e73\u8861\u56e0\u5b50\u75310->-1,parent\u5411\u4e0a\u66f4\u65b0，\u6b64\u65f610\u8fd9\u4e2aparent\u5e73\u8861\u56e0\u5b50\u53d8\u4e3a-2，\u90a3\u4e48\u6211\u4eec\u5c31\u8fdb\u884c\u5bf910\u8fdb\u884c\u53f3\u5355\u65cb，\u964d\u4f4e10\u7684\u9ad8\u5ea6，\u5c31\u53ef\u4ee5\u5c06\u9ad8\u5ea6\u4e3ah+1\u7684a\u7ed9subL，subLR\u53d8\u4e3aparent\u7684\u5de6\u8fb9，\u6b64\u65f6subL\u4e0eparent\u7684\u5de6\u53f3\u4e24\u8fb9\u9ad8\u5ea6\u5747\u76f8\u7b49，\u5e73\u8861\u56e0\u5b50\u4e5f\u5c31\u53d8\u4e3a\u4e860\u3002<\/p>\n

\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u5177\u4f53\u7684\u4f8b\u5b50：<\/p>\n

\"\"<\/p>\n

\"\"<\/p>\n

\"\"<\/p>\n

\"\"<\/p>\n

\u6211\u4eec\u53ef\u4ee5\u901a\u8fc7\u4ee5\u4e0a\u7684\u4f8b\u5b50，\u4e86\u89e3\u53f3\u5355\u65cb\u7684\u62bd\u8c61\u5b9e\u4f8b\u3002<\/p>\n

\u4ee3\u7801：<\/p>\n

void Rotate_Right(Node* parent)
\n{
\nNode* subL = parent->_left;
\nNode* subLR = subL->_right;
\nNode* Pparent = parent->_parent;<\/p>\n

subL->_right = parent;
\nparent->_left = subLR;
\nparent->_parent = subL;
\nif (subLR)
\n{
\nsubLR->_parent = parent;
\n}<\/p>\n

\/\/parent\u4e3a\u6839\u8282\u70b9\u7684\u60c5\u51b5
\nif (_root == parent)
\n{
\n_root = subL;
\nsubL->_parent = nullptr;
\n}
\nelse
\n{
\nif (Pparent->_left == parent)
\n{
\nPparent->_left = subL;
\n}
\n\/\/Pparent->_right == parent
\nelse
\n{
\nPparent->_right = subL;
\n}
\nsubL->_parent = Pparent;
\n}<\/p>\n

\/\/\u66f4\u65b0\u5e73\u8861\u56e0\u5b50
\nsubL->_bf = parent->_bf = 0;
\n}<\/p>\n

\u89e3\u91ca：\u6211\u4eec\u5148\u5b9a\u4e49subL\u4e0esubLR，\u5206\u522b\u4e3aparent\u7684\u5de6\u8fb9，subL\u7684\u53f3\u8fb9，\u6211\u4eec\u4e0d\u5149\u8981\u8981\u6539\u53d8subL\u7684\u53f3\u6307\u5411parent，parent\u7684\u5de6\u6307\u5411subLR，\u8fd8\u8981\u8003\u8651subLR\u4e0d\u4e3anullptr\u65f6，\u4f7fsubLR\u7684_parent\u6307\u5411parent，parent\u7684_parent\u6307\u5411subL，\u800c\u4e14\u8fd8\u8981\u8003\u8651parent\u4e3a_root\u65f6，\u6539\u53d8_root\u4e0esubL\u7684parent，\u4ee5\u53caparent\u4e0d\u4e3a_root\u65f6，\u8bb0\u5f55\u4e00\u4e2aPparent\u4e3aparent\u7684\u7236\u4eb2\u8282\u70b9，\u4f7fPParent\u7684\u5de6\u8fb9\/\u53f3\u8fb9\u6307\u5411subL，subL\u7684_parent\u6307\u5411Pparent，\u6700\u540e\u6539\u53d8subL->_bf \u4e0e\u00a0parent->_bf \u7684\u5e73\u8861\u56e0\u5b50\u3002<\/p>\n

2.2.\u5de6\u5355\u65cb<\/h3>\n

\u672c\u56fe6\u5c55\u793a\u7684\u662f10\u4e3a\u6839\u7684\u6811，\u6709a\/b\/c\u62bd\u8c61\u4e3a\u4e09\u68f5\u9ad8\u5ea6\u4e3ah\u7684\u5b50\u6811（h>=0），a\/b\/c\u5747\u7b26\u5408AVL\u6811\u7684\u8981\u6c42\u300210\u53ef\u80fd\u662f\u6574\u68f5\u6811\u7684\u6839，\u4e5f\u53ef\u80fd\u662f\u2f00\u4e2a\u6574\u68f5\u6811\u4e2d\u5c40\u90e8\u7684\u2f26\u6811\u7684\u6839\u3002\u8fd9\u2fa5a\/b\/c\u662f\u2fbc\u5ea6\u4e3ah\u7684\u2f26\u6811， \u662f\u2f00\u79cd\u6982\u62ec\u62bd\u8c61\u8868\u2f70，\u4ed6\u4ee3\u8868\u4e86\u6240\u6709\u53f3\u5355\u65cb\u7684\u573a\u666f，\u5b9e\u9645\u53f3\u5355\u65cb\u5f62\u6001\u6709\u5f88\u591a\u79cd，\u5177\u4f53\u8ddf\u4e0a\u2faf\u5de6\u65cb\u7c7b \u4f3c\u3002<\/p>\n

\u2022 \u5728a\u5b50\u6811\u4e2d\u63d2\u5165\u4e00\u4e2a\u65b0\u7ed3\u70b9，\u5bfc\u81f4a\u5b50\u6811\u7684\u9ad8\u5ea6\u4eceh\u53d8\u6210h+1，\u4e0d\u65ad\u5411\u4e0a\u66f4\u65b0\u5e73\u8861\u56e0\u5b50，\u5bfc\u81f410\u7684\u5e73\u8861\u56e0\u5b50\u4ece1\u53d8\u62102,10\u4e3a\u6839\u7684\u6811\u5de6\u53f3\u9ad8\u5ea6\u5dee\u8d85\u8fc71，\u8fdd\u53cd\u5e73\u8861\u89c4\u5219\u300210\u4e3a\u6839\u7684\u6811\u53f3\u8fb9\u592a\u2fbc\u4e86，\u9700\u8981\u5f80 \u5de6\u8fb9\u65cb\u8f6c，\u63a7\u5236\u4e24\u68f5\u6811\u7684\u5e73\u8861\u3002<\/p>\n

\u2022 \u65cb\u8f6c\u6838\u2f3c\u6b65\u9aa4，\u56e0\u4e3a10<b\u5b50\u6811\u7684\u503c<15，\u5c06b\u53d8\u621010\u7684\u53f3\u2f26\u6811，10\u53d8\u621015\u7684\u5de6\u2f26\u6811，15\u53d8\u6210\u8fd9\u68f5 \u6811\u65b0\u7684\u6839，\u7b26\u5408\u641c\u7d22\u6811\u7684\u89c4\u5219，\u63a7\u5236\u4e86\u5e73\u8861，\u540c\u65f6\u8fd9\u68f5\u7684\u2fbc\u5ea6\u6062\u590d\u5230\u4e86\u63d2\u2f0a\u4e4b\u524d\u7684h+2，\u7b26\u5408\u65cb\u8f6c \u539f\u5219\u3002\u5982\u679c\u63d2\u2f0a\u4e4b\u524d10\u6574\u68f5\u6811\u7684\u2f00\u4e2a\u5c40\u90e8\u2f26\u6811，\u65cb\u8f6c\u540e\u4e0d\u4f1a\u518d\u5f71\u54cd\u4e0a\u2f00\u5c42，\u63d2\u2f0a\u7ed3\u675f\u4e86\u3002<\/p>\n

\u4f8b\u5982：\"\"<\/p>\n

\u4ee3\u7801：<\/p>\n

void Rotate_Left(Node* parent)
\n{
\nNode* subR = parent->_right;
\nNode* subRL = subR->_left;
\nNode* Pparent = parent->_parent;<\/p>\n

subR->_left = parent;
\nparent->_right = subRL;
\nparent->_parent = subR;
\nif (subRL)
\n{
\nsubRL->_parent = parent;
\n}
\nif (parent == _root)
\n{
\n_root = subR;
\nsubR->_parent = nullptr;
\n}
\nelse
\n{
\nif (Pparent->_left == parent)
\n{
\nPparent->_left = subR;
\n}
\n\/\/Pparent->_right == parent
\nelse
\n{
\nPparent->_right = subR;
\n}
\nsubR->_parent = Pparent;
\n}<\/p>\n

\/\/\u66f4\u65b0\u5e73\u8861\u56e0\u5b50
\nsubR->_bf = parent->_bf = 0;
\n}<\/p>\n

2.3.\u5de6\u53f3\u53cc\u65cb<\/h4>\n

\u901a\u8fc7\u56fe1\u548c\u56fe2\u53ef\u4ee5\u770b\u5230，\u5de6\u8fb9\u2fbc\u65f6，\u5982\u679c\u63d2\u2f0a\u4f4d\u7f6e\u4e0d\u662f\u5728a\u2f26\u6811，\u2f7d\u662f\u63d2\u2f0a\u5728b\u2f26\u6811，b\u2f26\u6811\u2fbc\u5ea6\u4eceh\u53d8 \u6210h+1，\u5f15\u53d1\u65cb\u8f6c，\u53f3\u5355\u65cb\u2f46\u6cd5\u89e3\u51b3\u95ee\u9898，\u53f3\u5355\u65cb\u540e，\u6211\u4eec\u7684\u6811\u4f9d\u65e7\u4e0d\u5e73\u8861\u3002\u53f3\u5355\u65cb\u89e3\u51b3\u7684\u7eaf\u7cb9\u7684\u5de6\u8fb9 \u2fbc，\u4f46\u662f\u63d2\u2f0a\u5728b\u2f26\u6811\u4e2d，10\u4e3a\u8ddf\u7684\u2f26\u6811\u4e0d\u518d\u662f\u5355\u7eaf\u7684\u5de6\u8fb9\u2fbc，\u5bf9\u4e8e10\u662f\u5de6\u8fb9\u2fbc，\u4f46\u662f\u5bf9\u4e8e5\u662f\u53f3\u8fb9 \u2fbc，\u9700\u8981\u2f64\u4e24\u6b21\u65cb\u8f6c\u624d\u80fd\u89e3\u51b3，\u4ee55\u4e3a\u65cb\u8f6c\u70b9\u8fdb\u2f8f\u2f00\u4e2a\u5de6\u5355\u65cb，\u4ee510\u4e3a\u65cb\u8f6c\u70b9\u8fdb\u2f8f\u2f00\u4e2a\u53f3\u5355\u65cb，\u8fd9\u68f5\u6811 \u8fd9\u68f5\u6811\u5c31\u5e73\u8861\u4e86\u3002<\/p>\n

\u5982\u56fe1：\"\"<\/p>\n

\u5982\u56fe2：<\/p>\n

\"\"<\/p>\n

\u2022 \u56fe1\u548c\u56fe2\u5206\u522b\u4e3a\u5de6\u53f3\u53cc\u65cb\u4e2dh==0\u548ch==1\u5177\u4f53\u573a\u666f\u5206\u6790，\u4e0b\u2faf\u6211\u4eec\u5c06a\/b\/c\u2f26\u6811\u62bd\u8c61\u4e3a\u2fbc\u5ea6h\u7684AVL \u2f26\u6811\u8fdb\u2f8f\u5206\u6790，\u53e6\u5916\u6211\u4eec\u9700\u8981\u628ab\u2f26\u6811\u7684\u7ec6\u8282\u8fdb\u2f00\u6b65\u5c55\u5f00\u4e3a8\u548c\u5de6\u2f26\u6811\u2fbc\u5ea6\u4e3ah-1\u7684e\u548cf\u2f26\u6811，\u56e0\u4e3a \u6211\u4eec\u8981\u5bf9b\u7684\u2f57\u4eb25\u4e3a\u65cb\u8f6c\u70b9\u8fdb\u2f8f\u5de6\u5355\u65cb，\u5de6\u5355\u65cb\u9700\u8981\u52a8b\u6811\u4e2d\u7684\u5de6\u2f26\u6811\u3002b\u2f26\u6811\u4e2d\u65b0\u589e\u7ed3\u70b9\u7684\u4f4d\u7f6e \u4e0d\u540c，\u5e73\u8861\u56e0\u2f26\u66f4\u65b0\u7684\u7ec6\u8282\u4e5f\u4e0d\u540c，\u901a\u8fc7\u89c2\u5bdf8\u7684\u5e73\u8861\u56e0\u2f26\u4e0d\u540c，\u8fd9\u2fa5\u6211\u4eec\u8981\u5206\u4e09\u4e2a\u573a\u666f\u8ba8\u8bba\u3002\u00a0<\/p>\n

\u2022 \u573a\u666f1：h>=1\u65f6，\u65b0\u589e\u7ed3\u70b9\u63d2\u2f0a\u5728e\u2f26\u6811，e\u2f26\u6811\u2fbc\u5ea6\u4eceh-1\u5e76\u4e3ah\u5e76\u4e0d\u65ad\u66f4\u65b08->5->10\u5e73\u8861\u56e0\u2f26， \u5f15\u53d1\u65cb\u8f6c，\u5176\u4e2d8\u7684\u5e73\u8861\u56e0\u2f26\u4e3a-1，\u65cb\u8f6c\u540e8\u548c5\u5e73\u8861\u56e0\u2f26\u4e3a0，10\u5e73\u8861\u56e0\u2f26\u4e3a1\u3002<\/p>\n

\u2022 \u573a\u666f2：h>=1\u65f6，\u65b0\u589e\u7ed3\u70b9\u63d2\u2f0a\u5728f\u2f26\u6811，f\u2f26\u6811\u2fbc\u5ea6\u4eceh-1\u53d8\u4e3ah\u5e76\u4e0d\u65ad\u66f4\u65b08->5->10\u5e73\u8861\u56e0\u2f26，\u5f15 \u53d1\u65cb\u8f6c，\u5176\u4e2d8\u7684\u5e73\u8861\u56e0\u2f26\u4e3a1，\u65cb\u8f6c\u540e8\u548c10\u5e73\u8861\u56e0\u2f26\u4e3a0，5\u5e73\u8861\u56e0\u2f26\u4e3a-1\u3002<\/p>\n

\u2022 \u573a\u666f3：h==0\u65f6，a\/b\/c\u90fd\u662f\u7a7a\u6811，b\u2f83\u2f30\u5c31\u662f\u2f00\u4e2a\u65b0\u589e\u7ed3\u70b9，\u4e0d\u65ad\u66f4\u65b05->10\u5e73\u8861\u56e0\u2f26，\u5f15\u53d1\u65cb \u8f6c，\u5176\u4e2d8\u7684\u5e73\u8861\u56e0\u2f26\u4e3a0，\u65cb\u8f6c\u540e8\u548c10\u548c5\u5e73\u8861\u56e0\u2f26\u5747\u4e3a0\u3002<\/p>\n

\"\"<\/p>\n

\u4ee3\u7801：<\/p>\n

void Rotate_Left_Right(Node* parent)
\n{
\nNode* subL = parent->_left;
\nNode* subLR = subL->_right;
\nint bf = subLR->_bf;<\/p>\n

Rotate_Left(parent->_left);
\nRotate_Right(parent);
\nif (bf == 0)
\n{
\nparent->_bf = 0;
\nsubL->_bf = 0;
\nsubLR->_bf = 0;
\n}
\nelse if (bf == -1)
\n{
\nparent->_bf = 1;
\nsubL->_bf = 0;
\nsubLR->_bf = 0;
\n}
\nelse if (bf == 1)
\n{
\nparent->_bf = 0;
\nsubL->_bf = -1;
\nsubLR->_bf = 0;
\n}
\nelse
\n{
\nassert(false);
\n}
\n}<\/p>\n

2.4.\u53f3\u5de6\u53cc\u65cb<\/h5>\n

\u2022 \u8ddf\u5de6\u53f3\u53cc\u65cb\u7c7b\u4f3c，\u4e0b\u2faf\u6211\u4eec\u5c06a\/b\/c\u2f26\u6811\u62bd\u8c61\u4e3a\u2fbc\u5ea6h\u7684AVL\u2f26\u6811\u8fdb\u2f8f\u5206\u6790，\u53e6\u5916\u6211\u4eec\u9700\u8981\u628ab\u2f26\u6811\u7684 \u7ec6\u8282\u8fdb\u2f00\u6b65\u5c55\u5f00\u4e3a12\u548c\u5de6\u2f26\u6811\u2fbc\u5ea6\u4e3ah-1\u7684e\u548cf\u2f26\u6811，\u56e0\u4e3a\u6211\u4eec\u8981\u5bf9b\u7684\u2f57\u4eb215\u4e3a\u65cb\u8f6c\u70b9\u8fdb\u2f8f\u53f3\u5355 \u65cb，\u53f3\u5355\u65cb\u9700\u8981\u52a8b\u6811\u4e2d\u7684\u53f3\u2f26\u6811\u3002b\u2f26\u6811\u4e2d\u65b0\u589e\u7ed3\u70b9\u7684\u4f4d\u7f6e\u4e0d\u540c，\u5e73\u8861\u56e0\u2f26\u66f4\u65b0\u7684\u7ec6\u8282\u4e5f\u4e0d\u540c，\u901a \u8fc7\u89c2\u5bdf12\u7684\u5e73\u8861\u56e0\u2f26\u4e0d\u540c，\u8fd9\u2fa5\u6211\u4eec\u8981\u5206\u4e09\u4e2a\u573a\u666f\u8ba8\u8bba\u3002<\/p>\n

\u2022 \u573a\u666f1：h>=1\u65f6，\u65b0\u589e\u7ed3\u70b9\u63d2\u2f0a\u5728e\u2f26\u6811，e\u2f26\u6811\u2fbc\u5ea6\u4eceh-1\u53d8\u4e3ah\u5e76\u4e0d\u65ad\u66f4\u65b012->15->10\u5e73\u8861\u56e0 \u2f26，\u5f15\u53d1\u65cb\u8f6c，\u5176\u4e2d12\u7684\u5e73\u8861\u56e0\u2f26\u4e3a-1，\u65cb\u8f6c\u540e10\u548c12\u5e73\u8861\u56e0\u2f26\u4e3a0，15\u5e73\u8861\u56e0\u2f26\u4e3a1\u3002<\/p>\n

\u2022 \u573a\u666f2：h>=1\u65f6，\u65b0\u589e\u7ed3\u70b9\u63d2\u2f0a\u5728f\u2f26\u6811，f\u2f26\u6811\u2fbc\u5ea6\u4eceh-1\u53d8\u4e3ah\u5e76\u4e0d\u65ad\u66f4\u65b012->15->10\u5e73\u8861\u56e0\u2f26， \u5f15\u53d1\u65cb\u8f6c，\u5176\u4e2d12\u7684\u5e73\u8861\u56e0\u2f26\u4e3a1，\u65cb\u8f6c\u540e15\u548c12\u5e73\u8861\u56e0\u2f26\u4e3a0，10\u5e73\u8861\u56e0\u2f26\u4e3a-1\u3002<\/p>\n

\u2022 \u573a\u666f3：h==0\u65f6，a\/b\/c\u90fd\u662f\u7a7a\u6811，b\u2f83\u2f30\u5c31\u662f\u2f00\u4e2a\u65b0\u589e\u7ed3\u70b9，\u4e0d\u65ad\u66f4\u65b015->10\u5e73\u8861\u56e0\u2f26，\u5f15\u53d1\u65cb \u8f6c，\u5176\u4e2d12\u7684\u5e73\u8861\u56e0\u2f26\u4e3a0，\u65cb\u8f6c\u540e10\u548c12\u548c15\u5e73\u8861\u56e0\u2f26\u5747\u4e3a0\u3002<\/p>\n

\u5982\u56fe：\"\"<\/p>\n

\u4ee3\u7801：<\/p>\n

void Rotate_Right_Left(Node* parent)
\n{
\nNode* subR = parent->_right;
\nNode* subRL = subR->_left;
\nint bf = subRL->_bf;<\/p>\n

Rotate_Right(parent->_right);
\nRotate_Left(parent);
\nif (bf == 0)
\n{
\nparent->_bf = 0;
\nsubR->_bf = 0;
\nsubRL->_bf = 0;
\n}
\nelse if (bf == 1)
\n{
\nparent->_bf = -1;
\nsubR->_bf = 0;
\nsubRL->_bf = 0;
\n}
\nelse if (bf == -1)
\n{
\nparent->_bf = 0;
\nsubR->_bf = 1;
\nsubRL->_bf = 0;
\n}
\nelse
\n{
\nassert(false);
\n}
\n}<\/p>\n

\u4e09.\u5176\u4ed6\u63a5\u53e3\u5b9e\u73b0<\/h4>\n

1.\u4e2d\u5e8f\u904d\u5386<\/p>\n

\u4ee3\u7801：<\/p>\n

void InOrder()
\n{
\n_InOrder(_root);
\n}
\nvoid _InOrder(Node* root)
\n{
\nif (root == nullptr)
\n{
\nreturn;
\n}
\n_InOrder(root->_left);
\ncout << root->_kv.first << ":" << root->_kv.second << endl;
\n_InOrder(root->_right);
\n}<\/p>\n

2.\u67e5\u627e\u503c\u4e3akey\u63a5\u53e3<\/p>\n

\u4ee3\u7801：<\/p>\n

Node* Find(const K& key)
\n{
\nreturn _Find(key);
\n}
\nNode* _Find(const K& key)
\n{
\nNode* cur = _root;
\nwhile (cur)
\n{
\nif (cur->_kv.first < key)
\n{
\ncur = cur->_right;
\n}
\nelse if (cur->_kv.first > key)
\n{
\ncur = cur->_left;
\n}
\nelse
\n{
\nreturn cur;
\n}
\n}
\nreturn nullptr;
\n}<\/p>\n

3.\u8ba1\u7b97\u6811\u7684\u5bb9\u91cf<\/p>\n

\u4ee3\u7801：<\/p>\n

int Size()
\n{
\nreturn _Size(_root);
\n}
\nint _Size(Node* root)
\n{
\nif (root == nullptr)
\n{
\nreturn 0;
\n}
\nreturn _Size(root->_left) + _Size(root->_right) + 1;
\n}<\/p>\n

4.\u8ba1\u7b97\u6811\u7684\u9ad8\u5ea6<\/p>\n

\u4ee3\u7801：<\/p>\n

int Height()
\n{
\nreturn _Height(_root);
\n}
\nint _Height(Node* root)
\n{
\nif (root == nullptr)
\n{
\nreturn 0;
\n}
\nint Height_Left = _Height(root->_left);
\nint Height_Right = _Height(root->_right);
\nreturn Height_Left > Height_Right ? Height_Left + 1 : Height_Right + 1;
\n}<\/p>\n

5.\u68c0\u67e5\u662f\u5426\u4e3aAVL\u6811<\/p>\n

\u4ee3\u7801：<\/p>\n

bool IsBalanceTree()
\n{
\nreturn _IsBalanceTree(_root);
\n}
\nbool _IsBalanceTree(Node* root)
\n{
\nif (root == nullptr)
\n{
\nreturn true;
\n}
\nint Height_Left = _Height(root->_left);
\nint Height_Right = _Height(root->_right);
\nint diff = Height_Right – Height_Left;<\/p>\n

if (abs(diff) >= 2)
\n{
\ncout << root->_kv.first <<":" << "\u9ad8\u5ea6\u5dee\u5f02\u5e38" << endl;
\nreturn false;
\n}
\nif (root->_bf != diff)
\n{
\ncout << root->_kv.first << ":" << "\u5e73\u8861\u56e0\u5b50\u5f02\u5e38" << endl;
\nreturn false;
\n}
\nreturn _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
\n}<\/p>\n

6.\u6790\u6784\u51fd\u6570<\/p>\n

\u4ee3\u7801：<\/p>\n

~AVLTree()
\n{
\n_Destroy(_root);
\n_root = nullptr;
\n}
\nvoid _Destroy(Node* root)
\n{
\nif (root == nullptr)
\n{
\nreturn;
\n}
\n_Destroy(root->_left);
\n_Destroy(root->_right);
\ndelete root;
\nroot = nullptr;
\n}<\/p>\n

\u6ce8\u610f：\u5176\u4ed6\u63a5\u53e3\u5b9e\u73b0\u65f6，\u5b9e\u73b0\u4ee3\u7801\u5e94\u6539\u653e\u5728private,\u5426\u5219\u53ef\u80fd\u4f1a\u56e0\u4e3a\u8c03\u7528\u63a5\u53e3\u65f6，\u8c03\u7528\u4e86\u542b\u6709_root\u7684\u63a5\u53e3，\u56e0\u4e3a_root\u4e3aprivate\u800c\u62a5\u9519\u3002<\/p>\n

\u56db.AVL\u6811\u7684\u6d4b\u8bd5<\/h5>\n

\u4ee3\u7801：<\/p>\n

#include"AVLTree.h"
\nvoid TestAVLTree1()
\n{
\n kong_AVLTree::AVLTree<int, int> t;
\n \/\/ \u5e38\u89c4\u7684\u6d4b\u8bd5\u2f64\u4f8b
\n \/\/int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
\n \/\/\u7279\u6b8a\u7684\u5e26\u6709\u53cc\u65cb\u573a\u666f\u7684\u6d4b\u8bd5\u2f64\u4f8b
\n int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
\n for (auto e : a)
\n {
\n t.Insert({ e, e });
\n }
\n t.InOrder();
\n cout << t.IsBalanceTree() << endl;
\n}
\nvoid TestAVLTree2()
\n{
\n const int N = 100000;
\n vector<int> v;
\n v.reserve(N);
\n srand(time(0));
\n for (size_t i = 0; i < N; i++)
\n {
\n v.push_back(rand() + i);
\n }
\n size_t begin2 = clock();
\n kong_AVLTree::AVLTree<int, int> t;
\n for (auto e : v)
\n {
\n t.Insert(make_pair(e, e));
\n }
\n size_t end2 = clock();
\n cout << "Insert:" << end2 – begin2 << endl;
\n cout << "Height:" << t.Height() << endl;
\n cout << "Size:" << t.Size() << endl;
\n size_t begin1 = clock();
\n \/\/ \u786e\u5b9a\u5728\u7684\u503c<\/p>\n

\/*for (auto e : v)
\n {
\n t.Find(e);
\n }*\/
\n \/\/ \u968f\u673a\u503c
\n for (size_t i = 0; i < N; i++)
\n {
\n t.Find((rand() + i));
\n }
\n size_t end1 = clock();
\n cout << "Find:" << end1 – begin1 << endl;
\n cout << "\u662f\u5426\u4e3a\u5e73\u8861\u6811:";
\n cout << t.IsBalanceTree() << endl;
\n}
\nint main()
\n{
\n TestAVLTree1();
\n TestAVLTree2();
\nreturn 0;
\n}<\/p>\n

\u6211\u4eec\u53ef\u4ee5\u901a\u8fc7\u8fd9\u4e2a\u4ee3\u7801\u6d4b\u8bd5\u8fd9\u4e2a\u6811\u662f\u5426\u4e3aAVL\u6811，\u4ee5\u53ca\u6d4b\u8bd5AVL\u6811\u7684\u6548\u7387\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"

\u4e00.AVL\u6811\u7684\u6982\u5ff5\u4e0e\u7ed3\u67841.AVL\u6811\u7684\u6982\u5ff51.1.\u4e3a\u4ec0\u4e48\u7528AVL\u6811\u539f\u56e0：\u666e\u901a\u7684\u4e8c\u53c9\u641c\u7d22\u6811（BST）\u5728\u63d2\u5165\u6709\u5e8f\u6570\u636e（\u5982 1， 2， 3， 4， 5）\u65f6，\u4f1a\u53d8\u6210\u4e00\u4e2a\u53ea\u6709\u53f3\u5b69\u5b50\u7684\u957f\u94fe，\u6b64\u65f6\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u67e5\u627e\u6548\u7387\u5c31\u4eceO(log N)\u9000\u5316\u5230O(N)，\u4f46\u662fAVL \u6811：\u901a\u8fc7\u65cb\u8f6c\u673a\u5236，\u5f3a\u5236\u4fdd\u8bc1\u5de6\u53f3\u5b50\u6811<\/p>\n","protected":false},"author":2,"featured_media":78101,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[55,1813],"topic":[],"class_list":["post-78117","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-server","tag-c","tag-1813"],"yoast_head":"\nAVL\u6811\u7684\u5b9e\u73b0 - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.wsisp.com\/helps\/78117.html\" \/>\n<meta property=\"og:locale\" content=\"zh_CN\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"AVL\u6811\u7684\u5b9e\u73b0 - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\" \/>\n<meta property=\"og:description\" content=\"\u4e00.AVL\u6811\u7684\u6982\u5ff5\u4e0e\u7ed3\u67841.AVL\u6811\u7684\u6982\u5ff51.1.\u4e3a\u4ec0\u4e48\u7528AVL\u6811\u539f\u56e0：\u666e\u901a\u7684\u4e8c\u53c9\u641c\u7d22\u6811（BST）\u5728\u63d2\u5165\u6709\u5e8f\u6570\u636e（\u5982 1， 2， 3， 4， 5）\u65f6，\u4f1a\u53d8\u6210\u4e00\u4e2a\u53ea\u6709\u53f3\u5b69\u5b50\u7684\u957f\u94fe，\u6b64\u65f6\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u67e5\u627e\u6548\u7387\u5c31\u4eceO(log N)\u9000\u5316\u5230O(N)，\u4f46\u662fAVL \u6811：\u901a\u8fc7\u65cb\u8f6c\u673a\u5236，\u5f3a\u5236\u4fdd\u8bc1\u5de6\u53f3\u5b50\u6811\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.wsisp.com\/helps\/78117.html\" \/>\n<meta property=\"og:site_name\" content=\"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\" \/>\n<meta property=\"article:published_time\" content=\"2026-02-26T00:11:32+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/02\/20260226001128-699f8fb0100aa.png\" \/>\n<meta name=\"author\" content=\"admin\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"\u4f5c\u8005\" \/>\n\t<meta name=\"twitter:data1\" content=\"admin\" \/>\n\t<meta name=\"twitter:label2\" content=\"\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4\" \/>\n\t<meta name=\"twitter:data2\" content=\"10 \u5206\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/78117.html\",\"url\":\"https:\/\/www.wsisp.com\/helps\/78117.html\",\"name\":\"AVL\u6811\u7684\u5b9e\u73b0 - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\",\"isPartOf\":{\"@id\":\"https:\/\/www.wsisp.com\/helps\/#website\"},\"datePublished\":\"2026-02-26T00:11:32+00:00\",\"dateModified\":\"2026-02-26T00:11:32+00:00\",\"author\":{\"@id\":\"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41\"},\"breadcrumb\":{\"@id\":\"https:\/\/www.wsisp.com\/helps\/78117.html#breadcrumb\"},\"inLanguage\":\"zh-Hans\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/www.wsisp.com\/helps\/78117.html\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/78117.html#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\u9996\u9875\",\"item\":\"https:\/\/www.wsisp.com\/helps\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"AVL\u6811\u7684\u5b9e\u73b0\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/#website\",\"url\":\"https:\/\/www.wsisp.com\/helps\/\",\"name\":\"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\",\"description\":\"\u9999\u6e2f\u670d\u52a1\u5668_\u9999\u6e2f\u4e91\u670d\u52a1\u5668\u8d44\u8baf_\u670d\u52a1\u5668\u5e2e\u52a9\u6587\u6863_\u670d\u52a1\u5668\u6559\u7a0b\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/www.wsisp.com\/helps\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"zh-Hans\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41\",\"name\":\"admin\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"zh-Hans\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery\",\"contentUrl\":\"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery\",\"caption\":\"admin\"},\"sameAs\":[\"http:\/\/wp.wsisp.com\"],\"url\":\"https:\/\/www.wsisp.com\/helps\/author\/admin\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"AVL\u6811\u7684\u5b9e\u73b0 - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.wsisp.com\/helps\/78117.html","og_locale":"zh_CN","og_type":"article","og_title":"AVL\u6811\u7684\u5b9e\u73b0 - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","og_description":"\u4e00.AVL\u6811\u7684\u6982\u5ff5\u4e0e\u7ed3\u67841.AVL\u6811\u7684\u6982\u5ff51.1.\u4e3a\u4ec0\u4e48\u7528AVL\u6811\u539f\u56e0：\u666e\u901a\u7684\u4e8c\u53c9\u641c\u7d22\u6811（BST）\u5728\u63d2\u5165\u6709\u5e8f\u6570\u636e（\u5982 1， 2， 3， 4， 5）\u65f6，\u4f1a\u53d8\u6210\u4e00\u4e2a\u53ea\u6709\u53f3\u5b69\u5b50\u7684\u957f\u94fe，\u6b64\u65f6\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u67e5\u627e\u6548\u7387\u5c31\u4eceO(log N)\u9000\u5316\u5230O(N)，\u4f46\u662fAVL \u6811：\u901a\u8fc7\u65cb\u8f6c\u673a\u5236，\u5f3a\u5236\u4fdd\u8bc1\u5de6\u53f3\u5b50\u6811","og_url":"https:\/\/www.wsisp.com\/helps\/78117.html","og_site_name":"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","article_published_time":"2026-02-26T00:11:32+00:00","og_image":[{"url":"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/02\/20260226001128-699f8fb0100aa.png"}],"author":"admin","twitter_card":"summary_large_image","twitter_misc":{"\u4f5c\u8005":"admin","\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4":"10 \u5206"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/www.wsisp.com\/helps\/78117.html","url":"https:\/\/www.wsisp.com\/helps\/78117.html","name":"AVL\u6811\u7684\u5b9e\u73b0 - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","isPartOf":{"@id":"https:\/\/www.wsisp.com\/helps\/#website"},"datePublished":"2026-02-26T00:11:32+00:00","dateModified":"2026-02-26T00:11:32+00:00","author":{"@id":"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41"},"breadcrumb":{"@id":"https:\/\/www.wsisp.com\/helps\/78117.html#breadcrumb"},"inLanguage":"zh-Hans","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.wsisp.com\/helps\/78117.html"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/www.wsisp.com\/helps\/78117.html#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\u9996\u9875","item":"https:\/\/www.wsisp.com\/helps"},{"@type":"ListItem","position":2,"name":"AVL\u6811\u7684\u5b9e\u73b0"}]},{"@type":"WebSite","@id":"https:\/\/www.wsisp.com\/helps\/#website","url":"https:\/\/www.wsisp.com\/helps\/","name":"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","description":"\u9999\u6e2f\u670d\u52a1\u5668_\u9999\u6e2f\u4e91\u670d\u52a1\u5668\u8d44\u8baf_\u670d\u52a1\u5668\u5e2e\u52a9\u6587\u6863_\u670d\u52a1\u5668\u6559\u7a0b","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.wsisp.com\/helps\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"zh-Hans"},{"@type":"Person","@id":"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41","name":"admin","image":{"@type":"ImageObject","inLanguage":"zh-Hans","@id":"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/image\/","url":"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery","contentUrl":"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery","caption":"admin"},"sameAs":["http:\/\/wp.wsisp.com"],"url":"https:\/\/www.wsisp.com\/helps\/author\/admin"}]}},"_links":{"self":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/posts\/78117","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/comments?post=78117"}],"version-history":[{"count":0,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/posts\/78117\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/media\/78101"}],"wp:attachment":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/media?parent=78117"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/categories?post=78117"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/tags?post=78117"},{"taxonomy":"topic","embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/topic?post=78117"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}