![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2025\/06\/20250620220604-6855db4c39a4f.gif\")
<\/p>\n<\/p>\n
\u4eba\u751f\u7684\u6001\u5ea6\u662f，\u62b1\u6700\u5927\u7684\u5e0c\u671b，\u5c3d\u6700\u5927\u7684\u52aa\u529b，\u505a\u6700\u574f\u7684\u6253\u7b97\u3002<\/span><\/p>\n \u2014\u2014 \u67cf\u62c9\u56fe \u300a\u7406\u60f3\u56fd\u300b<\/p>\n \u76ee\u5f55<\/p>\n 1\u3001\u7406\u8bba\u57fa\u77f3\u2014\u2014\u6df1\u5ea6\u5256\u6790 BSTree\u3001AVLTree \u4e0e RBTree \u7684\u6982\u5ff5\u533a\u522b<\/p>\n 2\u3001\u8fed\u4ee3\u5668\u673a\u5236\u2014\u2014RBTree \u8fed\u4ee3\u5668\u7684\u67b6\u6784\u4e0e\u5de5\u7a0b\u5b9e\u73b0<\/p>\n 3\u3001\u9ad8\u7ea7\u5bb9\u5668\u8bbe\u8ba1\u2014\u2014Map \u4e0e Set \u7684\u6a21\u5757\u5316\u5c01\u88c5<\/p>\n 3.1 \u6cdb\u578b\u652f\u6301\u589e\u5f3a\u2014\u2014RBTree \u6a21\u677f\u53c2\u6570\u8bbe\u8ba1\u4f18\u5316<\/p>\n 3.2\u00a0Set \u5bb9\u5668\u6784\u5efa\u2014\u2014\u9762\u5411\u96c6\u5408\u64cd\u4f5c\u7684\u4f18\u5316\u8bbe\u8ba1<\/p>\n \u00a03.3\u00a0Map \u5bb9\u5668\u6784\u5efa\u2014\u2014\u9ad8\u6548\u952e\u503c\u5b58\u50a8\u7684\u5c01\u88c5\u5b9e\u73b0<\/p>\n Thanks\u8c22\u8c22\u9605\u8bfb！！！<\/p>\n \u4e3a\u4e86\u5b9e\u73b0 Map \u548c Set \u7684\u5c01\u88c5，\u6211\u4eec\u9996\u5148\u8fdb\u884c\u4e86\u5145\u5206\u7684\u77e5\u8bc6\u50a8\u5907，\u786e\u4fdd\u7406\u89e3\u5e95\u5c42\u6570\u636e\u7ed3\u6784\u7684\u539f\u7406\u4e0e\u5b9e\u73b0\u3002<\/p>\n \u4e8c\u53c9\u641c\u7d22\u6811\u53ca\u5176\u53d8\u79cd<\/span><\/p>\n \u4e3a\u4e86\u6df1\u5165\u7406\u89e3 Map \u548c Set \u7684\u5e95\u5c42\u539f\u7406，\u6211\u4eec\u4ece\u4e8c\u53c9\u641c\u7d22\u6811 (BST)\u5165\u624b\u3002\u4e8c\u53c9\u641c\u7d22\u6811\u5728\u4e8c\u53c9\u6811\u7684\u57fa\u7840\u4e0a\u52a0\u5165\u4e86\u4ee5\u4e0b\u91cd\u8981\u7279\u6027：<\/p>\n \u8fd9\u79cd\u7ed3\u6784\u5728\u5927\u591a\u6570\u60c5\u51b5\u4e0b\u53ef\u4ee5\u6709\u6548\u652f\u6301\u5feb\u901f\u67e5\u627e，\u4f46\u5728\u67d0\u4e9b\u6781\u7aef\u60c5\u51b5\u4e0b（\u4f8b\u5982\u5355\u4fa7\u6811\u5f62\u7ed3\u6784），\u641c\u7d22\u6548\u7387\u4f1a\u9000\u5316\u4e3a O(n)\u3002\u56e0\u6b64，\u6211\u4eec\u5f15\u5165\u4e86\u66f4\u4e3a\u9ad8\u6548\u7684\u5e73\u8861\u4e8c\u53c9\u641c\u7d22\u6811，\u5176\u4e2d AVL\u6811 \u548c \u7ea2\u9ed1\u6811 (RBTree) \u662f\u4e24\u79cd\u7ecf\u5178\u7684\u53d8\u79cd，\u5b83\u4eec\u901a\u8fc7\u4e0d\u540c\u7684\u65b9\u5f0f\u63d0\u9ad8\u4e86\u6027\u80fd\u4e0e\u7a33\u5b9a\u6027\u3002<\/p>\n \u5e73\u8861\u4e8c\u53c9\u641c\u7d22\u6811：AVL \u6811\u4e0e\u7ea2\u9ed1\u6811<\/span><\/p>\n AVL \u6811 \u548c \u7ea2\u9ed1\u6811 \u90fd\u662f\u5728\u4fdd\u6301\u4e8c\u53c9\u641c\u7d22\u6811\u57fa\u672c\u6027\u8d28\u7684\u57fa\u7840\u4e0a，\u901a\u8fc7\u65cb\u8f6c\u4e0e\u91cd\u65b0\u5e73\u8861\u64cd\u4f5c，\u786e\u4fdd\u6811\u7684\u9ad8\u5ea6\u7ef4\u6301\u5728\u4e00\u4e2a\u76f8\u5bf9\u5e73\u8861\u7684\u72b6\u6001，\u4ece\u800c\u4fdd\u8bc1\u4e86\u64cd\u4f5c\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u59cb\u7ec8\u4e3a O(log n)\u3002\u5b83\u4eec\u7684\u51fa\u73b0\u5927\u5927\u63d0\u5347\u4e86\u4e8c\u53c9\u641c\u7d22\u6811\u5728\u5b9e\u9645\u5e94\u7528\u4e2d\u7684\u6027\u80fd\u4e0e\u53ef\u9760\u6027\u3002<\/p>\n AVL \u6811 \u589e\u52a0\u4e86\u4ee5\u4e0b\u7279\u6027：<\/p>\n \u7ea2\u9ed1\u6811 \u5219\u5728\u5176\u57fa\u7840\u4e0a\u5f15\u5165\u4e86\u4ee5\u4e0b\u7279\u70b9：<\/p>\n \u867d\u7136\u7ea2\u9ed1\u6811\u5728\u65cb\u8f6c\u64cd\u4f5c\u7684\u9891\u7387\u4e0a\u4f4e\u4e8e AVL \u6811，\u4f46\u5b83\u901a\u8fc7\u8f83\u5c11\u7684\u65cb\u8f6c\u4fdd\u6301\u6811\u7684\u63a5\u8fd1\u5e73\u8861\u72b6\u6001，\u80fd\u591f\u786e\u4fdd\u826f\u597d\u7684\u6027\u80fd\u3002<\/p>\n Map \u4e0e Set \u7684\u5e95\u5c42\u5b9e\u73b0<\/span><\/p>\n \u7531\u4e8e Map \u548c Set \u5927\u591a\u7528\u4e8e\u9ad8\u6548\u68c0\u7d22，\u6211\u4eec\u9009\u62e9\u4f7f\u7528 \u7ea2\u9ed1\u6811 \u6765\u5b9e\u73b0\u5b83\u4eec\u7684\u5e95\u5c42\u7ed3\u6784\u3002\u7ea2\u9ed1\u6811\u80fd\u591f\u5728\u4fdd\u8bc1\u76f8\u5bf9\u5e73\u8861\u7684\u540c\u65f6，\u786e\u4fdd\u64cd\u4f5c\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a O(log n)，\u975e\u5e38\u9002\u5408\u7528\u4e8e\u5904\u7406\u5927\u91cf\u7684\u952e\u503c\u5bf9\u6570\u636e\u3002<\/p>\n \u5c01\u88c5\u524d\u7684\u8fed\u4ee3\u5668\u5b9e\u73b0<\/span><\/p>\n \u5728\u5c01\u88c5 Map \u548c Set \u4e4b\u524d，\u6211\u4eec\u9700\u8981\u5148\u5b9e\u73b0\u4e00\u4e2a\u5173\u952e\u7684\u7ec4\u4ef6：\u8fed\u4ee3\u5668\u3002\u8fed\u4ee3\u5668\u662f\u904d\u5386\u5bb9\u5668\u5185\u5143\u7d20\u7684\u6838\u5fc3\u5de5\u5177，\u5b83\u63d0\u4f9b\u4e86\u8bbf\u95ee\u548c\u64cd\u4f5c\u5143\u7d20\u7684\u65b9\u5f0f，\u5e76\u4e3a\u6211\u4eec\u540e\u7eed\u7684\u5c01\u88c5\u5de5\u4f5c\u5960\u5b9a\u4e86\u57fa\u7840\u3002<\/p>\n \u8fed\u4ee3\u5668\u662f\u5bb9\u5668\u4e2d\u975e\u5e38\u91cd\u8981\u7684\u7ec4\u6210\u90e8\u5206，\u5b83\u4f7f\u5f97\u6211\u4eec\u53ef\u4ee5\u65b9\u4fbf\u5730\u904d\u5386\u6570\u636e\u3002\u5728 \u7ea2\u9ed1\u6811 \u7684\u5b9e\u73b0\u4e2d，\u589e\u52a0\u8fed\u4ee3\u5668\u652f\u6301\u4e0d\u4ec5\u4ec5\u662f\u4e3a\u4e86\u63d0\u4f9b\u904d\u5386\u7684\u4fbf\u5229，\u66f4\u662f\u4e3a\u4e86\u4f7f\u5f97\u7ea2\u9ed1\u6811\u80fd\u591f\u7b26\u5408\u73b0\u4ee3 C++ \u6cdb\u578b\u7f16\u7a0b\u7684\u8981\u6c42，\u9075\u5faa STL \u4e2d\u5bf9\u8fed\u4ee3\u5668\u7684\u4e25\u683c\u89c4\u8303\u3002<\/p>\n \u9996\u5148，\u8003\u8651\u5230\u8fed\u4ee3\u5668\u7684\u8bbe\u8ba1，\u6211\u4eec\u9700\u8981\u89e3\u51b3\u51e0\u4e2a\u5173\u952e\u95ee\u9898：<\/p>\n \u6cdb\u578b\u7f16\u7a0b\u4e0e\u8fed\u4ee3\u5668\u6846\u67b6 \u8fed\u4ee3\u5668\u7684\u5b9e\u73b0\u8981\u652f\u6301\u6cdb\u578b\u7f16\u7a0b，\u56e0\u6b64\u9700\u8981\u8003\u8651\u5176\u63a5\u53e3\u8bbe\u8ba1，\u786e\u4fdd\u5b83\u80fd\u9002\u5e94\u4e0d\u540c\u7c7b\u578b\u7684\u5bb9\u5668\u7ed3\u6784\u3002\u5177\u4f53\u800c\u8a00，\u6211\u4eec\u9700\u8981\u5b9e\u73b0\u4e00\u4e2a\u9002\u7528\u4e8e\u7ea2\u9ed1\u6811\u7684\u8fed\u4ee3\u5668\u6a21\u677f，\u652f\u6301\u4e0d\u540c\u7c7b\u578b\u7684\u952e\u503c\u5bf9\u5bb9\u5668\u3002<\/p>\n<\/li>\n begin() \u4e0e end() \u7684\u8bbe\u8ba1STL \u660e\u786e\u89c4\u5b9a\u4e86 begin() \u4e0e end() \u65b9\u6cd5\u5206\u522b\u4ee3\u8868\u5bb9\u5668\u7684\u8d77\u59cb\u4f4d\u7f6e\u548c\u7ed3\u675f\u4f4d\u7f6e，\u4e14\u662f\u524d\u95ed\u540e\u5f00\u7684\u533a\u95f4\u3002\u5728\u7ea2\u9ed1\u6811\u7684\u60c5\u51b5\u4e0b，\u7531\u4e8e\u5176\u8282\u70b9\u7ecf\u8fc7\u4e2d\u5e8f\u904d\u5386\u662f\u6709\u5e8f\u7684，begin() \u5e94\u8be5\u6307\u5411\u6811\u7684\u6700\u5c0f\u8282\u70b9（\u5373\u6700\u5de6\u4fa7\u8282\u70b9），end() \u5219\u5e94\u6307\u5411\u4e00\u4e2a\u7a7a\u8282\u70b9，\u5373\u6700\u5927\u8282\u70b9\u7684\u4e0b\u4e00\u4e2a\u4f4d\u7f6e（\u4e3a\u4e86\u7b80\u5316\u8bbe\u8ba1，\u53ef\u4ee5\u8bbe\u4e3a nullptr）\u3002<\/p>\n<\/li>\n operator++() \u548c operator–() \u7684\u5b9e\u73b0 \u5728\u8fed\u4ee3\u5668\u7684\u64cd\u4f5c\u7b26 ++ \u548c — \u5b9e\u73b0\u4e0a，\u9700\u8981\u9075\u5faa\u7ea2\u9ed1\u6811\u7684\u4e2d\u5e8f\u904d\u5386\u987a\u5e8f\u3002\u4e0e\u94fe\u8868\u6216\u6570\u7ec4\u4e0d\u540c，\u7ea2\u9ed1\u6811\u7684\u8282\u70b9\u5e76\u4e0d\u662f\u987a\u5e8f\u6392\u5217\u7684，\u56e0\u6b64\u7b80\u5355\u7684\u6307\u9488\u9012\u589e\u6216\u9012\u51cf\u64cd\u4f5c\u65e0\u6cd5\u6ee1\u8db3\u9700\u6c42\u3002\u6211\u4eec\u9700\u8981\u901a\u8fc7\u6811\u7684\u7ed3\u6784\u6765\u786e\u5b9a\u201c\u4e0b\u4e00\u4e2a\u201d\u6216\u201c\u4e0a\u4e00\u4e2a\u201d\u8282\u70b9\u7684\u4f4d\u7f6e，\u8fd9\u901a\u5e38\u901a\u8fc7\u65cb\u8f6c\u548c\u7236\u8282\u70b9\u5f15\u7528\u6765\u5b9e\u73b0\u3002<\/p>\n<\/li>\n \u5728\u786e\u5b9a\u4e86\u8fed\u4ee3\u5668\u7684\u9700\u6c42\u540e，\u63a5\u4e0b\u6765\u6211\u4eec\u53ef\u4ee5\u7740\u624b\u642d\u5efa\u8fed\u4ee3\u5668\u6846\u67b6\u3002\u8be5\u6846\u67b6\u9700\u8981\u652f\u6301\u4ee5\u4e0b\u529f\u80fd：<\/p>\n \/\/ \u8fed\u4ee3\u5668 \/\/\u5185\u90e8\u662f\u8282\u70b9\u6307\u9488 \/\/\u4e24\u79cd\u6307\u5411\u65b9\u5f0f bool operator!= (const Self& s) }; <\/p>\n ++ \u4e2d\u5e8f\u904d\u5386\u7684\u987a\u5e8f\u662f\u5148\u904d\u5386\u5de6\u8fb9\u518d\u904d\u5386\u5f53\u524d\u8282\u70b9\u6700\u540e\u662f\u53f3\u5b50\u6811\u3002<\/p>\n Self& operator++() \u9002\u5ea6\u7ed3\u5408\u56fe\u50cf\u5206\u6790，\u8fd8\u662f\u8981\u9075\u5faa\u5de6\u6839\u53f3\u7684\u6838\u5fc3\u601d\u7ef4\u51b3\u5b9a\u4e0b\u4e00\u4e2a\u8282\u70b9\u7684\u4f4d\u7f6e<\/span><\/p>\n — \u5012\u4e2d\u5e8f\u904d\u5386 \u53f3 \u6839 \u5de6 \u903b\u8f91\u53d6\u53cd\u5373\u53ef\u00a0<\/span><\/p>\n Self& operator–() \u8fd9\u91cc\u7279\u6b8a\u60c5\u51b5\u662f\u56e0\u4e3a \u6211\u4eec\u8bbe\u7f6e\u7684\u5bb9\u5668\u8fed\u4ee3\u5668 end（） \u4e3a\u7a7a\u6307\u9488 （STTL\u5e93\u662f\u52a0\u4e86\u4e2a\u54e8\u5175\u4f4d\u8282\u70b9）\u4e0d\u53ef\u4ee5\u518d\u8bbf\u95ee\u4e86\u6240\u4ee5\u7279\u6b8a\u5904\u7406\u4e00\u4e0b<\/p>\n \u6211\u4eec\u5148\u6765\u770b\u4e4b\u524d\u5199\u7684\u7ea2\u9ed1\u6811\u7684\u8282\u70b9\u4ee3\u7801：<\/p>\n \/\/ \u8282\u70b9\u7ed3\u6784\u4f53 pair<K, V> _kv; };<\/p>\n \u5728\u5b9e\u73b0 Map \u548c Set \u7684\u5c01\u88c5\u65f6，\u6211\u4eec\u53d1\u73b0，\u5f53\u524d\u7684\u8bbe\u8ba1\u4f7f\u5f97\u6bcf\u4e2a\u7ea2\u9ed1\u6811\u7684\u8282\u70b9\u90fd\u5b58\u50a8\u4e86\u4e00\u4e2a\u56fa\u5b9a\u7684\u6570\u636e\u7c7b\u578b pair<K, V>\u3002\u8fd9\u79cd\u505a\u6cd5\u867d\u7136\u5bf9 Map \u7684\u5b9e\u73b0\u6765\u8bf4\u975e\u5e38\u76f4\u63a5，\u4f46\u5f53\u6211\u4eec\u5c1d\u8bd5\u4e3a Set \u5c01\u88c5\u65f6，\u95ee\u9898\u5c31\u663e\u73b0\u51fa\u6765\u4e86：Set \u4e2d\u7684\u8282\u70b9\u53ea\u9700\u8981\u5b58\u50a8\u952e K，\u800c\u4e0d\u662f\u952e\u503c\u5bf9 pair<K, V>\u3002\u8fd9\u610f\u5473\u7740\u5982\u679c\u6211\u4eec\u7167\u8fd9\u79cd\u65b9\u5f0f\u5b9e\u73b0 Set，\u6211\u4eec\u5c31\u4e0d\u5f97\u4e0d\u91cd\u590d\u7f16\u5199\u4e00\u4efd\u7c7b\u4f3c\u7684\u7ea2\u9ed1\u6811\u4ee3\u7801\u6765\u5904\u7406\u4e0d\u540c\u7684\u6570\u636e\u7ed3\u6784\u3002\u8fd9\u6837\u4e0d\u4ec5\u589e\u52a0\u4e86\u4ee3\u7801\u7684\u5197\u4f59，\u4e5f\u8ba9\u4ee3\u7801\u7684\u7ef4\u62a4\u53d8\u5f97\u4e0d\u591f\u4f18\u96c5\u3002<\/p>\n \u4e3a\u4e86\u66f4\u597d\u5730\u5c01\u88c5 Map \u548c Set，\u6211\u4eec\u53ef\u4ee5\u501f\u9274 STL \u6e90\u7801\u4e2d\u7684\u8bbe\u8ba1\u7406\u5ff5\u3002STL \u4e2d\u901a\u8fc7 \u6a21\u677f\u7f16\u7a0b \u548c \u7c7b\u578b\u7279\u5316 \u7684\u65b9\u5f0f，\u4f7f\u5f97\u540c\u4e00\u4e2a\u6570\u636e\u7ed3\u6784\u80fd\u591f\u652f\u6301\u4e0d\u540c\u7c7b\u578b\u7684\u5bb9\u5668，\u800c\u4e0d\u9700\u8981\u91cd\u590d\u7f16\u5199\u4ee3\u7801\u3002\u8fd9\u79cd\u8bbe\u8ba1\u4e0d\u4ec5\u63d0\u9ad8\u4e86\u4ee3\u7801\u7684\u590d\u7528\u6027，\u8fd8\u4f7f\u5f97\u5bb9\u5668\u80fd\u591f\u7075\u6d3b\u5730\u5904\u7406\u4e0d\u540c\u7684\u6570\u636e\u7c7b\u578b\u3002<\/p>\n STL \u7684\u8bbe\u8ba1\u601d\u8def<\/span><\/p>\n \u5728 STL \u4e2d，Map \u548c Set \u90fd\u662f\u901a\u8fc7\u5e95\u5c42\u7ea2\u9ed1\u6811（\u6216\u5176\u4ed6\u5e73\u8861\u6811）\u6765\u5b9e\u73b0\u7684，\u4f46\u5b83\u4eec\u6709\u4e0d\u540c\u7684\u7ed3\u6784\u548c\u9700\u6c42：<\/p>\n \u7136\u800c，\u5c3d\u7ba1\u5b83\u4eec\u7684\u6570\u636e\u5b58\u50a8\u7ed3\u6784\u4e0d\u540c，STL \u5e76\u6ca1\u6709\u4e3a Map \u548c Set \u5206\u522b\u5199\u4e24\u4efd\u5b8c\u5168\u4e0d\u540c\u7684\u7ea2\u9ed1\u6811\u4ee3\u7801\u3002\u76f8\u53cd，STL \u901a\u8fc7\u5de7\u5999\u7684\u6a21\u677f\u8bbe\u8ba1，\u4f7f\u5f97\u540c\u4e00\u4e2a\u7ea2\u9ed1\u6811\u5b9e\u73b0\u80fd\u591f\u6839\u636e\u9700\u6c42\u7075\u6d3b\u5b58\u50a8\u952e\u503c\u5bf9\u6216\u8005\u4ec5\u5b58\u50a8\u952e\u3002<\/p>\n \u53ef\u4ee5\u770b\u51fa，STL \u6e90\u7801\u4e2d\u7684\u8bbe\u8ba1\u5de7\u5999\u5730\u5229\u7528\u4e86\u6a21\u677f\u7f16\u7a0b，\u6210\u529f\u5730\u5b9e\u73b0\u4e86 Map \u548c Set \u7684\u7edf\u4e00\u5c01\u88c5，\u907f\u514d\u4e86\u4ee3\u7801\u5197\u4f59\u3002<\/p>\n \u9996\u5148，\u6700\u5e95\u5c42\u7684\u7ea2\u9ed1\u6811\u8282\u70b9\u7ed3\u6784\u4f53\u53ea\u4f7f\u7528\u4e86\u4e00\u4e2a\u6a21\u677f\u53c2\u6570 Value，\u8be5\u53c2\u6570\u51b3\u5b9a\u4e86\u8282\u70b9\u4e2d\u5b58\u50a8\u7684\u6570\u636e\u7c7b\u578b\u3002\u4e0a\u5c42\u7684\u7ea2\u9ed1\u6811\u6839\u636e\u63d0\u4f9b\u7684 Value \u7c7b\u578b\u6765\u9009\u62e9\u5177\u4f53\u7684\u6570\u636e\u5b58\u50a8\u7ed3\u6784\u3002\u8fd9\u6837，\u7ea2\u9ed1\u6811\u7684\u5e95\u5c42\u5b9e\u73b0\u4e0d\u9700\u8981\u533a\u5206 Map \u548c Set，\u800c\u662f\u901a\u8fc7\u6a21\u677f\u53c2\u6570 Value \u6765\u7075\u6d3b\u9002\u5e94\u4e0d\u540c\u9700\u6c42\u3002<\/p>\n \u5728\u7ea2\u9ed1\u6811\u7684\u5b9e\u73b0\u4e2d，\u5b58\u5728\u4e09\u4e2a\u5173\u952e\u7684\u6a21\u677f\u53c2\u6570：<\/p>\n \u901a\u8fc7\u5de7\u5999\u7684\u6a21\u677f\u8bbe\u8ba1，\u7ea2\u9ed1\u6811\u5e95\u5c42\u5b9e\u73b0\u53ef\u4ee5\u6839\u636e\u4e0d\u540c\u7684\u9700\u6c42\u4f7f\u7528\u4e0d\u540c\u7684\u6570\u636e\u7ed3\u6784\u6765\u5b58\u50a8：<\/p>\n \u901a\u8fc7\u8fd9\u79cd\u65b9\u5f0f，\u5c3d\u7ba1 Map \u548c Set \u7684\u6a21\u677f\u53c2\u6570\u4e0d\u540c（\u5206\u522b\u662f pair<K, V> \u548c K），\u5b83\u4eec\u5374\u53ef\u4ee5\u5171\u7528\u540c\u4e00\u4efd\u5e95\u5c42\u7ea2\u9ed1\u6811\u4ee3\u7801\u3002\u8fd9\u79cd\u8bbe\u8ba1\u4e0d\u4ec5\u907f\u514d\u4e86\u4ee3\u7801\u91cd\u590d，\u4e5f\u63d0\u9ad8\u4e86\u4ee3\u7801\u7684\u53ef\u7ef4\u62a4\u6027\u548c\u7075\u6d3b\u6027\u3002<\/p>\n \/\/——————————————- enum color T _data; };<\/p>\n \/\/\u9002\u914dmap\u4e0eset \u7684\u7248\u672c Node* _node; Ref operator*() \/\/K \u4e3a\u952e\u503c T \u4e3a\u50a8\u5b58\u7684\u7ed3\u6784 map\u5219\u4e3apair set\u5219\u4e3akey KeyOfValue \u662f\u53d6\u51faKey\u7684\u65b9\u5f0f Iterator begin() } } \/\/\u63d2\u5165\u51fd\u6570 \/\/ \u7236\u4eb2\u662f\u7ea2\u8272 \u51fa\u73b0\u4e86\u8fde\u7eed\u7ea2\u8282\u70b9 \u9700\u8981\u5904\u7406 \u53ef\u80fd\u591a\u6b21\u5904\u7406 while\u5411\u4e0a\u66f4\u65b0 \/\/\u5f80\u4e0a\u66f4\u65b0 \/\/\u5f80\u4e0a\u66f4\u65b0 Iterator find(const K& key) private: void _InOrder(Node* cur) \u6ce8\u610f\u6bd4\u8f83\u65b9\u5f0f\u7edf\u4e00\u6539\u6210\u7c7b\u4f3ckot(_data) < kot(node.data)\u7684\u6837\u5b50\u54e6！！！\u56e0\u4e3amap\u4e0eset\u7684\u53d6\u51fakey\u7684\u65b9\u5f0f\u4e0d\u540c！！！<\/span><\/p>\n Set \u5c01\u88c5\u7684\u5b9e\u73b0<\/span><\/p>\n \u5bf9\u4e8e Set\u00a0\u5c01\u88c5，\u5173\u952e\u662f\u8981\u6839\u636e\u7ea2\u9ed1\u6811\u7684\u5e95\u5c42\u5b9e\u73b0\u8981\u6c42\u63d0\u4f9b\u76f8\u5e94\u7684\u6a21\u677f\u53c2\u6570\u548c\u4eff\u51fd\u6570\u3002<\/p>\n \u6a21\u677f\u53c2\u6570\u4f20\u9012：<\/p>\n Set \u9700\u8981\u6ee1\u8db3 K \u548c V \u7684\u6a21\u677f\u53c2\u6570\u4f20\u9012\u3002K \u8868\u793a\u952e\u7684\u7c7b\u578b，V \u8868\u793a\u503c\u7684\u7c7b\u578b\u3002<\/li>\n \u4eff\u51fd\u6570\u5b9e\u73b0：<\/p>\n \u6211\u4eec\u9700\u8981\u5b9e\u73b0\u4e00\u4e2a\u4eff\u51fd\u6570，\u7528\u4e8e\u4ece\u5b58\u50a8\u7684 \u6a21\u677f\u53c2\u6570 V\u00a0\u4e2d\u63d0\u53d6\u51fa Key\u3002\u56e0\u4e3a\u6bd4\u8f83\u903b\u8f91\u662f\u6bd4\u8f83\u952e\u503c，\u4f46\u662f\u5e95\u5c42\u7ea2\u9ed1\u6811\u5e76\u4e0d\u77e5\u9053T\u6a21\u677f\u53c2\u6570\u662fpair \u8fd8\u662fkey struct SetKeyOfT \u5e95\u5c42\u7ea2\u9ed1\u6811\u7684\u5b9e\u4f8b\u5316：<\/p>\n \u5728 Set\u00a0\u7c7b\u4e2d，\u6211\u4eec\u5b9e\u4f8b\u5316\u4e00\u4e2a\u5e95\u5c42\u7ea2\u9ed1\u6811，\u4f20\u5165\u5bf9\u5e94\u7684\u6a21\u677f\u53c2\u6570 K\u3001const K（\u6ce8\u610f，\u952e\u662f\u4e0d\u53ef\u4fee\u6539\u7684，\u6240\u4ee5\u9700\u8981\u4f7f\u7528 const\u00a0\u6765\u786e\u4fdd\u952e\u662f\u5e38\u91cf），\u4ee5\u53ca SetOfT<\/span>\u00a0\u4eff\u51fd\u6570\u3002\u8fd9\u6837，\u7ea2\u9ed1\u6811\u80fd\u591f\u9002\u5e94 Set\u4e2d\u952e\u503c\u5bf9\u7684\u5b58\u50a8\u65b9\u5f0f\u3002<\/li>\n \u8fed\u4ee3\u5668\u7684\u5b9e\u73b0：<\/p>\n \u5728 Set\u00a0\u7c7b\u4e2d，\u6211\u4eec\u8fd8\u9700\u8981\u5b9e\u73b0\u4e00\u4e2a\u8fed\u4ee3\u5668\u3002\u53ea\u9700\u8981\u63d0\u4f9b\u57fa\u672c\u7684 begin() \u548c end() \u63a5\u53e3，\u76f4\u63a5\u8c03\u7528\u5e95\u5c42\u7ea2\u9ed1\u6811\u7684\u76f8\u5173\u65b9\u6cd5\u5373\u53ef\u3002\u8fed\u4ee3\u5668\u7684\u524d\u8fdb（++）\u548c\u540e\u9000（–）\u64cd\u4f5c\u4ea4\u7ed9\u5e95\u5c42\u7ea2\u9ed1\u6811\u7684\u8fed\u4ee3\u5668\u6765\u5904\u7406\u3002<\/li>\n namespace xc public: iterator begin() iterator end() const_iterator end()const pair<iterator,bool> insert(const K&key) iterator find(const K& key) \u5728\u5b8c\u6210\u4e86\u7ea2\u9ed1\u6811\u7684\u6539\u8fdb\u540e，\u63a5\u4e0b\u6765\u7684\u6b65\u9aa4\u5c31\u76f8\u5bf9\u7b80\u5355\u4e86\u3002\u6211\u4eec\u53ea\u9700\u8981\u5728\u4e0a\u5c42\u5b9e\u73b0 Map \u548c Set \u7684\u5177\u4f53\u5c01\u88c5，\u8c03\u7528\u5e95\u5c42\u7ea2\u9ed1\u6811\u7684\u63a5\u53e3\u5e76\u4f20\u5165\u76f8\u5e94\u7684\u6a21\u677f\u53c2\u6570\u5373\u53ef\u3002<\/p>\n Map \u5c01\u88c5\u7684\u5b9e\u73b0<\/span><\/p>\n \u5bf9\u4e8e Map \u5c01\u88c5，\u5173\u952e\u662f\u8981\u6839\u636e\u7ea2\u9ed1\u6811\u7684\u5e95\u5c42\u5b9e\u73b0\u8981\u6c42\u63d0\u4f9b\u76f8\u5e94\u7684\u6a21\u677f\u53c2\u6570\u548c\u4eff\u51fd\u6570\u3002<\/p>\n \u6a21\u677f\u53c2\u6570\u4f20\u9012：<\/p>\n Map \u9700\u8981\u6ee1\u8db3 K \u548c V \u7684\u6a21\u677f\u53c2\u6570\u4f20\u9012\u3002K \u8868\u793a\u952e\u7684\u7c7b\u578b，V \u8868\u793a\u503c\u7684\u7c7b\u578b\u3002<\/li>\n \u4eff\u51fd\u6570\u5b9e\u73b0：<\/p>\n \u6211\u4eec\u9700\u8981\u5b9e\u73b0\u4e00\u4e2a\u4eff\u51fd\u6570，\u7528\u4e8e\u4ece\u5b58\u50a8\u7684 pair<const K, V> \u4e2d\u63d0\u53d6\u51fa Key\u3002\u56e0\u4e3a\u6bd4\u8f83\u903b\u8f91\u662f\u6bd4\u8f83\u952e\u503c，\u4f46\u662f\u5e95\u5c42\u7ea2\u9ed1\u6811\u5e76\u4e0d\u77e5\u9053T\u6a21\u677f\u53c2\u6570\u662fpair \u8fd8\u662fkey struct MapKeyOfT \u5e95\u5c42\u7ea2\u9ed1\u6811\u7684\u5b9e\u4f8b\u5316：<\/p>\n \u5728 Map \u7c7b\u4e2d，\u6211\u4eec\u5b9e\u4f8b\u5316\u4e00\u4e2a\u5e95\u5c42\u7ea2\u9ed1\u6811，\u4f20\u5165\u5bf9\u5e94\u7684\u6a21\u677f\u53c2\u6570 K\u3001pair<const K, V>（\u6ce8\u610f，\u952e\u662f\u4e0d\u53ef\u4fee\u6539\u7684，\u6240\u4ee5\u9700\u8981\u4f7f\u7528 pair<const K, V> \u6765\u786e\u4fdd\u952e\u662f\u5e38\u91cf），\u4ee5\u53ca MapOfT\u00a0\u4eff\u51fd\u6570\u3002\u8fd9\u6837，\u7ea2\u9ed1\u6811\u80fd\u591f\u9002\u5e94 Map \u4e2d\u952e\u503c\u5bf9\u7684\u5b58\u50a8\u65b9\u5f0f\u3002<\/li>\n \u8fed\u4ee3\u5668\u7684\u5b9e\u73b0：<\/p>\n \u5728 Map \u7c7b\u4e2d，\u6211\u4eec\u8fd8\u9700\u8981\u5b9e\u73b0\u4e00\u4e2a\u8fed\u4ee3\u5668\u3002\u53ea\u9700\u8981\u63d0\u4f9b\u57fa\u672c\u7684 begin() \u548c end() \u63a5\u53e3，\u76f4\u63a5\u8c03\u7528\u5e95\u5c42\u7ea2\u9ed1\u6811\u7684\u76f8\u5173\u65b9\u6cd5\u5373\u53ef\u3002\u8fed\u4ee3\u5668\u7684\u524d\u8fdb（++）\u548c\u540e\u9000（–）\u64cd\u4f5c\u4ea4\u7ed9\u5e95\u5c42\u7ea2\u9ed1\u6811\u7684\u8fed\u4ee3\u5668\u6765\u5904\u7406\u3002<\/li>\n namespace xc public: iterator begin() iterator end() const_iterator end()const pair<iterator, bool> insert(const pair<K, V>& kv) iterator find(const K& key) V& operator[](const K& key) private: \u8fd9\u6837map \u5c01\u88c5\u597d\u4e86，\u6d4b\u8bd5\u4e00\u4e0b！！！<\/span><\/p>\n void test_map() xc::map<string, string>::iterator it = dict.begin(); for (auto &kv : dict) int main() \u53ef\u4ee5\u770b\u5230\u6211\u4eec\u5b9e\u73b0\u4e86 map \u7684\u5173\u952e\u91cd\u8f7d\u51fd\u6570 [ ]\u00a0<\/span> map\u548cset\u4ece\u96f6\u5efa\u7acb\u8d77\u6765\u4e0d\u4ec5\u9700\u8981\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u77e5\u8bc6\u8fd8\u9700\u8981AVL\u6811\u548c\u7ea2\u9ed1\u6811\u7684\u4f7f\u7528！！！\u751a\u81f3\u8fd8\u9700\u8981\u5bf9\u4e8e\u6a21\u7248\u7684\u66f4\u6df1\u7406\u89e3！！！<\/span><\/p>\n \u6587\u7ae0\u6d4f\u89c8\u9605\u8bfb2.9k\u6b21\uff0c\u70b9\u8d5e93\u6b21\uff0c\u6536\u85cf76\u6b21\u3002\u4eba\u751f\u7684\u6001\u5ea6\u662f\uff0c\u62b1\u6700\u5927\u7684\u5e0c\u671b\uff0c\u5c3d\u6700\u5927\u7684\u52aa\u529b\uff0c\u505a\u6700\u574f\u7684\u6253\u7b97\u3002\u2014\u2014 \u67cf\u62c9\u56fe \u300a\u7406\u60f3\u56fd\u300b\u76ee\u5f551\u3001\u7406\u8bba\u57fa\u77f3\u2014\u2014\u6df1\u5ea6\u5256\u6790 BSTree\u3001AVLTree \u4e0e RBTree \u7684\u6982\u5ff5\u533a\u522b2\u3001\u8fed\u4ee3\u5668\u673a\u5236\u2014\u2014RBTree \u8fed\u4ee3\u5668\u7684\u67b6\u6784\u4e0e\u5de5\u7a0b\u5b9e\u73b03\u3001\u9ad8\u7ea7\u5bb9\u5668\u8bbe\u8ba1\u2014\u2014Map \u4e0e Set \u7684\u6a21\u5757\u5316\u5c01\u88c53.1 \u6cdb\u578b\u652f\u6301\u589e\u5f3a\u2014\u2014RBTree \u6a21\u677f\u53c2\u6570\u8bbe\u8ba1\u4f18\u53163.2 Set \u5bb9\u5668\u6784\u5efa\u2014\u2014\u9762\u5411\u96c6\u5408\u64cd\u4f5c\u7684\u4f18\u5316\u8bbe\u8ba1 3.3 Map \u5bb9\u5668\u6784\u5efa\u2014\u2014\u9ad8\u6548\u952e\u503c\u5b58\u50a8\u7684\u5c01\u88c5\u5b9e\u73b0Thanks\u8c22\u8c22\u9605\u8bfb\uff01\uff01\uff01\u4e3a\u4e86\u5b9e\u73b0 Map \u548c Set \u7684\u5c01\u88c5\uff0c\u6211\u4eec\u9996\u5148\u8fdb\u884c\u4e86\u5145\u5206<\/p>\n","protected":false},"author":2,"featured_media":44886,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[55,99,190],"topic":[],"class_list":["post-44890","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-server","tag-c","tag-java","tag-190"],"yoast_head":"\n
\n
\n1\u3001\u7406\u8bba\u57fa\u77f3\u2014\u2014\u6df1\u5ea6\u5256\u6790 BSTree\u3001AVLTree \u4e0e RBTree \u7684\u6982\u5ff5\u533a\u522b<\/h2>\n
\n
\n
\n
\n
2\u3001\u8fed\u4ee3\u5668\u673a\u5236\u2014\u2014RBTree \u8fed\u4ee3\u5668\u7684\u67b6\u6784\u4e0e\u5de5\u7a0b\u5b9e\u73b0<\/h2>\n
\u8fed\u4ee3\u5668\u6846\u67b6\u7684\u642d\u5efa<\/h4>\n
\n
\n\/\/ T \u8868\u793a\u6570\u636e\u7c7b\u578b Ref\u4e3a\u5f15\u7528 Ptr\u4e3a\u6307\u9488
\ntemplate<class T,class Ptr,class Ref>
\nstruct RBTreeIterator
\n{
\n\/\/\u4e3a\u4e86\u65b9\u4fbf\u8c03\u7528，\u6211\u4eec\u91cd\u547d\u540d\u4e00\u4e0b
\ntypedef RBTreeNode<T> Node;
\ntypedef _RBTreeIterator<T, Ref, Ptr> Self;<\/p>\n
\nNode* _node;
\n_RBTreeIterator(Node* node)
\n:_node(node)
\n{}<\/p>\n
\nRef operator*()
\n{
\nreturn _node->_data;
\n}
\nPtr operator&()
\n{
\nreturn &_node->_data;
\n}<\/p>\n
\n{
\nreturn _node != s._node;
\n}
\nbool operator== (const Self& s)
\n{
\nreturn _node == s._node;
\n}<\/p>\n\u8fed\u4ee3\u5668\u7684\u8bbf\u95ee ++ \u548c —<\/h4>\n
\n{
\n\/\/\u9996\u5148，\u80fd\u8bbf\u95ee\u5230\u5f53\u524d\u8282\u70b9\u8bf4\u660e\u5de6\u5b50\u6811\u7684\u90fd\u5df2\u7ecf\u8bbf\u95ee\u8fc7\u5566 \u5de6 \u6839 \u53f3 \u4e2d\u5e8f
\n\/\/\u6240\u4ee5\u5c31\u8981\u5206\u7c7b\u8ba8\u8bba
\n\/\/\u5982\u679c\u53f3\u8fb9\u6709\u5b50\u6811,\u5c31\u8981\u53bb\u5bfb\u627e\u53f3\u5b50\u6811\u7684\u6700\u5de6\u8282\u70b9
\nif (_node->_right)
\n{
\nNode* cur = _node->_right;
\nwhile (cur->_left)
\n{
\ncur = cur->_left;
\n}
\n_node = cur;
\n}
\n\/\/\u5982\u679c\u53f3\u8fb9\u6ca1\u6709\u5b50\u6811\u4e86，\u8bf4\u660e\u8be5\u8282\u70b9\u4ee5\u4e0b\u7684\u5b50\u6811\u90fd\u5df2\u904d\u5386\u5b8c，\u90a3\u4e48\u5c31\u8981\u5411\u4e0a\u8fdb\u884c++
\n\/\/\u627e\u5230\u7956\u5148\u8282\u70b9(\u6ce8\u610f\u7956\u5148\u8282\u70b9\u53f3\u8fb9\u53ef\u80fd\u8fd8\u6ca1\u904d\u5386)
\n\/\/\u6b64\u65f6\u4e5f\u8981\u8fdb\u884c\u5206\u7c7b\u8ba8\u8bba
\nelse
\n{
\nNode* cur = _node;
\nNode* parent = _node->_parent;
\n\/\/ \u5982\u679c _node == parent->_right
\n\/\/\u8bf4\u660eparent\u7684\u8282\u70b9\u5df2\u7ecf\u8bbf\u95ee\u8fc7\u4e86 \u9700\u8981\u5411\u4e0a\u904d\u5386 \u627e\u5230\u6ca1\u6709\u8bbf\u95ee\u7684 \u53ef\u80fd\u4e00\u76f4\u5411\u4e0a \u5bfc\u81f4 parent \u7a7a \u6240\u4ee5\u5224\u65ad\u4e00\u4e0b
\nwhile (parent && cur == parent->_right)
\n{
\ncur = parent;
\nparent = cur->_parent;
\n}
\n_node = parent;
\n}
\nreturn *this;
\n} <\/p>\n
\n{
\nif (_node == nullptr) \/\/ end()
\n{
\n\/\/ –end()，\u7279\u6b8a\u5904\u7406，\u8d70\u5230\u4e2d\u5e8f\u6700\u540e\u2f00\u4e2a\u7ed3\u70b9，\u6574\u68f5\u6811\u7684\u6700\u53f3\u7ed3\u70b9
\nNode* rightMost = _root;
\nwhile (rightMost && rightMost->_right)
\n{
\nrightMost = rightMost->_right;
\n}
\n_node = rightMost;
\n}
\n\/\/\u9996\u5148，\u80fd\u8bbf\u95ee\u5230\u5f53\u524d\u8282\u70b9\u8bf4\u660e\u53f3\u5b50\u6811\u7684\u90fd\u5df2\u7ecf\u8bbf\u95ee\u8fc7\u5566 \u53f3 \u6839 \u5de6 \u5012\u4e2d\u5e8f
\n\/\/\u6240\u4ee5\u5c31\u8981\u5206\u7c7b\u8ba8\u8bba
\n\/\/\u5982\u679c\u5de6\u8fb9\u6709\u5b50\u6811,\u5c31\u8981\u53bb\u5bfb\u627e\u5de6\u5b50\u6811\u7684\u6700\u53f3\u8282\u70b9
\nelse if (_node->_left)
\n{
\nNode* cur = _node->_left;
\nwhile (cur->_right)
\n{
\ncur = cur->_right;
\n}
\n_node = cur;
\n}
\n\/\/\u5982\u679c\u5de6\u8fb9\u6ca1\u6709\u5b50\u6811\u4e86，\u8bf4\u660e\u8be5\u8282\u70b9\u4ee5\u4e0b\u7684\u5b50\u6811\u90fd\u5df2\u904d\u5386\u5b8c，\u90a3\u4e48\u5c31\u8981\u5411\u4e0a\u8fdb\u884c–
\n\/\/\u627e\u5230\u7956\u5148\u8282\u70b9(\u6ce8\u610f\u7956\u5148\u8282\u5de6\u8fb9\u53ef\u80fd\u8fd8\u6ca1\u904d\u5386)
\n\/\/\u6b64\u65f6\u4e5f\u8981\u8fdb\u884c\u5206\u7c7b\u8ba8\u8bba
\nelse
\n{
\nNode* cur = _node;
\nNode* parent = _node->_parent;
\n\/\/ \u5982\u679c _node == parent->_left
\n\/\/\u8bf4\u660eparent\u7684\u8282\u70b9\u5df2\u7ecf\u8bbf\u95ee\u8fc7\u4e86 \u9700\u8981\u5411\u4e0a\u904d\u5386 \u627e\u5230\u6ca1\u6709\u8bbf\u95ee\u7684 \u53ef\u80fd\u4e00\u76f4\u5411\u4e0a \u5bfc\u81f4 parent \u7a7a \u6240\u4ee5\u5224\u65ad\u4e00\u4e0b
\nwhile (parent && cur == parent->_left)
\n{
\ncur = parent;
\nparent = cur->_parent;
\n}
\n_node = parent;
\n}
\nreturn *this;
\n}<\/p>\n![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2025\/06\/20250620220604-6855db4c94bcc.png\")
<\/p>\n3\u3001\u9ad8\u7ea7\u5bb9\u5668\u8bbe\u8ba1\u2014\u2014Map \u4e0e Set \u7684\u6a21\u5757\u5316\u5c01\u88c5<\/h2>\n
3.1 \u6cdb\u578b\u652f\u6301\u589e\u5f3a\u2014\u2014RBTree \u6a21\u677f\u53c2\u6570\u8bbe\u8ba1\u4f18\u5316<\/h3>\n
\ntemplate<class K, class V>
\nstruct RBTreeNode
\n{
\nRBTreeNode<K, V>* _left;
\nRBTreeNode<K, V>* _right;
\nRBTreeNode<K, V>* _parent;<\/p>\n
\ncolor _col;
\nRBTreeNode(pair<K, V> kv)
\n:_left(nullptr),
\n_right(nullptr),
\n_parent(nullptr),
\n_kv(kv)
\n{}<\/p>\n\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2025\/06\/20250620220604-6855db4cec139.png\")
<\/p>\nSTL\u8bbe\u8ba1\u601d\u8def\u89e3\u6790<\/h4>\n
\u7ea2\u9ed1\u6811\u7684\u5173\u952e\u6a21\u677f\u53c2\u6570<\/h4>\n
\u7edf\u4e00\u5c01\u88c5：\u5982\u4f55\u5b9e\u73b0 Map \u4e0e Set \u7684\u5171\u4eab\u5e95\u5c42\u7ea2\u9ed1\u6811<\/h4>\n
\n
\n\/\/—————- \u7ea2\u9ed1\u6811\u5b9e\u73b0 —————–
\n\/\/——————————————-
\n\/\/——– \u9002\u914dmap \u4e0e set \u7684\u8fdb\u9636\u7248\u672c ———–
\n\/\/——————————————-<\/p>\n
\n{
\nBlack,
\nRed
\n};
\n\/\/ \u8282\u70b9\u7ed3\u6784\u4f53
\ntemplate<class T>
\nstruct RBTreeNode
\n{
\nRBTreeNode<T>* _left;
\nRBTreeNode<T>* _right;
\nRBTreeNode<T>* _parent;<\/p>\n
\ncolor _col;
\nRBTreeNode(T data)
\n:_left(nullptr),
\n_right(nullptr),
\n_parent(nullptr),
\n_data(data),
\n_col(Red)
\n{}<\/p>\n
\n\/\/ \u8fed\u4ee3\u5668
\ntemplate<class T , class Ref , class Ptr>
\nstruct _RBTreeIterator
\n{
\ntypedef RBTreeNode<T> Node;
\ntypedef _RBTreeIterator<T, Ref, Ptr> Self;<\/p>\n
\n_RBTreeIterator(Node* node)
\n:_node(node)
\n{}<\/p>\n
\n{
\nreturn _node->_data;
\n}
\nPtr operator&()
\n{
\nreturn &_node->_data;
\n}
\nbool operator!= (const Self& s)
\n{
\nreturn _node != s._node;
\n}
\n\/\/\u8fed\u4ee3\u5668\u7684++ \u4e2d\u5e8f\u904d\u5386\u7684\u987a\u5e8f
\nSelf& operator++()
\n{
\n}
\nSelf& operator–()
\n{
\n}
\n};<\/p>\n
\ntemplate<class K, class T , class KeyOfValue>
\nclass RBTree
\n{
\npublic:
\ntypedef _RBTreeIterator<T, T&, T*> Iterator;
\ntypedef RBTreeNode<T> Node;<\/p>\n
\n{<\/p>\n
\nIterator end()
\n{<\/p>\n
\n\/\/\u53f3\u5355\u65cb
\nvoid RotateR(Node* parent)
\n{
\n}
\n\/\/\u5de6\u53f3\u53cc\u65cb
\nvoid RotateLR(Node* parent)
\n{
\n}
\n\/\/\u53f3\u5de6\u53cc\u65cb
\nvoid RotateRL(Node* parent)
\n{
\n}<\/p>\n
\npair<Iterator,bool> insert(const T& data)
\n{
\nif (_root == nullptr)
\n{
\n_root = new Node(data);
\n_root->_col = BLACK;
\n\/\/return pair<Iterator, bool>(Iterator(_root,_root),true);
\nreturn { Iterator(_root,_root), true };
\n}
\nNode* cur = _root;
\nNode* parent = nullptr;
\n\/\/\u67e5\u627e\u903b\u8f91 cur \u5230\u5bf9\u5e94\u7684\u4f4d\u7f6e\u53bb
\n\/\/ KeyOfT \u53d6\u7b2c\u4e00\u4e2a\u6570\u636e\u6bd4\u8f83
\nKeyOfT kot;
\nwhile (cur)
\n{
\nif (kot(cur->_data) < kot(data))
\n{
\nparent = cur;
\ncur = cur->_right;
\n}
\nelse if (kot(cur->_data) > kot(data))
\n{
\nparent = cur;
\ncur = cur->_left;
\n}
\nelse
\n{
\nreturn { Iterator(cur,_root), false};
\n}
\n}
\ncur = new Node(data);
\nNode* newnode = cur;
\ncur->_col = RED; \/\/\u65b0\u63d2\u5165\u975e\u7a7a\u8282\u70b9 \u4e3a\u7ea2\u8272
\n\/\/ \u8fde\u63a5 prev \u4e0e cur
\nif (kot(parent->_data) > kot(data))
\nparent->_left = cur;
\nelse
\nparent->_right = cur;
\ncur->_parent = parent;<\/p>\n
\nwhile (parent && parent->_col == RED) \/\/\u53ef\u80fd\u4e3a\u7a7a
\n{
\nNode* grandfather = parent->_parent;
\nif (grandfather->_left == parent)
\n{
\n\/\/ g
\n\/\/ p u
\nNode* uncle = grandfather->_right;
\n\/\/ \u53d4\u53d4\u4e0d\u4e3a\u7a7a \u4e14\u7ea2\u8272
\nif (uncle && uncle->_col == RED)
\n{
\n\/\/\u7236\u4eb2\u548c\u53d4\u53d4\u53d8\u9ed1 \u7237\u7237\u53d8\u7ea2 \u53d8\u8272 \u89e3\u51b3\u8fde\u7eed\u7ea2\u8272\u8282\u70b9\u5e76\u4e14\u4fdd\u8bc1 \u8def\u5f84\u9ed1\u8282\u70b9\u6570\u91cf\u4e0d\u53d8
\nparent->_col = uncle->_col = BLACK;
\ngrandfather->_col = RED;<\/p>\n
\ncur = grandfather;
\nparent = cur->_parent;
\n}
\nelse
\n{
\nif (parent->_left == cur) \/\/\u53f3\u5355\u65cb+\u53d8\u8272
\n{\/\/ g
\n\/\/ p u
\n\/\/ c
\nRotateR(grandfather);
\nparent->_col = BLACK;
\ngrandfather->_col = RED;
\n}
\nelse \/\/\u53cc\u65cb\u5904\u7406
\n{
\n\/\/ g
\n\/\/ p u
\n\/\/ c
\nRotateLR(grandfather);
\ncur->_col = BLACK;
\ngrandfather->_col = RED;
\n}
\nbreak;
\n}
\n}
\nelse
\n{
\n\/\/ g
\n\/\/ u p
\nNode* uncle = grandfather->_left;
\n\/\/ \u53d4\u53d4\u4e0d\u4e3a\u7a7a \u4e14\u7ea2\u8272
\nif (uncle && uncle->_col == RED)
\n{
\n\/\/\u7236\u4eb2\u548c\u53d4\u53d4\u53d8\u9ed1 \u7237\u7237\u53d8\u7ea2 \u53d8\u8272 \u89e3\u51b3\u8fde\u7eed\u7ea2\u8272\u8282\u70b9\u5e76\u4e14\u4fdd\u8bc1 \u8def\u5f84\u9ed1\u8282\u70b9\u6570\u91cf\u4e0d\u53d8
\nparent->_col = uncle->_col = BLACK;
\ngrandfather->_col = RED;<\/p>\n
\ncur = grandfather;
\nparent = cur->_parent;
\n}
\nelse
\n{
\nif (parent->_right == cur) \/\/\u5de6\u5355\u65cb+\u53d8\u8272
\n{\/\/ g
\n\/\/ u p
\n\/\/ c
\nRotateL(grandfather);
\nparent->_col = BLACK;
\ngrandfather->_col = RED;
\n}
\nelse \/\/\u53cc\u65cb\u5904\u7406
\n{
\n\/\/ g
\n\/\/ u p
\n\/\/c
\nRotateRL(grandfather);
\ncur->_col = BLACK;
\ngrandfather->_col = RED;
\n}
\nbreak;
\n}
\n}
\n}
\n_root->_col = BLACK;
\nreturn { Iterator(newnode,_root), true};
\n}<\/p>\n
\n{
\nNode* cur = _root;
\nKeyOfT kot;
\nwhile (cur)
\n{
\nif (kot(cur->_data) < key)
\n{
\ncur = cur->_right;
\n}
\nelse if (kot(cur->_data) > key)
\n{
\ncur = cur->_left;
\n}
\nelse
\n{
\nreturn Iterator(cur,_root);
\n}
\n}
\nreturn End();
\n}<\/p>\n
\nvoid _IsBalance(Node* root , int num)
\n{
\n}
\nbool Check(Node* root, int blackNum, const int refNum)
\n{
\n}<\/p>\n
\n{
\n}
\nRBTreeNode<T>* _root = nullptr;
\n};<\/p>\n<\/h3>\n
3.2\u00a0Set \u5bb9\u5668\u6784\u5efa\u2014\u2014\u9762\u5411\u96c6\u5408\u64cd\u4f5c\u7684\u4f18\u5316\u8bbe\u8ba1<\/h3>\n
\n{
\nconst K& operator()(const K&key)
\n{
\nreturn key;
\n}
\n}; <\/p>\n<\/li>\n
\n{
\ntemplate<class K>
\nclass set
\n{
\nstruct SetKeyOfT
\n{
\nconst K& operator()(const K&key)
\n{
\nreturn key;
\n}
\n};<\/p>\n
\ntypedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;
\ntypedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator const_iterator;<\/p>\n
\n{
\nreturn _t.Begin();
\n}<\/p>\n
\n{
\nreturn _t.End();
\n}
\nconst_iterator begin()const
\n{
\nreturn _t.Begin();
\n}<\/p>\n
\n{
\nreturn _t.End();
\n}<\/p>\n
\n{
\nreturn _t.insert(key);
\n}<\/p>\n
\n{
\nreturn _t.find(key);
\n}
\nprivate:
\nRBTree<K, const K, SetKeyOfT> _t;
\n};
\n} <\/p>\n\u00a03.3\u00a0Map \u5bb9\u5668\u6784\u5efa\u2014\u2014\u9ad8\u6548\u952e\u503c\u5b58\u50a8\u7684\u5c01\u88c5\u5b9e\u73b0<\/h3>\n
\n{
\nconst K& operator()(const pair<K, V>& kv)
\n{
\nreturn kv.first;
\n}
\n}; <\/li>\n
\n{
\ntemplate<class K, class V>
\nclass map
\n{
\nstruct MapKeyOfT
\n{
\nconst K& operator()(const pair<K, V>& kv)
\n{
\nreturn kv.first;
\n}
\n};<\/p>\n
\ntypedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;
\ntypedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::ConstIterator const_iterator;<\/p>\n
\n{
\nreturn _t.Begin();
\n}<\/p>\n
\n{
\nreturn _t.End();
\n}
\nconst_iterator begin()const
\n{
\nreturn _t.Begin();
\n}<\/p>\n
\n{
\nreturn _t.End();
\n}<\/p>\n
\n{
\nreturn _t.insert(kv);
\n}<\/p>\n
\n{
\nreturn _t.find(key);
\n}<\/p>\n
\n{
\npair<iterator, bool> ret = insert({ key, V() });
\nreturn ret.first->second;
\n}<\/p>\n
\nRBTree<K, pair<const K, V>, MapKeyOfT> _t;
\n};
\n} <\/p>\n
\n{
\nxc::map<string, string> dict;
\ndict.insert({ "sort", "\u6392\u5e8f" });
\ndict.insert({ "left", "\u5de6\u8fb9" });
\ndict.insert({ "right", "\u53f3\u8fb9" });
\ndict["left"] = "\u5de6\u8fb9，\u5269\u4f59";
\ndict["insert"] = "\u63d2\u5165";
\ndict["string"];<\/p>\n
\nwhile (it != dict.end())
\n{
\n\/\/ \u4e0d\u80fd\u4fee\u6539first，\u53ef\u4ee5\u4fee\u6539second
\n\/\/it->first += 'x';
\nit->second += 'x';
\ncout << it->first << ":" << it->second << endl;
\n++it;
\n}
\ncout << endl;<\/p>\n
\n{
\ncout << kv.first << ":" << kv.second << endl;
\n}
\ncout << endl;
\n}<\/p>\n
\n{
\ntest_map();
\nreturn 0;
\n}<\/p>\n![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2025\/06\/20250620220606-6855db4e26666.png\")
<\/p>\nThanks\u8c22\u8c22\u9605\u8bfb！！！<\/h2>\n","protected":false},"excerpt":{"rendered":"