{"id":103,"date":"2025-07-01T01:12:42","date_gmt":"2025-06-30T17:12:42","guid":{"rendered":"http:\/\/120.76.99.214\/?p=103"},"modified":"2025-11-24T16:42:38","modified_gmt":"2025-11-24T08:42:38","slug":"%e5%b9%b3%e8%a1%a1%e4%ba%8c%e5%8f%89%e6%90%9c%e7%b4%a2%e6%a0%91%ef%bc%88avl%ef%bc%89","status":"publish","type":"post","link":"https:\/\/www.tgwttt.xyz\/?p=103","title":{"rendered":"\u5e73\u8861\u4e8c\u53c9\u641c\u7d22\u6811\uff08AVL\uff09"},"content":{"rendered":"\n

\u4e8c\u53c9\u641c\u7d22\u6811\u53c8\u79f0AVL\uff0c\u4ed6\u6bd4\u4e4b\u4e8c\u53c9\u641c\u7d22\u6811\uff08\u524d\u9762\u6587\u4ef6\u4ecb\u7ecd\u4e86\uff09\u591a\u4e86\u4e00\u4e2a\u91cd\u8981\u7684\u7279\u6027\uff0c\u5de6\u53f3\u5b50\u6811\u9ad8\u5ea6\u5dee\u4e0d\u80fd\u8d85\u8fc7\u4e00\uff0c\u800c\u8fd9\u4e2a\u7279\u6027\u662f\u7531\u5e73\u8861\u56e0\u5b50\u51b3\u5b9a\u7684\uff0c\u4eca\u5929\u4e3b\u64ad\u5c31\u5e26\u9886\u5927\u5bb6\u624b\u6413\u4e00\u4e2a\u5e73\u8861\u4e8c\u53c9\u641c\u7d22\u6811\u3002<\/p>\n\n\n\n

\n

\u9996\u5148\u662f\u8282\u70b9\u7684\u521b\u5efa\uff0c\u6211\u4eec\u4f9d\u65e7\u4f9d\u7167\u4ee5\u524d\u7684\u4e8c\u53c9\u641c\u7d22\u6811\u5199\uff0c\u53ea\u4e0d\u8fc7\u591a\u4e86parent\u6307\u9488\u548c\u5e73\u8861\u56e0\u5b50\u3002\u4ee3\u7801\u5982\u4e0b\uff1a template
struct AVLTreeNode
{
pair _kv;
AVLTreeNode* _left;
AVLTreeNode* _right;
AVLTreeNode* _parent;<\/p>\n\n\n\n

int _bf; \/\/ balance factor\n\nAVLTreeNode(const pair& kv)\n    :_kv(kv)\n    , _left(nullptr)\n    , _right(nullptr)\n    , _parent(nullptr)\n    , _bf(0)\n{\n}<\/code><\/pre>\n\n\n\n
};<\/p>\n<\/div>\n\n\n\n
\u540e\u9762\u5c31\u662f\u589e\u52a0\u64cd\u4f5c\u4e5f\u662f\u96be\u70b9\u4e4b\u4e00\uff1a\u5355\u7eaf\u63d2\u5165\u53ea\u9700\u8981\u6309\u7167\u5e73\u8861\u641c\u7d22\u6811\u7684\u64cd\u4f5c\u8fdb\u884c\u6b63\u5e38key\u6bd4\u8f83\u63d2\u5165\u5373\u53ef\uff0c\u4f46\u662f\u5982\u679c\u662f\u5e73\u8861\u641c\u7d22\u4e8c\u53c9\u6811\uff0c\u6211\u4eec\u5c31\u5fc5\u987b\u8003\u8651\u5e73\u8861\u56e0\u5b50\u7684\u7834\u574f\uff0c\u4ee5\u53ca\u8c03\u6574\u3002                                                                       \u5f53\u6211\u4eec\u8ba1\u7b97\u5e73\u8861\u56e0\u5b50\u65f6\u9700\u8981\u8ba1\u7b97\u51e0\u79cd\u60c5\u51b5\uff0c\u63d2\u5165\u8282\u70b9\u7684\u7236\u8282\u70b9\u5e73\u8861\u56e0\u5b50\u786e\u5b9a\u3002\u5f53\u4ece\u5de6\u63d2\u5165\u65f6\u5c31\u9700\u8981parent->bf\u5c31\u9700\u8981\u51cf\u4e00\uff0c\u5f53\u4ece\u53f3\u8fb9\u63d2\u5165\u65f6\u5e73\u8861\u56e0\u5b50\u5c31\u9700\u8981\u52a0\u4e00\u3002                                                                                          \u5728\u5e73\u8861\u56e0\u5b50\u53d8\u5316\u5faa\u73af\u52a0\u51cf\u4e00\u8f6e\u540e\u6211\u4eec\u9700\u8981\u5224\u65ad\u4e09\u79cd\u60c5\u51b5\uff1a                                                                                        1.parent->bf==0 \u8bf4\u660e\u6ca1\u6709\u53d8\u5316\u4e4b\u524d\u662f-1\u62161\uff0c\u6b64\u65f6\u5c31\u4e0d\u9700\u8981\u7ee7\u7eed\u5faa\u73af\uff0c\u4e0d\u5f71\u54cd\u4e0a\u9762\u7236\u8282\u70b9\u7684\u5e73\u8861\u56e0\u5b50\u3002                   2.parent->bf==1\u6216-1\uff0c\u8bf4\u660e\u539f\u6765\u5e73\u8861\u56e0\u5b50\u4e3a0\uff0c\u6b64\u65f6\u5c31\u9700\u8981\u7ee7\u7eed\u5faa\u73af\u3002                                                                      3.parent->bf==-2\u6216\u80052,\u6b64\u65f6\u6211\u4eec\u4e0d\u4ec5\u9700\u8981\u7ee7\u7eed\u5faa\u73af\uff0c\u8fd8\u9700\u8981\u5bf9\u4e8c\u53c9\u6811\u8fdb\u884c\u65cb\u8f6c\uff0c\u56e0\u4e3a\u6b64\u65f6\u4e8c\u53c9\u6811\u7684\u5e73\u8861\u6027\u5df2\u7ecf\u5b8c\u5168\u88ab\u7834\u574f\u4e86\u3002 <\/p>\n\n\n\n
\u65cb\u8f6c\u6709\u56db\u79cd\u60c5\u51b5\uff1a                                                                                                                                                          1.\u5de6\u5355\u65cb                                                                                                                                                                        2.\u53f3\u5355\u65cb                                                                                                                                                                         3.\u5de6\u53f3\u5355\u65cb                                                                                                                                                                                 4.\u53f3\u5de6\u5355\u65cb<\/p>\n\n\n\n
\u5982\u56fe\u6240\u793a\uff1a<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\u5355\u65cb\u8f6c\u65f6\u5e73\u8861\u56e0\u5b50\u7684\u8c03\u6574\u90fd\u662f\u6709\u89c4\u5f8b\u53ef\u5faa\uff0c\u4f46\u662f\u53cc\u65cb\u8f6c\u65f6\uff0c\u5e73\u8861\u56e0\u5b50\u7684\u8c03\u6574\u5c31\u6bd4\u8f83\u590d\u6742\uff0c\u5927\u81f4\u5206\u4e09\u79cd\u60c5\u51b5 \uff1a\u4e3e\u4f8b\u8bf4\u660e\uff1a<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\u4e0b\u9762\u662f\u4ee3\u7801\u5b9e\u73b0\uff1a<\/p>\n\n\n\n
bool Insert(const pair& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}<\/p>\n\n\n\n
Node* parent = nullptr;\nNode* cur = _root;\nwhile (cur)\n{\n    if (cur->_kv.first < kv.first)\n    {\n        parent = cur;\n        cur = cur->_right;\n    }\n    else if (cur->_kv.first > kv.first)\n    {\n        parent = cur;\n        cur = cur->_left;\n    }\n    else\n    {\n        return false;\n    }\n}\n\ncur = new Node(kv);\nif (parent->_kv.first < kv.first)\n{\n    parent->_right = cur;\n}\nelse\n{\n    parent->_left = cur;\n}\n\/\/ \u94fe\u63a5\u7236\u4eb2\ncur->_parent = parent;\n\n\/\/ \u63a7\u5236\u5e73\u8861\n\/\/ \u66f4\u65b0\u5e73\u8861\u56e0\u5b50\nwhile (parent)\n{\n    if (cur == parent->_left)\n        parent->_bf--;\n    else\n        parent->_bf++;\n\n    if (parent->_bf == 0)\n    {\n        break;\n    }\n    else if (parent->_bf == 1 || parent->_bf == -1)\n    {\n        cur = parent;\n        parent = parent->_parent;\n    }\n    else if (parent->_bf == 2 || parent->_bf == -2)\n    {\n        if (parent->_bf == -2 && cur->_bf == -1)\n        {\n            RotateR(parent);\n        }\n        else if (parent->_bf == 2 && cur->_bf == 1)\n        {\n            RotateL(parent);\n        }\n        else if (parent->_bf == -2 && cur->_bf == 1)\n        {\n            RotateLR(parent);\n        }\n        else if (parent->_bf == 2 && cur->_bf == -1)\n        {\n            RotateRL(parent);\n        }\n        else\n        {\n            assert(false);\n        }\n\n        break;\n    }\n    else\n    {\n        assert(false);\n    }\n}\n\n\nreturn true;<\/code><\/pre>\n\n\n\n
}<\/p>\n\n\n\n
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;<\/p>\n\n\n\n
parent->_left = subLR;\nif (subLR)\n    subLR->_parent = parent;\n\nNode* pParent = parent->_parent;\n\nsubL->_right = parent;\nparent->_parent = subL;\n\nif (parent == _root)\n{\n    _root = subL;\n    subL->_parent = nullptr;\n}\nelse\n{\n    if (pParent->_left == parent)\n    {\n        pParent->_left = subL;\n    }\n    else\n    {\n        pParent->_right = subL;\n    }\n\n    subL->_parent = pParent;\n}\n\nsubL->_bf = 0;\nparent->_bf = 0;<\/code><\/pre>\n\n\n\n
}<\/p>\n\n\n\n
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;<\/p>\n\n\n\n
Node* parentParent = parent->_parent;\nsubR->_left = parent;\nparent->_parent = subR;\nif (parentParent == nullptr)\n{\n    _root = subR;\n    subR->_parent = nullptr;\n}\nelse\n{\n    if (parent == parentParent->_left)\n    {\n        parentParent->_left = subR;\n    }\n    else\n    {\n        parentParent->_right = subR;\n    }\n    subR->_parent = parentParent;\n}\n\nparent->_bf = subR->_bf = 0;<\/code><\/pre>\n\n\n\n
}<\/p>\n\n\n\n
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;<\/p>\n\n\n\n
RotateL(parent->_left);\nRotateR(parent);\n\nif (bf == -1)\n{\n    subLR->_bf = 0;\n    subL->_bf = 0;\n    parent->_bf = 1;\n}\nelse if (bf == 1)\n{\n    subLR->_bf = 0;\n    subL->_bf = -1;\n    parent->_bf = 0;\n}\nelse if (bf == 0)\n{\n    subLR->_bf = 0;\n    subL->_bf = 0;\n    parent->_bf = 0;\n}\nelse\n{\n    assert(false);\n}<\/code><\/pre>\n\n\n\n
}<\/p>\n\n\n\n
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
if (bf == 0)
{
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = 0;
}
else if (bf == 1)
{
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = -1;
}
else if (bf == -1)
{
subR->_bf = 1;
subRL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}<\/p>\n\n\n\n
\u63a5\u4e0b\u6765\u5c31\u662f\u67e5\u627e\uff0c\u4e0e\u524d\u9762\u5927\u5dee\u4e0d\u5dee\uff1a<\/p>\n\n\n\n
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < key) { cur = cur->_right;
}
else if (cur->_kv.first > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}<\/p>\n\n\n\n
return nullptr;<\/code><\/pre>\n\n\n\n
}<\/p>\n\n\n\n
\u904d\u5386\uff0c\u9ad8\u5ea6\uff0c\u6570\u91cf\uff0c\u5e73\u8861\u6027\u68c0\u67e5\uff1a<\/p>\n\n\n\n
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}<\/p>\n\n\n\n
_InOrder(root->_left);\ncout << root->_kv.first << \":\" << root->_kv.second << endl;\n_InOrder(root->_right);<\/code><\/pre>\n\n\n\n
}<\/p>\n\n\n\n
int _Height(Node* root)
{
if (root == nullptr)
return 0;
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}<\/p>\n\n\n\n
int _Size(Node* root)
{
if (root == nullptr)
return 0;<\/p>\n\n\n\n
return _Size(root->_left) + _Size(root->_right) + 1;<\/code><\/pre>\n\n\n\n
}<\/p>\n\n\n\n
bool _IsBalanceTree(Node* root)
{
\/\/ \u7a7a\u6811\u4e5f\u662fAVL\u6811
if (nullptr == root)
return true;
\/\/ \u8ba1\u7b97pRoot\u7ed3\u70b9\u7684\u5e73\u8861\u56e0\u5b50\uff1a\u5373pRoot\u5de6\u53f3\u5b50\u6811\u7684\u9ad8\u5ea6\u5dee
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
int diff = rightHeight – leftHeight;<\/p>\n\n\n\n
\/\/ \u5982\u679c\u8ba1\u7b97\u51fa\u7684\u5e73\u8861\u56e0\u5b50\u4e0epRoot\u7684\u5e73\u8861\u56e0\u5b50\u4e0d\u76f8\u7b49\uff0c\u6216\u8005\n\/\/ pRoot\u5e73\u8861\u56e0\u5b50\u7684\u7edd\u5bf9\u503c\u8d85\u8fc71\uff0c\u5219\u4e00\u5b9a\u4e0d\u662fAVL\u6811\nif (abs(diff) >= 2)\n{\n    cout << root->_kv.first << \"\u9ad8\u5ea6\u5dee\u5f02\u5e38\" << endl;\n    return false;\n}\n\nif (root->_bf != diff)\n{\n    cout << root->_kv.first << \"\u5e73\u8861\u56e0\u5b50\u5f02\u5e38\" << endl;\n    return false;\n}\n\n\/\/ pRoot\u7684\u5de6\u548c\u53f3\u5982\u679c\u90fd\u662fAVL\u6811\uff0c\u5219\u8be5\u6811\u4e00\u5b9a\u662fAVL\u6811\nreturn _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);<\/code><\/pre>\n\n\n\n
}<\/p>\n\n\n\n
\u6700\u540e\u5c31\u662f\u5220\u9664\u4e86\uff0c\u5220\u9664\u501f\u9274\u63d2\u5165\u8fd8\u662f\u5f88\u5bb9\u6613\u5199\u51fa\u6765\u7684<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\u4ee3\u7801\u5b9e\u73b0\uff1abool _eraser(const K& key) {
Node* node = Find(key);
Node* parent = node->_parent;
if (node == nullptr) return false; \/\/ \u5982\u679c\u8282\u70b9\u4e0d\u5b58\u5728\uff0c\u8fd4\u56defalse
else {
if (node->_left == nullptr) { \/\/ \u5de6\u5b69\u5b50\u4e3a\u7a7a
if (node == _root) { \/\/ \u5982\u679c\u662f\u6839\u8282\u70b9
_root = node->_right;
}
else {
if (node->_parent->_left == node) { \/\/ \u5982\u679c\u662f\u5de6\u5b69\u5b50
node->_parent->_left = node->_right;
if (node->_right) node->_right->_parent = node->_parent;
node->_parent->_bf++;
}
else { \/\/ \u5982\u679c\u662f\u53f3\u5b69\u5b50
node->_parent->_right = node->_right;
if (node->_right) node->_right->_parent = node->_parent;
node->_parent->_bf–;
}
}
delete node;
}
else if (node->_right == nullptr) { \/\/ \u53f3\u5b69\u5b50\u4e3a\u7a7a
if (node == _root) { \/\/ \u5982\u679c\u662f\u6839\u8282\u70b9
_root = node->_left;
}
else {
if (node->_parent->_left == node) { \/\/ \u5982\u679c\u662f\u5de6\u5b69\u5b50
node->_parent->_left = node->_left;
if (node->_left) node->_left->_parent = node->_parent;
node->_parent->_bf++;
}
else { \/\/ \u5982\u679c\u662f\u53f3\u5b69\u5b50
node->_parent->_right = node->_left;
if (node->_left) node->_left->_parent = node->_parent;
node->_parent->_bf–;
}
}
delete node;
}
else { \/\/ \u5de6\u53f3\u5b69\u5b50\u90fd\u4e0d\u4e3a\u7a7a
Node* replaceparent = node;
Node* replace = node->_right; \/\/ \u66ff\u4ee3\u8282\u70b9\uff0c\u5de6\u5b50\u6811\u6700\u5de6\u8282\u70b9
while (replace->_left) {
replaceparent = replace;
replace = replace->_left;
}
node->_kv.first = replace->_kv.first;
if (replaceparent->_left == replace) {
replaceparent->_left = replace->_right;
if (replace->_right) replace->_right->_parent = replaceparent;
}
else {
replaceparent->_right = replace->_right;
if (replace->_right) replace->_right->_parent = replaceparent;
}
parent = replace->_parent;
delete replace;
}
\/\/ \u66f4\u65b0\u5e73\u8861\u56e0\u5b50\u5e76\u8c03\u6574\u5e73\u8861
Node* cur = parent;
while (cur) {
if (cur->_bf == 2 || cur->_bf == -2) {
if (cur->_bf == -2 && cur->_left->_bf == -1) {
RotateR(cur);
}
else if (cur->_bf == 2 && cur->_right->_bf == 1) {
RotateL(cur);
}
else if (cur->_bf == -2 && cur->_left->_bf == 1) {
RotateLR(cur);
}
else if (cur->_bf == 2 && cur->_right->_bf == -1) {
RotateRL(cur);
}
else {
assert(false);
}
break;
}
cur = cur->_parent;
}
}
return true;
}<\/p>\n\n\n\n
\u5982\u6709\u9519\u8bef\u6b22\u8fce\u6307\u51fa\uff0c\u4eca\u5929\u7684\u66f4\u65b0\u5c31\u5230\u8fd9\u91cc\u4e86\uff01<\/p>\n","protected":false},"excerpt":{"rendered":"
\u4e8c\u53c9\u641c\u7d22\u6811\u53c8\u79f0AVL\uff0c\u4ed6\u6bd4\u4e4b\u4e8c\u53c9\u641c\u7d22\u6811\uff08\u524d\u9762\u6587\u4ef6\u4ecb\u7ecd\u4e86\uff09\u591a\u4e86\u4e00\u4e2a\u91cd\u8981\u7684\u7279\u6027\uff0c\u5de6\u53f3\u5b50\u6811\u9ad8\u5ea6\u5dee\u4e0d\u80fd\u8d85\u8fc7\u4e00\uff0c\u800c\u8fd9\u4e2a\u7279…<\/p>\n","protected":false},"author":1,"featured_media":104,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_kad_post_classname":"","footnotes":""},"categories":[4],"tags":[],"class_list":["post-103","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-c"],"_links":{"self":[{"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/posts\/103","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=103"}],"version-history":[{"count":4,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/posts\/103\/revisions"}],"predecessor-version":[{"id":884,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/posts\/103\/revisions\/884"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/media\/104"}],"wp:attachment":[{"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=103"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=103"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=103"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}