![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/10\/20261031124046-6ae5e1ce7a6af.png\")
<\/p>\n\u672c\u7bc7\u76ee\u6807:
\n1.\u638c\u63e1\u7ea2\u9ed1\u6811\u7684\u6982\u5ff5\u4e0e\u67d3\u8272\u8fc7\u7a0b<\/p>\n
2.\u5b66\u4f1a\u7ea2\u9ed1\u6811\u7684\u5b9e\u73b0<\/p>\n<\/p>\n
\u6ce8\u610f：\u5b66\u4e60\u672c\u7247\u524d\u5fc5\u987b\u8981\u5b66\u4f1aAVL\u6811\u7684\u65cb\u8f6c\u3002<\/p>\n<\/p>\n
\u7ea2\u9ed1\u6811\u662f\u4e00\u68f5\u4e8c\u53c9\u641c\u7d22\u6811，\u4ed6\u7684\u6bcf\u4e2a\u7ed3\u70b9\u589e\u52a0\u2f00\u4e2a\u5b58\u50a8\u4f4d\u6765\u8868\u793a\u7ed3\u70b9\u7684\u989c\u8272，\u53ef\u4ee5\u662f\u7ea2\u8272\u6216\u8005\u9ed1\u8272\u3002 \u901a\u8fc7\u5bf9\u4efb\u4f55\u4e00\u6761\u4ece\u6839\u5230\u53f6\u5b50\u7684\u8def\u5f84\u4e0a\u5404\u4e2a\u7ed3\u70b9\u7684\u989c\u8272\u8fdb\u884c\u7ea6\u675f，\u7ea2\u9ed1\u6811\u786e\u4fdd\u6ca1\u6709\u2f00\u6761\u8def\u5f84\u4f1a\u6bd4\u5176\u4ed6\u8def\u5f84\u957f\u51fa2\u500d，\u56e0\u800c\u662f\u63a5\u8fd1\u5e73\u8861\u7684\u3002<\/p>\n
\u5982\u56fe：<\/p>\n
\u4e00\u68f5\u7ea2\u9ed1\u6811\u5fc5\u987b\u8981\u6ee1\u8db3\u4ee5\u4e0b\u7684\u89c4\u5219:<\/p>\n
<1>.\u6bcf\u4e2a\u7ed3\u70b9\u4e0d\u662f\u7ea2\u8272\u5c31\u662f\u9ed1\u8272<\/p>\n
<2>. \u6839\u7ed3\u70b9\u662f\u9ed1\u8272\u7684 <\/p>\n
<3>. \u5982\u679c\u2f00\u4e2a\u7ed3\u70b9\u662f\u7ea2\u8272\u7684，\u5219\u5b83\u7684\u4e24\u4e2a\u5b69\u5b50\u7ed3\u70b9\u5fc5\u987b\u662f\u9ed1\u8272\u7684，\u4e5f\u5c31\u662f\u8bf4\u4efb\u610f\u2f00\u6761\u8def\u5f84\u4e0d\u4f1a\u6709\u8fde\u7eed\u7684\u7ea2\u8272\u7ed3\u70b9\u3002 <\/p>\n
<4>. \u5bf9\u4e8e\u4efb\u610f\u2f00\u4e2a\u7ed3\u70b9，\u4ece\u8be5\u7ed3\u70b9\u5230\u5176\u6240\u6709NULL\u7ed3\u70b9\u7684\u7b80\u5355\u8def\u5f84\u4e0a，\u5747\u5305\u542b\u76f8\u540c\u6570\u91cf\u7684\u9ed1\u8272\u7ed3\u70b9<\/p>\n
\u9996\u5148\u5462，\u6211\u4eec\u5148\u770b\u4e00\u5f20\u56fe\u7247，\u770b\u770b\u8fd9\u5f20\u56fe\u7247\u4ece\u6839\u8282\u70b9\u5230NULL\u8282\u70b9\u4e0a\u6709\u51e0\u6761\u8def\u5f84？<\/p>\n
\u5982\u56fe：![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/10\/20261031124047-6ae5e1cf8cf6b.png\")
<\/p>\n
\u5f88\u591a\u4eba\u7684\u7b2c\u4e00\u53cd\u5e94\u53ef\u80fd\u662f 4 \u6761，\u56e0\u4e3a\u56fe\u4e2d\u6709 15\u300125\u300135\u300150 \u56db\u4e2a\u53f6\u5b50\u8282\u70b9\u3002\u4f46\u8fd9\u6570\u7684\u662f\u4ece\u6839\u8282\u70b9\u5230\u666e\u901a\u53f6\u5b50\u8282\u70b9\u7684\u8def\u5f84，\u8fd8\u6ca1\u6709\u8d70\u5230 NULL\u3002<\/p>\n
\u6bcf\u4e2a\u53f6\u5b50\u8282\u70b9\u90fd\u6709\u4e24\u4e2a\u7a7a\u5b69\u5b50，\u56e0\u6b64，\u8fd9\u56db\u4e2a\u53f6\u5b50\u8282\u70b9\u5bf9\u5e94：8\u6761\u5230 NULL \u7684\u8def\u5f84\u3002<\/p>\n
\u6b64\u5916，\u8282\u70b9 10 \u7684\u5de6\u5b69\u5b50\u4e5f\u662f NULL，\u8fd8\u9700\u8981\u518d\u7b97\u4e00\u6761\u3002<\/p>\n
\u6240\u4ee5，\u8fd9\u68f5\u6811\u4ece\u6839\u8282\u70b9\u5230 NULL \u8282\u70b9，\u4e00\u5171\u6709：9\u6761<\/p>\n
\u7ea2\u9ed1\u6811\u6027\u8d28\u4e2d\u6240\u8bf4\u7684\u53f6\u5b50\u8282\u70b9，\u6307\u7684\u662f\u8fd9\u4e9b\u9ed1\u8272\u7684 NULL（\u4e5f\u79f0 NIL）\u8282\u70b9\u3002 \u4e3a\u4e86\u8ba9\u56fe\u66f4\u7b80\u6d01，\u5b83<\/p>\n
\u4eec\u901a\u5e38\u6ca1\u6709\u753b\u51fa\u6765，\u4f46\u5206\u6790\u8def\u5f84\u65f6\u4e0d\u80fd\u5ffd\u7565\u3002<\/p>\n
\u6240\u4ee5\u5b8c\u6574\u7684\u56fe\u5982\u4e0b：![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/10\/20261031124048-6ae5e1d04110f.png\")
<\/p>\n
\u6ce8\u610f：\u901a\u5e38\u6bcf\u4e2aNULL\u8282\u70b9\u90fd\u662f\u9ed1\u8272\u7684，\u5982\u679c\u662f\u7ea2\u8272\u5bb9\u6613\u4e0e\u89c4\u5219\u4e09\u51b2\u7a81\u3002<\/p>\n
\u7136\u540e\u6211\u4eec\u63a5\u7740\u770b\u4e9b\u5176\u4ed6\u7684\u7ea2\u9ed1\u6811：<\/p>\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/10\/20261031124049-6ae5e1d1045a7.png\")
<\/p>\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/10\/20261031124049-6ae5e1d1d09f8.png\")
<\/p>\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/10\/20261031124050-6ae5e1d2e840b.png\")
<\/p>\n
\u9996\u5148，\u6211\u4eec\u601d\u8003\u2f00\u4e0b，\u7ea2\u9ed1\u6811\u5982\u4f55\u786e\u4fdd\u6700\u957f\u8def\u5f84\u4e0d\u8d85\u8fc7\u6700\u77ed\u8def\u5f84\u76842\u500d\u7684？<\/p>\n
\u5173\u952e\u5728\u4e8e\u4e24\u6761\u6027\u8d28：<\/p>\n
\u4ece\u6839\u8282\u70b9\u5230\u4efb\u610f NULL \u8282\u70b9\u7684\u8def\u5f84，\u5305\u542b\u7684\u9ed1\u8272\u8282\u70b9\u6570\u91cf\u76f8\u540c\u3002<\/p>\n<\/li>\n
\u7ea2\u8272\u8282\u70b9\u4e0d\u80fd\u8fde\u7eed\u51fa\u73b0，\u5e76\u4e14\u6839\u8282\u70b9\u4e3a\u9ed1\u8272\u3002<\/p>\n<\/li>\n<\/ul>\n
\u8bbe\u6bcf\u6761\u8def\u5f84\u4e0a\u90fd\u6709 bh \u4e2a\u9ed1\u8272\u8282\u70b9\u3002\u8fd9\u91cc\u7edf\u4e00\u4e0d\u8ba1 NULL，\u7528\u8def\u5f84\u4e0a\u7684\u975e\u7a7a\u8282\u70b9\u6570\u91cf\u8868\u793a\u8def\u5f84\u957f\u5ea6\u3002<\/p>\n
\u5bf9\u4e8e\u4efb\u610f\u4e00\u6761\u8def\u5f84：<\/p>\n
\u957f\u5ea6\u4e0b\u9650：\u5373\u4f7f\u6ca1\u6709\u7ea2\u8272\u8282\u70b9，\u4e5f\u6709 bh \u4e2a\u9ed1\u8272\u8282\u70b9，\u56e0\u6b64\u8def\u5f84\u957f\u5ea6\u81f3\u5c11\u4e3a bh\u3002<\/p>\n<\/li>\n
\u957f\u5ea6\u4e0a\u9650：\u7531\u4e8e\u6839\u4e3a\u9ed1\u8272，\u4e14\u7ea2\u8272\u8282\u70b9\u4e0d\u80fd\u8fde\u7eed\u51fa\u73b0，\u7ea2\u8272\u8282\u70b9\u6570\u91cf\u4e0d\u4f1a\u8d85\u8fc7\u9ed1\u8272\u8282\u70b9\u6570\u91cf，\u56e0\u6b64\u8def\u5f84\u957f\u5ea6\u81f3\u591a\u4e3a 2bh\u3002<\/p>\n<\/li>\n<\/ul>\n
\u6240\u4ee5，\u4efb\u610f\u8def\u5f84\u957f\u5ea6 h \u90fd\u6ee1\u8db3：bh \u2264 h \u2264 2 \u00d7 bh<\/p>\n
\u8bbe\u6700\u77ed\u8def\u5f84\u957f\u5ea6\u4e3a h_min，\u6700\u957f\u8def\u5f84\u957f\u5ea6\u4e3a h_max，\u5219：h_min \u2265 bh，h_max \u2264 2 \u00d7 bh<\/p>\n
\u56e0\u6b64：h_max \u2264 2 \u00d7 bh \u2264 2 \u00d7 h_min<\/p>\n
\u6240\u4ee5，\u6700\u957f\u8def\u5f84\u4e0d\u8d85\u8fc7\u6700\u77ed\u8def\u5f84\u7684\u4e24\u500d\u3002<\/p>\n
\u9700\u8981\u6ce8\u610f：\u5168\u9ed1\u8def\u5f84\u548c\u7ea2\u9ed1\u4ea4\u66ff\u8def\u5f84\u53ea\u662f\u5206\u6790\u4e0a\u4e0b\u9650\u65f6\u8003\u8651\u7684\u6781\u7aef\u60c5\u51b5，\u5e76\u4e0d\u8981\u6c42\u6bcf\u68f5\u7ea2\u9ed1\u6811\u4e2d\u90fd\u5b58\u5728\u8fd9\u6837\u7684\u8def\u5f84\u3002<\/p>\n
\u63a5\u4e0b\u6765，\u6211\u4eec\u8c08\u4e0b\u7ea2\u9ed1\u6811\u7684\u6548\u7387：<\/p>\n
\u5047\u8bbe\u7ea2\u9ed1\u6811\u4e2d\u6709 N \u4e2a\u975e\u7a7a\u8282\u70b9，\u6700\u77ed\u8def\u5f84\u957f\u5ea6\u4e3a h，\u6700\u957f\u8def\u5f84\u957f\u5ea6\u4e3a H\u3002\u8fd9\u91cc\u8def\u5f84\u957f\u5ea6\u7edf\u4e00\u6309\u4ece\u6839\u5230 NULL \u7ecf\u8fc7\u7684\u975e\u7a7a\u8282\u70b9\u6570\u8ba1\u7b97\u3002<\/p>\n
\u7531\u4e8e\u6700\u77ed\u8def\u5f84\u957f\u5ea6\u4e3a h，\u524d h \u5c42\u4e00\u5b9a\u662f\u6ee1\u7684，\u56e0\u6b64：N \u2265 2^h \u2212 1<\/p>\n
\u7531\u6b64\u5f97\u5230：h \u2264 log\u2082(N + 1)<\/p>\n
\u53c8\u56e0\u4e3a\u7ea2\u9ed1\u6811\u7684\u6700\u957f\u8def\u5f84\u4e0d\u8d85\u8fc7\u6700\u77ed\u8def\u5f84\u7684\u4e24\u500d，\u6240\u4ee5：H \u2264 2h \u2264 2 \u00d7 log\u2082(N + 1)<\/p>\n
\u56e0\u6b64，\u7ea2\u9ed1\u6811\u7684\u9ad8\u5ea6\u4e3a O(log N)，\u67e5\u627e\u3001\u63d2\u5165\u548c\u5220\u9664\u7684\u6700\u574f\u65f6\u95f4\u590d\u6742\u5ea6\u4e5f\u90fd\u662f O(log N)\u3002\u5982\u679c\u9700\u8981\u4fee\u6539 value，\u5148\u6309 key \u67e5\u627e\u5373\u53ef；key \u4e0d\u80fd\u76f4\u63a5\u4fee\u6539，\u5426\u5219\u53ef\u80fd\u7834\u574f\u641c\u7d22\u6811\u7684\u6027\u8d28\u3002<\/p>\n
\u4e0e AVL \u6811\u76f8\u6bd4，\u7ea2\u9ed1\u6811\u5bf9\u5e73\u8861\u7684\u63a7\u5236\u66f4\u52a0\u95f4\u63a5：AVL \u6811\u901a\u8fc7\u5de6\u53f3\u5b50\u6811\u7684\u9ad8\u5ea6\u5dee\u7ef4\u6301\u5e73\u8861，\u7ea2\u9ed1\u6811\u5219\u901a\u8fc7\u989c\u8272\u7ea6\u675f，\u4fdd\u8bc1\u6700\u957f\u8def\u5f84\u4e0d\u8d85\u8fc7\u6700\u77ed\u8def\u5f84\u7684\u4e24\u500d\u3002<\/p>\n
\u4e24\u8005\u7684\u64cd\u4f5c\u590d\u6742\u5ea6\u90fd\u5c5e\u4e8e O(log N)，\u4f46\u7ea2\u9ed1\u6811\u5bf9\u5e73\u8861\u7684\u8981\u6c42\u66f4\u5bbd\u677e，\u8c03\u6574\u65f6\u53ef\u4ee5\u901a\u8fc7\u53d8\u8272\u548c\u65cb\u8f6c\u6062\u590d\u6027\u8d28\u3002\u9700\u8981\u6ce8\u610f，\u4e0d\u80fd\u7b80\u5355\u8ba4\u4e3a\u63d2\u5165\u76f8\u540c\u6570\u91cf\u7684\u8282\u70b9，\u7ea2\u9ed1\u6811\u7684\u65cb\u8f6c\u6b21\u6570\u5c31\u4e00\u5b9a\u6bd4 AVL \u6811\u5c11，\u5177\u4f53\u6b21\u6570\u8fd8\u4e0e\u63d2\u5165\u987a\u5e8f\u6709\u5173\u3002<\/p>\n
\/\/ \u679a\u4e3e\u503c\u8868\u793a\u989c\u8272
\nenum Colour
\n{
\n RED,
\n BLACK
\n};
\n\/\/ \u9ed8\u8ba4\u6309 key\/value \u7ed3\u6784\u5b9e\u73b0
\ntemplate<class K, class V>
\nstruct RBTreeNode
\n{
\n pair<K, V> _kv;
\n RBTreeNode<K, V>* _left;
\n RBTreeNode<K, V>* _right;<\/p>\n
\/\/ \u8c03\u6574\u6811\u7684\u5e73\u8861\u65f6，\u9700\u8981\u901a\u8fc7 parent \u6307\u9488\u627e\u5230\u7236\u8282\u70b9
\n RBTreeNode<K, V>* _parent;
\n Colour _col;<\/p>\n
RBTreeNode(const pair<K, V>& kv)
\n : _kv(kv)
\n , _left(nullptr)
\n , _right(nullptr)
\n , _parent(nullptr)
\n {}
\n};
\ntemplate<class K, class V>
\nclass RBTree
\n{
\n typedef RBTreeNode<K, V> Node;
\npublic:
\nprivate:
\n Node* _root = nullptr;
\n};<\/p>\n
\u7ed3\u6784\u4e0e\u4e4b\u524d\u7684AVL\u6811\u5927\u81f4\u76f8\u540c，\u4f46\u662f\u7ea2\u9ed1\u6811\u4e2d\u6211\u4eec\u9700\u8981\u4e00\u4e2a\u7528\u6765\u8868\u793a\u989c\u8272\u7684Colour\u7ed3\u6784\u3002<\/p>\n
\u7ea2\u9ed1\u6811\u7684\u63d2\u5165\u5206\u4e3a\u4e24\u6b65：\u5148\u6309\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u89c4\u5219\u63d2\u5165\u8282\u70b9，\u518d\u68c0\u67e5\u5e76\u6062\u590d\u7ea2\u9ed1\u6811\u7684\u6027\u8d28\u3002<\/p>\n
<1>.\u6811\u4e3a\u7a7a：\u521b\u5efa\u65b0\u8282\u70b9\u4f5c\u4e3a\u6839\u8282\u70b9，\u5e76\u5c06\u5176\u8bbe\u4e3a\u9ed1\u8272，\u63d2\u5165\u7ed3\u675f\u3002<\/p>\n
<2>.\u6811\u4e0d\u4e3a\u7a7a：\u65b0\u589e\u8282\u70b9\u8bbe\u4e3a\u7ea2\u8272\u3002\u56e0\u4e3a\u63d2\u5165\u7ea2\u8272\u8282\u70b9\u4e0d\u4f1a\u6539\u53d8\u5404\u6761\u8def\u5f84\u4e0a\u7684\u9ed1\u8272\u8282\u70b9\u6570\u91cf；\u5982\u679c\u63d2\u5165\u9ed1\u8272\u8282\u70b9，\u5219\u4f1a\u7834\u574f\u9ed1\u8272\u8282\u70b9\u6570\u91cf\u76f8\u540c\u7684\u6027\u8d28，\u8c03\u6574\u8d77\u6765\u66f4\u52a0\u590d\u6742\u3002<\/p>\n
<3>.\u7236\u8282\u70b9\u4e3a\u9ed1\u8272：\u65b0\u589e\u7684\u7ea2\u8272\u8282\u70b9\u6ca1\u6709\u8fdd\u53cd\u4efb\u4f55\u6027\u8d28，\u63d2\u5165\u7ed3\u675f\u3002<\/p>\n
<4>.\u7236\u8282\u70b9\u4e3a\u7ea2\u8272：\u51fa\u73b0\u8fde\u7eed\u7684\u7ea2\u8272\u8282\u70b9，\u9700\u8981\u8fdb\u884c\u8c03\u6574\u3002\u6b64\u65f6，\u5f53\u524d\u8282\u70b9\u548c\u7236\u8282\u70b9\u90fd\u662f\u7ea2\u8272，\u7956\u7236\u8282\u70b9\u5fc5\u7136\u4e3a\u9ed1\u8272\u3002\u63a5\u4e0b\u6765\u9700\u8981\u6839\u636e\u53d4\u53d4\u8282\u70b9\u662f\u5426\u5b58\u5728\u53ca\u5176\u989c\u8272，\u7ed3\u5408\u5f53\u524d\u8282\u70b9\u4e0e\u7236\u8282\u70b9\u7684\u4f4d\u7f6e\u5173\u7cfb，\u5206\u522b\u5904\u7406\u3002<\/p>\n
\u540e\u7eed\u56fe\u4e2d\u7edf\u4e00\u4f7f\u7528\u4ee5\u4e0b\u6807\u8bb0：<\/p>\n
c（cur）：\u5f53\u524d\u9700\u8981\u5904\u7406\u7684\u8282\u70b9，\u521d\u59cb\u4e3a\u65b0\u589e\u8282\u70b9\u3002<\/p>\n<\/li>\n
p（parent）：c \u7684\u7236\u8282\u70b9\u3002<\/p>\n<\/li>\n
g（grandfather）：p \u7684\u7236\u8282\u70b9，\u5373 c \u7684\u7956\u7236\u8282\u70b9\u3002<\/p>\n<\/li>\n
u（uncle）：p \u7684\u5144\u5f1f\u8282\u70b9，\u5373 c \u7684\u53d4\u53d4\u8282\u70b9\u3002<\/p>\n<\/li>\n<\/ul>\n
\u8c03\u6574\u8fc7\u7a0b\u4e2d\u53ef\u80fd\u9700\u8981\u7ee7\u7eed\u5411\u4e0a\u5904\u7406，\u56e0\u6b64 c \u4e0d\u4e00\u5b9a\u59cb\u7ec8\u6307\u5411\u6700\u521d\u65b0\u589e\u7684\u8282\u70b9\u3002<\/p>\n
\u60c5\u51b5\u4e00：c \u4e3a\u7ea2\u8272，p \u4e3a\u7ea2\u8272，g \u4e3a\u9ed1\u8272，\u4e14\u53d4\u53d4\u8282\u70b9 u \u5b58\u5728\u5e76\u4e3a\u7ea2\u8272\u3002<\/p>\n
\u6b64\u65f6，c \u4e0e p \u8fde\u7eed\u4e3a\u7ea2\u8272，\u8fdd\u53cd\u4e86\u7ea2\u9ed1\u6811\u7684\u6027\u8d28\u3002\u5904\u7406\u65b9\u5f0f\u662f：<\/p>\n
\u5c06\u7236\u8282\u70b9 p \u548c\u53d4\u53d4\u8282\u70b9 u \u53d8\u4e3a\u9ed1\u8272\u3002<\/p>\n
\u5c06\u7956\u7236\u8282\u70b9 g \u53d8\u4e3a\u7ea2\u8272\u3002<\/p>\n
\u628a g \u5f53\u4f5c\u65b0\u7684 c，\u7ee7\u7eed\u5411\u4e0a\u68c0\u67e5\u3002<\/p>\n
\u4e3a\u4ec0\u4e48\u8fd9\u6837\u53d8\u8272？<\/p>\n
\u5c06 p \u548c u \u53d8\u9ed1\u540e，\u7ecf\u8fc7\u5b83\u4eec\u7684\u8def\u5f84\u90fd\u589e\u52a0\u4e86\u4e00\u4e2a\u9ed1\u8272\u8282\u70b9；\u518d\u5c06 g \u53d8\u7ea2，\u6bcf\u6761\u8def\u5f84\u53c8\u51cf\u5c11\u4e00\u4e2a\u9ed1\u8272\u8282\u70b9\u3002\u56e0\u6b64，\u4ece g \u6240\u5728\u5b50\u6811\u901a\u5f80\u5404\u4e2a NULL \u8282\u70b9\u7684\u8def\u5f84，\u9ed1\u8272\u8282\u70b9\u6570\u91cf\u4fdd\u6301\u4e0d\u53d8，\u540c\u65f6\u6d88\u9664\u4e86 c \u4e0e p \u8fde\u7eed\u4e3a\u7ea2\u8272\u7684\u95ee\u9898\u3002<\/p>\n
\u4e3a\u4ec0\u4e48\u8fd8\u8981\u5411\u4e0a\u68c0\u67e5？<\/p>\n
\u56e0\u4e3a g \u53d8\u6210\u4e86\u7ea2\u8272，\u53ef\u80fd\u4e0e\u5b83\u7684\u7236\u8282\u70b9\u5f62\u6210\u65b0\u7684\u8fde\u7eed\u7ea2\u8272：<\/p>\n
g \u7684\u7236\u8282\u70b9\u4e3a\u7ea2\u8272：\u7ee7\u7eed\u5411\u4e0a\u8c03\u6574\u3002<\/p>\n<\/li>\n
g \u7684\u7236\u8282\u70b9\u4e3a\u9ed1\u8272：\u8c03\u6574\u7ed3\u675f\u3002<\/p>\n<\/li>\n
g \u5df2\u7ecf\u662f\u6839\u8282\u70b9：\u5c06 g \u91cd\u65b0\u8bbe\u4e3a\u9ed1\u8272，\u8c03\u6574\u7ed3\u675f\u3002<\/p>\n<\/li>\n<\/ul>\n
\u8fd9\u79cd\u60c5\u51b5\u53ea\u9700\u8981\u53d8\u8272，\u4e0d\u9700\u8981\u65cb\u8f6c\u3002 \u65e0\u8bba c \u662f p \u7684\u5de6\u5b69\u5b50\u8fd8\u662f\u53f3\u5b69\u5b50，p \u662f g \u7684\u5de6\u5b69\u5b50\u8fd8\u662f\u53f3\u5b69\u5b50，\u5904\u7406\u65b9\u5f0f\u90fd\u76f8\u540c\u3002<\/p>\n
\u53d8\u8272\u5982\u56fe：<\/p>\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/10\/20261031124051-6ae5e1d3848f0.png\")
<\/p>\n
\u8fd9\u4e2a\u56fe\u7247\u5411\u6211\u4eec\u5c55\u793a\u4e86\u2f00\u79cd\u5177\u4f53\u60c5\u51b5，\u4f46\u662f\u5b9e\u9645\u4e2d\u9700\u8981\u8fd9\u6837\u5904\u7406\u7684\u6709\u5f88\u591a\u79cd\u60c5\u51b5\u3002<\/p>\n
\u62bd\u8c61\u56fe\u5982\u4e0b：<\/p>\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/10\/20261031124053-6ae5e1d5457a3.png\")
<\/p>\n
\u8be5\u56fe\u5c06\u4ee5\u4e0a\u7c7b\u4f3c\u7684\u5904\u7406\u8fdb\u884c\u4e86\u62bd\u8c61\u8868\u8fbe，d\/e\/f\u4ee3\u8868\u6bcf\u6761\u8def\u5f84\u62e5\u6709hb\u4e2a\u9ed1\u8272\u7ed3\u70b9\u7684\u5b50\u6811，a\/b\u4ee3\u8868\u6bcf <\/p>\n
\u6761\u8def\u5f84\u62e5\u6709hb-1\u4e2a\u9ed1\u8272\u7ed3\u70b9\u7684\u6839\u4e3a\u7ea2\u7684\u5b50\u6811，hb>=0\u3002<\/p>\n
\u4ee3\u7801\u5982\u4e0b：<\/p>\n
bool Insert(const pair<K, V>& kv)
\n{
\nif (_root == nullptr)
\n{
\n_root = new Node(kv);
\n_root->_col = Black;
\nreturn true;
\n}<\/p>\n
\/\/\u5bfb\u627e\u63d2\u5165\u7684\u5730\u65b9
\nNode* 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}
\n\/\/\u63d2\u5165\u8282\u70b9
\ncur = new Node(kv);
\ncur->_col = Red;
\nif (parent->_kv.first < kv.first)
\n{
\nparent->_right = cur;
\n}
\nelse
\n{
\nparent->_left = cur;
\n}
\ncur->_parent = parent;<\/p>\n
\/\/\u68c0\u67e5parent\u662f\u5426\u4e3aRed
\n\/\/\u6ce8\u610f\u6b64\u5904\u662f\u5148\u68c0\u67e5parent\u662f\u5426\u5b58\u5728，\u5728\u68c0\u67e5parent\u7684\u989c\u8272\u662f\u5426\u4e3a\u7ea2\u8272
\nwhile (parent&&parent->_col == Red)
\n{
\nNode* grandfather = parent->_parent;
\nif (grandfather->_left == parent)
\n{
\nNode* uncle = grandfather->_right;
\n\/\/\u67d3\u8272\u4e0d\u65cb\u8f6c
\nif (uncle && uncle->_col == Red)
\n{
\nparent->_col = Black;
\nuncle->_col = Black;
\ngrandfather->_col = Red;
\n\/\/ \u7ee7\u7eed\u5f80\u4e0a\u5904\u7406
\ncur = grandfather;
\nparent = cur->_parent;
\n}
\n\/\/uncle->_col == Black||uncle==nullptr
\nelse
\n{
\n }
\n}
\n\/\/grandfather->_right == parent
\nelse
\n{
\nNode* uncle = grandfather->_left;
\nif (uncle && uncle->_col == Red)
\n{
\nparent->_col = Black;
\nuncle->_col = Black;
\ngrandfather->_col = Red;<\/p>\n
cur = grandfather;
\nparent = cur->_parent;
\n}<\/p>\n
else
\n{
\n}
\n}
\n}
\nreturn true;
\n}<\/p>\n
\u4f46\u662f，\u6211\u4eec\u8fd8\u6709\u4e2a\u95ee\u9898：\u4f1a\u4e0d\u4f1a\u6539\u7740\u6539\u7740\u5c06\u6839\u8282\u70b9\u7ed9\u6539\u6210\u7ea2\u8272\u7684\u4e86？\u5f53\u7136\u662f\u6709\u8fd9\u79cd\u53ef\u80fd\u7684，\u6240\u4ee5\u6211\u4eec\u8981\u5728\u6700\u540e\u52a0\u4e0a：<\/p>\n
_root->_col = Black;<\/p>\n
\u800c\u4e14\u6211\u4eec\u8fd9\u4e2a\u4ee3\u7801\u8fd8\u8981\u533a\u5206grandfather\u7684\u5de6\u8282\u70b9\u548c\u53f3\u8282\u70b9\u54ea\u4e00\u4e2a\u6307\u5411parent?\u8fd9\u4e2a\u5c06\u4f1a\u5f71\u54cd\u540e\u9762<\/p>\n
\u7684\u65cb\u8f6c，\u4f46\u662f\u8fd9\u7bc7\u6587\u7ae0\u6211\u4eec\u4f18\u5148\u8003\u8651grandfather->_left==parent，\u5f53\u6211\u4eec\u771f\u6b63\u7684\u4e86\u89e3\u601d\u60f3\u540e\u5c31\u53ef\u4ee5\u72ec\u7acb\u7684\u5199grandfather->_right==parent\u7684\u4ee3\u7801\u4e86\u3002<\/p>\n
\u60c5\u51b5\u4e8c：c \u4e3a\u7ea2\u8272，p \u4e3a\u7ea2\u8272，g \u4e3a\u9ed1\u8272，\u53d4\u53d4\u8282\u70b9 u \u4e0d\u5b58\u5728\u6216\u4e3a\u9ed1\u8272\u3002<\/p>\n
\u8fd9\u91cc\u53ef\u4ee5\u8fdb\u4e00\u6b65\u533a\u5206：<\/p>\n
u \u4e0d\u5b58\u5728：c \u662f\u672c\u6b21\u65b0\u589e\u7684\u7ea2\u8272\u8282\u70b9\u3002<\/p>\n<\/li>\n
u \u5b58\u5728\u4e14\u4e3a\u9ed1\u8272：c \u4e0d\u662f\u65b0\u589e\u8282\u70b9，\u800c\u662f\u5728\u4e0b\u5c42\u6309\u60c5\u51b5\u4e00\u8c03\u6574\u65f6，\u7531\u9ed1\u8272\u53d8\u4e3a\u7ea2\u8272，\u518d\u4f5c\u4e3a\u65b0\u7684 c \u5411\u4e0a\u4f20\u9012\u7684\u8282\u70b9\u3002<\/p>\n<\/li>\n<\/ul>\n
\u6b64\u65f6，c \u4e0e p \u8fde\u7eed\u4e3a\u7ea2\u8272，\u9700\u8981\u8c03\u6574\u3002\u4f46\u7531\u4e8e\u53d4\u53d4\u4e00\u4fa7\u6ca1\u6709\u7ea2\u8272\u8282\u70b9\u53ef\u4ee5\u4e00\u8d77\u53d8\u9ed1，\u5355\u7eaf\u53d8\u8272\u65e0\u6cd5\u540c\u65f6\u4fdd\u8bc1\u9ed1\u8272\u8282\u70b9\u6570\u91cf\u76f8\u540c，\u56e0\u6b64\u9700\u8981\u901a\u8fc7\u65cb\u8f6c\u914d\u5408\u53d8\u8272\u6062\u590d\u7ea2\u9ed1\u6811\u7684\u6027\u8d28\u3002<\/p>\n
<1>. p \u662f g \u7684\u5de6\u5b69\u5b50，c \u662f p \u7684\u5de6\u5b69\u5b50：\u53f3\u5355\u65cb＋\u53d8\u8272<\/p>\n
g
\n p u(\u53ef\u80fd\u4e0d\u5b58\u5728)
\nc<\/p>\n
\u6b64\u65f6，g\u3001p\u3001c \u5f62\u6210\u5de6\u5de6\u7ed3\u6784，\u5904\u7406\u6b65\u9aa4\u5982\u4e0b：<\/p>\n
\u4ee5 g \u4e3a\u65cb\u8f6c\u70b9\u8fdb\u884c\u53f3\u5355\u65cb，\u8ba9 p \u6210\u4e3a\u8fd9\u68f5\u5b50\u6811\u7684\u65b0\u6839\u3002<\/p>\n<\/li>\n
\u5c06 p \u53d8\u4e3a\u9ed1\u8272，g \u53d8\u4e3a\u7ea2\u8272\u3002<\/p>\n<\/li>\n
c \u4fdd\u6301\u7ea2\u8272\u3002<\/p>\n<\/li>\n
\u8c03\u6574\u540e，p \u4e3a\u9ed1\u8272，c \u548c g \u4e3a\u7ea2\u8272，\u6d88\u9664\u4e86\u8fde\u7eed\u7ea2\u8272\u8282\u70b9，\u540c\u65f6\u4fdd\u6301\u8fd9\u68f5\u5b50\u6811\u5404\u6761\u8def\u5f84\u4e0a\u7684\u9ed1\u8272\u8282\u70b9\u6570\u91cf\u4e0d\u53d8\u3002<\/p>\n
<2>. p \u662f g \u7684\u53f3\u5b69\u5b50，c \u662f p \u7684\u53f3\u5b69\u5b50：\u5de6\u5355\u65cb＋\u53d8\u8272<\/p>\n
g
\n u p
\n c<\/p>\n
\u6b64\u65f6，g\u3001p\u3001c \u5f62\u6210\u53f3\u53f3\u7ed3\u6784，\u4e0e\u5de6\u5de6\u60c5\u51b5\u5bf9\u79f0：<\/p>\n
\u4ee5 g \u4e3a\u65cb\u8f6c\u70b9\u8fdb\u884c\u5de6\u5355\u65cb，\u8ba9 p \u6210\u4e3a\u8fd9\u68f5\u5b50\u6811\u7684\u65b0\u6839\u3002<\/p>\n<\/li>\n
\u5c06 p \u53d8\u4e3a\u9ed1\u8272，g \u53d8\u4e3a\u7ea2\u8272\u3002<\/p>\n<\/li>\n
c \u4fdd\u6301\u7ea2\u8272\u3002<\/p>\n<\/li>\n
\u8c03\u6574\u540e，\u540c\u6837\u6d88\u9664\u4e86\u8fde\u7eed\u7ea2\u8272\u8282\u70b9，\u5e76\u4fdd\u6301\u8fd9\u68f5\u5b50\u6811\u5404\u6761\u8def\u5f84\u4e0a\u7684\u9ed1\u8272\u8282\u70b9\u6570\u91cf\u4e0d\u53d8\u3002<\/p>\n
\u8fd9\u4e24\u79cd\u60c5\u51b5\u8c03\u6574\u5b8c\u6210\u540e，\u90fd\u4e0d\u9700\u8981\u7ee7\u7eed\u5411\u4e0a\u5904\u7406\u3002<\/p>\n
\u56e0\u4e3a\u65b0\u7684\u5b50\u6811\u6839\u8282\u70b9 p \u4e3a\u9ed1\u8272，\u65e0\u8bba\u5b83\u4e0a\u9762\u8fde\u63a5\u7684\u662f\u7ea2\u8272\u8282\u70b9\u3001\u9ed1\u8272\u8282\u70b9，\u8fd8\u662f\u5b83\u76f4\u63a5\u6210\u4e3a\u6574\u68f5\u6811\u7684\u6839，\u90fd\u4e0d\u4f1a\u4ea7\u751f\u65b0\u7684\u989c\u8272\u51b2\u7a81；\u540c\u65f6，\u5b50\u6811\u5bf9\u5916\u7684\u9ed1\u8272\u9ad8\u5ea6\u4fdd\u6301\u4e0d\u53d8，\u4e0d\u4f1a\u5f71\u54cd\u5176\u4ed6\u8def\u5f84\u3002<\/p>\n
\u8fd9\u91cc\u6211\u62ff\u4e0a\u9762\u7684\u53f3\u5355\u65cb\u6765\u4e3e\u4f8b\u5b50：<\/p>\n
\u793a\u4f8b\u4e00:<\/p>\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/10\/20261031124056-6ae5e1d81b362.png\")
<\/p>\n
\u63d2\u5165\u7ea2\u8272\u8282\u70b9 3 \u540e，3 \u4e0e\u7236\u8282\u70b9 6 \u8fde\u7eed\u4e3a\u7ea2，\u5f62\u6210\u5de6\u5de6\u7ed3\u6784\u3002\u4ee5 10 \u4e3a\u65cb\u8f6c\u70b9\u53f3\u5355\u65cb，\u518d\u5c06 6 \u53d8\u9ed1\u300110 \u53d8\u7ea2，\u8c03\u6574\u7ed3\u675f\u3002<\/p>\n
\u793a\u4f8b\u4e8c：<\/p>\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/10\/20261031124056-6ae5e1d8bacb7.png\")
<\/p>\n
\u8282\u70b9 3 \u539f\u672c\u4e3a\u9ed1\u8272\u3002\u5728\u5b83\u7684\u5b50\u6811\u4e2d\u63d2\u5165\u8282\u70b9\u5e76\u8fdb\u884c\u53d8\u8272\u540e，3 \u53d8\u7ea2，\u4f5c\u4e3a\u65b0\u7684 c \u5411\u4e0a\u68c0\u67e5，\u4e0e\u7ea2\u8272\u7236\u8282\u70b9 6 \u4ea7\u751f\u51b2\u7a81\u3002<\/p>\n
\u6b64\u65f6\u53d4\u53d4 15 \u4e3a\u9ed1\u8272，\u9700\u8981\u4ee5 10 \u4e3a\u65cb\u8f6c\u70b9\u53f3\u5355\u65cb：<\/p>\n
\u793a\u4f8b\u4e09：<\/p>\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/10\/20261031124058-6ae5e1da2ec46.png\")
<\/p>\n
\u6700\u521d a\u3001b \u7684\u6839\u4e3a\u7ea2\u8272，d \u7684\u6839\u4e3a\u9ed1\u8272\u3002\u4e0b\u5c42\u63d2\u5165\u5e76\u53d8\u8272\u540e，a\u3001b \u7684\u6839\u53d8\u9ed1，\u8282\u70b9 3 \u53d8\u7ea2，\u56e0\u6b64\u7ecf\u8fc7 3 \u7684\u8def\u5f84\u4e0a，\u9ed1\u8272\u8282\u70b9\u6570\u91cf\u4fdd\u6301\u4e0d\u53d8\u3002<\/p>\n
\u968f\u540e\u8fdb\u884c\u53f3\u5355\u65cb\u548c\u53d8\u8272，\u6d88\u9664 3 \u4e0e 6 \u8fde\u7eed\u4e3a\u7ea2\u7684\u95ee\u9898\u3002\u8c03\u6574\u540e\u7684\u5b50\u6811\u6839 6 \u4e3a\u9ed1\u8272，\u5b50\u6811\u5bf9\u5916\u7684\u9ed1\u8272\u9ad8\u5ea6\u4fdd\u6301\u4e0d\u53d8，\u4e0d\u9700\u8981\u7ee7\u7eed\u5411\u4e0a\u8c03\u6574\u3002<\/p>\n
\u4ee3\u7801：<\/p>\n
\/\/\u5b58\u5728\u4e14\u4e3a\u2fca\u6216\u4e0d\u5b58\u5728-\u300b\u65cb\u8f6c+\u53d8\u2f8a
\nif (parent->_left == cur)
\n{
\n Rotate_Right(grandfather);
\nparent->_col = Black;
\ngrandfather->_col = Red;
\n}<\/p>\n
\u60c5\u51b5\u4e09：c \u4e3a\u7ea2\u8272，p \u4e3a\u7ea2\u8272，g \u4e3a\u9ed1\u8272，\u53d4\u53d4\u8282\u70b9 u \u4e0d\u5b58\u5728\u6216\u4e3a\u9ed1\u8272，\u4e14 c \u4e0e p \u7684\u65b9\u5411\u4e0d\u540c\u3002<\/p>\n
\u5176\u4e2d：<\/p>\n
u \u4e0d\u5b58\u5728：c \u662f\u672c\u6b21\u65b0\u589e\u7684\u7ea2\u8272\u8282\u70b9\u3002<\/p>\n<\/li>\n
u \u5b58\u5728\u4e14\u4e3a\u9ed1\u8272：c \u662f\u4e0b\u5c42\u6309\u60c5\u51b5\u4e00\u53d8\u8272\u540e，\u7531\u9ed1\u8272\u53d8\u4e3a\u7ea2\u8272，\u518d\u5411\u4e0a\u4f20\u9012\u7684\u8282\u70b9\u3002<\/p>\n<\/li>\n<\/ul>\n
\u6b64\u65f6，c \u4e0e p \u8fde\u7eed\u4e3a\u7ea2\u8272，\u5355\u7eaf\u53d8\u8272\u65e0\u6cd5\u540c\u65f6\u7ef4\u6301\u5404\u6761\u8def\u5f84\u4e0a\u7684\u9ed1\u8272\u8282\u70b9\u6570\u91cf，\u9700\u8981\u901a\u8fc7\u53cc\u65cb\u914d\u5408\u53d8\u8272\u6062\u590d\u7ea2\u9ed1\u6811\u7684\u6027\u8d28\u3002<\/p>\n
<1>. p \u662f g \u7684\u5de6\u5b69\u5b50，c \u662f p \u7684\u53f3\u5b69\u5b50：\u5de6\u53f3\u53cc\u65cb＋\u53d8\u8272<\/p>\n
g
\n p u(\u53ef\u80fd\u4e0d\u5b58\u5728)
\n c<\/p>\n
\u5904\u7406\u6b65\u9aa4\u5982\u4e0b：<\/p>\n
\u4ee5 p \u4e3a\u65cb\u8f6c\u70b9\u8fdb\u884c\u5de6\u5355\u65cb，\u5c06\u5de6\u53f3\u7ed3\u6784\u8f6c\u5316\u4e3a\u5de6\u5de6\u7ed3\u6784\u3002<\/p>\n<\/li>\n
\u4ee5 g \u4e3a\u65cb\u8f6c\u70b9\u8fdb\u884c\u53f3\u5355\u65cb，\u8ba9\u539f\u6765\u7684 c \u6210\u4e3a\u8fd9\u68f5\u5b50\u6811\u7684\u65b0\u6839\u3002<\/p>\n<\/li>\n
\u5c06 c \u53d8\u4e3a\u9ed1\u8272，g \u53d8\u4e3a\u7ea2\u8272，p \u4fdd\u6301\u7ea2\u8272\u3002<\/p>\n<\/li>\n
\u8c03\u6574\u540e，c \u4e3a\u9ed1\u8272，\u5de6\u53f3\u5b69\u5b50 p\u3001g \u4e3a\u7ea2\u8272，\u6d88\u9664\u4e86\u8fde\u7eed\u7ea2\u8272\u8282\u70b9，\u5e76\u4fdd\u6301\u5b50\u6811\u5404\u6761\u8def\u5f84\u4e0a\u7684\u9ed1\u8272\u8282\u70b9\u6570\u91cf\u4e0d\u53d8\u3002<\/p>\n
<2>. p \u662f g \u7684\u53f3\u5b69\u5b50，c \u662f p \u7684\u5de6\u5b69\u5b50：\u53f3\u5de6\u53cc\u65cb＋\u53d8\u8272<\/p>\n
g
\n u p
\n c<\/p>\n
\u5904\u7406\u6b65\u9aa4\u4e0e\u5de6\u53f3\u60c5\u51b5\u5bf9\u79f0：<\/p>\n
\u4ee5 p \u4e3a\u65cb\u8f6c\u70b9\u8fdb\u884c\u53f3\u5355\u65cb，\u5c06\u53f3\u5de6\u7ed3\u6784\u8f6c\u5316\u4e3a\u53f3\u53f3\u7ed3\u6784\u3002<\/p>\n<\/li>\n
\u4ee5 g \u4e3a\u65cb\u8f6c\u70b9\u8fdb\u884c\u5de6\u5355\u65cb，\u8ba9\u539f\u6765\u7684 c \u6210\u4e3a\u8fd9\u68f5\u5b50\u6811\u7684\u65b0\u6839\u3002<\/p>\n<\/li>\n
\u5c06 c \u53d8\u4e3a\u9ed1\u8272，g \u53d8\u4e3a\u7ea2\u8272，p \u4fdd\u6301\u7ea2\u8272\u3002<\/p>\n<\/li>\n
\u53cc\u65cb\u5b8c\u6210\u540e，\u53d8\u9ed1\u7684\u662f\u65b0\u7684\u5b50\u6811\u6839 c，\u800c\u4e0d\u662f p\u3002<\/p>\n
\u65b0\u7684\u5b50\u6811\u6839 c \u4e3a\u9ed1\u8272，\u65e0\u8bba\u5b83\u4e0a\u9762\u8fde\u63a5\u7684\u662f\u7ea2\u8272\u8282\u70b9\u3001\u9ed1\u8272\u8282\u70b9，\u8fd8\u662f\u5b83\u76f4\u63a5\u6210\u4e3a\u6574\u68f5\u6811\u7684\u6839，\u90fd\u4e0d\u4f1a\u4ea7\u751f\u65b0\u7684\u989c\u8272\u51b2\u7a81\u3002\u540c\u65f6，\u5b50\u6811\u5bf9\u5916\u7684\u9ed1\u8272\u9ad8\u5ea6\u4fdd\u6301\u4e0d\u53d8，\u56e0\u6b64\u4e0d\u9700\u8981\u7ee7\u7eed\u5411\u4e0a\u8c03\u6574\u3002<\/p>\n
\u90a3\u4e48\u6211\u62ff\u4e0a\u9762\u7684\u5de6\u53f3\u5355\u65cb\u6765\u4e3e\u4f8b\u5b50：<\/p>\n
\u793a\u4f8b\u4e00：<\/p>\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/10\/20261031124059-6ae5e1dbbe408.png\")
<\/p>\n<\/p>\n
\u5148\u4ee5 p（6） \u5de6\u65cb，\u4f7f 8 \u6210\u4e3a 10 \u7684\u5de6\u5b69\u5b50，6 \u6210\u4e3a 8 \u7684\u5de6\u5b69\u5b50；\u518d\u4ee5 g（10） \u53f3\u65cb，\u4f7f 8 \u6210\u4e3a\u5b50\u6811\u7684\u65b0\u6839\u3002\u6700\u540e\u5c06 8 \u53d8\u9ed1\u300110 \u53d8\u7ea2，6 \u4fdd\u6301\u7ea2\u8272\u3002<\/p>\n
\u793a\u4f8b\u4e8c：![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/10\/20261031124100-6ae5e1dce8260.png\")
<\/p>\n
\u7b2c\u4e00\u6b21\u5de6\u65cb\u65f6，\u5b50\u6811 a \u8f6c\u63a5\u4e3a 6 \u7684\u53f3\u5b50\u6811，b \u4ecd\u4e3a 8 \u7684\u53f3\u5b50\u6811\u3002\u7b2c\u4e8c\u6b21\u53f3\u65cb\u65f6，\u5b50\u6811 b \u8f6c\u63a5\u4e3a 10 \u7684\u5de6\u5b50\u6811\u3002\u6700\u7ec8 6\u300110 \u5206\u522b\u6210\u4e3a 8 \u7684\u5de6\u53f3\u5b69\u5b50\u3002<\/p>\n
\u793a\u4f8b\u4e09：<\/p>\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/10\/20261031124102-6ae5e1dec6b6c.png\")
<\/p>\n
\u4e0b\u5c42\u63d2\u5165\u5e76\u53d8\u8272\u540e，8 \u7531\u9ed1\u53d8\u7ea2，\u4e0e\u7236\u8282\u70b9 6 \u4ea7\u751f\u51b2\u7a81\u3002\u968f\u540e\u4f9d\u6b21\u5de6\u65cb\u3001\u53f3\u65cb\u5e76\u53d8\u8272，\u5728\u6d88\u9664\u8fde\u7eed\u7ea2\u8272\u8282\u70b9\u7684\u540c\u65f6，\u4fdd\u6301\u5b50\u6811\u5bf9\u5916\u7684\u9ed1\u8272\u9ad8\u5ea6\u4e0d\u53d8，\u8c03\u6574\u7ed3\u675f\u3002<\/p>\n
\u4ee3\u7801：<\/p>\n
\/\/\u67d3\u8272+\u53cc\u65cb\u8f6c,parent->_right == cur
\nelse
\n{
\nRotate_Left(parent);
\nRotate_Right(grandfather);
\ncur->_col = Black;
\ngrandfather->_col = Red;
\n}
\nbreak;<\/p>\n
\u6240\u4ee5\u4e00\u4e2a\u534a\u5b8c\u6574\u7684\u4ee3\u7801\u5982\u4e0b：<\/p>\n
if (grandfather->_left == parent)
\n{
\nNode* uncle = grandfather->_right;
\n\/\/\u67d3\u8272\u4e0d\u65cb\u8f6c
\nif (uncle && uncle->_col == Red)
\n{
\nparent->_col = Black;
\nuncle->_col = Black;
\ngrandfather->_col = Red;
\n\/\/ \u7ee7\u7eed\u5f80\u4e0a\u5904\u7406
\ncur = grandfather;
\nparent = cur->_parent;
\n}
\n\/\/uncle->_col == Black||uncle==nullptr
\nelse
\n{
\n\/\/\u5b58\u5728\u4e14\u4e3a\u2fca\u6216\u4e0d\u5b58\u5728-\u300b\u65cb\u8f6c+\u53d8\u2f8a
\nif (parent->_left == cur)
\n{
\nRotate_Right(grandfather);
\nparent->_col = Black;
\ngrandfather->_col = Red;
\n}
\n\/\/\u67d3\u8272+\u53cc\u65cb\u8f6c,parent->_right == cur
\nelse
\n{
\nRotate_Left(parent);
\nRotate_Right(grandfather);
\ncur->_col = Black;
\ngrandfather->_col = Red;
\n}
\nbreak;
\n}
\n}<\/p>\n
\u90a3\u4e48\u8fd9\u4e2agrandfather->_right == parent\u7684\u4ee3\u7801\u6211\u5c31\u4e0d\u518d\u8be6\u7ec6\u7684\u89e3\u91ca\u4e86，\u5982\u4e0b：<\/p>\n
\/\/ grandfather->_right == parent
\nelse
\n{
\n Node* uncle = grandfather->_left;<\/p>\n
\/\/ \u67d3\u8272，\u4e0d\u65cb\u8f6c
\n if (uncle && uncle->_col == Red)
\n {
\n parent->_col = Black;
\n uncle->_col = Black;
\n grandfather->_col = Red;<\/p>\n
cur = grandfather;
\n parent = cur->_parent;
\n }
\n else
\n {
\n \/\/ \u67d3\u8272 + \u5355\u65cb\u8f6c
\n if (parent->_right == cur)
\n {
\n Rotate_Left(grandfather);<\/p>\n
parent->_col = Black;
\n grandfather->_col = Red;
\n }
\n \/\/ \u67d3\u8272 + \u53cc\u65cb\u8f6c，parent->_left == cur
\n else
\n {
\n Rotate_Right(parent);
\n Rotate_Left(grandfather);<\/p>\n
cur->_col = Black;
\n grandfather->_col = Red;
\n }<\/p>\n
break;
\n }
\n}<\/p>\n
\u4ec5\u901a\u8fc7\u83b7\u53d6\u6700\u957f\u8def\u5f84\u548c\u6700\u77ed\u8def\u5f84，\u68c0\u67e5\u6700\u957f\u8def\u5f84\u662f\u5426\u4e0d\u8d85\u8fc7\u6700\u77ed\u8def\u5f84\u7684 2 \u500d，\u65e0\u6cd5\u5224\u65ad\u4e00\u68f5\u6811\u662f\u5426\u6ee1\u8db3\u7ea2\u9ed1\u6811\u7684\u89c4\u5219\u3002<\/p>\n
\u56e0\u4e3a\u5373\u4f7f\u6ee1\u8db3\u8fd9\u4e2a\u6761\u4ef6，\u7ed3\u70b9\u7684\u989c\u8272\u4ecd\u53ef\u80fd\u8fdd\u53cd\u89c4\u5219\u3002\u5f53\u524d\u6682\u65f6\u6ca1\u6709\u51fa\u73b0\u95ee\u9898，\u540e\u7eed\u7ee7\u7eed\u63d2\u5165\u65f6\u4e5f\u53ef\u80fd\u51fa\u73b0\u95ee\u9898\u3002<\/p>\n
\u56e0\u6b64，\u6211\u4eec\u8fd8\u662f\u9700\u8981\u68c0\u67e5\u4ee5\u4e0b 4 \u6761\u89c4\u5219\u3002\u6ee1\u8db3\u8fd9\u4e9b\u89c4\u5219，\u5c31\u80fd\u4fdd\u8bc1\u6700\u957f\u8def\u5f84\u4e0d\u8d85\u8fc7\u6700\u77ed\u8def\u5f84\u7684 2 \u500d\u3002<\/p>\n
<1>.\u7ed3\u70b9\u7684\u989c\u8272\u4e0d\u662f\u9ed1\u8272，\u5c31\u662f\u7ea2\u8272\u3002<\/p>\n
\u4f7f\u7528\u679a\u4e3e\u7c7b\u578b\u5b9a\u4e49\u989c\u8272，\u5728\u6b63\u5e38\u4f7f\u7528\u7684\u60c5\u51b5\u4e0b\u5373\u53ef\u4fdd\u8bc1\u8fd9\u4e00\u70b9\u3002<\/p>\n
<2>.\u6839\u7ed3\u70b9\u5fc5\u987b\u662f\u9ed1\u8272\u3002<\/p>\n
\u76f4\u63a5\u68c0\u67e5\u6839\u7ed3\u70b9\u7684\u989c\u8272\u5373\u53ef\u3002<\/p>\n
<3>.\u4e0d\u80fd\u51fa\u73b0\u8fde\u7eed\u7684\u7ea2\u8272\u7ed3\u70b9\u3002<\/p>\n
\u4f7f\u7528\u524d\u5e8f\u904d\u5386\u68c0\u67e5\u3002\u9047\u5230\u7ea2\u8272\u7ed3\u70b9\u65f6，\u53ef\u4ee5\u68c0\u67e5\u5176\u5b69\u5b50\u662f\u5426\u4e3a\u7ea2\u8272，\u4f46\u5b69\u5b50\u6709\u4e24\u4e2a，\u800c\u4e14\u4e0d\u4e00\u5b9a\u5b58\u5728\u3002<\/p>\n
\u56e0\u6b64，\u53cd\u8fc7\u6765\u68c0\u67e5\u5176\u7236\u4eb2\u7684\u989c\u8272\u66f4\u65b9\u4fbf：\u5982\u679c\u5f53\u524d\u7ed3\u70b9\u548c\u7236\u4eb2\u90fd\u662f\u7ea2\u8272，\u5c31\u8fdd\u53cd\u4e86\u89c4\u5219\u3002<\/p>\n
<4>.\u4ece\u6839\u7ed3\u70b9\u5230\u6bcf\u4e2a\u7a7a\u7ed3\u70b9\u7684\u8def\u5f84\u4e0a，\u9ed1\u8272\u7ed3\u70b9\u7684\u6570\u91cf\u5fc5\u987b\u76f8\u540c\u3002<\/p>\n
\u4f7f\u7528\u524d\u5e8f\u904d\u5386，\u901a\u8fc7\u5f62\u53c2 blackNum \u8bb0\u5f55\u4ece\u6839\u7ed3\u70b9\u5230\u5f53\u524d\u7ed3\u70b9\u7684\u9ed1\u8272\u7ed3\u70b9\u6570\u91cf\u3002\u6bcf\u9047\u5230\u4e00\u4e2a\u9ed1\u8272\u7ed3\u70b9，\u5c31\u6267\u884c ++blackNum；\u8d70\u5230\u7a7a\u7ed3\u70b9\u65f6，\u5c31\u5f97\u5230\u4e86\u4e00\u6761\u5b8c\u6574\u8def\u5f84\u4e0a\u7684\u9ed1\u8272\u7ed3\u70b9\u6570\u91cf\u3002<\/p>\n
\u4efb\u9009\u4e00\u6761\u8def\u5f84\u7684\u9ed1\u8272\u7ed3\u70b9\u6570\u91cf\u4f5c\u4e3a\u53c2\u8003\u503c，\u518d\u4f9d\u6b21\u6bd4\u8f83\u5176\u4ed6\u8def\u5f84\u3002\u5982\u679c\u5b58\u5728\u4e0d\u540c\u7684\u6570\u91cf，\u5c31\u8fdd\u53cd\u4e86\u89c4\u5219\u3002<\/p>\n
\u4ee3\u7801\u5982\u4e0b：<\/p>\n
bool Check(Node* root, int blackNum, const int refNum)
\n{
\n if (root == nullptr)
\n {
\n \/\/ \u904d\u5386\u5230\u7a7a\u7ed3\u70b9，\u610f\u5473\u7740\u4e00\u6761\u8def\u5f84\u8d70\u5b8c\u4e86
\n if (refNum != blackNum)
\n {
\n cout << "\u5b58\u5728\u9ed1\u8272\u7ed3\u70b9\u6570\u91cf\u4e0d\u76f8\u7b49\u7684\u8def\u5f84" << endl;
\n return false;
\n }
\n return true;
\n }
\n \/\/ \u68c0\u67e5\u5f53\u524d\u7ed3\u70b9\u548c\u7236\u4eb2\u662f\u5426\u90fd\u662f\u7ea2\u8272
\n if (root->_col == RED && root->_parent->_col == RED)
\n {
\n cout << root->_kv.first << " \u5b58\u5728\u8fde\u7eed\u7684\u7ea2\u8272\u7ed3\u70b9" << endl;
\n return false;
\n }
\n \/\/ \u8bb0\u5f55\u5f53\u524d\u8def\u5f84\u4e0a\u7684\u9ed1\u8272\u7ed3\u70b9\u6570\u91cf
\n if (root->_col == BLACK)
\n {
\n blackNum++;
\n }
\n return Check(root->_left, blackNum, refNum)
\n && Check(root->_right, blackNum, refNum);
\n}<\/p>\n
bool IsBalance()
\n{
\n \/\/ \u7a7a\u6811\u7b26\u5408\u7ea2\u9ed1\u6811\u89c4\u5219
\n if (_root == nullptr)
\n {
\n return true;
\n }
\n \/\/ \u6839\u7ed3\u70b9\u5fc5\u987b\u662f\u9ed1\u8272
\n if (_root->_col == RED)
\n {
\n return false;
\n }
\n \/\/ \u7edf\u8ba1\u6700\u5de6\u4fa7\u8def\u5f84\u4e0a\u7684\u9ed1\u8272\u7ed3\u70b9\u6570\u91cf，\u4f5c\u4e3a\u53c2\u8003\u503c
\n int refNum = 0;
\n Node* cur = _root;
\n while (cur)
\n {
\n if (cur->_col == BLACK)
\n {
\n ++refNum;
\n }
\n cur = cur->_left;
\n }
\n return Check(_root, 0, refNum);
\n}<\/p>\n
\u8fd9\u91cc\u8bb2\u4e00\u4e0b\u601d\u8def：<\/p>\n
\u5148\u68c0\u67e5\u6839\u7ed3\u70b9，\u518d\u9009\u62e9\u4e00\u6761\u8def\u5f84\u4f5c\u4e3a\u53c2\u8003，\u6700\u540e\u9012\u5f52\u68c0\u67e5\u6574\u68f5\u6811\u3002<\/p>\n
IsBalance()：\u68c0\u67e5\u6839\u7ed3\u70b9，\u786e\u5b9a\u53c2\u8003\u503c\u3002<\/p>\n
\u7a7a\u6811\u76f4\u63a5\u8fd4\u56de true；\u6839\u7ed3\u70b9\u4e3a\u7ea2\u8272，\u76f4\u63a5\u8fd4\u56de false\u3002<\/p>\n
\u63a5\u7740\u4ece\u6839\u7ed3\u70b9\u5f00\u59cb，\u4e00\u76f4\u5f80\u5de6\u8d70，\u7edf\u8ba1\u8fd9\u6761\u8def\u5f84\u4e0a\u7684\u9ed1\u8272\u7ed3\u70b9\u6570\u91cf，\u8bb0\u4e3a refNum\u3002\u9009\u6700\u5de6\u4fa7\u8def\u5f84\u53ea\u662f\u56e0\u4e3a\u65b9\u4fbf，\u4efb\u610f\u4e00\u6761\u4ece\u6839\u5230\u7a7a\u7ed3\u70b9\u7684\u8def\u5f84\u90fd\u53ef\u4ee5\u4f5c\u4e3a\u53c2\u8003\u3002<\/p>\n<\/li>\n
Check()：\u7edf\u8ba1\u6bcf\u6761\u8def\u5f84\u4e0a\u7684\u9ed1\u8272\u7ed3\u70b9\u6570\u91cf\u3002<\/p>\n
blackNum \u8868\u793a\u5f53\u524d\u8def\u5f84\u4e0a\u5df2\u7ecf\u9047\u5230\u7684\u9ed1\u8272\u7ed3\u70b9\u6570\u91cf\u3002\u9047\u5230\u9ed1\u8272\u7ed3\u70b9，\u5c31\u6267\u884c blackNum++\u3002<\/p>\n
\u5f53 root == nullptr \u65f6，\u8bf4\u660e\u4e00\u6761\u8def\u5f84\u8d70\u5b8c\u4e86，\u6b64\u65f6\u6bd4\u8f83：<\/p>\n
refNum == blackNum<\/p>\n
\u76f8\u7b49，\u8bf4\u660e\u8fd9\u6761\u8def\u5f84\u7b26\u5408\u8981\u6c42；\u4e0d\u76f8\u7b49，\u8bf4\u660e\u4e0d\u540c\u8def\u5f84\u4e0a\u7684\u9ed1\u8272\u7ed3\u70b9\u6570\u91cf\u4e0d\u4e00\u81f4\u3002<\/p>\n
\u8fd9\u91cc\u6ca1\u6709\u628a\u7a7a\u7ed3\u70b9\u8ba1\u5165\u9ed1\u8272\u7ed3\u70b9\u6570\u91cf，\u4f46\u6bcf\u6761\u8def\u5f84\u90fd\u91c7\u7528\u76f8\u540c\u7684\u7edf\u8ba1\u65b9\u5f0f，\u56e0\u6b64\u4e0d\u5f71\u54cd\u6bd4\u8f83\u7ed3\u679c\u3002<\/p>\n<\/li>\n
\u9047\u5230\u7ea2\u8272\u7ed3\u70b9，\u68c0\u67e5\u5176\u7236\u4eb2\u7684\u989c\u8272\u3002<\/p>\n
if (root->_col == RED && root->_parent->_col == RED)<\/p>\n
\u5f53\u524d\u7ed3\u70b9\u548c\u7236\u4eb2\u90fd\u662f\u7ea2\u8272，\u5c31\u51fa\u73b0\u4e86\u8fde\u7eed\u7684\u7ea2\u8272\u7ed3\u70b9，\u8fd4\u56de false\u3002<\/p>\n
\u8fd9\u91cc\u4f9d\u8d56 IsBalance() \u5df2\u7ecf\u68c0\u67e5\u6839\u7ed3\u70b9\u4e3a\u9ed1\u8272\u3002 \u68c0\u67e5\u5230\u6839\u7ed3\u70b9\u65f6，&& \u5de6\u4fa7\u4e3a\u5047，\u53f3\u4fa7\u4e0d\u4f1a\u6267\u884c，\u56e0\u6b64\u4e0d\u4f1a\u8bbf\u95ee\u6839\u7ed3\u70b9\u7684\u7a7a\u7236\u6307\u9488\u3002<\/p>\n<\/li>\n
\u5de6\u53f3\u5b50\u6811\u90fd\u901a\u8fc7，\u5f53\u524d\u5b50\u6811\u624d\u901a\u8fc7\u3002<\/p>\n
return Check(root->_left, blackNum, refNum)
\n && Check(root->_right, blackNum, refNum);<\/p>\n
\u4efb\u610f\u4e00\u4fa7\u8fd4\u56de false，\u6574\u4f53\u5c31\u8fd4\u56de false\u3002<\/p>\n
blackNum \u6309\u503c\u4f20\u9012，\u5de6\u53f3\u9012\u5f52\u62ff\u5230\u7684\u662f\u5404\u81ea\u7684\u526f\u672c，\u6240\u4ee5\u5de6\u5b50\u6811\u5bf9\u8ba1\u6570\u7684\u4fee\u6539\u4e0d\u4f1a\u5f71\u54cd\u53f3\u5b50\u6811，\u4e5f\u4e0d\u9700\u8981\u5728\u9012\u5f52\u8fd4\u56de\u540e\u6267\u884c –blackNum\u3002<\/p>\n<\/li>\n
\u6700\u540e，\u5220\u9664\u8fd9\u4e2a\u90e8\u5206\u4f9d\u65e7\u4e0d\u8bb2，\u5982\u679c\u540e\u671f\u6211\u5b66\u4f1a\u4e86\u76f8\u5173\u7684\u64cd\u4f5c\u518d\u8003\u8651\u8981\u4e0d\u8981\u8865\u5145\u3002<\/p>\n<\/p>\n
\u603b\u7ed3：<\/p>\n
\u7ea2\u9ed1\u6811\u662f\u5728\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u57fa\u7840\u4e0a，\u901a\u8fc7\u989c\u8272\u89c4\u5219\u7ef4\u6301\u8fd1\u4f3c\u5e73\u8861\u7684\u6570\u636e\u7ed3\u6784，\u5176\u67e5\u627e\u3001\u63d2\u5165\u548c\u5220\u9664\u7684\u6700\u574f\u65f6\u95f4\u590d\u6742\u5ea6\u5747\u4e3a O(log N)\u3002\u63d2\u5165\u65f6，\u82e5\u51fa\u73b0\u8fde\u7eed\u7684\u7ea2\u8272\u7ed3\u70b9，\u5c31\u6839\u636e\u53d4\u53d4\u7ed3\u70b9\u7684\u989c\u8272\u53ca\u7ed3\u70b9\u7684\u4f4d\u7f6e，\u901a\u8fc7\u53d8\u8272\u3001\u5355\u65cb\u6216\u53cc\u65cb\u6062\u590d\u7ea2\u9ed1\u6811\u7684\u6027\u8d28\u3002\u9a8c\u8bc1\u65f6，\u5e94\u68c0\u67e5\u6839\u7ed3\u70b9\u4e3a\u9ed1\u8272\u3001\u4e0d\u5b58\u5728\u8fde\u7eed\u7ea2\u8272\u7ed3\u70b9，\u4ee5\u53ca\u5404\u6761\u4ece\u6839\u5230 NULL \u7684\u8def\u5f84\u4e0a\u9ed1\u8272\u7ed3\u70b9\u6570\u91cf\u76f8\u540c，\u4e0d\u80fd\u4ec5\u51ed\u6700\u957f\u8def\u5f84\u4e0d\u8d85\u8fc7\u6700\u77ed\u8def\u5f84\u7684\u4e24\u500d\u6765\u5224\u65ad\u3002<\/p><\/p>\n","protected":false},"excerpt":{"rendered":"
\u672c\u7bc7\u76ee\u6807:
\n1.\u638c\u63e1\u7ea2\u9ed1\u6811\u7684\u6982\u5ff5\u4e0e\u67d3\u8272\u8fc7\u7a0b2.\u5b66\u4f1a\u7ea2\u9ed1\u6811\u7684\u5b9e\u73b0\u6ce8\u610f：\u5b66\u4e60\u672c\u7247\u524d\u5fc5\u987b\u8981\u5b66\u4f1aAVL\u6811\u7684\u65cb\u8f6c\u3002\u4e00.\u7ea2\u9ed1\u6811\u7684\u6982\u5ff51.\u6982\u5ff5\u7ea2\u9ed1\u6811\u662f\u4e00\u68f5\u4e8c\u53c9\u641c\u7d22\u6811，\u4ed6\u7684\u6bcf\u4e2a\u7ed3\u70b9\u589e\u52a0\u2f00\u4e2a\u5b58\u50a8\u4f4d\u6765\u8868\u793a\u7ed3\u70b9\u7684\u989c\u8272，\u53ef\u4ee5\u662f\u7ea2\u8272\u6216\u8005\u9ed1\u8272\u3002 \u901a\u8fc7\u5bf9\u4efb\u4f55\u4e00\u6761\u4ece\u6839\u5230\u53f6\u5b50\u7684\u8def\u5f84\u4e0a\u5404\u4e2a\u7ed3\u70b9\u7684\u989c\u8272\u8fdb\u884c\u7ea6\u675f，\u7ea2\u9ed1\u6811\u786e\u4fdd\u6ca1\u6709\u2f00\u6761\u8def\u5f84\u4f1a\u6bd4\u5176\u4ed6\u8def\u5f84\u957f\u51fa2\u500d，\u56e0\u800c\u662f\u63a5\u8fd1\u5e73\u8861\u7684\u3002\u5982\u56fe：2.\u89c4\u5219\u4e00\u68f5\u7ea2\u9ed1\u6811\u5fc5\u987b\u8981\u6ee1\u8db3\u4ee5\u4e0b\u7684\u89c4\u5219:.\u6bcf\u4e2a\u7ed3<\/p>\n","protected":false},"author":2,"featured_media":120494,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[9139,55,1813,427],"topic":[],"class_list":["post-120508","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-server","tag-9139","tag-c","tag-1813","tag-427"],"yoast_head":"\n