\n
1.\u7ea2\u9ed1\u6811\u7684\u89c4\u5219：<\/h3>\n
\u8bf4\u660e：\u300a\u7b97\u6cd5\u5bfc\u8bba\u300b\u7b49\u4e66\u7c4d\u4e0a\u8865\u5145\u4e86\u2f00\u6761\u6bcf\u4e2a\u53f6\u2f26\u7ed3\u70b9(NIL)\u90fd\u662f\u2fca\u2f8a\u7684\u89c4\u5219\u3002\u4ed6\u8fd9\u2fa5\u6240\u6307\u7684\u53f6\u2f26\u7ed3\u70b9\u4e0d\u662f\u4f20\u7edf\u7684\u610f\u4e49\u4e0a\u7684\u53f6\u2f26\u7ed3\u70b9，\u2f7d\u662f\u6211\u4eec\u8bf4\u7684\u7a7a\u7ed3\u70b9，\u6709\u4e9b\u4e66\u7c4d\u4e0a\u4e5f\u628aNIL\u53eb\u505a\u5916\u90e8\u7ed3\u70b9\u3002NIL\u662f\u4e3a\u4e86\u2f45\u4fbf\u51c6\u786e\u7684\u6807\u8bc6\u51fa\u6240\u6709\u8def\u5f84，\u300a\u7b97\u6cd5\u5bfc\u8bba\u300b\u5728\u540e\u7eed\u8bb2\u89e3\u5b9e\u73b0\u7684\u7ec6\u8282\u4e2d\u4e5f\u5ffd\u7565\u4e86NIL\u7ed3\u70b9，\u6240\u4ee5\u6211\u4eec\u77e5\u9053\u2f00\u4e0b\u8fd9\u4e2a\u6982\u5ff5\u5373\u53ef\u3002<\/p>\n
\u7b80\u5355\u56fe\u793a\u4e00\u4e0b：<\/p>\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260827083241-6a8ff629459b5.png\")
<\/p>\n
2.\u8865\u5145\u95ee\u9898<\/h3>\n
1.\u4e3a\u4ec0\u4e48\u5b83\u7684\u6839\u8282\u70b9\u662f\u9ed1\u8272\u7684，\u4e0d\u662f\u7ea2\u8272\u7684？<\/p>\n<\/p>\n
\u7b54：\u5176\u5b9e\u4e0d\u662f\u5fc5\u987b，\u662f\u89c4\u5b9a\u6210\u9ed1\u8272\u66f4\u7701\u4e8b<\/span>\u3002<\/p>\n \u7ea2\u9ed1\u6811\u672c\u8eab\u6ca1\u6709\u89c4\u5b9a\u6839\u5fc5\u987b\u662f\u9ed1\u7684，\u5b83\u53ea\u89c4\u5b9a\u4e86\u6bcf\u6761\u8def\u5f84\u4e0a\u7684\u9ed1\u8272\u8282\u70b9\u6570\u91cf\u8981\u4e00\u6837\u3002\u8fd9\u4e2a\u89c4\u5219\u8db3\u591f\u4fdd\u8bc1\u6811\u7684\u5927\u81f4\u5e73\u8861\u3002\u95ee\u9898\u51fa\u5728\u5b9e\u73b0\u4e0a\u3002\u5982\u679c\u6839\u662f\u7ea2\u7684，\u63d2\u5165\u5220\u9664\u7684\u65f6\u5019，\u4f60\u603b\u5f97\u989d\u5916\u60f3\u4e00\u4e0b：\u201c\u54ce，\u8fd9\u4e2a\u6839\u662f\u4e0d\u662f\u7ea2\u7684？\u8981\u4e0d\u8981\u7ed9\u5b83\u6539\u6210\u9ed1\u7684？\u201d\u6539\u6765\u6539\u53bb\u5f88\u70e6\u3002<\/p>\n \u6240\u4ee5\u5e72\u8106\u4e00\u5f00\u59cb\u5c31\u628a\u6839\u5b9a\u6210\u9ed1\u7684，\u7701\u5f97\u6bcf\u6b21\u90fd\u8981\u5904\u7406\u8fd9\u4e2a\u7279\u6b8a\u60c5\u51b5\u3002\u4ee3\u7801\u5199\u8d77\u6765\u5c11\u4e00\u4e2a\u5206\u652f，\u8111\u5b50\u5c11\u60f3\u4e00\u4ef6\u4e8b\u3002\u8bf4\u767d\u4e86，\u4e0d\u662f\u6280\u672f\u4e0a\u7684\u5fc5\u987b，\u662f\u8bbe\u8ba1\u4e0a\u7684\u65b9\u4fbf<\/span>\u3002\u89c4\u5219\u7edf\u4e00\u4e86，\u5b9e\u73b0\u5c31\u7b80\u5355\u4e86\u3002<\/p>\n 2.\u601d\u8003\u2f00\u4e0b，\u7ea2\u2fca\u6811\u5982\u4f55\u786e\u4fdd\u6700\u957f\u8def\u5f84\u4e0d\u8d85\u8fc7\u6700\u77ed\u8def\u5f84\u76842\u500d\u7684？<\/p>\n \u2022 \u7531\u89c4\u52194\u53ef\u77e5，\u4ece\u6839\u5230NULL\u7ed3\u70b9\u7684\u6bcf\u6761\u8def\u5f84\u90fd\u6709\u76f8\u540c\u6570\u91cf\u7684\u2fca\u2f8a\u7ed3\u70b9，\u6240\u4ee5\u6781\u7aef\u573a\u666f\u4e0b，\u6700\u77ed\u8def\u5f84\u5c31\u662f\u5168\u662f\u9ed1\u8272\u7ed3\u70b9\u7684\u8def\u5f84，\u5047\u8bbe\u6700\u77ed\u8def\u5f84\u957f\u5ea6\u4e3abh(black height)\u3002 \u5047\u8bbeN\u662f\u7ea2\u2fca\u6811\u6811\u4e2d\u7ed3\u70b9\u6570\u91cf，h\u6700\u77ed\u8def\u5f84\u7684\u2ed3\u5ea6，\u90a3\u4e48 2^h\u00a0\u22121, \u7531\u6b64\u63a8\u51fah 1 <= N < 2^2h-1<\/span>\u7531\u6b64\u63a8\u51fah \u2248 logN <\/span>，\u4e5f\u5c31\u662f\u610f\u5473\u7740\u7ea2\u2fca\u6811\u589e\u5220\u67e5\u6539\u6700\u574f\u4e5f\u5c31\u662f\u2f9b\u6700\u2ed3\u8def\u5f84 2 \u2217 logN ，\u90a3\u4e48\u65f6\u95f4\u590d\u6742\u5ea6\u8fd8\u662fO(logN)<\/p>\n \u7ea2\u2fca\u6811\u7684\u8868\u8fbe\u76f8\u5bf9AVL\u6811\u8981\u62bd\u8c61\u2f00\u4e9b，AVL\u6811\u901a\u8fc7\u2fbc\u5ea6\u5dee\u76f4\u89c2\u7684\u63a7\u5236\u4e86\u5e73\u8861\u3002\u7ea2\u2fca\u6811\u901a\u8fc74\u6761\u89c4\u5219\u7684\u989c\u2f8a\u7ea6\u675f，\u95f4\u63a5\u7684\u5b9e\u73b0\u4e86\u8fd1\u4f3c\u5e73\u8861，\u4ed6\u4eec\u6548\u7387\u90fd\u662f\u540c\u2f00\u6863\u6b21，\u4f46\u662f\u76f8\u5bf9\u2f7d\u2f94，\u63d2\u2f0a\u76f8\u540c\u6570\u91cf\u7684\u7ed3\u70b9，\u7ea2\u2fca\u6811\u7684\u65cb\u8f6c\u6b21\u6570\u662f\u66f4\u5c11\u7684，\u56e0\u4e3a\u4ed6\u5bf9\u5e73\u8861\u7684\u63a7\u5236\u6ca1\u90a3\u4e48\u4e25\u683c\u3002<\/p>\n \u7ea2\u9ed1\u6811\u672c\u8eab\u4e0d\u5173\u5fc3\u4f60\u5b58\u7684\u662f\u4ec0\u4e48，\u5b83\u53ea\u7ba1\u628a\u00a0T\u5f53\u4f5c\u4e00\u4e2a\u6574\u4f53\u5b58\u5230\u8282\u70b9\u91cc\u3002\u81f3\u4e8e\u00a0T\u00a0\u662f\u4ec0\u4e48，\u7531\u4e0a\u5c42\u5bb9\u5668\u6765\u51b3\u5b9a：<\/p>\n set\u00a0\u7ed9\u7ea2\u9ed1\u6811\u4f20\u7684\u662f\u00a0Key<\/span>，\u6240\u4ee5\u7ea2\u9ed1\u6811\u91cc\u5b58\u7684\u5c31\u662f\u952e\u503c\u672c\u8eab<\/p>\n<\/li>\n map\u00a0\u7ed9\u7ea2\u9ed1\u6811\u4f20\u7684\u662f\u00a0pair<const Key, V><\/span>，\u6240\u4ee5\u7ea2\u9ed1\u6811\u91cc\u5b58\u7684\u5c31\u662f\u952e\u503c\u5bf9，\u5176\u4e2d\u00a0Key\u00a0\u5e26\u00a0const\u00a0\u662f\u9632\u6b62\u952e\u88ab\u4fee\u6539<\/span><\/p>\n<\/li>\n<\/ul>\n \u6240\u4ee5\u7ea2\u9ed1\u6811\u5c31\u50cf\u4e2a\u901a\u7528\u7684\u67b6\u5b50，set\u00a0\u548c\u00a0map\u00a0\u53ea\u662f\u5f80\u8fd9\u4e2a\u67b6\u5b50\u4e0a\u653e\u4e86\u4e0d\u540c\u7c7b\u578b\u7684\u4e1c\u897f\u3002<\/p>\n \/\/ \u989c\u8272\u679a\u4e3e \/\/ \u7ea2\u9ed1\u6811\u8282\u70b9\u7ed3\u6784\u4f53 \/\/\u6570\u636e\u57df \/\/\u989c\u8272\u6807\u8bb0\u8272，\u7ea2\u6216\u9ed1 \/\/\u6784\u9020\u51fd\u6570 \u5b9a\u4e49\u7ea2\u9ed1\u6811\u7ed3\u6784（KV）<\/p>\n \u7ea2\u9ed1\u6811\u4f5c\u4e3a\u4e00\u4e2a\u5e95\u5c42\u5bb9\u5668，\u9700\u8981\u540c\u65f6\u652f\u6301 set \u548c map \u4e24\u79cd\u4e0a\u5c42\u5bb9\u5668\u3002\u4f46\u95ee\u9898\u662f，set \u5b58\u7684\u662f Key，map \u5b58\u7684\u662f pair<const Key, V>，\u4e24\u8005\u5728\u63d2\u5165\u65f6\u6bd4\u8f83\u6570\u636e\u7684\u65b9\u5f0f\u4e0d\u540c\u3002\u5982\u679c\u7ea2\u9ed1\u6811\u5199\u6b7b\u4e86\u6bd4\u8f83\u65b9\u5f0f，\u5c31\u53ea\u80fd\u9002\u914d\u4e00\u79cd\u5bb9\u5668，\u6ca1\u6cd5\u901a\u7528\u3002<\/p>\n \u6539\u9020\u4e4b\u524d\u7684\u4ee3\u7801：<\/p>\n \/\/ \u7ea2\u9ed1\u6811\u7c7b\u6a21\u677f public: \/\/ \u63d2\u5165\u8282\u70b9：\u5c06\u6570\u636e\u63d2\u5165\u5230\u7ea2\u9ed1\u6811\u4e2d，\u5e76\u4fdd\u6301\u7ea2\u9ed1\u6811\u7684\u6027\u8d28 \/\/ … \u5176\u4ed6\u63a5\u53e3（\u67e5\u627e\u3001\u5220\u9664\u3001\u4e2d\u5e8f\u904d\u5386\u7b49）<\/p>\n private: \u5728\u7ea2\u9ed1\u6811\u7684\u63d2\u5165\u8282\u70b9\u63a5\u53e3\u4e2d\u8981\u5148\u901a\u8fc7\u6bd4\u8f83\u8282\u70b9\u4e2d\u6570\u636e\u7684\u5927\u5c0f\u6765\u67e5\u627e\u9002\u5408\u63d2\u5165\u7684\u4f4d\u7f6e<\/span>，\u4f46\u662f\u7ea2\u9ed1\u6811\u5e76\u4e0d\u77e5\u9053\u6570\u636e data \u5230\u5e95\u662f key \u8fd8\u662f pair，\u6ca1\u6709\u529e\u6cd5\u786e\u5b9a\u3002\u5047\u8bbe\u6570\u636e data \u662f key<\/span>，\u90a3\u4e48\u76f4\u63a5\u53d6 key <\/span>\u6765\u4f5c\u6bd4\u8f83；\u5982\u679c\u6570\u636e data \u662f pair，\u5219\u9700\u8981\u53d6 first <\/span>\u6765\u4f5c\u6bd4\u8f83\u3002<\/p>\n \u90a3\u5982\u4f55\u89e3\u51b3\u5462？STL\u6e90\u7801\u7ed9\u51fa\u4e86\u8fd9\u6837\u7684\u7ed3\u679c：\u901a\u8fc7\u4f20\u7ed9\u6a21\u677f\u53c2\u6570 KeyOfValue \u7684\u662f set \u7684\u4eff\u51fd\u6570\u8fd8\u662f map \u7684\u4eff\u51fd\u6570\u6765\u5e94\u5bf9\u4e0d\u540c\u7c7b\u578b\u6570\u636e\u7684\u6bd4\u8f83：<\/span><\/p>\n \u63a5\u7740\u770b\u6539\u9020\u4e4b\u540e\u7684\u4ee3\u7801：<\/p>\n<\/p>\n \u7ea2\u9ed1\u6811\u53ea\u8d1f\u8d23\u5b58\u6570\u636e\u548c\u7ef4\u62a4\u5e73\u8861，\u4f46\u5b83\u4e0d\u77e5\u9053\u4e0a\u5c42\u4f20\u8fdb\u6765\u7684\u662f\u4ec0\u4e48\u7c7b\u578b\u7684\u6570\u636e\u3002\u6bd4\u8f83\u7684\u65f6\u5019，\u5982\u679c\u662f\u00a0set，\u76f4\u63a5\u6bd4\u8f83\u00a0Key\u00a0\u5c31\u884c；\u5982\u679c\u662f\u00a0map，\u9700\u8981\u53d6\u00a0pair\u00a0\u7684\u00a0first\u00a0\u6765\u6bd4\u8f83\u3002<\/p>\n \u4e3a\u4e86\u8ba9\u7ea2\u9ed1\u6811\u80fd\u7edf\u4e00\u5904\u7406\u8fd9\u4e24\u79cd\u60c5\u51b5，\u7ed9\u5b83\u589e\u52a0\u4e86\u4e00\u4e2a\u6a21\u677f\u53c2\u6570\u00a0KeyOfT，\u5b83\u662f\u4e00\u4e2a\u4eff\u51fd\u6570\u7c7b，\u7531\u00a0set\u00a0\u548c\u00a0map\u00a0\u5404\u81ea\u5b9e\u73b0\u5e76\u4f20\u8fdb\u6765<\/span><\/span>：<\/p>\n \u6709\u4e86\u8fd9\u4e2a\u4eff\u51fd\u6570，\u7ea2\u9ed1\u6811\u5728\u63d2\u5165\u65f6\u5c31\u4e0d\u7528\u5173\u5fc3\u00a0T\u00a0\u5230\u5e95\u662f\u4ec0\u4e48\u7c7b\u578b\u4e86，\u53ea\u9700\u8981\u8c03\u7528\u00a0KeyOfT\u00a0\u4ece\u6570\u636e\u4e2d\u53d6\u51fa\u952e\u503c\u6765\u6bd4\u8f83\u5373\u53ef\u3002<\/p>\n \u65b0\u7684\u7ea2\u9ed1\u6811\u7684\u5b9a\u4e49：<\/p>\n \/\/ \u7ea2\u9ed1\u6811\u7c7b\u6a21\u677f（\u6539\u9020\u540e） public: \/\/ \u63d2\u5165\u8282\u70b9 \/\/ …..\u5176\u4ed6\u63a5\u53e3\u8fed\u4ee3\u5668\u3001\u67e5\u627e\u3001\u5220\u9664\u3001operator[] \u7b49）<\/p>\n private: \u56fe\u793a\u58f0\u660e：<\/p>\n \u6211\u4eec\u901a\u8fc7 T \u7684\u7c7b\u578b\u548c\u5bf9\u5e94\u7684\u53d6 T \u7c7b\u578b\u5bf9\u8c61\u7684\u503c\u7684\u4eff\u51fd\u6570<\/span>，\u5c31\u53ef\u4ee5\u8fdb\u884c\u4e0d\u540c\u7c7b\u578b\u6570\u636e\u7684\u6bd4\u8f83\u4e86：<\/p>\n 1. \u63d2\u2f0a\u2f00\u4e2a\u503c\u6309\u2f06\u53c9\u641c\u7d22\u6811\u89c4\u5219\u8fdb\u2f8f\u63d2\u2f0a，\u63d2\u2f0a\u540e\u6211\u4eec\u53ea\u9700\u8981\u89c2\u5bdf\u662f\u5426\u7b26\u5408\u7ea2\u2fca\u6811\u76844\u6761\u89c4\u5219\u3002 \u8bf4\u660e：\u4e0b\u56fe\u4e2d\u5047\u8bbe\u6211\u4eec\u628a\u65b0\u589e\u7ed3\u70b9\u6807\u8bc6\u4e3ac (cur)，c\u7684\u2f57\u4eb2\u6807\u8bc6\u4e3ap(parent)，p\u7684\u2f57\u4eb2\u6807\u8bc6\u4e3a c\u4e3a\u7ea2，p\u4e3a\u7ea2，g\u4e3a\u2fca，u\u5b58\u5728\u4e14\u4e3a\u7ea2，\u5219\u5c06p\u548cu\u53d8\u2fca，g\u53d8\u7ea2\u3002\u5728\u628ag\u5f53\u505a\u65b0\u7684c，\u7ee7\u7eed\u5f80\u4e0a\u66f4\u65b0\u3002 \u56fe0：<\/p>\n \u56fe1：<\/p>\n \u56fe2：<\/p>\n \u56fe3：<\/p>\n \u56fe4：<\/p>\n c\u4e3a\u7ea2，p\u4e3a\u7ea2，g\u4e3a\u2fca，u\u4e0d\u5b58\u5728\u6216\u8005u\u5b58\u5728\u4e14\u4e3a\u2fca，u\u4e0d\u5b58\u5728，\u5219c\u2f00\u5b9a\u662f\u65b0\u589e\u7ed3\u70b9，u\u5b58\u5728\u4e14\u4e3a\u2fca，\u5219c\u2f00\u5b9a\u4e0d\u662f\u65b0\u589e，c\u4e4b\u524d\u662f\u2fca\u2f8a\u7684，\u662f\u5728c\u7684\u2f26\u6811\u4e2d\u63d2\u2f0a，\u7b26\u5408\u60c5\u51b51，\u53d8\u2f8a\u5c06c\u4ece\u2fca\u2f8a\u53d8\u6210\u7ea2\u2f8a，\u66f4\u65b0\u4e0a\u6765\u7684\u3002<\/p>\n \u5206\u6790：p\u5fc5\u987b\u53d8\u2fca，\u624d\u80fd\u89e3\u51b3，\u8fde\u7eed\u7ea2\u2f8a\u7ed3\u70b9\u7684\u95ee\u9898，u\u4e0d\u5b58\u5728\u6216\u8005\u662f\u2fca\u2f8a\u7684，\u8fd9\u2fa5\u5355\u7eaf\u7684\u53d8\u2f8a\u2f46\u6cd5\u89e3\u51b3\u95ee\u9898，\u9700\u8981\u65cb\u8f6c+\u53d8\u2f8a\u3002<\/p>\n \u5982\u679cp\u662fg\u7684\u5de6，c\u662fp\u7684\u5de6，\u90a3\u4e48\u4ee5g\u4e3a\u65cb\u8f6c\u70b9\u8fdb\u2f8f\u53f3\u5355\u65cb，\u518d\u628ap\u53d8\u2fca，g\u53d8\u7ea2\u5373\u53ef\u3002p\u53d8\u6210\u8bfe\u8fd9\u9897\u6811\u65b0\u7684\u6839，\u8fd9\u6837\u2f26\u6811\u2fca\u2f8a\u7ed3\u70b9\u7684\u6570\u91cf\u4e0d\u53d8，\u6ca1\u6709\u8fde\u7eed\u7684\u7ea2\u2f8a\u7ed3\u70b9\u4e86，\u4e14\u4e0d\u9700\u8981\u5f80\u4e0a\u66f4\u65b0，\u56e0\u4e3ap\u7684\u2f57\u4eb2\u662f\u2fca\u2f8a\u8fd8\u662f\u7ea2\u2f8a\u6216\u8005\u7a7a\u90fd\u4e0d\u8fdd\u53cd\u89c4\u5219\u3002<\/p>\n \u5982\u679cp\u662fg\u7684\u53f3，c\u662fp\u7684\u53f3，\u90a3\u4e48\u4ee5g\u4e3a\u65cb\u8f6c\u70b9\u8fdb\u2f8f\u5de6\u5355\u65cb，\u518d\u628ap\u53d8\u2fca，g\u53d8\u7ea2\u5373\u53ef\u3002p\u53d8\u6210\u8bfe\u8fd9\u9897\u6811\u65b0\u7684\u6839，\u8fd9\u6837\u2f26\u6811\u2fca\u2f8a\u7ed3\u70b9\u7684\u6570\u91cf\u4e0d\u53d8，\u6ca1\u6709\u8fde\u7eed\u7684\u7ea2\u2f8a\u7ed3\u70b9\u4e86，\u4e14\u4e0d\u9700\u8981\u5f80\u4e0a\u66f4\u65b0，\u56e0\u4e3ap\u7684\u2f57\u4eb2\u662f\u2fca\u2f8a\u8fd8\u662f\u7ea2\u2f8a\u6216\u8005\u7a7a\u90fd\u4e0d\u8fdd\u53cd\u89c4\u5219\u3002<\/p>\n c\u4e3a\u7ea2，p\u4e3a\u7ea2，g\u4e3a\u2fca，u\u4e0d\u5b58\u5728\u6216\u8005u\u5b58\u5728\u4e14\u4e3a\u2fca，u\u4e0d\u5b58\u5728，\u5219c\u2f00\u5b9a\u662f\u65b0\u589e\u7ed3\u70b9，u\u5b58\u5728\u4e14\u4e3a\u2fca，\u5219c\u2f00\u5b9a\u4e0d\u662f\u65b0\u589e，c\u4e4b\u524d\u662f\u2fca\u2f8a\u7684，\u662f\u5728c\u7684\u2f26\u6811\u4e2d\u63d2\u2f0a，\u7b26\u5408\u60c5\u51b51，\u53d8\u2f8a\u5c06c\u4ece\u2fca\u2f8a\u53d8\u6210\u7ea2\u2f8a，\u66f4\u65b0\u4e0a\u6765\u7684\u3002<\/p>\n \u5206\u6790：p\u5fc5\u987b\u53d8\u2fca，\u624d\u80fd\u89e3\u51b3，\u8fde\u7eed\u7ea2\u2f8a\u7ed3\u70b9\u7684\u95ee\u9898，u\u4e0d\u5b58\u5728\u6216\u8005\u662f\u2fca\u2f8a\u7684，\u8fd9\u2fa5\u5355\u7eaf\u7684\u53d8\u2f8a\u2f46\u6cd5\u89e3\u51b3\u95ee\u9898，\u9700\u8981\u65cb\u8f6c+\u53d8\u2f8a\u3002<\/p>\n \u5982\u679cp\u662fg\u7684\u5de6，c\u662fp\u7684\u53f3，\u90a3\u4e48\u5148\u4ee5p\u4e3a\u65cb\u8f6c\u70b9\u8fdb\u2f8f\u5de6\u5355\u65cb，\u518d\u4ee5g\u4e3a\u65cb\u8f6c\u70b9\u8fdb\u2f8f\u53f3\u5355\u65cb，\u518d\u628ac\u53d8\u2fca，g\u53d8\u7ea2\u5373\u53ef\u3002c\u53d8\u6210\u8bfe\u8fd9\u9897\u6811\u65b0\u7684\u6839，\u8fd9\u6837\u2f26\u6811\u2fca\u2f8a\u7ed3\u70b9\u7684\u6570\u91cf\u4e0d\u53d8，\u6ca1\u6709\u8fde\u7eed\u7684\u7ea2\u2f8a\u7ed3\u70b9\u4e86，\u4e14\u4e0d\u9700\u8981\u5f80\u4e0a\u66f4\u65b0，\u56e0\u4e3ac\u7684\u2f57\u4eb2\u662f\u2fca\u2f8a\u8fd8\u662f\u7ea2\u2f8a\u6216\u8005\u7a7a\u90fd\u4e0d\u8fdd\u53cd\u89c4\u5219\u3002<\/p>\n \u5982\u679cp\u662fg\u7684\u53f3，c\u662fp\u7684\u5de6，\u90a3\u4e48\u5148\u4ee5p\u4e3a\u65cb\u8f6c\u70b9\u8fdb\u2f8f\u53f3\u5355\u65cb，\u518d\u4ee5g\u4e3a\u65cb\u8f6c\u70b9\u8fdb\u2f8f\u5de6\u5355\u65cb，\u518d\u628ac\u53d8 \/\/ \u7ea2\u9ed1\u6811\u63d2\u5165 bool Insert(const pair<K, V>& kv) \/\/ \u7b2c2\u6b65：\u67e5\u627e\u63d2\u5165\u4f4d\u7f6e while (cur) \/\/\u7b2c3\u6b65：\u63d2\u5165\u65b0\u8282\u70b9 \/\/ \u8fde\u63a5\u7236\u8282\u70b9 \/\/\u7b2c4\u6b65：\u8c03\u6574\u5e73\u8861 \/\/\u60c5\u51b5\u4e00：\u7236\u8282\u70b9\u662f\u7956\u7236\u7684\u5de6\u5b69\u5b50 if (parent == grandfather->_left) \/\/ \u5b50\u60c5\u51b51：\u53d4\u53d4\u5b58\u5728\u4e14\u4e3a\u7ea2\u8272 \u2192 \u53d8\u8272\u5373\u53ef \/\/\u60c5\u51b5\u4e8c：\u7236\u8282\u70b9\u662f\u7956\u7236\u7684\u53f3\u5b69\u5b50（\u5bf9\u79f0 else \/\/ \u5b50\u60c5\u51b51：\u53d4\u53d4\u5b58\u5728\u4e14\u4e3a\u7ea2\u8272 \u2192 \u53d8\u8272\u5373\u53ef \/\/ \u7b2c5\u6b65：\u4fdd\u8bc1\u6839\u8282\u70b9\u662f\u9ed1\u8272 \u6309\u2f06\u53c9\u641c\u7d22\u6811\u903b\u8f91\u5b9e\u73b0\u5373\u53ef，\u641c\u7d22\u6548\u7387\u4e3a O(logN)<\/p>\n \/\/ \u67e5\u627e\u51fd\u6570：\u6839\u636e\u952e\u503c key \u5728\u7ea2\u9ed1\u6811\u4e2d\u67e5\u627e\u5bf9\u5e94\u7684\u8282\u70b9 Node* Find(const K& key) while (cur) \/\/ \u53ea\u8981\u5f53\u524d\u8282\u70b9\u4e0d\u4e3a\u7a7a，\u7ee7\u7eed\u67e5\u627e return nullptr; \/\/ \u904d\u5386\u5b8c\u8fd8\u6ca1\u627e\u5230，\u8fd4\u56de\u7a7a\u6307\u9488 \u8fd9\u2fa5\u83b7\u53d6\u6700\u2ed3\u8def\u5f84\u548c\u6700\u77ed\u8def\u5f84，\u68c0\u67e5\u6700\u2ed3\u8def\u5f84\u4e0d\u8d85\u8fc7\u6700\u77ed\u8def\u5f84\u76842\u500d\u662f\u4e0d\u53ef\u2f8f\u7684，\u56e0\u4e3a\u5c31\u7b97\u6ee1\u2f9c\u8fd9\u4e2a\u6761\u4ef6，\u7ea2\u2fca\u6811\u4e5f\u53ef\u80fd\u989c\u2f8a\u4e0d\u6ee1\u2f9c\u89c4\u5219，\u5f53\u524d\u6682\u65f6\u6ca1\u51fa\u95ee\u9898，\u540e\u7eed\u7ee7\u7eed\u63d2\u2f0a\u8fd8\u662f\u4f1a\u51fa\u95ee\u9898\u7684\u3002\u6240\u4ee5\u6211\u4eec\u8fd8\u662f\u53bb\u68c0\u67e54\u70b9\u89c4\u5219，\u6ee1\u2f9c\u8fd94\u70b9\u89c4\u5219，\u2f00\u5b9a\u80fd\u4fdd\u8bc1\u6700\u2ed3\u8def\u5f84\u4e0d\u8d85\u8fc7\u6700\u77ed\u8def\u5f84\u76842\u500d\u3002<\/p>\n \u8fd9\u6bb5\u4ee3\u7801\u7528\u4e8e\u9a8c\u8bc1\u4e00\u68f5\u6811\u662f\u5426\u6ee1\u8db3\u7ea2\u9ed1\u6811\u7684\u6027\u8d28<\/span><\/span>，\u4e3b\u8981\u68c0\u67e5\u4e09\u6761：<\/p>\n \u6839\u8282\u70b9\u662f\u9ed1\u8272\u7684；<\/p>\n \u6ca1\u6709\u8fde\u7eed\u7684\u7ea2\u8272\u8282\u70b9；<\/p>\n \u6240\u6709\u8def\u5f84\u4e0a\u7684\u9ed1\u8272\u8282\u70b9\u6570\u91cf\u76f8\u540c\u3002<\/p>\n IsBalance —-\u00a0\u00a0\u5165\u53e3\u51fd\u6570<\/p>\n bool IsBalance() \/\/ \u89c4\u52191：\u6839\u8282\u70b9\u5fc5\u987b\u662f\u9ed1\u8272 \/\/\u8ba1\u7b97\u53c2\u8003\u503c refNum \/\/ \u9012\u5f52\u68c0\u67e5\u6bcf\u6761\u8def\u5f84 \u901a\u4fd7\u7406\u89e3：\u5148\u7b97\u51fa\u6807\u51c6\u7b54\u6848（\u6700\u5de6\u8def\u5f84\u6709\u591a\u5c11\u4e2a\u9ed1\u8272\u8282\u70b9），\u7136\u540e\u62ff\u7740\u8fd9\u4e2a\u6807\u51c6\u53bb\u68c0\u67e5\u6bcf\u4e00\u6761\u8def\u5f84\u662f\u5426\u4e00\u81f4\u3002<\/p>\n Check —-\u00a0\u9012\u5f52\u68c0\u67e5\u51fd\u6570<\/p>\n bool Check(Node* root, int blackNum, const int refNum) \/\/2. \u68c0\u67e5\u8fde\u7eed\u7ea2\u8272\u8282\u70b9 \/\/3. \u7edf\u8ba1\u9ed1\u8272\u8282\u70b9 \/\/4. \u9012\u5f52\u68c0\u67e5\u5de6\u53f3\u5b50\u6811 \u7ea2\u2fca\u6811\u7684\u5220\u9664\u6bd4\u8f83\u590d\u6742，\u638c\u63e1\u7ea2\u9ed1\u6811\u7684\u5dee\u8ddd\u5df2\u7ecf\u8db3\u591f\u4e86，\u672c\u8282\u4e0d\u505a\u8bb2\u89e3，\u6709\u5174\u8da3\u7684\u8bdd\u53ef\u53c2\u8003：\u300a\u7b97\u6cd5\u5bfc\u8bba\u300b\u6216\u8005\u300aSTL\u6e90\u7801\u5256\u6790\u300b\u4e2d\u8bb2\u89e3\u3002<\/p>\n \u4e0b\u9762\u7684\u4ee3\u7801\u8fd9\u662f\u4e00\u68f5\u624b\u5199\u7684\u7ea2\u9ed1\u6811，\u4e13\u95e8\u7ed9 set \u548c map \u5f53\u5e95\u5c42\u6846\u67b6\u7528\u7684，\u56e0\u4e3a\u4e3a\u4e86\u6a21\u62df\u5b9e\u73b0map\u548cset(\u91cc\u9762\u7684\u547d\u540d\u6211\u505a\u4e86\u5927\u81f4\u4fee\u6539\u65b9\u4fbf\u540e\u7eed\u5b66\u4e60）\u3002<\/p>\n #pragma once \/\/ \u7ea2\u9ed1\u6811\u8282\u70b9 T _data; \/\/ \u6570\u636e\u57df（set\u5b58Key，map\u5b58pair） RBTreeNode(const T& data) \/\/ \u7ea2\u9ed1\u6811\u8fed\u4ee3\u5668 template<class T, class Ref, class Ptr> __RBTreeIterator(Node* node = nullptr) \/\/ \u5e26\u9ed8\u8ba4\u503c，\u65b9\u4fbf\u6784\u9020end() \/\/ ========== \u89e3\u5f15\u7528\u64cd\u4f5c ========== Ptr operator->() \/\/\u6bd4\u8f83\u64cd\u4f5c bool operator==(const Self& s) const \/\/ \u524d\u7f6e++：\u4e2d\u5e8f\u540e\u7ee7（\u4e0b\u4e00\u4e2a\u8282\u70b9） \/\/ \u524d\u7f6e–：\u4e2d\u5e8f\u524d\u9a71（\u4e0a\u4e00\u4e2a\u8282\u70b9） \/\/ \u7ea2\u9ed1\u6811\u672c\u4f53 public: \/\/ begin：\u8fd4\u56de\u6700\u5de6\u8282\u70b9（\u6700\u5c0f\u503c） \/\/ end：\u8fd4\u56denullptr（\u7ed3\u675f\u6807\u5fd7） \/\/ \u63d2\u5165\u51fd\u6570 \u2014\u2014 \u6838\u5fc3 \/\/\u6811\u4e3a\u7a7a \/\/ \u627e\u63d2\u5165\u4f4d\u7f6e \/\/ \u63d2\u5165\u65b0\u8282\u70b9 if (kot(parent->_data) < kot(data)) \/\/ \u8c03\u6574\u5e73\u8861（\u6838\u5fc3\u96be\u70b9） \/\/ \u60c5\u51b5A：\u7236\u8282\u70b9\u662f\u7237\u7237\u7684\u5de6\u5b69\u5b50 \/\/ \u60c5\u51b51：\u53d4\u53d4\u5b58\u5728\u4e14\u4e3a\u7ea2\u8272 \u2192 \u53d8\u8272，\u7ee7\u7eed\u5f80\u4e0a\u5904\u7406 \/\/ \u60c5\u51b51：\u53d4\u53d4\u5b58\u5728\u4e14\u4e3a\u7ea2\u8272 –> \u53d8\u8272，\u7ee7\u7eed\u5f80\u4e0a\u5904\u7406 \/\/\u6700\u540e\u4fdd\u8bc1\u6839\u8282\u70b9\u662f\u9ed1\u8272 \/\/ \u4e2d\u5e8f\u904d\u5386：\u5de6–>\u6839–>\u53f3，\u5f97\u5230\u6709\u5e8f\u5e8f\u5217 void InOrder() \/\/ \u9a8c\u8bc1\u7ea2\u9ed1\u6811\u662f\u5426\u5408\u6cd5 \/\/ \u89c4\u52191：\u6839\u5fc5\u987b\u662f\u9ed1\u8272 \/\/ benchmark：\u6700\u5de6\u8def\u5f84\u4e0a\u7684\u9ed1\u8272\u8282\u70b9\u6570\u91cf（\u4f5c\u4e3a\u6807\u51c6\u503c） private:<\/p>\n \/\/ PrevCheck：\u9012\u5f52\u68c0\u67e5\u6bcf\u6761\u8def\u5f84 bool PrevCheck(Node* root, int blackNum, int& benchmark) \/\/\u7edf\u8ba1\u9ed1\u8272\u8282\u70b9 \/\/ \u89c4\u52192：\u4e0d\u80fd\u6709\u8fde\u7eed\u7ea2\u8272\u8282\u70b9 \/\/ \u9012\u5f52\u68c0\u67e5\u5de6\u53f3\u5b50\u6811 \/\/ \u4e2d\u5e8f\u904d\u5386\u9012\u5f52\u5b9e\u73b0 \/\/ \u5de6\u5355\u65cb \/\/ subRL \u4ea4\u7ed9 parent \u505a\u53f3\u5b50\u6811 Node* ppNode = parent->_parent;<\/p>\n \/\/ parent \u6210\u4e3a subR \u7684\u5de6\u5b50\u6811 \/\/ subR \u9876\u66ff parent \u7684\u4f4d\u7f6e \/\/ \u53f3\u5355\u65cb \/\/ subLR \u4ea4\u7ed9 parent \u505a\u5de6\u5b50\u6811 Node* ppNode = parent->_parent;<\/p>\n \/\/ parent \u6210\u4e3a subL \u7684\u53f3\u5b50\u6811 \/\/ subL \u9876\u66ff parent \u7684\u4f4d\u7f6e private: \u4ee3\u7801\u5177\u4f53\u5e72\u4e86\u8fd9\u51e0\u4ef6\u4e8b： \u63d2\u5165\u65f6\u81ea\u52a8\u8c03\u5e73\u8861：\u63d2\u5b8c\u6570\u636e\u540e\u81ea\u52a8\u53d8\u8272\u3001\u65cb\u8f6c，\u4fdd\u8bc1\u6811\u59cb\u7ec8\u5e73\u8861，\u67e5\u627e\u6548\u7387\u7a33\u5b9a\u5728 O(logN)<\/p>\n \u904d\u5386：\u63d0\u4f9b\u4e86\u8fed\u4ee3\u5668，\u652f\u6301 begin() \/ end()，\u53ef\u4ee5\u7528\u8303\u56f4 for \u904d\u5386<\/p>\n \u9a8c\u8bc1：\u81ea\u5e26 IsBalance()，\u68c0\u67e5\u6709\u6ca1\u6709\u8fde\u7eed\u7ea2\u8282\u70b9\u3001\u6bcf\u6761\u8def\u5f84\u9ed1\u8282\u70b9\u6570\u662f\u5426\u4e00\u81f4<\/p>\n \u8fed\u4ee3\u5668\u8bbe\u8ba1\u8bf4\u660e：<\/p>\n \u8fed\u4ee3\u5668\u7684\u597d\u5904\u5728\u4e8e\u53ef\u4ee5\u65b9\u4fbf\u5730\u904d\u5386\u5bb9\u5668，\u8ba9\u7528\u6237\u65e0\u9700\u5173\u5fc3\u5e95\u5c42\u7684\u5177\u4f53\u6570\u636e\u7ed3\u6784\u3002map \u548c set \u7684\u8fed\u4ee3\u5668\u672c\u8d28\u4e0a\u5c31\u662f\u5bf9\u7ea2\u9ed1\u6811\u8fed\u4ee3\u5668\u7684\u5c01\u88c5\u3002<\/p>\n \u5982\u679c\u8981\u5728\u7ea2\u9ed1\u6811\u4e2d\u589e\u52a0\u8fed\u4ee3\u5668\u652f\u6301，\u9700\u8981\u89e3\u51b3\u4ee5\u4e0b\u4e24\u4e2a\u6838\u5fc3\u95ee\u9898：<\/p>\n STL \u89c4\u5b9a，begin()\u00a0\u4e0e\u00a0end()\u00a0\u6784\u6210\u4e00\u4e2a\u524d\u95ed\u540e\u5f00\u7684\u533a\u95f4\u00a0[begin, end)\u3002<\/p>\n \u5bf9\u7ea2\u9ed1\u6811\u8fdb\u884c\u4e2d\u5e8f\u904d\u5386\u53ef\u4ee5\u5f97\u5230\u4e00\u4e2a\u6709\u5e8f\u5e8f\u5217\u3002\u5728 SGI-STL \u7684\u6e90\u7801\u5b9e\u73b0\u4e2d，\u7ea2\u9ed1\u6811\u8bbe\u6709\u54e8\u5175\u5934\u8282\u70b9（header）：<\/p>\n \u95ee\u9898\u6765\u4e86，end() \u5e94\u8be5\u653e\u5728\u54ea\u91cc？<\/p>\n begin()\u00a0\u653e\u5728\u6700\u5de6\u4fa7\u8282\u70b9\u5f88\u5bb9\u6613\u7406\u89e3，\u4f46\u00a0end()\u00a0\u7684\u4f4d\u7f6e\u9700\u8981\u601d\u8003：\u5b83\u5e94\u8be5\u653e\u5728\u6700\u5927\u8282\u70b9（\u6700\u53f3\u4fa7\u8282\u70b9）\u7684\u4e0b\u4e00\u4e2a\u4f4d\u7f6e，\u95ee\u9898\u5728\u4e8e\u8fd9\u4e2a\u4e0b\u4e00\u4e2a\u4f4d\u7f6e<\/span>\u5177\u4f53\u5728\u54ea\u91cc？<\/p>\n \u7406\u8bba\u4e0a，\u53ef\u4ee5\u5728\u7ea2\u9ed1\u6811\u4e2d\u589e\u8bbe\u4e00\u4e2a\u5934\u8282\u70b9（header）\u4f5c\u4e3a\u54e8\u5175，\u8ba9\u00a0end()\u00a0\u6307\u5411\u5b83，\u8fd9\u6837\u5c31\u80fd\u5408\u6cd5\u8868\u793a\u672b\u5c3e\u4e4b\u540e<\/span>\u7684\u4f4d\u7f6e\u3002<\/p>\n \u4e0d\u8fc7\u6211\u4eec\u8fd9\u91cc\u53ea\u662f\u4e3a\u4e86\u7406\u89e3\u5e95\u5c42\u539f\u7406，\u505a\u6a21\u62df\u5b9e\u73b0\u65f6\u6ca1\u5fc5\u8981\u641e\u5f97\u90a3\u4e48\u590d\u6742\u3002\u4e3a\u4e86\u4fdd\u6301\u4ee3\u7801\u7b80\u6d01，\u6211\u4eec\u4e0d\u8bbe\u7f6e header \u8282\u70b9，\u76f4\u63a5\u8ba9\u00a0end()\u00a0\u8fd4\u56de\u00a0nullptr\u00a0\u5373\u53ef\u3002<\/p>\n \u8fd9\u6837\u867d\u7136\u548c STL \u6e90\u7801\u7684\u5b9e\u73b0\u6709\u7ec6\u5fae\u5dee\u522b，\u4f46\u6838\u5fc3\u903b\u8f91\u662f\u76f8\u901a\u7684，\u4e0d\u5f71\u54cd\u5bf9\u8fed\u4ee3\u5668\u673a\u5236\u7684\u7406\u89e3\u3002<\/p>\n \/\/ \u7ea2\u9ed1\u6811\u8fed\u4ee3\u5668\u63a5\u53e3 template<class K, class T, class KeyOfT> public: \/\/ begin()：\u8fd4\u56de\u6307\u5411\u6811\u4e2d\u6700\u5c0f\u8282\u70b9\u7684\u8fed\u4ee3\u5668 \/\/ \u7531\u4e8e\u8fed\u4ee3\u5668\u6784\u9020\u51fd\u6570\u652f\u6301\u9690\u5f0f\u7c7b\u578b\u8f6c\u6362（\u5355\u53c2\u6784\u9020）， \/\/ end()：\u8fd4\u56de\u4e00\u4e2a\u4ee3\u8868\u672b\u5c3e\u4e4b\u540e\u4f4d\u7f6e\u7684\u8fed\u4ee3\u5668 iterator end() private: \u54b1\u662f\u6309\u7167\u4e2d\u5e8f\u904d\u5386（\u5de6\u5b50\u6811 –>\u00a0\u6839 –> \u53f3\u5b50\u6811）\u00a0\u6765\u8d70，\u5206\u4e3a\u4ee5\u4e0b\u51e0\u79cd\u60c5\u51b5：\u00a0<\/p>\n 1.\u5f53\u8fed\u4ee3\u5668\u00a0<\/span>it<\/span>\u00a0\u6307\u5411\u7684\u8282\u70b9\u6709\u53f3\u5b50\u6811\u65f6（\u5373\u00a0<\/span>_node->_right<\/span>\u00a0\u4e0d\u4e3a\u7a7a）<\/span><\/span>，\u6267\u884c\u00a0++it\u00a0\u64cd\u4f5c\u65f6，\u4e0b\u4e00\u4e2a\u8981\u8bbf\u95ee\u7684\u8282\u70b9\u662f\u53f3\u5b50\u6811\u4e2d\u5e8f\u904d\u5386\u7684\u7b2c\u4e00\u4e2a\u8282\u70b9\u3002\u53f3\u5b50\u6811\u7684\u4e2d\u5e8f\u904d\u5386\u987a\u5e8f\u4e3a：\u5de6\u5b50\u6811 –>\u00a0\u6839 –>\u00a0\u53f3\u5b50\u6811，\u6240\u4ee5\u7b2c\u4e00\u4e2a\u88ab\u8bbf\u95ee\u7684\u8282\u70b9\u5c31\u662f\u53f3\u5b50\u6811\u4e2d\u7684\u6700\u5de6\u8282\u70b9，\u4e5f\u5c31\u662f\u53f3\u5b50\u6811\u4e2d\u503c\u6700\u5c0f\u7684\u8282\u70b9\u3002<\/p>\n 2.\u5f53\u8fed\u4ee3\u5668 it \u6307\u5411\u7684\u8282\u70b9\u6ca1\u6709\u53f3\u5b50\u6811\u65f6（_node->_right == nullptr），\u8bf4\u660e\u4ee5 it \u4e3a\u6839\u7684\u5b50\u6811\u5df2\u7ecf\u904d\u5386\u5b8c\u4e86\u3002\u6b64\u65f6\u9700\u8981\u5411\u4e0a\u56de\u6eaf，\u627e\u5230\u7b2c\u4e00\u4e2a\u6ee1\u8db3\u4ee5\u4e0b\u6761\u4ef6\u7684\u7956\u5148\u8282\u70b9：\u5f53\u524d\u8282\u70b9\u4e0d\u662f\u5176\u7236\u8282\u70b9\u7684\u53f3\u5b69\u5b50（\u5373\u5f53\u524d\u8282\u70b9\u662f\u7236\u8282\u70b9\u7684\u5de6\u5b69\u5b50）\u3002\u8fd9\u4e2a\u7956\u5148\u8282\u70b9，\u5c31\u662f\u4e0b\u4e00\u4e2a\u8981\u8bbf\u95ee\u7684\u4f4d\u7f6e<\/p>\n \u5219 it++ \u8981\u8bbf\u95ee\u7684\u8282\u70b9\u662f：it \u6307\u5411\u8282\u70b9\u7684\u7236\u4eb2\u7684\u7236\u4eb2（\u5373\u8282\u70b9 13）\u3002<\/p>\n it \u6307\u5411\u8282\u70b9 11，\u800c\u8282\u70b9 11 \u7684\u53f3\u5b50\u6811\u4e3a\u7a7a；\u540c\u65f6 it \u662f\u7236\u8282\u70b9 8 \u7684\u53f3\u5b69\u5b50\u3002 \u6b64\u65f6，it++ \u8981\u8bbf\u95ee\u7684\u8282\u70b9\u662f：it \u6240\u6307\u5411\u8282\u70b9\u7684\u7236\u4eb2\u7684\u7236\u4eb2，\u4e5f\u5c31\u662f\u8282\u70b9 13\u3002<\/p>\n 3.\u5f53 it \u6307\u5411\u7684\u8282\u70b9\u6ca1\u6709\u53f3\u5b50\u6811，\u4e14\u8be5\u8282\u70b9\u662f\u7236\u8282\u70b9\u7684\u5de6\u5b69\u5b50\u65f6，\u8bf4\u660e\u4ee5\u8be5\u8282\u70b9\u4e3a\u6839\u7684\u5b50\u6811\u5df2\u7ecf\u8bbf\u95ee\u5b8c\u4e86，\u800c\u7236\u8282\u70b9\u8fd8\u6ca1\u6709\u88ab\u8bbf\u95ee\u3002\u56e0\u6b64\u4e0b\u4e00\u4e2a\u8bbf\u95ee\u7684\u5c31\u662f\u5b83\u7684\u7236\u8282\u70b9\u3002\u5219 it++ \u8981\u8bbf\u95ee\u7684\u8282\u70b9\u662f：it \u6307\u5411\u8282\u70b9\u7684\u7236\u4eb2\u8282\u70b9（\u5373\u8282\u70b9 17）\u3002<\/p>\n<\/p>\n it \u6307\u5411\u8282\u70b9 15\u7684\u53f3\u5b50\u6811\u4e3a\u7a7a，\u4e14 it \u662f\u5b83\u7236\u8282\u70b9 17 \u7684\u5de6\u5b69\u5b50 \u5219 it++ \u8981\u8bbf\u95ee\u7684\u8282\u70b9\u662f：it \u6307\u5411\u8282\u70b9\u7684\u7236\u8282\u70b9（\u5373\u8282\u70b9 17）<\/p>\n \u6ce8\u610f<\/span>：\u5f53\u00a0it\u00a0\u8bbf\u95ee\u5230\u6700\u540e\u4e00\u4e2a\u8282\u70b9（\u5373\u6811\u4e2d\u7684\u6700\u5927\u8282\u70b9）\u65f6，\u8be5\u8282\u70b9\u6ca1\u6709\u53f3\u5b50\u6811，\u56e0\u6b64\u4f1a\u89e6\u53d1\u5411\u4e0a\u56de\u6eaf\u7684\u903b\u8f91\u3002\u6b64\u65f6\u4e0d\u65ad\u5411\u4e0a\u627e\u7236\u8282\u70b9，\u4e00\u8def\u56de\u6eaf\u5230\u6839\u8282\u70b9\u3002\u7531\u4e8e\u6839\u8282\u70b9\u4e5f\u6ca1\u6709\u7236\u8282\u70b9，\u6700\u7ec8\u4f1a\u8d70\u5230\u00a0nullptr，\u8fed\u4ee3\u5668\u53d8\u6210\u00a0end()\u3002\u800c\u6211\u4eec\u7684\u00a0end()\u00a0\u5e95\u5c42\u5c31\u662f\u7528\u00a0nullptr\u00a0\u8868\u793a\u7684，\u6240\u4ee5\u5f53\u00a0it\u00a0\u8bbf\u95ee\u5b8c\u6700\u540e\u4e00\u4e2a\u8282\u70b9\u540e\u518d\u6267\u884c\u00a0++，\u5b83\u5c31\u81ea\u52a8\u7b49\u4e8e\u00a0end()\u00a0\u4e86\u3002<\/p>\n \u5982\u679c cur \u8d70\u5230\u6700\u540e\u4e00\u4e2a\u8282\u70b9 27 \u65f6： \u7ecf\u8fc7 while \u5faa\u73af，cur \u4f1a\u8d70\u5230\u6839，\u6b64\u65f6 cur \u7236\u4eb2\u4e3a\u7a7a，\u7ed3\u675f\u5faa\u73af，\u8fd4\u56de\u7a7a，\u4e5f\u5373\u662f end ()<\/p>\n T：\u6570\u636e\u7684\u7c7b\u578b，\u5982\u679c\u662f map，\u5219\u4e3a pair<const K, V>；\u5982\u679c\u662f set，\u5219\u4e3a K\u3002<\/p>\n<\/li>\n \/\/ \u7ea2\u9ed1\u6811\u8fed\u4ee3\u5668 template<class T, class Ref, class Ptr> Node* _node; \/\/ \u8282\u70b9\u6307\u9488，\u6307\u5411\u5f53\u524d\u8fed\u4ee3\u5668\u4f4d\u7f6e<\/p>\n \/\/\u6784\u9020\u51fd\u6570 \/\/ \u89e3\u5f15\u7528\u64cd\u4f5c \/\/ operator->：\u8fd4\u56de\u8282\u70b9\u6570\u636e\u7684\u6307\u9488 \/\/ \u6bd4\u8f83\u64cd\u4f5c bool operator==(const Self& s) const \/\/ operator++：\u524d\u7f6e++，\u6307\u5411\u4e2d\u5e8f\u904d\u5386\u7684\u4e0b\u4e00\u4e2a\u8282\u70b9 Self& operator++() \/\/ \u60c5\u51b52：\u5f53\u524d\u8282\u70b9\u6ca1\u6709\u53f3\u5b50\u6811 \/\/ \u4e0d\u65ad\u5411\u4e0a\u8d70，\u76f4\u5230 cur \u662f parent \u7684\u5de6\u5b69\u5b50 return *this; \/\/ \u8fd4\u56de\u81ea\u8eab\u7684\u5f15\u7528（\u652f\u6301\u94fe\u5f0f\u64cd\u4f5c） \/\/ operator–：\u524d\u7f6e–，\u6307\u5411\u4e2d\u5e8f\u904d\u5386\u7684\u4e0a\u4e00\u4e2a\u8282\u70b9 Self& operator–() \/\/\u60c5\u51b52：\u5f53\u524d\u8282\u70b9\u6ca1\u6709\u5de6\u5b50\u6811 while (parent && cur == parent->_left) return *this; map\u00a0\u548c\u00a0set\u00a0\u7684\u63d2\u5165\u64cd\u4f5c，\u5e95\u5c42\u90fd\u662f\u8c03\u7528\u7ea2\u9ed1\u6811\u7684\u63d2\u5165\u63a5\u53e3\u3002\u6240\u4ee5\u60f3\u8981\u7406\u89e3\u5b83\u4eec，\u5f97\u5148\u641e\u6e05\u695a\u7ea2\u9ed1\u6811\u7684\u63d2\u5165\u662f\u600e\u4e48\u505a\u7684\u3002<\/p>\n \u7ea2\u9ed1\u6811\u7684\u63d2\u5165\u903b\u8f91\u662f\u8fd9\u6837\u7684：\u5148\u6839\u636e\u952e\u503c\u53bb\u6811\u91cc\u627e，\u770b\u8fd9\u4e2a\u952e\u5b58\u4e0d\u5b58\u5728\u3002<\/p>\n \u8fd9\u91cc\u7684\u00a0T\u00a0\u662f\u7ea2\u9ed1\u6811\u5b58\u7684\u6570\u636e\u7c7b\u578b：<\/p>\n \/\/ \u7ea2\u9ed1\u6811\u63d2\u5165\u51fd\u6570 pair<iterator, bool> Insert(const T& data) return make_pair(iterator(_root), true); \/\/ \u60c5\u51b52：\u6811\u4e0d\u4e3a\u7a7a，\u627e\u63d2\u5165\u4f4d\u7f6e while (cur) \/\/ cur \u4e3a\u7a7a\u65f6，\u8bf4\u660e\u627e\u5230\u63d2\u5165\u4f4d\u7f6e\u4e86 \/\/ \u60c5\u51b53：\u63d2\u5165\u65b0\u8282\u70b9 \/\/ \u8fde\u63a5\u7236\u8282\u70b9 \/\/ \u60c5\u51b54：\u8c03\u6574\u5e73\u8861 \/\/ \u60c5\u51b5A：\u7236\u8282\u70b9\u662f\u7237\u7237\u7684\u5de6\u5b69\u5b50 \/\/ \u5b50\u60c5\u51b51：\u53d4\u53d4\u5b58\u5728\u4e14\u4e3a\u7ea2\u8272 –> \u53d8\u8272，\u7ee7\u7eed\u5f80\u4e0a\u5904\u7406 \/\/ \u60c5\u51b5B：\u7236\u8282\u70b9\u662f\u7237\u7237\u7684\u53f3\u5b69\u5b50（\u5bf9\u79f0） \/\/ \u5b50\u60c5\u51b51：\u53d4\u53d4\u5b58\u5728\u4e14\u4e3a\u7ea2\u8272 –> \u53d8\u8272，\u7ee7\u7eed\u5f80\u4e0a\u5904\u7406 \/\/ \u60c5\u51b55：\u6700\u540e\u4fdd\u8bc1\u6839\u8282\u70b9\u662f\u9ed1\u8272 map\u7684\u5e95\u5c42\u7ed3\u6784\u5c31\u662f\u7ea2\u9ed1\u6811，\u56e0\u6b64\u5728 map \u4e2d\u76f4\u63a5\u5c01\u88c5\u4e00\u68f5\u7ea2\u9ed1\u6811，\u7136\u540e\u5c06\u5176\u63a5\u53e3\u5305\u88c5\u4e0b\u5c31\u884c\u3002<\/p>\n namespace hjq template<class K, class V> \/\/ \u4eff\u51fd\u6570 MapKeyOfT struct MapKeyOfT public:<\/p>\n \/\/ \u8fed\u4ee3\u5668\u7c7b\u578b\u522b\u540d typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;<\/p>\n \/\/ begin()：\u8fd4\u56de\u6307\u5411\u7b2c\u4e00\u4e2a\u5143\u7d20\u7684\u8fed\u4ee3\u5668 iterator begin() \/\/ end()：\u8fd4\u56de\u6307\u5411\u672b\u5c3e\u7684\u8fed\u4ee3\u5668 iterator end() \/\/ insert：\u63d2\u5165\u952e\u503c\u5bf9 pair<iterator, bool> insert(const pair<K, V>& kv) \/\/ operator[]：\u901a\u8fc7\u952e\u8bbf\u95ee\u5bf9\u5e94\u7684\u503c V& operator[](const K& key) \/\/ ret.first \u662f\u6307\u5411\u8be5\u952e\u503c\u5bf9\u7684\u8fed\u4ee3\u5668 private:<\/p>\n \/\/ \u7ea2\u9ed1\u6811\u5e95\u5c42\u5bb9\u5668 RBTree<K, pair<K, V>, MapKeyOfT> _t; set \u7684\u5e95\u5c42\u4e3a\u7ea2\u9ed1\u6811，\u53ea\u9700\u5728 set \u5185\u90e8\u5c01\u88c5\u4e00\u68f5\u7ea2\u9ed1\u6811，\u5c31\u53ef\u4ee5\u5c06\u8be5\u5bb9\u5668\u5b9e\u73b0\u51fa\u6765（\u53c2\u8003 map）\u3002<\/p>\n namespace hjq template<class K> \/\/ \u4eff\u51fd\u6570 SetKeyOfT struct SetKeyOfT public:<\/p>\n \/\/ \u8fed\u4ee3\u5668\u7c7b\u578b\u522b\u540d typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;<\/p>\n \/\/ begin()：\u8fd4\u56de\u6307\u5411\u7b2c\u4e00\u4e2a\u5143\u7d20\u7684\u8fed\u4ee3\u5668 \/\/ end()：\u8fd4\u56de\u6307\u5411\u672b\u5c3e\u7684\u8fed\u4ee3\u5668 iterator end() \/\/ insert：\u63d2\u5165\u5143\u7d20 pair<iterator, bool> insert(const K& key) \/\/ inorder：\u4e2d\u5e8f\u904d\u5386 void inorder() private:<\/p>\n \/\/ \u7ea2\u9ed1\u6811\u5e95\u5c42\u5bb9\u5668 \u4e00. \u7ea2\u2fca\u6811\u7684\u6982\u5ff5\u7ea2\u2fca\u6811\u662f\u2f00\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\u2f8a，\u53ef\u4ee5\u662f\u7ea2\u2f8a\u6216\u8005\u2fca\u2f8a\u3002\u901a\u8fc7\u5bf9\u4efb\u4f55\u2f00\u6761\u4ece\u6839\u5230\u53f6\u2f26\u7684\u8def\u5f84\u4e0a\u5404\u4e2a\u7ed3\u70b9\u7684\u989c\u2f8a\u8fdb\u2f8f\u7ea6\u675f，\u7ea2\u2fca\u6811\u786e\u4fdd\u6ca1\u6709\u2f00\u6761\u8def\u5f84\u4f1a\u6bd4\u5176\u4ed6\u8def\u5f84\u957f\u51fa2\u500d，\u56e0\u2f7d\u662f\u63a5\u8fd1\u5e73\u8861\u7684\u30021.\u7ea2\u9ed1\u6811\u7684\u89c4\u5219：\u6bcf\u4e2a\u7ed3\u70b9\u4e0d\u662f\u7ea2\u2f8a\u5c31\u662f\u2fca\u2f8a\u6839\u7ed3\u70b9\u662f\u2fca\u2f8a\u7684\u5982\u679c\u2f00\u4e2a\u7ed3\u70b9\u662f\u7ea2\u2f8a\u7684，\u5219\u5b83\u7684\u4e24\u4e2a\u5b69\u2f26\u7ed3\u70b9\u5fc5\u987b\u662f\u2fca\u2f8a\u7684，\u4e5f\u5c31\u662f\u8bf4\u4efb\u610f\u2f00\u6761\u8def\u5f84\u4e0d\u4f1a\u6709\u8fde\u7eed\u7684\u7ea2\u2f8a\u7ed3\u70b9\u3002\u5bf9\u4e8e\u4efb<\/p>\n","protected":false},"author":2,"featured_media":96406,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[9139,11035,11036,11037,11038],"topic":[],"class_list":["post-96426","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-server","tag-9139","tag-11035","tag-mapset","tag-11037","tag-11038"],"yoast_head":"\n
\n
\n\u2022 \u7531\u89c4\u52192\u548c\u89c4\u52193\u53ef\u77e5，\u4efb\u610f\u2f00\u6761\u8def\u5f84\u4e0d\u4f1a\u6709\u8fde\u7eed\u7684\u7ea2\u2f8a\u7ed3\u70b9，\u6240\u4ee5\u6781\u7aef\u573a\u666f\u4e0b，\u6700\u2ed3\u7684\u8def\u5f84\u5c31\u662f\u2f00\u9ed1\u2f00\u7ea2\u95f4\u9694\u7ec4\u6210，\u90a3\u4e48\u6700\u957f\u8def\u5f84\u7684\u957f\u5ea6\u4e3a2*bh\u3002
\n\u2022 \u7efc\u5408\u7ea2\u9ed1\u6811\u76844\u70b9\u89c4\u5219\u2f7d\u8a00，\u7406\u8bba\u4e0a\u7684\u5168\u9ed1\u6700\u77ed\u8def\u5f84\u548c\u2f00\u9ed1\u2f00\u7ea2\u7684\u6700\u957f\u8def\u5f84\u5e76\u4e0d\u662f\u5728\u6bcf\u68f5\u7ea2\u9ed1\u6811\u90fd\u5b58\u5728\u7684\u3002\u5047\u8bbe\u4efb\u610f\u2f00\u6761\u4ece\u6839\u5230NULL\u7ed3\u70b9\u8def\u5f84\u7684\u2ed3\u5ea6\u4e3ax，\u90a3\u4e48bh <= h <= 2*bh\u3002<\/p>\n
\n3.\u7ea2\u2fca\u6811\u7684\u6548\u7387：<\/h3>\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260827083241-6a8ff629f1b39.png\")
<\/p>\n![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260827083242-6a8ff62a85490.png\")
<\/p>\n
\n\u4e8c.\u7ea2\u9ed1\u6811\u7684\u5b9e\u73b0<\/h2>\n
\n
\n1.\u5b9a\u4e49\u7ea2\u9ed1\u6811\u7684\u8282\u70b9\u7ed3\u6784<\/h3>\n
\nenum Colour
\n{
\n RED,
\n BLACK
\n};<\/p>\n
\ntemplate<class T>
\nstruct RBTreeNode
\n{
\n \/\/ ———- \u4e09\u53c9\u94fe ———-
\n RBTreeNode<T>* _left; \/\/ \u5de6\u5b69\u5b50
\n RBTreeNode<T>* _right; \/\/ \u53f3\u5b69\u5b50
\n RBTreeNode<T>* _parent; \/\/ \u7236\u8282\u70b9（\u65b9\u4fbf\u5411\u4e0a\u56de\u6eaf）<\/p>\n
\n T _data; \/\/ \u5b58\u50a8\u7684\u6570\u636e，\u53ef\u80fd\u662f Key \u6216 pair<const Key, V><\/p>\n
\n Colour _col; <\/p>\n
\n RBTreeNode(const T& data)
\n : _left(nullptr)
\n , _right(nullptr)
\n , _parent(nullptr)
\n , _data(data)
\n , _col(RED) \/\/ \u65b0\u8282\u70b9\u9ed8\u8ba4\u7ea2\u8272
\n {}
\n};<\/p>\n
\n2.\u5b9a\u4e49\u7ea2\u9ed1\u6811\u7ed3\u6784<\/h3>\n
\n
\n\/\/ K：\u952e\u7684\u7c7b\u578b（\u7528\u4e8e\u6bd4\u8f83\u67e5\u627e）
\n\/\/ T：\u8282\u70b9\u5b58\u50a8\u7684\u6570\u636e\u7c7b\u578b（set\u4f20Key，map\u4f20pair<const K, V>）
\ntemplate<class K, class T>
\nclass RBTree
\n{
\n typedef RBTreeNode<T> Node;<\/p>\n
\n \/\/ \u6784\u9020\u51fd\u6570：\u521d\u59cb\u65f6\u6811\u4e3a\u7a7a，\u6839\u8282\u70b9\u7f6e\u7a7a
\n RBTree() : _root(nullptr) {}<\/p>\n
\n bool Insert(const T& data);<\/p>\n
\n Node* _root; \/\/ \u6839\u8282\u70b9\u6307\u9488<\/p>\n
\n![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260827083243-6a8ff62b3c84a.png\")
<\/p>\n
\n\n
\n
\ntemplate<class K, class T, class KeyOfT>
\nclass RBTree
\n{
\n \/\/ \u7ed9\u7ea2\u9ed1\u6811\u8282\u70b9\u7c7b\u578b\u8d77\u522b\u540d
\n typedef RBTreeNode<T> Node;<\/p>\n
\n \/\/ \u6784\u9020\u51fd\u6570：\u6811\u521d\u59cb\u4e3a\u7a7a，\u6839\u8282\u70b9\u6307\u5411 nullptr
\n RBTree() : _root(nullptr) {}<\/p>\n
\n \/\/ \u53c2\u6570 data \u662f\u8981\u63d2\u5165\u7684\u6570\u636e（\u53ef\u80fd\u662f Key \u6216 pair）
\n \/\/ \u8fd4\u56de\u503c：\u5f53\u524d\u662f bool（true\/false），\u540e\u7eed\u4f1a\u6539\u6210 pair<iterator, bool>
\n \/\/ \u4ee5\u4fbf\u548c STL \u63a5\u53e3\u4fdd\u6301\u4e00\u81f4
\n bool Insert(const T& data);<\/p>\n
\n Node* _root; \/\/ \u6839\u8282\u70b9\u6307\u9488，\u6574\u68f5\u6811\u7684\u5165\u53e3
\n};<\/p>\n
\n![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260827083243-6a8ff62b80640.png\")
<\/p>\n
\n3.\u7ea2\u9ed1\u6811\u7684\u63d2\u5165<\/h3>\n
\u7ea2\u9ed1\u6811\u63d2\u2f0a\u2f00\u4e2a\u503c\u7684\u2f24\u6982\u8fc7\u7a0b：<\/h4>\n
\n2. \u5982\u679c\u662f\u7a7a\u6811\u63d2\u2f0a，\u65b0\u589e\u7ed3\u70b9\u662f\u2fca\u2f8a\u7ed3\u70b9\u3002\u5982\u679c\u662f\u2fae\u7a7a\u6811\u63d2\u2f0a，\u65b0\u589e\u7ed3\u70b9\u5fc5\u987b\u7ea2\u2f8a\u7ed3\u70b9，\u56e0\u4e3a\u2fae\u7a7a\u6811\u63d2\u2f0a，\u65b0\u589e\u2fca\u2f8a\u7ed3\u70b9\u5c31\u7834\u574f\u4e86\u89c4\u52194，\u89c4\u52194\u662f\u5f88\u96be\u7ef4\u62a4\u7684\u3002
\n3. \u2fae\u7a7a\u6811\u63d2\u2f0a\u540e，\u65b0\u589e\u7ed3\u70b9\u5fc5\u987b\u7ea2\u2f8a\u7ed3\u70b9，\u5982\u679c\u2f57\u4eb2\u7ed3\u70b9\u662f\u2fca\u2f8a\u7684，\u5219\u6ca1\u6709\u8fdd\u53cd\u4efb\u4f55\u89c4\u5219，\u63d2\u2f0a\u7ed3\u675f
\n4. \u2fae\u7a7a\u6811\u63d2\u2f0a\u540e，\u65b0\u589e\u7ed3\u70b9\u5fc5\u987b\u7ea2\u2f8a\u7ed3\u70b9，\u5982\u679c\u2f57\u4eb2\u7ed3\u70b9\u662f\u7ea2\u2f8a\u7684，\u5219\u8fdd\u53cd\u89c4\u52193\u3002\u8fdb\u2f00\u6b65\u5206\u6790，c\u662f\u7ea2\u2f8a，p\u4e3a\u7ea2，g\u5fc5\u4e3a\u2fca，\u8fd9\u4e09\u4e2a\u989c\u2f8a\u90fd\u56fa\u5b9a\u4e86，\u5173\u952e\u7684\u53d8\u5316\u770bu\u7684\u60c5\u51b5，\u9700\u8981\u6839\u636eu\u5206\u4e3a\u4ee5\u4e0b\u2f0f\u79cd\u60c5\u51b5\u5206\u522b\u5904\u7406\u3002<\/p>\n
\ng(grandfather)，p\u7684\u5144\u5f1f\u6807\u8bc6\u4e3au（uncle）\u3002<\/p>\n\u60c5\u51b51：\u53d8\u2f8a<\/h4>\n
\n\u5206\u6790：\u56e0\u4e3ap\u548cu\u90fd\u662f\u7ea2\u2f8a，g\u662f\u2fca\u2f8a，\u628ap\u548cu\u53d8\u2fca，\u5de6\u8fb9\u2f26\u6811\u8def\u5f84\u5404\u589e\u52a0\u2f00\u4e2a\u2fca\u2f8a\u7ed3\u70b9，g\u518d\u53d8\u7ea2，\u76f8\u5f53\u4e8e\u4fdd\u6301g\u6240\u5728\u2f26\u6811\u7684\u2fca\u2f8a\u7ed3\u70b9\u7684\u6570\u91cf\u4e0d\u53d8，\u540c\u65f6\u89e3\u51b3\u4e86c\u548cp\u8fde\u7eed\u7ea2\u2f8a\u7ed3\u70b9\u7684\u95ee\u9898，\u9700\u8981\u7ee7\u7eed\u5f80\u4e0a\u66f4\u65b0\u662f\u56e0\u4e3a，g\u662f\u7ea2\u2f8a，\u5982\u679cg\u7684\u2f57\u4eb2\u8fd8\u662f\u7ea2\u2f8a，\u90a3\u4e48\u5c31\u8fd8\u9700\u8981\u7ee7\u7eed\u5904\u7406；\u5982\u679cg\u7684\u2f57\u4eb2\u662f\u2fca\u2f8a，\u5219\u5904\u7406\u7ed3\u675f\u4e86；\u5982\u679cg\u5c31\u662f\u6574\u68f5\u6811\u7684\u6839，\u518d\u628ag\u53d8\u56de\u2fca\u2f8a\u3002
\n\u60c5\u51b51\u53ea\u53d8\u2f8a，\u4e0d\u65cb\u8f6c\u3002\u6240\u4ee5\u2f46\u8bbac\u662fp\u7684\u5de6\u8fd8\u662f\u53f3，p\u662fg\u7684\u5de6\u8fd8\u662f\u53f3，\u90fd\u662f\u4e0a\u2faf\u7684\u53d8\u2f8a\u5904\u7406\u2f45\u5f0f\u3002<\/span><\/p>\n![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260827083243-6a8ff62bea155.png\")
<\/p>\n\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260827083245-6a8ff62d59494.png\")
<\/p>\n![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260827083247-6a8ff62fd9640.png\")
<\/p>\n![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260827083249-6a8ff6316e93a.png\")
<\/p>\n
\n![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260827083252-6a8ff6344e88f.png\")
<\/p>\n
\n\u60c5\u51b52：\u5355\u65cb+\u53d8\u2f8a<\/h4>\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260827083256-6a8ff63819e39.png\")
<\/p>\n
\n![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260827083256-6a8ff638310cf.png\")
<\/p>\n
\n![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260827083256-6a8ff63848173.png\")
<\/p>\n\u60c5\u51b53：\u53cc\u65cb+\u53d8\u2f8a<\/h4>\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260827083256-6a8ff6388b309.png\")
<\/p>\n
\n![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260827083256-6a8ff638a22d9.png\")
<\/p>\n
\n
\n\u2fca，g\u53d8\u7ea2\u5373\u53ef\u3002c\u53d8\u6210\u8bfe\u8fd9\u9897\u6811\u65b0\u7684\u6839，\u8fd9\u6837\u2f26\u6811\u2fca\u2f8a\u7ed3\u70b9\u7684\u6570\u91cf\u4e0d\u53d8，\u6ca1\u6709\u8fde\u7eed\u7684\u7ea2\u2f8a\u7ed3\u70b9\u4e86，\u4e14\u4e0d\u9700\u8981\u5f80\u4e0a\u66f4\u65b0，\u56e0\u4e3ac\u7684\u2f57\u4eb2\u662f\u2fca\u2f8a\u8fd8\u662f\u7ea2\u2f8a\u6216\u8005\u7a7a\u90fd\u4e0d\u8fdd\u53cd\u89c4\u5219\u3002<\/p>\n![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260827083256-6a8ff638b90e8.png\")
<\/p>\n\u7ea2\u2fca\u6811\u7684\u63d2\u2f0a\u4ee3\u7801\u5b9e\u73b0：<\/h4>\n
\n\/\/ \u65cb\u8f6c\u4ee3\u7801\u8ddf AVL \u6811\u4e00\u6837，\u53ea\u662f\u4e0d\u9700\u8981\u66f4\u65b0\u5e73\u8861\u56e0\u5b50
\n\/\/ \u6838\u5fc3\u56fd\u6210：\u63d2\u5165\u65b0\u8282\u70b9 —> \u68c0\u6d4b\u662f\u5426\u8fdd\u53cd\u89c4\u5219 —> \u53d8\u8272\/\u65cb\u8f6c\u4fee\u590d<\/p>\n
\n{
\n \/\/\u7b2c1\u6b65：\u6811\u4e3a\u7a7a，\u76f4\u63a5\u63d2\u5165\u6839\u8282\u70b9 if (_root == nullptr)
\n {
\n _root = new Node(kv);
\n _root->_col = BLACK; \/\/ \u6839\u8282\u70b9\u5fc5\u987b\u662f\u9ed1\u8272
\n return true;
\n }<\/p>\n
\n Node* parent = nullptr;
\n Node* cur = _root;<\/p>\n
\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; \/\/ \u952e\u5df2\u5b58\u5728，\u63d2\u5165\u5931\u8d25
\n }
\n }<\/p>\n
\n cur = new Node(kv);
\n cur->_col = RED; \/\/ \u65b0\u8282\u70b9\u9ed8\u8ba4\u7ea2\u8272（\u4e0d\u5f71\u54cd\u9ed1\u8272\u8def\u5f84）<\/p>\n
\n if (parent->_kv.first < kv.first)
\n {
\n parent->_right = cur;
\n }
\n else
\n {
\n parent->_left = cur;
\n }
\n cur->_parent = parent;<\/p>\n
\n \/\/ \u7236\u8282\u70b9\u662f\u7ea2\u8272\u624d\u9700\u8981\u8c03\u6574（\u8fdd\u53cd\u4e0d\u80fd\u8fde\u7eed\u7ea2\u89c4\u5219）
\n while (parent && parent->_col == RED)
\n {
\n Node* grandfather = parent->_parent;<\/p>\n
\n \/\/ g(\u9ed1)
\n \/\/ \/ \\\\
\n \/\/ p(\u7ea2) u(?)<\/p>\n
\n {
\n Node* uncle = grandfather->_right;<\/p>\n
\n if (uncle && uncle->_col == RED)
\n {
\n parent->_col = uncle->_col = BLACK;
\n grandfather->_col = RED;
\n \/\/ \u7ee7\u7eed\u5f80\u4e0a\u5904\u7406
\n cur = grandfather;
\n parent = cur->_parent;
\n }
\n else \/\/ \u5b50\u60c5\u51b52+3：\u53d4\u53d4\u4e0d\u5b58\u5728 \u6216 \u53d4\u53d4\u4e3a\u9ed1\u8272 \u2192 \u9700\u8981\u65cb\u8f6c
\n {
\n if (cur == parent->_left)
\n {
\n \/\/ \u5b50\u60c5\u51b52：\u5de6\u5de6 \u2192 \u53f3\u5355\u65cb
\n \/\/ g
\n \/\/ \/ \\\\
\n \/\/ p u
\n \/\/ \/
\n \/\/ c
\n RotateR(grandfather);
\n parent->_col = BLACK;
\n grandfather->_col = RED;
\n }
\n else
\n {
\n \/\/ \u5b50\u60c5\u51b53：\u5de6\u53f3 \u2192 \u5de6\u53f3\u53cc\u65cb
\n \/\/ g
\n \/\/ \/ \\\\
\n \/\/ p u
\n \/\/ \\\\
\n \/\/ c
\n RotateL(parent);
\n RotateR(grandfather);
\n cur->_col = BLACK;
\n grandfather->_col = RED;
\n }
\n break; \/\/ \u65cb\u8f6c\u540e\u6811\u5df2\u5e73\u8861，\u9000\u51fa\u5faa\u73af
\n }
\n }<\/p>\n
\n \/\/ g(\u9ed1)
\n \/\/ \/ \\\\
\n \/\/ u(?) p(\u7ea2)<\/p>\n
\n {
\n Node* uncle = grandfather->_left;<\/p>\n
\n if (uncle && uncle->_col == RED)
\n {
\n parent->_col = uncle->_col = BLACK;
\n grandfather->_col = RED;
\n cur = grandfather;
\n parent = cur->_parent;
\n }
\n else \/\/ \u5b50\u60c5\u51b52+3：\u53d4\u53d4\u4e0d\u5b58\u5728 \u6216 \u53d4\u53d4\u4e3a\u9ed1\u8272 –> \u9700\u8981\u65cb\u8f6c
\n {
\n if (cur == parent->_right)
\n {
\n \/\/ \u5b50\u60c5\u51b52：\u53f3\u53f3 \u2192 \u5de6\u5355\u65cb
\n \/\/ g
\n \/\/ \/ \\\\
\n \/\/ u p
\n \/\/ \\\\
\n \/\/ c
\n RotateL(grandfather);
\n parent->_col = BLACK;
\n grandfather->_col = RED;
\n }
\n else
\n {
\n \/\/ \u5b50\u60c5\u51b53：\u53f3\u5de6 \u2192 \u53f3\u5de6\u53cc\u65cb
\n \/\/ g
\n \/\/ \/ \\\\
\n \/\/ u p
\n \/\/ \/
\n \/\/ c
\n RotateR(parent);
\n RotateL(grandfather);
\n cur->_col = BLACK;
\n grandfather->_col = RED;
\n }
\n break; \/\/ \u65cb\u8f6c\u540e\u6811\u5df2\u5e73\u8861，\u9000\u51fa\u5faa\u73af
\n }
\n }
\n }<\/p>\n
\n _root->_col = BLACK;
\n return true;
\n}<\/p>\n
\n4.\u7ea2\u2fca\u6811\u7684\u67e5\u627e：<\/h3>\n
\n\/\/ \u8fd4\u56de\u503c：\u627e\u5230\u8fd4\u56de\u8282\u70b9\u6307\u9488，\u627e\u4e0d\u5230\u8fd4\u56de nullptr<\/p>\n
\n{
\n Node* cur = _root; \/\/ \u4ece\u6839\u8282\u70b9\u5f00\u59cb\u67e5\u627e<\/p>\n
\n {
\n if (cur->_kv.first < key) \/\/ \u5f53\u524d\u8282\u70b9\u7684\u952e < \u76ee\u6807\u952e
\n {
\n cur = cur->_right; \/\/ \u76ee\u6807\u66f4\u5927，\u5f80\u53f3\u5b50\u6811\u8d70
\n }
\n else if (cur->_kv.first > key) \/\/ \u5f53\u524d\u8282\u70b9\u7684\u952e > \u76ee\u6807\u952e
\n {
\n cur = cur->_left; \/\/ \u76ee\u6807\u66f4\u5c0f，\u5f80\u5de6\u5b50\u6811\u8d70
\n }
\n else \/\/ \u5f53\u524d\u8282\u70b9\u7684\u952e == \u76ee\u6807\u952e
\n {
\n return cur; \/\/ \u627e\u5230\u4e86，\u8fd4\u56de\u5f53\u524d\u8282\u70b9
\n }
\n }<\/p>\n
\n}<\/p>\n
\n5.\u7ea2\u2fca\u6811\u7684\u9a8c\u8bc1：<\/h3>\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260827083257-6a8ff639089c8.png\")
<\/p>\n
\n{
\n \/\/ \u7a7a\u6811\u4e5f\u7b97\u7ea2\u9ed1\u6811
\n if (_root == nullptr)
\n return true;<\/p>\n
\n if (_root->_col == RED)
\n return false;<\/p>\n
\n \/\/ \u53d6\u6700\u5de6\u8def\u5f84\u4e0a\u7684\u9ed1\u8272\u8282\u70b9\u6570\u91cf\u4f5c\u4e3a\u57fa\u51c6\u503c
\n \/\/ \u6240\u6709\u8def\u5f84\u7684\u9ed1\u8272\u8282\u70b9\u6570\u91cf\u90fd\u5fc5\u987b\u7b49\u4e8e\u8fd9\u4e2a\u503c
\n int refNum = 0;
\n Node* cur = _root;
\n while (cur)
\n {
\n if (cur->_col == BLACK)
\n {
\n ++refNum; \/\/ \u7edf\u8ba1\u6700\u5de6\u8def\u5f84\u4e0a\u7684\u9ed1\u8272\u8282\u70b9\u6570
\n }
\n cur = cur->_left; \/\/ \u4e00\u76f4\u5f80\u5de6\u8d70
\n }<\/p>\n
\n return Check(_root, 0, refNum);
\n}<\/p>\n
\n{
\n \/\/1. \u8d70\u5230\u7a7a\u8282\u70b9
\n \/\/ \u8bf4\u660e\u4e00\u6761\u8def\u5f84\u8d70\u5b8c\u4e86，\u68c0\u67e5\u9ed1\u8272\u8282\u70b9\u6570\u91cf\u662f\u5426\u8fbe\u6807
\n if (root == nullptr)
\n {
\n if (refNum != blackNum)
\n {
\n cout << "\u5b58\u5728\u9ed1\u8272\u8282\u70b9\u6570\u91cf\u4e0d\u76f8\u7b49\u7684\u8def\u5f84" << endl;
\n return false;
\n }
\n return true;
\n }<\/p>\n
\n \/\/ \u5f53\u524d\u8282\u70b9\u662f\u7ea2\u8272，\u7236\u8282\u70b9\u4e5f\u662f\u7ea2\u8272 —> \u8fdd\u89c4
\n \/\/ \u68c0\u67e5\u5b69\u5b50\u4e0d\u65b9\u4fbf（\u4e24\u4e2a\u5b69\u5b50\u4e0d\u4e00\u5b9a\u5b58\u5728），\u53cd\u8fc7\u6765\u68c0\u67e5\u7236\u4eb2\u66f4\u65b9\u4fbf
\n if (root->_col == RED && root->_parent->_col == RED)
\n {
\n cout << root->_kv.first << "\u5b58\u5728\u8fde\u7eed\u7684\u7ea2\u8272\u8282\u70b9" << endl;
\n return false;
\n }<\/p>\n
\n \/\/ \u5f53\u524d\u8282\u70b9\u662f\u9ed1\u8272，\u8def\u5f84\u4e0a\u7684\u9ed1\u8272\u8282\u70b9\u6570 +1
\n if (root->_col == BLACK)
\n {
\n blackNum++;
\n }<\/p>\n
\n \/\/ \u4e24\u6761\u8def\u5f84\u90fd\u5fc5\u987b\u6ee1\u8db3\u6761\u4ef6
\n return Check(root->_left, blackNum, refNum)
\n && Check(root->_right, blackNum, refNum);
\n}<\/p>\n
\n6.\u7ea2\u9ed1\u6811\u7684\u5220\u9664<\/h3>\n
\n
\n\/\/ \u989c\u8272\u679a\u4e3e：\u6807\u8bb0\u8282\u70b9\u662f\u7ea2\u8272\u8fd8\u662f\u9ed1\u8272
\n\/\/ \u7ea2\u9ed1\u6811\u9760\u989c\u8272\u6765\u7ef4\u6301\u5e73\u8861，\u7ea2\u8272\u8282\u70b9\u4e0d\u80fd\u8fde\u7eed\u51fa\u73b0
\nenum Colour
\n{
\n RED,
\n BLACK
\n};<\/p>\n
\n\/\/ \u4e09\u53c9\u94fe\u7ed3\u6784：\u5de6\u5b69\u5b50 + \u53f3\u5b69\u5b50 + \u7236\u8282\u70b9（\u65b9\u4fbf\u5411\u4e0a\u56de\u6eaf）
\n\/\/ \u5b58\u6570\u636e + \u989c\u8272\u6807\u8bb0
\n\/\/ \u65b0\u8282\u70b9\u9ed8\u8ba4\u7ea2\u8272，\u63d2\u5165\u65f6\u8c03\u6574\u6210\u672c\u66f4\u4f4e
\ntemplate<class T>
\nstruct RBTreeNode
\n{
\n RBTreeNode<T>* _left; \/\/ \u5de6\u5b69\u5b50
\n RBTreeNode<T>* _right; \/\/ \u53f3\u5b69\u5b50
\n RBTreeNode<T>* _parent; \/\/ \u7236\u8282\u70b9（\u5411\u4e0a\u56de\u6eaf\u7528）<\/p>\n
\n Colour _col; \/\/ \u989c\u8272\u6807\u8bb0<\/p>\n
\n : _left(nullptr)
\n , _right(nullptr)
\n , _parent(nullptr)
\n , _data(data)
\n , _col(RED) \/\/ \u65b0\u8282\u70b9\u9ed8\u8ba4\u7ea2\u8272
\n {}
\n};<\/p>\n
\n\/\/ \u652f\u6301 *\u3001->\u3001++\u3001–\u3001==\u3001!=
\n\/\/ \u904d\u5386\u987a\u5e8f\u662f\u4e2d\u5e8f\u904d\u5386（\u5de6->\u6839->\u53f3），\u5f97\u5230\u6709\u5e8f\u5e8f\u5217<\/p>\n
\nstruct __RBTreeIterator
\n{
\n typedef RBTreeNode<T> Node;
\n typedef __RBTreeIterator<T, Ref, Ptr> Self;
\n Node* _node; \/\/ \u6307\u5411\u5f53\u524d\u8282\u70b9<\/p>\n
\n : _node(node)
\n {}<\/p>\n
\n Ref operator*()
\n {
\n return _node->_data; \/\/ \u8fd4\u56de\u8282\u70b9\u6570\u636e\u7684\u5f15\u7528
\n }<\/p>\n
\n {
\n return &_node->_data; \/\/ \u8fd4\u56de\u8282\u70b9\u6570\u636e\u7684\u6307\u9488
\n }<\/p>\n
\n bool operator!=(const Self& s) const
\n {
\n return _node != s._node;
\n }<\/p>\n
\n {
\n return _node == s._node;
\n }<\/p>\n
\n \/\/ \u5982\u679c\u6709\u53f3\u5b50\u6811，\u627e\u53f3\u5b50\u6811\u7684\u6700\u5de6\u8282\u70b9
\n \/\/ \u5982\u679c\u6ca1\u6709\u53f3\u5b50\u6811，\u5411\u4e0a\u627e\u7b2c\u4e00\u4e2a\u4e0d\u662f\u7236\u8282\u70b9\u53f3\u5b69\u5b50\u7684\u7956\u5148
\n Self& operator++()
\n {
\n if (_node->_right)
\n {
\n \/\/ \u6709\u53f3\u5b50\u6811 -> \u53f3\u5b50\u6811\u7684\u6700\u5de6\u8282\u70b9
\n Node* left = _node->_right;
\n while (left->_left)
\n {
\n left = left->_left;
\n }
\n _node = left;
\n }
\n else
\n {
\n \/\/ \u6ca1\u53f3\u5b50\u6811 -> \u5f80\u4e0a\u627e
\n \/\/ \u76f4\u5230\u5f53\u524d\u8282\u70b9\u4e0d\u662f\u7236\u8282\u70b9\u7684\u53f3\u5b69\u5b50\u65f6\u505c
\n Node* parent = _node->_parent;
\n Node* cur = _node;
\n while (parent && cur == parent->_right)
\n {
\n cur = cur->_parent;
\n parent = parent->_parent;
\n }
\n _node = parent;
\n }
\n return *this;
\n }<\/p>\n
\n \/\/ \u5982\u679c\u6709\u5de6\u5b50\u6811，\u627e\u5de6\u5b50\u6811\u7684\u6700\u53f3\u8282\u70b9
\n \/\/ \u5982\u679c\u6ca1\u6709\u5de6\u5b50\u6811，\u5411\u4e0a\u627e\u7b2c\u4e00\u4e2a\u4e0d\u662f\u7236\u8282\u70b9\u5de6\u5b69\u5b50\u7684\u7956\u5148
\n Self& operator–()
\n {
\n if (_node->_left)
\n {
\n \/\/ \u6709\u5de6\u5b50\u6811 -> \u5de6\u5b50\u6811\u7684\u6700\u53f3\u8282\u70b9
\n Node* right = _node->_left;
\n while (right->_right)
\n {
\n right = right->_right;
\n }
\n _node = right;
\n }
\n else
\n {
\n \/\/ \u6ca1\u5de6\u5b50\u6811 -> \u5f80\u4e0a\u627e
\n \/\/ \u76f4\u5230\u5f53\u524d\u8282\u70b9\u4e0d\u662f\u7236\u8282\u70b9\u7684\u5de6\u5b69\u5b50\u65f6\u505c
\n Node* parent = _node->_parent;
\n Node* cur = _node;
\n while (parent && cur == parent->_left)
\n {
\n cur = cur->_parent;
\n parent = parent->_parent;
\n }
\n _node = parent;
\n }
\n return *this;
\n }
\n};<\/p>\n
\n\/\/ K：\u952e\u7684\u7c7b\u578b，\u7528\u4e8e\u6bd4\u8f83\u67e5\u627e
\n\/\/ T：\u5b58\u7684\u6570\u636e\u7c7b\u578b（set\u4f20Key，map\u4f20pair<const Key, V>）
\n\/\/ KeyOfT：\u4eff\u51fd\u6570\u7c7b，\u4eceT\u4e2d\u53d6\u51fa\u952e\u503cK\u6765\u6bd4\u8f83
\ntemplate<class K, class T, class KeyOfT>
\nstruct RBTree
\n{
\n typedef RBTreeNode<T> Node;<\/p>\n
\n typedef __RBTreeIterator<T, T&, T*> iterator;<\/p>\n
\n \/\/ \u4ece\u6839\u4e00\u76f4\u5f80\u5de6\u8d70\u5230\u5e95
\n iterator begin()
\n {
\n Node* left = _root;
\n while (left && left->_left)
\n {
\n left = left->_left;
\n }
\n return iterator(left);
\n }<\/p>\n
\n iterator end()
\n {
\n return iterator(nullptr);
\n }<\/p>\n
\n \/\/ \u6b65\u9aa4：
\n \/\/ 1. \u6811\u4e3a\u7a7a –> \u76f4\u63a5\u63d2，\u6839\u8282\u70b9\u67d3\u9ed1
\n \/\/ 2. \u6309BST\u89c4\u5219\u627e\u63d2\u5165\u4f4d\u7f6e
\n \/\/ 3. \u63d2\u5165\u65b0\u8282\u70b9，\u9ed8\u8ba4\u7ea2\u8272
\n \/\/ 4. \u7236\u8282\u70b9\u4e3a\u7ea2\u8272 –> \u9700\u8981\u8c03\u6574（\u53d8\u8272\/\u65cb\u8f6c）
\n \/\/ 5. \u6700\u540e\u6839\u8282\u70b9\u5f3a\u5236\u9ed1\u8272
\n \/\/ \u8fd4\u56de\u503c：pair<iterator, bool>（\u8fed\u4ee3\u5668\u6307\u5411\u63d2\u5165\u8282\u70b9，bool\u8868\u793a\u662f\u5426\u6210\u529f）
\n pair<iterator, bool> Insert(const T& data)
\n {
\n KeyOfT kot; \/\/ \u4eff\u51fd\u6570\u5bf9\u8c61，\u7528\u6765\u53d6\u51fa\u952e\u503c<\/p>\n
\n if (_root == nullptr)
\n {
\n _root = new Node(data);
\n _root->_col = BLACK;
\n return make_pair(iterator(_root), true);
\n }<\/p>\n
\n Node* parent = nullptr;
\n Node* cur = _root;
\n while (cur)
\n {
\n if (kot(cur->_data) < kot(data))
\n {
\n parent = cur;
\n cur = cur->_right;
\n }
\n else if (kot(cur->_data) > kot(data))
\n {
\n parent = cur;
\n cur = cur->_left;
\n }
\n else
\n {
\n return make_pair(iterator(cur), false); \/\/ \u952e\u5df2\u5b58\u5728，\u63d2\u5165\u5931\u8d25
\n }
\n }<\/p>\n
\n cur = new Node(data);
\n Node* newnode = cur; \/\/ \u4fdd\u5b58\u65b0\u8282\u70b9\u6307\u9488，\u7528\u4e8e\u8fd4\u56de
\n cur->_col = RED; \/\/ \u65b0\u8282\u70b9\u9ed8\u8ba4\u7ea2\u8272<\/p>\n
\n {
\n parent->_right = cur;
\n }
\n else
\n {
\n parent->_left = cur;
\n }
\n cur->_parent = parent;<\/p>\n
\n \/\/ \u7236\u8282\u70b9\u662f\u7ea2\u8272 –> \u8fdd\u53cd\u4e0d\u80fd\u8fde\u7eed\u7ea2\u89c4\u5219，\u9700\u8981\u5904\u7406
\n \/\/ \u5904\u7406\u65b9\u5f0f：\u770b\u53d4\u53d4\u7684\u989c\u8272
\n \/\/ \u53d4\u53d4\u662f\u7ea2\u8272 –> \u53d8\u8272，\u7ee7\u7eed\u5f80\u4e0a
\n \/\/ \u53d4\u53d4\u662f\u9ed1\u8272\u6216\u4e0d\u5b58\u5728 –> \u65cb\u8f6c + \u53d8\u8272，\u7ed3\u675f
\n while (parent && parent->_col == RED)
\n {
\n Node* grandfater = parent->_parent;
\n assert(grandfater); \/\/ \u7237\u7237\u5fc5\u987b\u5b58\u5728
\n assert(grandfater->_col == BLACK); \/\/ \u7237\u7237\u5fc5\u987b\u662f\u9ed1\u8272<\/p>\n
\n if (parent == grandfater->_left)
\n {
\n Node* uncle = grandfater->_right;<\/p>\n
\n if (uncle && uncle->_col == RED)
\n {
\n parent->_col = uncle->_col = BLACK;
\n grandfater->_col = RED;
\n cur = grandfater;
\n parent = cur->_parent;
\n }
\n \/\/ \u60c5\u51b52+3：\u53d4\u53d4\u4e0d\u5b58\u5728\u6216\u4e3a\u9ed1\u8272 –> \u65cb\u8f6c + \u53d8\u8272
\n else
\n {
\n \/\/ \u60c5\u51b52：\u5de6\u5de6（cur\u662fparent\u7684\u5de6\u5b69\u5b50）–> \u53f3\u5355\u65cb
\n if (cur == parent->_left)
\n {
\n RotateR(grandfater);
\n parent->_col = BLACK;
\n grandfater->_col = RED;
\n }
\n \/\/ \u60c5\u51b53：\u5de6\u53f3（cur\u662fparent\u7684\u53f3\u5b69\u5b50）–> \u5de6\u53f3\u53cc\u65cb
\n else
\n {
\n RotateL(parent);
\n RotateR(grandfater);
\n cur->_col = BLACK;
\n grandfater->_col = RED;
\n }
\n break; \/\/ \u8c03\u6574\u5b8c\u6210，\u9000\u51fa\u5faa\u73af
\n }
\n }
\n \/\/\u60c5\u51b5B：\u7236\u8282\u70b9\u662f\u7237\u7237\u7684\u53f3\u5b69\u5b50（\u5bf9\u79f0）
\n else
\n {
\n Node* uncle = grandfater->_left;<\/p>\n
\n if (uncle && uncle->_col == RED)
\n {
\n parent->_col = uncle->_col = BLACK;
\n grandfater->_col = RED;
\n cur = grandfater;
\n parent = cur->_parent;
\n }
\n \/\/ \u60c5\u51b52+3：\u53d4\u53d4\u4e0d\u5b58\u5728\u6216\u4e3a\u9ed1\u8272 –> \u65cb\u8f6c + \u53d8\u8272
\n else
\n {
\n \/\/ \u60c5\u51b52：\u53f3\u53f3（cur\u662fparent\u7684\u53f3\u5b69\u5b50）\u2192 \u5de6\u5355\u65cb
\n if (cur == parent->_right)
\n {
\n RotateL(grandfater);
\n parent->_col = BLACK;
\n grandfater->_col = RED;
\n }
\n \/\/ \u60c5\u51b53：\u53f3\u5de6（cur\u662fparent\u7684\u5de6\u5b69\u5b50）–> \u53f3\u5de6\u53cc\u65cb
\n else
\n {
\n RotateR(parent);
\n RotateL(grandfater);
\n cur->_col = BLACK;
\n grandfater->_col = RED;
\n }
\n break; \/\/ \u8c03\u6574\u5b8c\u6210，\u9000\u51fa\u5faa\u73af
\n }
\n }
\n }<\/p>\n
\n _root->_col = BLACK;
\n return make_pair(iterator(newnode), true);
\n }<\/p>\n
\n \/\/ \u7528\u6765\u9a8c\u8bc1\u6811\u662f\u5426\u6ee1\u8db3\u4e8c\u53c9\u641c\u7d22\u6811\u6027\u8d28<\/p>\n
\n {
\n _InOrder(_root);
\n cout << endl;
\n }<\/p>\n
\n \/\/ \u68c0\u67e5\u4e09\u9879：
\n \/\/ 1. \u6839\u8282\u70b9\u662f\u9ed1\u8272
\n \/\/ 2. \u6ca1\u6709\u8fde\u7eed\u7684\u7ea2\u8272\u8282\u70b9
\n \/\/ 3. \u6240\u6709\u8def\u5f84\u4e0a\u7684\u9ed1\u8272\u8282\u70b9\u6570\u91cf\u76f8\u540c
\n bool IsBalance()
\n {
\n if (_root == nullptr)
\n {
\n return true;
\n }<\/p>\n
\n if (_root->_col == RED)
\n {
\n cout << "\u6839\u8282\u70b9\u4e0d\u662f\u9ed1\u8272" << endl;
\n return false;
\n }<\/p>\n
\n int benchmark = 0;
\n return PrevCheck(_root, 0, benchmark);
\n }<\/p>\n
\n \/\/ \u53c2\u6570：
\n \/\/ root \u5f53\u524d\u8282\u70b9
\n \/\/ blackNum \u5f53\u524d\u8def\u5f84\u5df2\u7d2f\u8ba1\u7684\u9ed1\u8272\u8282\u70b9\u6570
\n \/\/ benchmark \u57fa\u51c6\u503c（\u6240\u6709\u8def\u5f84\u5fc5\u987b\u76f8\u7b49）
\n \/\/ \u8fd4\u56de\u503c：true\u8868\u793a\u8be5\u8def\u5f84\u5408\u6cd5，false\u8868\u793a\u4e0d\u5408\u6cd5<\/p>\n
\n {
\n \/\/\u8d70\u5230\u7a7a，\u8bf4\u660e\u4e00\u6761\u8def\u5f84\u8d70\u5b8c\u4e86
\n if (root == nullptr)
\n {
\n \/\/ \u7b2c\u4e00\u6b21\u8d70\u5230\u7a7a，\u8bbe\u7f6e\u57fa\u51c6\u503c
\n if (benchmark == 0)
\n {
\n benchmark = blackNum;
\n return true;
\n }
\n \/\/ \u68c0\u67e5\u5f53\u524d\u8def\u5f84\u7684\u9ed1\u8282\u70b9\u6570\u662f\u5426\u7b49\u4e8e\u57fa\u51c6\u503c
\n if (blackNum != benchmark)
\n {
\n cout << "\u67d0\u6761\u8def\u5f84\u9ed1\u8272\u8282\u70b9\u7684\u6570\u91cf\u4e0d\u76f8\u7b49" << endl;
\n return false;
\n }
\n return true;
\n }<\/p>\n
\n if (root->_col == BLACK)
\n {
\n ++blackNum;
\n }<\/p>\n
\n \/\/ \u68c0\u67e5\u7236\u4eb2\u6bd4\u68c0\u67e5\u5b69\u5b50\u66f4\u65b9\u4fbf（\u5b69\u5b50\u53ef\u80fd\u4e0d\u5b58\u5728）
\n if (root->_col == RED && root->_parent->_col == RED)
\n {
\n cout << "\u5b58\u5728\u8fde\u7eed\u7684\u7ea2\u8272\u8282\u70b9" << endl;
\n return false;
\n }<\/p>\n
\n return PrevCheck(root->_left, blackNum, benchmark)
\n && PrevCheck(root->_right, blackNum, benchmark);
\n }<\/p>\n
\n void _InOrder(Node* root)
\n {
\n if (root == nullptr)
\n {
\n return;
\n }
\n _InOrder(root->_left);
\n cout << root->_kv.first << ":" << root->_kv.second << endl;
\n _InOrder(root->_right);
\n }<\/p>\n
\n \/\/ \u9002\u7528\u573a\u666f：\u53f3\u53f3\u578b（parent->_bf == 2，subR->_bf == 1）
\n \/\/ \u65cb\u8f6c\u540e：parent\u548csubR\u7684\u5e73\u8861\u56e0\u5b50\u90fd\u4e3a0
\n void RotateL(Node* parent)
\n {
\n Node* subR = parent->_right;
\n Node* subRL = subR->_left;<\/p>\n
\n parent->_right = subRL;
\n if (subRL)
\n {
\n subRL->_parent = parent;
\n }<\/p>\n
\n subR->_left = parent;
\n parent->_parent = subR;<\/p>\n
\n if (_root == parent)
\n {
\n _root = subR;
\n subR->_parent = nullptr;
\n }
\n else
\n {
\n if (ppNode->_left == parent)
\n {
\n ppNode->_left = subR;
\n }
\n else
\n {
\n ppNode->_right = subR;
\n }
\n subR->_parent = ppNode;
\n }
\n }<\/p>\n
\n \/\/ \u9002\u7528\u573a\u666f：\u5de6\u5de6\u578b（parent->_bf == -2，subL->_bf == -1）
\n \/\/ \u65cb\u8f6c\u540e：parent\u548csubL\u7684\u5e73\u8861\u56e0\u5b50\u90fd\u4e3a0
\n void RotateR(Node* parent)
\n {
\n Node* subL = parent->_left;
\n Node* subLR = subL->_right;<\/p>\n
\n parent->_left = subLR;
\n if (subLR)
\n {
\n subLR->_parent = parent;
\n }<\/p>\n
\n subL->_right = parent;
\n parent->_parent = subL;<\/p>\n
\n if (_root == parent)
\n {
\n _root = subL;
\n subL->_parent = nullptr;
\n }
\n else
\n {
\n if (ppNode->_left == parent)
\n {
\n ppNode->_left = subL;
\n }
\n else
\n {
\n ppNode->_right = subL;
\n }
\n subL->_parent = ppNode;
\n }
\n }<\/p>\n
\n Node* _root = nullptr; \/\/ \u6839\u8282\u70b9\u6307\u9488
\n};<\/p>\n
\n\u5b58\u6570\u636e：\u8282\u70b9\u91cc\u6709\u4e00\u4e2a _data，\u53ef\u4ee5\u5b58 Key（\u7ed9 set \u7528），\u4e5f\u53ef\u4ee5\u5b58 pair<const Key, V>（\u7ed9 map \u7528）<\/p>\n
\n\u4e09.\u7ea2\u9ed1\u6811\u7684\u8fed\u4ee3\u5668<\/h2>\n
1.begin() \u4e0e end() \u7684\u5b9a\u4f4d<\/h3>\n
\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260827083258-6a8ff63acda3f.png\")
<\/p>\n
\n![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260827083259-6a8ff63b12309.png\")
<\/p>\n
\n\/\/ begin() \u8fd4\u56de\u6307\u5411\u6700\u5c0f\u8282\u70b9\u7684\u8fed\u4ee3\u5668
\n\/\/ end() \u8fd4\u56de\u6307\u5411 nullptr \u7684\u8fed\u4ee3\u5668（\u7ed3\u675f\u6807\u5fd7）<\/p>\n
\nstruct RBTree
\n{
\n typedef RBTreeNode<T> Node; \/\/ \u8282\u70b9\u7c7b\u578b\u522b\u540d<\/p>\n
\n typedef _RBTreeIterator<T, T&, T*> iterator; \/\/ \u8fed\u4ee3\u5668\u7c7b\u578b\u522b\u540d<\/p>\n
\n \/\/ \u6700\u5c0f\u8282\u70b9\u5c31\u662f\u6700\u5de6\u4fa7\u7684\u8282\u70b9（\u4e00\u76f4\u5f80\u5de6\u8d70\u5230\u5e95）
\n \/\/ \u65f6\u95f4\u590d\u6742\u5ea6：O(logN)
\n iterator begin()
\n {
\n Node* left = _root;
\n while (left && left->_left) \/\/ \u4e00\u76f4\u5f80\u5de6\u8d70，\u76f4\u5230\u6ca1\u6709\u5de6\u5b69\u5b50
\n {
\n left = left->_left;
\n }
\n return iterator(left); \/\/ \u7528\u6700\u5de6\u8282\u70b9\u6784\u9020\u8fed\u4ee3\u5668<\/p>\n
\n \/\/ \u4e5f\u53ef\u4ee5\u76f4\u63a5\u5199：return left; \u7f16\u8bd1\u5668\u4f1a\u81ea\u52a8\u5c06 Node* \u8f6c\u6362\u4e3a iterator
\n }<\/p>\n
\n \/\/ \u6211\u4eec\u7684\u5b9e\u73b0\u4e2d\u76f4\u63a5\u7528 nullptr \u8868\u793a\u7ed3\u675f
\n \/\/ \u548c STL \u6e90\u7801\u4e2d\u7528\u54e8\u5175\u5934\u8282\u70b9\u4e0d\u540c，\u4f46\u529f\u80fd\u7b49\u4ef7<\/p>\n
\n {
\n return iterator(nullptr); \/\/ nullptr \u4f5c\u4e3a\u7ed3\u675f\u6807\u5fd7
\n \/\/ \u4e5f\u53ef\u4ee5\u7b80\u5199\u4e3a：return nullptr;
\n }<\/p>\n
\n Node* _root = nullptr; \/\/ \u6839\u8282\u70b9
\n};<\/p>\n
\n2.operator++()\u4e0eoperator–() \u00a0<\/h3>\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260827083259-6a8ff63b75113.png\")
<\/p>\n
\n![\"\"](\"2026-08-271wtehm1dwa5.png\")
<\/p>\n
\n![\"\"](\"2026-08-27nhohft4lmbo.png\")
<\/p>\n![\"\"](\"2026-08-27bxaqo0itcvq.png\")
<\/p>\n
\n
\n\/\/ \u6a21\u62df\u5b9e\u73b0 STL \u7684\u8fed\u4ee3\u5668，\u652f\u6301\u4e2d\u5e8f\u904d\u5386（\u6709\u5e8f\u904d\u5386）<\/p>\n
\nstruct __RBTreeIterator
\n{
\n \/\/ \u7c7b\u578b\u522b\u540d
\n typedef RBTreeNode<T> Node; \/\/ \u8282\u70b9\u7c7b\u578b
\n typedef __RBTreeIterator<T, Ref, Ptr> Self; \/\/ \u8fed\u4ee3\u5668\u81ea\u8eab\u7c7b\u578b<\/p>\n
\n \/\/ \u7528\u8282\u70b9\u6307\u9488\u6784\u9020\u8fed\u4ee3\u5668（\u652f\u6301\u9690\u5f0f\u7c7b\u578b\u8f6c\u6362）
\n __RBTreeIterator(Node* node = nullptr) \/\/ \u5e26\u9ed8\u8ba4\u503c，\u65b9\u4fbf\u6784\u9020 end()
\n : _node(node)
\n {}<\/p>\n
\n \/\/ operator* ：\u8fd4\u56de\u8282\u70b9\u6570\u636e\u7684\u5f15\u7528
\n Ref operator*()
\n {
\n return _node->_data;
\n }<\/p>\n
\n Ptr operator->()
\n {
\n return &_node->_data;
\n }<\/p>\n
\n \/\/ \u6bd4\u8f83\u4e24\u4e2a\u8fed\u4ee3\u5668\u662f\u5426\u76f8\u7b49（\u6bd4\u8f83\u8282\u70b9\u6307\u9488\u5373\u53ef）
\n bool operator!=(const Self& s) const
\n {
\n return _node != s._node;
\n }<\/p>\n
\n {
\n return _node == s._node;
\n }<\/p>\n
\n \/\/ \u4e2d\u5e8f\u904d\u5386\u987a\u5e8f：\u5de6\u5b50\u6811 –> \u6839 –> \u53f3\u5b50\u6811<\/p>\n
\n {
\n \/\/ \u60c5\u51b51：\u5f53\u524d\u8282\u70b9\u6709\u53f3\u5b50\u6811
\n \/\/ \u4e0b\u4e00\u4e2a\u8282\u70b9 = \u53f3\u5b50\u6811\u4e2d\u7684\u6700\u5de6\u8282\u70b9（\u6700\u5c0f\u503c）
\n if (_node->_right != nullptr)
\n {
\n Node* left = _node->_right;
\n while (left->_left) \/\/ \u4e00\u76f4\u5f80\u5de6\u8d70
\n {
\n left = left->_left;
\n }
\n _node = left; \/\/ \u627e\u5230\u53f3\u5b50\u6811\u7684\u6700\u5de6\u8282\u70b9
\n }<\/p>\n
\n \/\/ \u9700\u8981\u5411\u4e0a\u56de\u6eaf，\u76f4\u5230\u5f53\u524d\u8282\u70b9\u662f\u5176\u7236\u8282\u70b9\u7684\u5de6\u5b69\u5b50
\n else
\n {
\n Node* parent = _node->_parent;
\n Node* cur = _node;<\/p>\n
\n \/\/ \u6216\u8005 parent \u4e3a\u7a7a（\u8bf4\u660e\u8d70\u5230\u4e86\u6839，++ \u540e\u53d8\u6210 end()）
\n while (parent && cur == parent->_right)
\n {
\n cur = parent;
\n parent = parent->_parent;
\n }
\n _node = parent; \/\/ \u5982\u679c parent \u4e3a\u7a7a，_node \u4e3a nullptr \u2192 end()
\n }<\/p>\n
\n }<\/p>\n
\n \/\/ \u4e2d\u5e8f\u9006\u5e8f\u904d\u5386\u987a\u5e8f：\u53f3\u5b50\u6811 –> \u6839 –> \u5de6\u5b50\u6811（\u5bf9\u79f0）<\/p>\n
\n {
\n \/\/ \u60c5\u51b51：\u5f53\u524d\u8282\u70b9\u6709\u5de6\u5b50\u6811
\n \/\/ \u4e0a\u4e00\u4e2a\u8282\u70b9 = \u5de6\u5b50\u6811\u4e2d\u7684\u6700\u53f3\u8282\u70b9（\u6700\u5927\u503c）
\n if (_node->_left != nullptr)
\n {
\n Node* right = _node->_left;
\n while (right->_right) \/\/ \u4e00\u76f4\u5f80\u53f3\u8d70
\n {
\n right = right->_right;
\n }
\n _node = right; \/\/ \u627e\u5230\u5de6\u5b50\u6811\u7684\u6700\u53f3\u8282\u70b9
\n }<\/p>\n
\n \/\/ \u9700\u8981\u5411\u4e0a\u56de\u6eaf，\u76f4\u5230\u5f53\u524d\u8282\u70b9\u662f\u5176\u7236\u8282\u70b9\u7684\u53f3\u5b69\u5b50
\n else
\n {
\n Node* parent = _node->_parent;
\n Node* cur = _node;<\/p>\n
\n {
\n cur = parent;
\n parent = parent->_parent;
\n }
\n _node = parent;
\n }<\/p>\n
\n }
\n};<\/p>\n
\n\u56db.map\u548cset\u7684\u63d2\u5165<\/h2>\n
\n
\n
\n\/\/ \u8fd4\u56de\u503c：pair<iterator, bool>
\n\/\/ first：\u6307\u5411\u63d2\u5165\u8282\u70b9（\u6216\u5df2\u5b58\u5728\u8282\u70b9）\u7684\u8fed\u4ee3\u5668
\n\/\/ second：true \u8868\u793a\u63d2\u5165\u6210\u529f，false \u8868\u793a\u952e\u5df2\u5b58\u5728<\/p>\n
\n{
\n \/\/ \u60c5\u51b51：\u6811\u4e3a\u7a7a
\n if (_root == nullptr)
\n {
\n _root = new Node(data); \/\/ \u521b\u5efa\u6839\u8282\u70b9
\n _root->_col = BLACK; \/\/ \u6839\u8282\u70b9\u5fc5\u987b\u4e3a\u9ed1\u8272<\/p>\n
\n }<\/p>\n
\n Node* parent = nullptr;
\n Node* cur = _root;<\/p>\n
\n {
\n \/\/ \u7528\u4eff\u51fd\u6570\u53d6\u51fa\u952e\u503c\u8fdb\u884c\u6bd4\u8f83
\n if (KeyOfT()(data) > KeyOfT()(cur->_data)) \/\/ \u63d2\u5165\u952e > \u5f53\u524d\u952e –> \u5f80\u53f3\u8d70
\n {
\n parent = cur;
\n cur = cur->_right;
\n }
\n else if (KeyOfT()(data) < KeyOfT()(cur->_data)) \/\/ \u63d2\u5165\u952e < \u5f53\u524d\u952e –> \u5f80\u5de6\u8d70
\n {
\n parent = cur;
\n cur = cur->_left;
\n }
\n else \/\/ \u952e\u5df2\u5b58\u5728，\u4e0d\u5141\u8bb8\u91cd\u590d\u63d2\u5165
\n {
\n return make_pair(iterator(cur), false);
\n }
\n }<\/p>\n
\n cur = new Node(data); \/\/ \u521b\u5efa\u65b0\u8282\u70b9
\n Node* newnode = cur; \/\/ \u4fdd\u5b58\u65b0\u8282\u70b9\u4f4d\u7f6e（\u7528\u4e8e\u8fd4\u56de）
\n cur->_col = RED; \/\/ \u65b0\u8282\u70b9\u9ed8\u8ba4\u7ea2\u8272<\/p>\n
\n if (KeyOfT()(cur->_data) > KeyOfT()(parent->_data))
\n {
\n parent->_right = cur;
\n }
\n else
\n {
\n parent->_left = cur;
\n }
\n cur->_parent = parent; \/\/ \u8bbe\u7f6e\u7236\u6307\u9488<\/p>\n
\n \/\/ \u7236\u8282\u70b9\u662f\u7ea2\u8272\u65f6\u624d\u9700\u8981\u5904\u7406（\u8fdd\u53cd\u4e0d\u80fd\u8fde\u7eed\u7ea2\u89c4\u5219）
\n while (parent && parent->_col == RED)
\n {
\n Node* grandfater = parent->_parent;
\n assert(grandfater);
\n assert(grandfater->_col == BLACK);<\/p>\n
\n \/\/ g(\u9ed1)
\n \/\/ \/ \\\\
\n \/\/ p(\u7ea2) u(?)
\n if (parent == grandfater->_left)
\n {
\n Node* uncle = grandfater->_right;<\/p>\n
\n if (uncle && uncle->_col == RED)
\n {
\n parent->_col = uncle->_col = BLACK;
\n grandfater->_col = RED;
\n cur = grandfater;
\n parent = cur->_parent;
\n }
\n \/\/ \u5b50\u60c5\u51b52+3：\u53d4\u53d4\u4e0d\u5b58\u5728\u6216\u4e3a\u9ed1\u8272 –> \u65cb\u8f6c + \u53d8\u8272
\n else
\n {
\n \/\/ \u5b50\u60c5\u51b52：\u5de6\u5de6 –> \u53f3\u5355\u65cb
\n \/\/ g
\n \/\/ \/ \\\\
\n \/\/ p u
\n \/\/ \/
\n \/\/ c
\n if (cur == parent->_left)
\n {
\n RotateR(grandfater);
\n parent->_col = BLACK;
\n grandfater->_col = RED;
\n }
\n \/\/ \u5b50\u60c5\u51b53：\u5de6\u53f3 –> \u5de6\u53f3\u53cc\u65cb
\n \/\/ g
\n \/\/ \/ \\\\
\n \/\/ p u
\n \/\/ \\\\
\n \/\/ c
\n else
\n {
\n RotateL(parent);
\n RotateR(grandfater);
\n cur->_col = BLACK;
\n grandfater->_col = RED;
\n }
\n break; \/\/ \u8c03\u6574\u5b8c\u6210，\u9000\u51fa\u5faa\u73af
\n }
\n }<\/p>\n
\n \/\/ g(\u9ed1)
\n \/\/ \/ \\\\
\n \/\/ u(?) p(\u7ea2)
\n else
\n {
\n Node* uncle = grandfater->_left;<\/p>\n
\n if (uncle && uncle->_col == RED)
\n {
\n parent->_col = uncle->_col = BLACK;
\n grandfater->_col = RED;
\n cur = grandfater;
\n parent = cur->_parent;
\n }
\n \/\/ \u5b50\u60c5\u51b52+3：\u53d4\u53d4\u4e0d\u5b58\u5728\u6216\u4e3a\u9ed1\u8272 –> \u65cb\u8f6c + \u53d8\u8272
\n else
\n {
\n \/\/ \u5b50\u60c5\u51b52：\u53f3\u53f3 –> \u5de6\u5355\u65cb
\n \/\/ g
\n \/\/ \/ \\\\
\n \/\/ u p
\n \/\/ \\\\
\n \/\/ c
\n if (cur == parent->_right)
\n {
\n RotateL(grandfater);
\n parent->_col = BLACK;
\n grandfater->_col = RED;
\n }
\n \/\/ \u5b50\u60c5\u51b53：\u53f3\u5de6 –> \u53f3\u5de6\u53cc\u65cb
\n \/\/ g
\n \/\/ \/ \\\\
\n \/\/ u p
\n \/\/ \/
\n \/\/ c
\n else
\n {
\n RotateR(parent);
\n RotateL(grandfater);
\n cur->_col = BLACK;
\n grandfater->_col = RED;
\n }
\n break; \/\/ \u8c03\u6574\u5b8c\u6210，\u9000\u51fa\u5faa\u73af
\n }
\n }
\n }<\/p>\n
\n _root->_col = BLACK;
\n return make_pair(iterator(newnode), true);
\n}<\/p>\n
\n\u4e94.map \u7684\u6a21\u62df\u5b9e\u73b0<\/h2>\n
\n{<\/p>\n
\n class map
\n {<\/p>\n
\n \/\/ \u4f5c\u7528：\u4ece pair<K, V> \u4e2d\u53d6\u51fa\u952e\u503c K
\n \/\/ \u7ea2\u9ed1\u6811\u5728\u6bd4\u8f83\u65f6\u4e0d\u77e5\u9053\u5b58\u7684\u662f Key \u8fd8\u662f pair，\u901a\u8fc7\u8fd9\u4e2a\u4eff\u51fd\u6570\u544a\u8bc9\u5b83\u600e\u4e48\u53d6\u952e<\/p>\n
\n {
\n const K& operator()(const pair<K, V>& kv)
\n {
\n return kv.first; \/\/ \u8fd4\u56de pair \u4e2d\u7684 key
\n }
\n };<\/p>\n
\n \/\/ \u6ce8\u610f：\u8fd9\u91cc\u7684 iterator \u662f\u7ea2\u9ed1\u6811\u7684\u8fed\u4ee3\u5668，map \u76f4\u63a5\u590d\u7528
\n \/\/ typename \u7684\u4f5c\u7528：
\n \/\/ \u7f16\u8bd1\u5230\u8fd9\u91cc\u65f6，\u7ea2\u9ed1\u6811\u6a21\u677f\u53ef\u80fd\u8fd8\u6ca1\u6709\u5b9e\u4f8b\u5316，\u7f16\u8bd1\u5668\u4e0d\u8ba4\u8bc6
\n \/\/ RBTree<K, pair<K, V>, MapKeyOfT>::iterator \u662f\u7c7b\u578b\u8fd8\u662f\u9759\u6001\u6210\u5458？
\n \/\/ \u52a0\u4e0a typename \u544a\u8bc9\u7f16\u8bd1\u5668：\u8fd9\u662f\u4e2a\u7c7b\u578b，\u7b49\u5b9e\u4f8b\u5316\u540e\u518d\u53bb\u67e5\u627e<\/p>\n
\n \/\/ \u76f4\u63a5\u590d\u7528\u7ea2\u9ed1\u6811\u7684 begin()<\/p>\n
\n {
\n return _t.begin();
\n }<\/p>\n
\n \/\/ \u76f4\u63a5\u590d\u7528\u7ea2\u9ed1\u6811\u7684 end()<\/p>\n
\n {
\n return _t.end();
\n }<\/p>\n
\n \/\/ \u76f4\u63a5\u8c03\u7528\u7ea2\u9ed1\u6811\u7684 Insert \u63a5\u53e3
\n \/\/ \u8fd4\u56de\u503c：pair<iterator, bool>
\n \/\/ first：\u6307\u5411\u63d2\u5165\u8282\u70b9（\u6216\u5df2\u5b58\u5728\u8282\u70b9）\u7684\u8fed\u4ee3\u5668
\n \/\/ second：true \u8868\u793a\u63d2\u5165\u6210\u529f，false \u8868\u793a\u952e\u5df2\u5b58\u5728<\/p>\n
\n {
\n return _t.Insert(kv);
\n }<\/p>\n
\n \/\/ \u529f\u80fd：
\n \/\/ 1. key \u5b58\u5728 –> \u8fd4\u56de\u5bf9\u5e94 value \u7684\u5f15\u7528
\n \/\/ 2. key \u4e0d\u5b58\u5728 –> \u63d2\u5165 <key, V()>（V() \u662f\u9ed8\u8ba4\u503c），\u518d\u8fd4\u56de value \u7684\u5f15\u7528
\n \/\/
\n \/\/ \u5b9e\u73b0\u539f\u7406：
\n \/\/ 1. \u7528 make_pair(key, V()) \u6784\u9020\u4e00\u4e2a\u952e\u503c\u5bf9（V() \u662f\u7f3a\u7701\u503c）
\n \/\/ 2. \u8c03\u7528 insert \u5c1d\u8bd5\u63d2\u5165
\n \/\/ 3. \u4e0d\u7ba1\u63d2\u5165\u6210\u529f\u8fd8\u662f\u5931\u8d25，\u90fd\u901a\u8fc7\u8fed\u4ee3\u5668\u53d6\u51fa value \u8fd4\u56de<\/p>\n
\n {
\n \/\/ make_pair(key, V()) \u7528 key \u548c V \u7c7b\u578b\u7684\u9ed8\u8ba4\u503c\u6784\u9020 pair
\n \/\/ V() \u662f\u7f3a\u7701\u503c，\u6bd4\u5982 int \u662f 0，string \u662f ""
\n pair<iterator, bool> ret = insert(make_pair(key, V()));<\/p>\n
\n \/\/ ret.first->second \u53d6\u51fa value，\u8fd4\u56de\u5f15\u7528
\n return ret.first->second;
\n }<\/p>\n
\n \/\/ \u6a21\u677f\u53c2\u6570：
\n \/\/ K：\u952e\u7684\u7c7b\u578b
\n \/\/ pair<K, V>：\u5b58\u50a8\u7684\u6570\u636e\u7c7b\u578b
\n \/\/ MapKeyOfT：\u4eff\u51fd\u6570，\u4ece pair \u4e2d\u53d6\u51fa\u952e<\/p>\n
\n };
\n}<\/p>\n
\n\u516d.set \u7684\u6a21\u62df\u5b9e\u73b0<\/h2>\n
\n{<\/p>\n
\n class set
\n {<\/p>\n
\n \/\/ \u4f5c\u7528：\u4ece K \u4e2d\u53d6\u51fa\u952e\u503c K
\n \/\/ \u5bf9\u4e8e set \u6765\u8bf4，\u6570\u636e\u672c\u8eab K \u5c31\u662f\u952e，\u6240\u4ee5\u76f4\u63a5\u8fd4\u56de key \u672c\u8eab<\/p>\n
\n {
\n const K& operator()(const K& key)
\n {
\n return key; \/\/ set \u4e2d key \u5c31\u662f\u6570\u636e\u672c\u8eab
\n }
\n };<\/p>\n
\n \/\/ \u6ce8\u610f：typename \u7684\u4f5c\u7528\u662f\u544a\u8bc9\u7f16\u8bd1\u5668 iterator \u662f\u4e00\u4e2a\u7c7b\u578b
\n \/\/ \u56e0\u4e3a\u7f16\u8bd1\u5230\u8fd9\u91cc\u65f6，RBTree<K, K, SetKeyOfT> \u53ef\u80fd\u8fd8\u6ca1\u6709\u5b9e\u4f8b\u5316
\n \/\/ \u7f16\u8bd1\u5668\u4e0d\u77e5\u9053 ::iterator \u662f\u7c7b\u578b\u8fd8\u662f\u9759\u6001\u6210\u5458\u53d8\u91cf
\n \/\/ \u52a0\u4e0a typename \u8ba9\u7f16\u8bd1\u5668\u7b49\u5b9e\u4f8b\u5316\u540e\u518d\u53bb\u67e5\u627e<\/p>\n
\n \/\/ \u76f4\u63a5\u590d\u7528\u7ea2\u9ed1\u6811\u7684 begin()
\n iterator begin()
\n {
\n return _t.begin();
\n }<\/p>\n
\n \/\/ \u76f4\u63a5\u590d\u7528\u7ea2\u9ed1\u6811\u7684 end()<\/p>\n
\n {
\n return _t.end();
\n }<\/p>\n
\n \/\/ \u76f4\u63a5\u8c03\u7528\u7ea2\u9ed1\u6811\u7684 Insert \u63a5\u53e3
\n \/\/ \u8fd4\u56de\u503c：pair<iterator, bool>
\n \/\/ first：\u6307\u5411\u63d2\u5165\u8282\u70b9（\u6216\u5df2\u5b58\u5728\u8282\u70b9）\u7684\u8fed\u4ee3\u5668
\n \/\/ second：true \u8868\u793a\u63d2\u5165\u6210\u529f，false \u8868\u793a\u952e\u5df2\u5b58\u5728<\/p>\n
\n {
\n return _t.Insert(key); \/\/ \u5e95\u5c42\u8c03\u7528\u7ea2\u9ed1\u6811\u7684\u63d2\u5165
\n }<\/p>\n
\n \/\/ \u7528\u4e8e\u6253\u5370 set \u4e2d\u7684\u6240\u6709\u5143\u7d20（\u6709\u5e8f）<\/p>\n
\n {
\n _t.InOrder();
\n }<\/p>\n
\n \/\/ \u6a21\u677f\u53c2\u6570：
\n \/\/ K：\u952e\u7684\u7c7b\u578b
\n \/\/ K：\u5b58\u50a8\u7684\u6570\u636e\u7c7b\u578b（set \u4e2d\u6570\u636e\u548c\u952e\u662f\u540c\u4e00\u4e2a\u7c7b\u578b）
\n \/\/ SetKeyOfT：\u4eff\u51fd\u6570，\u4ece\u6570\u636e\u4e2d\u53d6\u51fa\u952e（\u76f4\u63a5\u8fd4\u56de\u81ea\u8eab）
\n RBTree<K, K, SetKeyOfT> _t;
\n };
\n}<\/p>\n","protected":false},"excerpt":{"rendered":"