{"id":4507,"date":"2020-08-14T19:14:31","date_gmt":"2020-08-14T11:14:31","guid":{"rendered":"https:\/\/damogame.cn\/wordpress\/?p=4507"},"modified":"2020-08-14T19:14:31","modified_gmt":"2020-08-14T11:14:31","slug":"%e7%ba%a2%e9%bb%91%e6%a0%91%e5%9b%9b%e4%b9%8b-c%e7%9a%84%e5%ae%9e%e7%8e%b0","status":"publish","type":"post","link":"https:\/\/i007.cc\/wordpress\/archives\/4507","title":{"rendered":"\u7ea2\u9ed1\u6811(\u56db)\u4e4b C++\u7684\u5b9e\u73b0"},"content":{"rendered":"
\u539f\u6587\u5730\u5740<\/a><\/div>\n
\n
\n

 <\/p>\n

\u6982\u8981<\/strong><\/h3>\n

\u524d\u9762\u5206\u522b\u4ecb\u7ecd\u7ea2\u9ed1\u6811\u7684\u7406\u8bba\u77e5\u8bc6<\/a>\u548c\u7ea2\u9ed1\u6811\u7684C\u8bed\u8a00\u5b9e\u73b0<\/a>\u3002\u672c\u7ae0\u662f\u7ea2\u9ed1\u6811\u7684C++\u5b9e\u73b0\uff0c\u82e5\u8bfb\u8005\u5bf9\u7ea2\u9ed1\u6811\u7684\u7406\u8bba\u77e5\u8bc6\u4e0d\u719f\u6089\uff0c\u5efa\u7acb\u5148\u5b66\u4e60\u7ea2\u9ed1\u6811\u7684\u7406\u8bba\u77e5\u8bc6<\/a>\uff0c\u518d\u6765\u5b66\u4e60\u672c\u7ae0\u3002<\/p>\n

\u76ee\u5f55<\/strong>
\n1.\u00a0\u7ea2\u9ed1\u6811\u7684\u4ecb\u7ecd<\/a>
\n2. \u7ea2\u9ed1\u6811\u7684C++\u5b9e\u73b0(\u4ee3\u7801\u8bf4\u660e)<\/a>
\n3. \u7ea2\u9ed1\u6811\u7684C++\u5b9e\u73b0(\u5b8c\u6574\u6e90\u7801)<\/a>
\n4. \u7ea2\u9ed1\u6811\u7684C++\u6d4b\u8bd5\u7a0b\u5e8f<\/a><\/p>\n

\u8f6c\u8f7d\u8bf7\u6ce8\u660e\u51fa\u5904\uff1ahttp:\/\/www.cnblogs.com\/skywang12345\/p\/3624291.html<\/a><\/p>\n

\n

\u66f4\u591a\u5185\u5bb9\uff1a<\/strong>\u6570\u636e\u7ed3\u6784\u4e0e\u7b97\u6cd5\u7cfb\u5217 \u76ee\u5f55<\/a><\/p>\n

(01)\u00a0\u7ea2\u9ed1\u6811(\u4e00)\u4e4b \u539f\u7406\u548c\u7b97\u6cd5\u8be6\u7ec6\u4ecb\u7ecd<\/a>
\n(02)\u00a0\u7ea2\u9ed1\u6811(\u4e8c)\u4e4b C\u8bed\u8a00\u7684\u5b9e\u73b0<\/a>
\n(03)\u00a0\u7ea2\u9ed1\u6811(\u4e09)\u4e4b Linux\u5185\u6838\u4e2d\u7ea2\u9ed1\u6811\u7684\u7ecf\u5178\u5b9e\u73b0
\n<\/a>(04)\u00a0\u7ea2\u9ed1\u6811(\u56db)\u4e4b C++\u7684\u5b9e\u73b0
\n<\/a>(05)\u00a0\u7ea2\u9ed1\u6811(\u4e94)\u4e4b Java\u7684\u5b9e\u73b0<\/a>
\n<\/a>(06)\u00a0\u7ea2\u9ed1\u6811(\u516d)\u4e4b \u53c2\u8003\u8d44\u6599<\/a><\/p>\n

 <\/p>\n

<\/a>\u7ea2\u9ed1\u6811\u7684\u4ecb\u7ecd<\/strong><\/h3>\n

\u7ea2\u9ed1\u6811(Red-Black Tree\uff0c\u7b80\u79f0R-B Tree)\uff0c\u5b83\u4e00\u79cd\u7279\u6b8a\u7684\u4e8c\u53c9\u67e5\u627e\u6811\u3002
\n\u7ea2\u9ed1\u6811\u662f\u7279\u6b8a\u7684\u4e8c\u53c9\u67e5\u627e\u6811\uff0c\u610f\u5473\u7740\u5b83\u6ee1\u8db3\u4e8c\u53c9\u67e5\u627e\u6811\u7684\u7279\u5f81\uff1a\u4efb\u610f\u4e00\u4e2a\u8282\u70b9\u6240\u5305\u542b\u7684\u952e\u503c\uff0c\u5927\u4e8e\u7b49\u4e8e\u5de6\u5b69\u5b50\u7684\u952e\u503c\uff0c\u5c0f\u4e8e\u7b49\u4e8e\u53f3\u5b69\u5b50\u7684\u952e\u503c\u3002
\n\u9664\u4e86\u5177\u5907\u8be5\u7279\u6027\u4e4b\u5916\uff0c\u7ea2\u9ed1\u6811\u8fd8\u5305\u62ec\u8bb8\u591a\u989d\u5916\u7684\u4fe1\u606f\u3002<\/p>\n

\u7ea2\u9ed1\u6811\u7684\u6bcf\u4e2a\u8282\u70b9\u4e0a\u90fd\u6709\u5b58\u50a8\u4f4d\u8868\u793a\u8282\u70b9\u7684\u989c\u8272\uff0c\u989c\u8272\u662f\u7ea2(Red)\u6216\u9ed1(Black)\u3002
\n\u7ea2\u9ed1\u6811\u7684\u7279\u6027:
\n(1) \u6bcf\u4e2a\u8282\u70b9\u6216\u8005\u662f\u9ed1\u8272\uff0c\u6216\u8005\u662f\u7ea2\u8272\u3002
\n(2) \u6839\u8282\u70b9\u662f\u9ed1\u8272\u3002
\n(3) \u6bcf\u4e2a\u53f6\u5b50\u8282\u70b9\u662f\u9ed1\u8272\u3002 [\u6ce8\u610f\uff1a\u8fd9\u91cc\u53f6\u5b50\u8282\u70b9\uff0c\u662f\u6307\u4e3a\u7a7a\u7684\u53f6\u5b50\u8282\u70b9\uff01]
\n(4) \u5982\u679c\u4e00\u4e2a\u8282\u70b9\u662f\u7ea2\u8272\u7684\uff0c\u5219\u5b83\u7684\u5b50\u8282\u70b9\u5fc5\u987b\u662f\u9ed1\u8272\u7684\u3002
\n(5) \u4ece\u4e00\u4e2a\u8282\u70b9\u5230\u8be5\u8282\u70b9\u7684\u5b50\u5b59\u8282\u70b9\u7684\u6240\u6709\u8def\u5f84\u4e0a\u5305\u542b\u76f8\u540c\u6570\u76ee\u7684\u9ed1\u8282\u70b9\u3002<\/p>\n

\u5173\u4e8e\u5b83\u7684\u7279\u6027\uff0c\u9700\u8981\u6ce8\u610f\u7684\u662f\uff1a
\n\u7b2c\u4e00\uff0c\u7279\u6027(3)\u4e2d\u7684\u53f6\u5b50\u8282\u70b9\uff0c\u662f\u53ea\u4e3a\u7a7a(NIL\u6216null)\u7684\u8282\u70b9\u3002
\n\u7b2c\u4e8c\uff0c\u7279\u6027(5)\uff0c\u786e\u4fdd\u6ca1\u6709\u4e00\u6761\u8def\u5f84\u4f1a\u6bd4\u5176\u4ed6\u8def\u5f84\u957f\u51fa\u4fe9\u500d\u3002\u56e0\u800c\uff0c\u7ea2\u9ed1\u6811\u662f\u76f8\u5bf9\u662f\u63a5\u8fd1\u5e73\u8861\u7684\u4e8c\u53c9\u6811\u3002<\/p>\n

\u7ea2\u9ed1\u6811\u793a\u610f\u56fe\u5982\u4e0b\uff1a<\/p>\n

\"\"<\/a><\/p>\n

 <\/p>\n

<\/a>\u7ea2\u9ed1\u6811\u7684C++\u5b9e\u73b0(\u4ee3\u7801\u8bf4\u660e)<\/strong><\/h3>\n

\u7ea2\u9ed1\u6811\u7684\u57fa\u672c\u64cd\u4f5c\u662f\u6dfb\u52a0<\/strong>\u3001\u5220\u9664<\/strong>\u548c\u65cb\u8f6c<\/strong>\u3002\u5728\u5bf9\u7ea2\u9ed1\u6811\u8fdb\u884c\u6dfb\u52a0\u6216\u5220\u9664\u540e\uff0c\u4f1a\u7528\u5230\u65cb\u8f6c\u65b9\u6cd5\u3002\u4e3a\u4ec0\u4e48\u5462\uff1f\u9053\u7406\u5f88\u7b80\u5355\uff0c\u6dfb\u52a0\u6216\u5220\u9664\u7ea2\u9ed1\u6811\u4e2d\u7684\u8282\u70b9\u4e4b\u540e\uff0c\u7ea2\u9ed1\u6811\u5c31\u53d1\u751f\u4e86\u53d8\u5316\uff0c\u53ef\u80fd\u4e0d\u6ee1\u8db3\u7ea2\u9ed1\u6811\u76845\u6761\u6027\u8d28\uff0c\u4e5f\u5c31\u4e0d\u518d\u662f\u4e00\u9897\u7ea2\u9ed1\u6811\u4e86\uff0c\u800c\u662f\u4e00\u9897\u666e\u901a\u7684\u6811\u3002\u800c\u901a\u8fc7\u65cb\u8f6c\uff0c\u53ef\u4ee5\u4f7f\u8fd9\u9897\u6811\u91cd\u65b0\u6210\u4e3a\u7ea2\u9ed1\u6811\u3002\u7b80\u5355\u70b9\u8bf4\uff0c\u65cb\u8f6c\u7684\u76ee\u7684\u662f\u8ba9\u6811\u4fdd\u6301\u7ea2\u9ed1\u6811\u7684\u7279\u6027\u3002
\n\u65cb\u8f6c\u5305\u62ec\u4e24\u79cd\uff1a\u5de6\u65cb \u548c \u53f3\u65cb\u3002\u4e0b\u9762\u5206\u522b\u5bf9\u7ea2\u9ed1\u6811\u7684\u57fa\u672c\u64cd\u4f5c\u8fdb\u884c\u4ecb\u7ecd\u3002<\/p>\n

 <\/p>\n

1. \u57fa\u672c\u5b9a\u4e49<\/strong><\/p>\n

\n
\"\u590d\u5236\u4ee3\u7801\"<\/a><\/span><\/div>\n
enum RBTColor{RED, BLACK};\r\n\r\ntemplate <class T>\r\nclass RBTNode{\r\n    public:\r\n        RBTColor color;    \/\/ \u989c\u8272\r\n        T key;            \/\/ \u5173\u952e\u5b57(\u952e\u503c)\r\n        RBTNode *left;    \/\/ \u5de6\u5b69\u5b50\r\n        RBTNode *right;    \/\/ \u53f3\u5b69\u5b50\r\n        RBTNode *parent; \/\/ \u7236\u7ed3\u70b9\r\n\r\n        RBTNode(T value, RBTColor c, RBTNode *p, RBTNode *l, RBTNode *r):\r\n            key(value),color(c),parent(),left(l),right(r) {}\r\n};\r\n\r\ntemplate <class T>\r\nclass RBTree {\r\n    private:\r\n        RBTNode<T> *mRoot;    \/\/ \u6839\u7ed3\u70b9\r\n\r\n    public:\r\n        RBTree();\r\n        ~RBTree();\r\n\r\n        \/\/ \u524d\u5e8f\u904d\u5386\"\u7ea2\u9ed1\u6811\"\r\n        void preOrder();\r\n        \/\/ \u4e2d\u5e8f\u904d\u5386\"\u7ea2\u9ed1\u6811\"\r\n        void inOrder();\r\n        \/\/ \u540e\u5e8f\u904d\u5386\"\u7ea2\u9ed1\u6811\"\r\n        void postOrder();\r\n\r\n        \/\/ (\u9012\u5f52\u5b9e\u73b0)\u67e5\u627e\"\u7ea2\u9ed1\u6811\"\u4e2d\u952e\u503c\u4e3akey\u7684\u8282\u70b9\r\n        RBTNode<T>* search(T key);\r\n        \/\/ (\u975e\u9012\u5f52\u5b9e\u73b0)\u67e5\u627e\"\u7ea2\u9ed1\u6811\"\u4e2d\u952e\u503c\u4e3akey\u7684\u8282\u70b9\r\n        RBTNode<T>* iterativeSearch(T key);\r\n\r\n        \/\/ \u67e5\u627e\u6700\u5c0f\u7ed3\u70b9\uff1a\u8fd4\u56de\u6700\u5c0f\u7ed3\u70b9\u7684\u952e\u503c\u3002\r\n        T minimum();\r\n        \/\/ \u67e5\u627e\u6700\u5927\u7ed3\u70b9\uff1a\u8fd4\u56de\u6700\u5927\u7ed3\u70b9\u7684\u952e\u503c\u3002\r\n        T maximum();\r\n\r\n        \/\/ \u627e\u7ed3\u70b9(x)\u7684\u540e\u7ee7\u7ed3\u70b9\u3002\u5373\uff0c\u67e5\u627e\"\u7ea2\u9ed1\u6811\u4e2d\u6570\u636e\u503c\u5927\u4e8e\u8be5\u7ed3\u70b9\"\u7684\"\u6700\u5c0f\u7ed3\u70b9\"\u3002\r\n        RBTNode<T>* successor(RBTNode<T> *x);\r\n        \/\/ \u627e\u7ed3\u70b9(x)\u7684\u524d\u9a71\u7ed3\u70b9\u3002\u5373\uff0c\u67e5\u627e\"\u7ea2\u9ed1\u6811\u4e2d\u6570\u636e\u503c\u5c0f\u4e8e\u8be5\u7ed3\u70b9\"\u7684\"\u6700\u5927\u7ed3\u70b9\"\u3002\r\n        RBTNode<T>* predecessor(RBTNode<T> *x);\r\n\r\n        \/\/ \u5c06\u7ed3\u70b9(key\u4e3a\u8282\u70b9\u952e\u503c)\u63d2\u5165\u5230\u7ea2\u9ed1\u6811\u4e2d\r\n        void insert(T key);\r\n\r\n        \/\/ \u5220\u9664\u7ed3\u70b9(key\u4e3a\u8282\u70b9\u952e\u503c)\r\n        void remove(T key);\r\n\r\n        \/\/ \u9500\u6bc1\u7ea2\u9ed1\u6811\r\n        void destroy();\r\n\r\n        \/\/ \u6253\u5370\u7ea2\u9ed1\u6811\r\n        void print();\r\n    private:\r\n        \/\/ \u524d\u5e8f\u904d\u5386\"\u7ea2\u9ed1\u6811\"\r\n        void preOrder(RBTNode<T>* tree) const;\r\n        \/\/ \u4e2d\u5e8f\u904d\u5386\"\u7ea2\u9ed1\u6811\"\r\n        void inOrder(RBTNode<T>* tree) const;\r\n        \/\/ \u540e\u5e8f\u904d\u5386\"\u7ea2\u9ed1\u6811\"\r\n        void postOrder(RBTNode<T>* tree) const;\r\n\r\n        \/\/ (\u9012\u5f52\u5b9e\u73b0)\u67e5\u627e\"\u7ea2\u9ed1\u6811x\"\u4e2d\u952e\u503c\u4e3akey\u7684\u8282\u70b9\r\n        RBTNode<T>* search(RBTNode<T>* x, T key) const;\r\n        \/\/ (\u975e\u9012\u5f52\u5b9e\u73b0)\u67e5\u627e\"\u7ea2\u9ed1\u6811x\"\u4e2d\u952e\u503c\u4e3akey\u7684\u8282\u70b9\r\n        RBTNode<T>* iterativeSearch(RBTNode<T>* x, T key) const;\r\n\r\n        \/\/ \u67e5\u627e\u6700\u5c0f\u7ed3\u70b9\uff1a\u8fd4\u56detree\u4e3a\u6839\u7ed3\u70b9\u7684\u7ea2\u9ed1\u6811\u7684\u6700\u5c0f\u7ed3\u70b9\u3002\r\n        RBTNode<T>* minimum(RBTNode<T>* tree);\r\n        \/\/ \u67e5\u627e\u6700\u5927\u7ed3\u70b9\uff1a\u8fd4\u56detree\u4e3a\u6839\u7ed3\u70b9\u7684\u7ea2\u9ed1\u6811\u7684\u6700\u5927\u7ed3\u70b9\u3002\r\n        RBTNode<T>* maximum(RBTNode<T>* tree);\r\n\r\n        \/\/ \u5de6\u65cb\r\n        void leftRotate(RBTNode<T>* &root, RBTNode<T>* x);\r\n        \/\/ \u53f3\u65cb\r\n        void rightRotate(RBTNode<T>* &root, RBTNode<T>* y);\r\n        \/\/ \u63d2\u5165\u51fd\u6570\r\n        void insert(RBTNode<T>* &root, RBTNode<T>* node);\r\n        \/\/ \u63d2\u5165\u4fee\u6b63\u51fd\u6570\r\n        void insertFixUp(RBTNode<T>* &root, RBTNode<T>* node);\r\n        \/\/ \u5220\u9664\u51fd\u6570\r\n        void remove(RBTNode<T>* &root, RBTNode<T> *node);\r\n        \/\/ \u5220\u9664\u4fee\u6b63\u51fd\u6570\r\n        void removeFixUp(RBTNode<T>* &root, RBTNode<T> *node, RBTNode<T> *parent);\r\n\r\n        \/\/ \u9500\u6bc1\u7ea2\u9ed1\u6811\r\n        void destroy(RBTNode<T>* &tree);\r\n\r\n        \/\/ \u6253\u5370\u7ea2\u9ed1\u6811\r\n        void print(RBTNode<T>* tree, T key, int direction);\r\n\r\n#define rb_parent(r)   ((r)->parent)\r\n#define rb_color(r) ((r)->color)\r\n#define rb_is_red(r)   ((r)->color==RED)\r\n#define rb_is_black(r)  ((r)->color==BLACK)\r\n#define rb_set_black(r)  do { (r)->color = BLACK; } while (0)\r\n#define rb_set_red(r)  do { (r)->color = RED; } while (0)\r\n#define rb_set_parent(r,p)  do { (r)->parent = (p); } while (0)\r\n#define rb_set_color(r,c)  do { (r)->color = (c); } while (0)\r\n};<\/pre>\n
\"\u590d\u5236\u4ee3\u7801\"<\/a><\/span><\/div>\n<\/div>\n
RBTNode\u662f\u7ea2\u9ed1\u6811\u7684\u8282\u70b9\u7c7b\uff0c\u800cRBTree\u5bf9\u5e94\u662f\u7ea2\u9ed1\u6811\u7684\u64cd\u4f5c\u5b9e\u73b0\u7c7b\u3002\u5728RBTree\u4e2d\u5305\u542b\u4e86\u6839\u8282\u70b9mRoot\u548c\u7ea2\u9ed1\u6811\u7684\u76f8\u5173API\u3002
\n\u6ce8\u610f\uff1a(01) \u5728\u5b9e\u73b0\u7ea2\u9ed1\u6811API\u7684\u8fc7\u7a0b\u4e2d\uff0c\u6211\u91cd\u8f7d\u4e86\u8bb8\u591a\u51fd\u6570\u3002\u91cd\u8f7d\u7684\u539f\u56e0\uff0c\u4e00\u662f\u56e0\u4e3a\u6709\u7684API\u662f\u5185\u90e8\u63a5\u53e3\uff0c\u6709\u7684\u662f\u5916\u90e8\u63a5\u53e3\uff1b\u4e8c\u662f\u4e3a\u4e86\u8ba9\u7ed3\u6784\u66f4\u52a0\u6e05\u6670\u3002
\n(02) \u7531\u4e8eC++\u7684\u5b9e\u73b0\u662f\u5728\u4e0a\u4e00\u7bc7\u4ecb\u7ecd\u7684”C\u8bed\u8a00”\u5b9e\u73b0\u57fa\u7840\u4e0a\u79fb\u690d\u800c\u6765\uff0c\u5728\u8be5\u4ee3\u7801\u4e2d\uff0c\u4fdd\u7559\u4e86\u4e00\u4e9bC\u8bed\u8a00\u7684\u7279\u6027\uff1b\u4f8b\u5982(\u5b8f\u5b9a\u4e49)\u3002<\/p>\n
 <\/p>\n
2. \u5de6\u65cb<\/strong><\/p>\n
\"\"<\/a><\/p>\n
\u5bf9x\u8fdb\u884c\u5de6\u65cb\uff0c\u610f\u5473\u7740”\u5c06x\u53d8\u6210\u4e00\u4e2a\u5de6\u8282\u70b9”\u3002<\/p>\n
 <\/p>\n
\u5de6\u65cb\u7684\u5b9e\u73b0\u4ee3\u7801(C++\u8bed\u8a00)<\/p>\n
\n
\"\u590d\u5236\u4ee3\u7801\"<\/a><\/span><\/div>\n
\/* \r\n * \u5bf9\u7ea2\u9ed1\u6811\u7684\u8282\u70b9(x)\u8fdb\u884c\u5de6\u65cb\u8f6c\r\n *\r\n * \u5de6\u65cb\u793a\u610f\u56fe(\u5bf9\u8282\u70b9x\u8fdb\u884c\u5de6\u65cb)\uff1a\r\n *      px                              px\r\n *     \/                               \/\r\n *    x                               y                \r\n *   \/  \\      --(\u5de6\u65cb)-->           \/ \\                #\r\n *  lx   y                          x  ry     \r\n *     \/   \\                       \/  \\\r\n *    ly   ry                     lx  ly  \r\n *\r\n *\r\n *\/\r\ntemplate <class T>\r\nvoid RBTree<T>::leftRotate(RBTNode<T>* &root, RBTNode<T>* x)\r\n{\r\n    \/\/ \u8bbe\u7f6ex\u7684\u53f3\u5b69\u5b50\u4e3ay\r\n    RBTNode<T> *y = x->right;\r\n\r\n    \/\/ \u5c06 \u201cy\u7684\u5de6\u5b69\u5b50\u201d \u8bbe\u4e3a \u201cx\u7684\u53f3\u5b69\u5b50\u201d\uff1b\r\n    \/\/ \u5982\u679cy\u7684\u5de6\u5b69\u5b50\u975e\u7a7a\uff0c\u5c06 \u201cx\u201d \u8bbe\u4e3a \u201cy\u7684\u5de6\u5b69\u5b50\u7684\u7236\u4eb2\u201d\r\n    x->right = y->left;\r\n    if (y->left != NULL)\r\n        y->left->parent = x;\r\n\r\n    \/\/ \u5c06 \u201cx\u7684\u7236\u4eb2\u201d \u8bbe\u4e3a \u201cy\u7684\u7236\u4eb2\u201d\r\n    y->parent = x->parent;\r\n\r\n    if (x->parent == NULL)\r\n    {\r\n        root = y;            \/\/ \u5982\u679c \u201cx\u7684\u7236\u4eb2\u201d \u662f\u7a7a\u8282\u70b9\uff0c\u5219\u5c06y\u8bbe\u4e3a\u6839\u8282\u70b9\r\n    }\r\n    else\r\n    {\r\n        if (x->parent->left == x)\r\n            x->parent->left = y;    \/\/ \u5982\u679c x\u662f\u5b83\u7236\u8282\u70b9\u7684\u5de6\u5b69\u5b50\uff0c\u5219\u5c06y\u8bbe\u4e3a\u201cx\u7684\u7236\u8282\u70b9\u7684\u5de6\u5b69\u5b50\u201d\r\n        else\r\n            x->parent->right = y;    \/\/ \u5982\u679c x\u662f\u5b83\u7236\u8282\u70b9\u7684\u5de6\u5b69\u5b50\uff0c\u5219\u5c06y\u8bbe\u4e3a\u201cx\u7684\u7236\u8282\u70b9\u7684\u5de6\u5b69\u5b50\u201d\r\n    }\r\n    \r\n    \/\/ \u5c06 \u201cx\u201d \u8bbe\u4e3a \u201cy\u7684\u5de6\u5b69\u5b50\u201d\r\n    y->left = x;\r\n    \/\/ \u5c06 \u201cx\u7684\u7236\u8282\u70b9\u201d \u8bbe\u4e3a \u201cy\u201d\r\n    x->parent = y;\r\n}<\/pre>\n
\"\u590d\u5236\u4ee3\u7801\"<\/a><\/span><\/div>\n<\/div>\n
 <\/p>\n
3. \u53f3\u65cb<\/strong><\/p>\n
\"\"<\/a><\/p>\n
\u5bf9y\u8fdb\u884c\u5de6\u65cb\uff0c\u610f\u5473\u7740”\u5c06y\u53d8\u6210\u4e00\u4e2a\u53f3\u8282\u70b9”\u3002<\/p>\n
 <\/p>\n
\u53f3\u65cb\u7684\u5b9e\u73b0\u4ee3\u7801(C++\u8bed\u8a00)<\/p>\n
\n
\"\u590d\u5236\u4ee3\u7801\"<\/a><\/span><\/div>\n
\/* \r\n * \u5bf9\u7ea2\u9ed1\u6811\u7684\u8282\u70b9(y)\u8fdb\u884c\u53f3\u65cb\u8f6c\r\n *\r\n * \u53f3\u65cb\u793a\u610f\u56fe(\u5bf9\u8282\u70b9y\u8fdb\u884c\u5de6\u65cb)\uff1a\r\n *            py                               py\r\n *           \/                                \/\r\n *          y                                x                  \r\n *         \/  \\      --(\u53f3\u65cb)-->            \/  \\                     #\r\n *        x   ry                           lx   y  \r\n *       \/ \\                                   \/ \\                   #\r\n *      lx  rx                                rx  ry\r\n * \r\n *\/\r\ntemplate <class T>\r\nvoid RBTree<T>::rightRotate(RBTNode<T>* &root, RBTNode<T>* y)\r\n{\r\n    \/\/ \u8bbe\u7f6ex\u662f\u5f53\u524d\u8282\u70b9\u7684\u5de6\u5b69\u5b50\u3002\r\n    RBTNode<T> *x = y->left;\r\n\r\n    \/\/ \u5c06 \u201cx\u7684\u53f3\u5b69\u5b50\u201d \u8bbe\u4e3a \u201cy\u7684\u5de6\u5b69\u5b50\u201d\uff1b\r\n    \/\/ \u5982\u679c\"x\u7684\u53f3\u5b69\u5b50\"\u4e0d\u4e3a\u7a7a\u7684\u8bdd\uff0c\u5c06 \u201cy\u201d \u8bbe\u4e3a \u201cx\u7684\u53f3\u5b69\u5b50\u7684\u7236\u4eb2\u201d\r\n    y->left = x->right;\r\n    if (x->right != NULL)\r\n        x->right->parent = y;\r\n\r\n    \/\/ \u5c06 \u201cy\u7684\u7236\u4eb2\u201d \u8bbe\u4e3a \u201cx\u7684\u7236\u4eb2\u201d\r\n    x->parent = y->parent;\r\n\r\n    if (y->parent == NULL) \r\n    {\r\n        root = x;            \/\/ \u5982\u679c \u201cy\u7684\u7236\u4eb2\u201d \u662f\u7a7a\u8282\u70b9\uff0c\u5219\u5c06x\u8bbe\u4e3a\u6839\u8282\u70b9\r\n    }\r\n    else\r\n    {\r\n        if (y == y->parent->right)\r\n            y->parent->right = x;    \/\/ \u5982\u679c y\u662f\u5b83\u7236\u8282\u70b9\u7684\u53f3\u5b69\u5b50\uff0c\u5219\u5c06x\u8bbe\u4e3a\u201cy\u7684\u7236\u8282\u70b9\u7684\u53f3\u5b69\u5b50\u201d\r\n        else\r\n            y->parent->left = x;    \/\/ (y\u662f\u5b83\u7236\u8282\u70b9\u7684\u5de6\u5b69\u5b50) \u5c06x\u8bbe\u4e3a\u201cx\u7684\u7236\u8282\u70b9\u7684\u5de6\u5b69\u5b50\u201d\r\n    }\r\n\r\n    \/\/ \u5c06 \u201cy\u201d \u8bbe\u4e3a \u201cx\u7684\u53f3\u5b69\u5b50\u201d\r\n    x->right = y;\r\n\r\n    \/\/ \u5c06 \u201cy\u7684\u7236\u8282\u70b9\u201d \u8bbe\u4e3a \u201cx\u201d\r\n    y->parent = x;\r\n}<\/pre>\n
\"\u590d\u5236\u4ee3\u7801\"<\/a><\/span><\/div>\n<\/div>\n
 <\/p>\n
4. \u6dfb\u52a0<\/strong><\/p>\n
\u5c06\u4e00\u4e2a\u8282\u70b9\u63d2\u5165\u5230\u7ea2\u9ed1\u6811\u4e2d\uff0c\u9700\u8981\u6267\u884c\u54ea\u4e9b\u6b65\u9aa4\u5462\uff1f\u9996\u5148\uff0c\u5c06\u7ea2\u9ed1\u6811\u5f53\u4f5c\u4e00\u9897\u4e8c\u53c9\u67e5\u627e\u6811\uff0c\u5c06\u8282\u70b9\u63d2\u5165\uff1b\u7136\u540e\uff0c\u5c06\u8282\u70b9\u7740\u8272\u4e3a\u7ea2\u8272\uff1b\u6700\u540e\uff0c\u901a\u8fc7”\u65cb\u8f6c\u548c\u91cd\u65b0\u7740\u8272”\u7b49\u4e00\u7cfb\u5217\u64cd\u4f5c\u6765\u4fee\u6b63\u8be5\u6811\uff0c\u4f7f\u4e4b\u91cd\u65b0\u6210\u4e3a\u4e00\u9897\u7ea2\u9ed1\u6811\u3002\u8be6\u7ec6\u63cf\u8ff0\u5982\u4e0b\uff1a
\n\u7b2c\u4e00\u6b65: \u5c06\u7ea2\u9ed1\u6811\u5f53\u4f5c\u4e00\u9897\u4e8c\u53c9\u67e5\u627e\u6811\uff0c\u5c06\u8282\u70b9\u63d2\u5165\u3002<\/strong>
\n\u7ea2\u9ed1\u6811\u672c\u8eab\u5c31\u662f\u4e00\u9897\u4e8c\u53c9\u67e5\u627e\u6811\uff0c\u5c06\u8282\u70b9\u63d2\u5165\u540e\uff0c\u8be5\u6811\u4ecd\u7136\u662f\u4e00\u9897\u4e8c\u53c9\u67e5\u627e\u6811\u3002\u4e5f\u5c31\u610f\u5473\u7740\uff0c\u6811\u7684\u952e\u503c\u4ecd\u7136\u662f\u6709\u5e8f\u7684\u3002\u6b64\u5916\uff0c\u65e0\u8bba\u662f\u5de6\u65cb\u8fd8\u662f\u53f3\u65cb\uff0c\u82e5\u65cb\u8f6c\u4e4b\u524d\u8fd9\u68f5\u6811\u662f\u4e8c\u53c9\u67e5\u627e\u6811\uff0c\u65cb\u8f6c\u4e4b\u540e\u5b83\u4e00\u5b9a\u8fd8\u662f\u4e8c\u53c9\u67e5\u627e\u6811\u3002\u8fd9\u4e5f\u5c31\u610f\u5473\u7740\uff0c\u4efb\u4f55\u7684\u65cb\u8f6c\u548c\u91cd\u65b0\u7740\u8272\u64cd\u4f5c\uff0c\u90fd\u4e0d\u4f1a\u6539\u53d8\u5b83\u4ecd\u7136\u662f\u4e00\u9897\u4e8c\u53c9\u67e5\u627e\u6811\u7684\u4e8b\u5b9e\u3002
\n\u597d\u5427\uff1f\u90a3\u63a5\u4e0b\u6765\uff0c\u6211\u4eec\u5c31\u6765\u60f3\u65b9\u8bbe\u6cd5\u7684\u65cb\u8f6c\u4ee5\u53ca\u91cd\u65b0\u7740\u8272\uff0c\u4f7f\u8fd9\u9897\u6811\u91cd\u65b0\u6210\u4e3a\u7ea2\u9ed1\u6811\uff01<\/p>\n
\u7b2c\u4e8c\u6b65\uff1a\u5c06\u63d2\u5165\u7684\u8282\u70b9\u7740\u8272\u4e3a”\u7ea2\u8272”\u3002<\/strong>
\n\u4e3a\u4ec0\u4e48\u7740\u8272\u6210\u7ea2\u8272\uff0c\u800c\u4e0d\u662f\u9ed1\u8272\u5462\uff1f\u4e3a\u4ec0\u4e48\u5462\uff1f\u5728\u56de\u7b54\u4e4b\u524d\uff0c\u6211\u4eec\u9700\u8981\u91cd\u65b0\u6e29\u4e60\u4e00\u4e0b\u7ea2\u9ed1\u6811\u7684\u7279\u6027\uff1a
\n(1) \u6bcf\u4e2a\u8282\u70b9\u6216\u8005\u662f\u9ed1\u8272\uff0c\u6216\u8005\u662f\u7ea2\u8272\u3002
\n(2) \u6839\u8282\u70b9\u662f\u9ed1\u8272\u3002
\n(3) \u6bcf\u4e2a\u53f6\u5b50\u8282\u70b9\u662f\u9ed1\u8272\u3002 [\u6ce8\u610f\uff1a\u8fd9\u91cc\u53f6\u5b50\u8282\u70b9\uff0c\u662f\u6307\u4e3a\u7a7a\u7684\u53f6\u5b50\u8282\u70b9\uff01]
\n(4) \u5982\u679c\u4e00\u4e2a\u8282\u70b9\u662f\u7ea2\u8272\u7684\uff0c\u5219\u5b83\u7684\u5b50\u8282\u70b9\u5fc5\u987b\u662f\u9ed1\u8272\u7684\u3002
\n(5) \u4ece\u4e00\u4e2a\u8282\u70b9\u5230\u8be5\u8282\u70b9\u7684\u5b50\u5b59\u8282\u70b9\u7684\u6240\u6709\u8def\u5f84\u4e0a\u5305\u542b\u76f8\u540c\u6570\u76ee\u7684\u9ed1\u8282\u70b9\u3002
\n\u5c06\u63d2\u5165\u7684\u8282\u70b9\u7740\u8272\u4e3a\u7ea2\u8272\uff0c\u4e0d\u4f1a\u8fdd\u80cc”\u7279\u6027(5)”\uff01\u5c11\u8fdd\u80cc\u4e00\u6761\u7279\u6027\uff0c\u5c31\u610f\u5473\u7740\u6211\u4eec\u9700\u8981\u5904\u7406\u7684\u60c5\u51b5\u8d8a\u5c11\u3002\u63a5\u4e0b\u6765\uff0c\u5c31\u8981\u52aa\u529b\u7684\u8ba9\u8fd9\u68f5\u6811\u6ee1\u8db3\u5176\u5b83\u6027\u8d28\u5373\u53ef\uff1b\u6ee1\u8db3\u4e86\u7684\u8bdd\uff0c\u5b83\u5c31\u53c8\u662f\u4e00\u9897\u7ea2\u9ed1\u6811\u4e86\u3002o(\u2229\u2229)o…\u54c8\u54c8<\/p>\n
\u7b2c\u4e09\u6b65: \u901a\u8fc7\u4e00\u7cfb\u5217\u7684\u65cb\u8f6c\u6216\u7740\u8272\u7b49\u64cd\u4f5c\uff0c\u4f7f\u4e4b\u91cd\u65b0\u6210\u4e3a\u4e00\u9897\u7ea2\u9ed1\u6811\u3002<\/strong>
\n\u7b2c\u4e8c\u6b65\u4e2d\uff0c\u5c06\u63d2\u5165\u8282\u70b9\u7740\u8272\u4e3a”\u7ea2\u8272”\u4e4b\u540e\uff0c\u4e0d\u4f1a\u8fdd\u80cc”\u7279\u6027(5)”\u3002\u90a3\u5b83\u5230\u5e95\u4f1a\u8fdd\u80cc\u54ea\u4e9b\u7279\u6027\u5462\uff1f
\n\u5bf9\u4e8e”\u7279\u6027(1)”\uff0c\u663e\u7136\u4e0d\u4f1a\u8fdd\u80cc\u4e86\u3002\u56e0\u4e3a\u6211\u4eec\u5df2\u7ecf\u5c06\u5b83\u6d82\u6210\u7ea2\u8272\u4e86\u3002
\n\u5bf9\u4e8e”\u7279\u6027(2)”\uff0c\u663e\u7136\u4e5f\u4e0d\u4f1a\u8fdd\u80cc\u3002\u5728\u7b2c\u4e00\u6b65\u4e2d\uff0c\u6211\u4eec\u662f\u5c06\u7ea2\u9ed1\u6811\u5f53\u4f5c\u4e8c\u53c9\u67e5\u627e\u6811\uff0c\u7136\u540e\u6267\u884c\u7684\u63d2\u5165\u64cd\u4f5c\u3002\u800c\u6839\u636e\u4e8c\u53c9\u67e5\u627e\u6570\u7684\u7279\u70b9\uff0c\u63d2\u5165\u64cd\u4f5c\u4e0d\u4f1a\u6539\u53d8\u6839\u8282\u70b9\u3002\u6240\u4ee5\uff0c\u6839\u8282\u70b9\u4ecd\u7136\u662f\u9ed1\u8272\u3002
\n\u5bf9\u4e8e”\u7279\u6027(3)”\uff0c\u663e\u7136\u4e0d\u4f1a\u8fdd\u80cc\u4e86\u3002\u8fd9\u91cc\u7684\u53f6\u5b50\u8282\u70b9\u662f\u6307\u7684\u7a7a\u53f6\u5b50\u8282\u70b9\uff0c\u63d2\u5165\u975e\u7a7a\u8282\u70b9\u5e76\u4e0d\u4f1a\u5bf9\u5b83\u4eec\u9020\u6210\u5f71\u54cd\u3002
\n\u5bf9\u4e8e”\u7279\u6027(4)”\uff0c\u662f\u6709\u53ef\u80fd\u8fdd\u80cc\u7684\uff01
\n\u90a3\u63a5\u4e0b\u6765\uff0c\u60f3\u529e\u6cd5\u4f7f\u4e4b”\u6ee1\u8db3\u7279\u6027(4)”\uff0c\u5c31\u53ef\u4ee5\u5c06\u6811\u91cd\u65b0\u6784\u9020\u6210\u7ea2\u9ed1\u6811\u4e86\u3002<\/p>\n
\u6dfb\u52a0\u64cd\u4f5c\u7684\u5b9e\u73b0\u4ee3\u7801(C++\u8bed\u8a00)<\/p>\n
\n
\"\u590d\u5236\u4ee3\u7801\"<\/a><\/span><\/div>\n
\/* \r\n * \u5c06\u7ed3\u70b9\u63d2\u5165\u5230\u7ea2\u9ed1\u6811\u4e2d\r\n *\r\n * \u53c2\u6570\u8bf4\u660e\uff1a\r\n *     root \u7ea2\u9ed1\u6811\u7684\u6839\u7ed3\u70b9\r\n *     node \u63d2\u5165\u7684\u7ed3\u70b9        \/\/ \u5bf9\u5e94\u300a\u7b97\u6cd5\u5bfc\u8bba\u300b\u4e2d\u7684node\r\n *\/\r\ntemplate <class T>\r\nvoid RBTree<T>::insert(RBTNode<T>* &root, RBTNode<T>* node)\r\n{\r\n    RBTNode<T> *y = NULL;\r\n    RBTNode<T> *x = root;\r\n\r\n    \/\/ 1. \u5c06\u7ea2\u9ed1\u6811\u5f53\u4f5c\u4e00\u9897\u4e8c\u53c9\u67e5\u627e\u6811\uff0c\u5c06\u8282\u70b9\u6dfb\u52a0\u5230\u4e8c\u53c9\u67e5\u627e\u6811\u4e2d\u3002\r\n    while (x != NULL)\r\n    {\r\n        y = x;\r\n        if (node->key < x->key)\r\n            x = x->left;\r\n        else\r\n            x = x->right;\r\n    }\r\n\r\n    node->parent = y;\r\n    if (y!=NULL)\r\n    {\r\n        if (node->key < y->key)\r\n            y->left = node;\r\n        else\r\n            y->right = node;\r\n    }\r\n    else\r\n        root = node;\r\n\r\n    \/\/ 2. \u8bbe\u7f6e\u8282\u70b9\u7684\u989c\u8272\u4e3a\u7ea2\u8272\r\n    node->color = RED;\r\n\r\n    \/\/ 3. \u5c06\u5b83\u91cd\u65b0\u4fee\u6b63\u4e3a\u4e00\u9897\u4e8c\u53c9\u67e5\u627e\u6811\r\n    insertFixUp(root, node);\r\n}\r\n\r\n\/* \r\n * \u5c06\u7ed3\u70b9(key\u4e3a\u8282\u70b9\u952e\u503c)\u63d2\u5165\u5230\u7ea2\u9ed1\u6811\u4e2d\r\n *\r\n * \u53c2\u6570\u8bf4\u660e\uff1a\r\n *     tree \u7ea2\u9ed1\u6811\u7684\u6839\u7ed3\u70b9\r\n *     key \u63d2\u5165\u7ed3\u70b9\u7684\u952e\u503c\r\n *\/\r\ntemplate <class T>\r\nvoid RBTree<T>::insert(T key)\r\n{\r\n    RBTNode<T> *z=NULL;\r\n\r\n    \/\/ \u5982\u679c\u65b0\u5efa\u7ed3\u70b9\u5931\u8d25\uff0c\u5219\u8fd4\u56de\u3002\r\n    if ((z=new RBTNode<T>(key,BLACK,NULL,NULL,NULL)) == NULL)\r\n        return ;\r\n\r\n    insert(mRoot, z);\r\n}<\/pre>\n
\"\u590d\u5236\u4ee3\u7801\"<\/a><\/span><\/div>\n<\/div>\n
\u5185\u90e8\u63a5\u53e3<\/strong>\u00a0— insert(root, node)\u7684\u4f5c\u7528\u662f\u5c06”node”\u8282\u70b9\u63d2\u5165\u5230\u7ea2\u9ed1\u6811\u4e2d\u3002\u5176\u4e2d\uff0croot\u662f\u6839\uff0cnode\u662f\u88ab\u63d2\u5165\u8282\u70b9\u3002
\n\u5916\u90e8\u63a5\u53e3<\/strong>\u00a0— insert(key)\u7684\u4f5c\u7528\u662f\u5c06”key”\u6dfb\u52a0\u5230\u7ea2\u9ed1\u6811\u4e2d\u3002<\/p>\n
\u6dfb\u52a0\u4fee\u6b63\u64cd\u4f5c\u7684\u5b9e\u73b0\u4ee3\u7801(C++\u8bed\u8a00)<\/p>\n
\n
\"\u590d\u5236\u4ee3\u7801\"<\/a><\/span><\/div>\n
\/*\r\n * \u7ea2\u9ed1\u6811\u63d2\u5165\u4fee\u6b63\u51fd\u6570\r\n *\r\n * \u5728\u5411\u7ea2\u9ed1\u6811\u4e2d\u63d2\u5165\u8282\u70b9\u4e4b\u540e(\u5931\u53bb\u5e73\u8861)\uff0c\u518d\u8c03\u7528\u8be5\u51fd\u6570\uff1b\r\n * \u76ee\u7684\u662f\u5c06\u5b83\u91cd\u65b0\u5851\u9020\u6210\u4e00\u9897\u7ea2\u9ed1\u6811\u3002\r\n *\r\n * \u53c2\u6570\u8bf4\u660e\uff1a\r\n *     root \u7ea2\u9ed1\u6811\u7684\u6839\r\n *     node \u63d2\u5165\u7684\u7ed3\u70b9        \/\/ \u5bf9\u5e94\u300a\u7b97\u6cd5\u5bfc\u8bba\u300b\u4e2d\u7684z\r\n *\/\r\ntemplate <class T>\r\nvoid RBTree<T>::insertFixUp(RBTNode<T>* &root, RBTNode<T>* node)\r\n{\r\n    RBTNode<T> *parent, *gparent;\r\n\r\n    \/\/ \u82e5\u201c\u7236\u8282\u70b9\u5b58\u5728\uff0c\u5e76\u4e14\u7236\u8282\u70b9\u7684\u989c\u8272\u662f\u7ea2\u8272\u201d\r\n    while ((parent = rb_parent(node)) && rb_is_red(parent))\r\n    {\r\n        gparent = rb_parent(parent);\r\n\r\n        \/\/\u82e5\u201c\u7236\u8282\u70b9\u201d\u662f\u201c\u7956\u7236\u8282\u70b9\u7684\u5de6\u5b69\u5b50\u201d\r\n        if (parent == gparent->left)\r\n        {\r\n            \/\/ Case 1\u6761\u4ef6\uff1a\u53d4\u53d4\u8282\u70b9\u662f\u7ea2\u8272\r\n            {\r\n                RBTNode<T> *uncle = gparent->right;\r\n                if (uncle && rb_is_red(uncle))\r\n                {\r\n                    rb_set_black(uncle);\r\n                    rb_set_black(parent);\r\n                    rb_set_red(gparent);\r\n                    node = gparent;\r\n                    continue;\r\n                }\r\n            }\r\n\r\n            \/\/ Case 2\u6761\u4ef6\uff1a\u53d4\u53d4\u662f\u9ed1\u8272\uff0c\u4e14\u5f53\u524d\u8282\u70b9\u662f\u53f3\u5b69\u5b50\r\n            if (parent->right == node)\r\n            {\r\n                RBTNode<T> *tmp;\r\n                leftRotate(root, parent);\r\n                tmp = parent;\r\n                parent = node;\r\n                node = tmp;\r\n            }\r\n\r\n            \/\/ Case 3\u6761\u4ef6\uff1a\u53d4\u53d4\u662f\u9ed1\u8272\uff0c\u4e14\u5f53\u524d\u8282\u70b9\u662f\u5de6\u5b69\u5b50\u3002\r\n            rb_set_black(parent);\r\n            rb_set_red(gparent);\r\n            rightRotate(root, gparent);\r\n        } \r\n        else\/\/\u82e5\u201cz\u7684\u7236\u8282\u70b9\u201d\u662f\u201cz\u7684\u7956\u7236\u8282\u70b9\u7684\u53f3\u5b69\u5b50\u201d\r\n        {\r\n            \/\/ Case 1\u6761\u4ef6\uff1a\u53d4\u53d4\u8282\u70b9\u662f\u7ea2\u8272\r\n            {\r\n                RBTNode<T> *uncle = gparent->left;\r\n                if (uncle && rb_is_red(uncle))\r\n                {\r\n                    rb_set_black(uncle);\r\n                    rb_set_black(parent);\r\n                    rb_set_red(gparent);\r\n                    node = gparent;\r\n                    continue;\r\n                }\r\n            }\r\n\r\n            \/\/ Case 2\u6761\u4ef6\uff1a\u53d4\u53d4\u662f\u9ed1\u8272\uff0c\u4e14\u5f53\u524d\u8282\u70b9\u662f\u5de6\u5b69\u5b50\r\n            if (parent->left == node)\r\n            {\r\n                RBTNode<T> *tmp;\r\n                rightRotate(root, parent);\r\n                tmp = parent;\r\n                parent = node;\r\n                node = tmp;\r\n            }\r\n\r\n            \/\/ Case 3\u6761\u4ef6\uff1a\u53d4\u53d4\u662f\u9ed1\u8272\uff0c\u4e14\u5f53\u524d\u8282\u70b9\u662f\u53f3\u5b69\u5b50\u3002\r\n            rb_set_black(parent);\r\n            rb_set_red(gparent);\r\n            leftRotate(root, gparent);\r\n        }\r\n    }\r\n\r\n    \/\/ \u5c06\u6839\u8282\u70b9\u8bbe\u4e3a\u9ed1\u8272\r\n    rb_set_black(root);\r\n}<\/pre>\n
\"\u590d\u5236\u4ee3\u7801\"<\/a><\/span><\/div>\n<\/div>\n
insertFixUp(root, node)\u7684\u4f5c\u7528\u662f\u5bf9\u5e94”\u4e0a\u9762\u6240\u8bb2\u7684\u7b2c\u4e09\u6b65”\u3002\u5b83\u662f\u4e00\u4e2a\u5185\u90e8\u63a5\u53e3\u3002<\/p>\n
 <\/p>\n
5. \u5220\u9664\u64cd\u4f5c<\/strong><\/p>\n
\u5c06\u7ea2\u9ed1\u6811\u5185\u7684\u67d0\u4e00\u4e2a\u8282\u70b9\u5220\u9664\u3002\u9700\u8981\u6267\u884c\u7684\u64cd\u4f5c\u4f9d\u6b21\u662f\uff1a\u9996\u5148\uff0c\u5c06\u7ea2\u9ed1\u6811\u5f53\u4f5c\u4e00\u9897\u4e8c\u53c9\u67e5\u627e\u6811\uff0c\u5c06\u8be5\u8282\u70b9\u4ece\u4e8c\u53c9\u67e5\u627e\u6811\u4e2d\u5220\u9664\uff1b\u7136\u540e\uff0c\u901a\u8fc7”\u65cb\u8f6c\u548c\u91cd\u65b0\u7740\u8272”\u7b49\u4e00\u7cfb\u5217\u6765\u4fee\u6b63\u8be5\u6811\uff0c\u4f7f\u4e4b\u91cd\u65b0\u6210\u4e3a\u4e00\u68f5\u7ea2\u9ed1\u6811\u3002\u8be6\u7ec6\u63cf\u8ff0\u5982\u4e0b\uff1a<\/p>\n
\u7b2c\u4e00\u6b65\uff1a\u5c06\u7ea2\u9ed1\u6811\u5f53\u4f5c\u4e00\u9897\u4e8c\u53c9\u67e5\u627e\u6811\uff0c\u5c06\u8282\u70b9\u5220\u9664\u3002<\/strong>
\n\u8fd9\u548c”\u5220\u9664\u5e38\u89c4\u4e8c\u53c9\u67e5\u627e\u6811\u4e2d\u5220\u9664\u8282\u70b9\u7684\u65b9\u6cd5\u662f\u4e00\u6837\u7684”\u3002\u52063\u79cd\u60c5\u51b5\uff1a
\n\u2460 \u88ab\u5220\u9664\u8282\u70b9\u6ca1\u6709\u513f\u5b50\uff0c\u5373\u4e3a\u53f6\u8282\u70b9\u3002\u90a3\u4e48\uff0c\u76f4\u63a5\u5c06\u8be5\u8282\u70b9\u5220\u9664\u5c31OK\u4e86\u3002
\n\u2461 \u88ab\u5220\u9664\u8282\u70b9\u53ea\u6709\u4e00\u4e2a\u513f\u5b50\u3002\u90a3\u4e48\uff0c\u76f4\u63a5\u5220\u9664\u8be5\u8282\u70b9\uff0c\u5e76\u7528\u8be5\u8282\u70b9\u7684\u552f\u4e00\u5b50\u8282\u70b9\u9876\u66ff\u5b83\u7684\u4f4d\u7f6e\u3002
\n\u2462 \u88ab\u5220\u9664\u8282\u70b9\u6709\u4e24\u4e2a\u513f\u5b50\u3002\u90a3\u4e48\uff0c\u5148\u627e\u51fa\u5b83\u7684\u540e\u7ee7\u8282\u70b9\uff1b\u7136\u540e\u628a\u201c\u5b83\u7684\u540e\u7ee7\u8282\u70b9\u7684\u5185\u5bb9\u201d\u590d\u5236\u7ed9\u201c\u8be5\u8282\u70b9\u7684\u5185\u5bb9\u201d\uff1b\u4e4b\u540e\uff0c\u5220\u9664\u201c\u5b83\u7684\u540e\u7ee7\u8282\u70b9\u201d\u3002\u5728\u8fd9\u91cc\uff0c\u540e\u7ee7\u8282\u70b9\u76f8\u5f53\u4e8e\u66ff\u8eab\uff0c\u5728\u5c06\u540e\u7ee7\u8282\u70b9\u7684\u5185\u5bb9\u590d\u5236\u7ed9”\u88ab\u5220\u9664\u8282\u70b9”\u4e4b\u540e\uff0c\u518d\u5c06\u540e\u7ee7\u8282\u70b9\u5220\u9664\u3002\u8fd9\u6837\u5c31\u5de7\u5999\u7684\u5c06\u95ee\u9898\u8f6c\u6362\u4e3a”\u5220\u9664\u540e\u7ee7\u8282\u70b9”\u7684\u60c5\u51b5\u4e86\uff0c\u4e0b\u9762\u5c31\u8003\u8651\u540e\u7ee7\u8282\u70b9\u3002 \u5728”\u88ab\u5220\u9664\u8282\u70b9”\u6709\u4e24\u4e2a\u975e\u7a7a\u5b50\u8282\u70b9\u7684\u60c5\u51b5\u4e0b\uff0c\u5b83\u7684\u540e\u7ee7\u8282\u70b9\u4e0d\u53ef\u80fd\u662f\u53cc\u5b50\u975e\u7a7a\u3002\u65e2\u7136”\u7684\u540e\u7ee7\u8282\u70b9”\u4e0d\u53ef\u80fd\u53cc\u5b50\u90fd\u975e\u7a7a\uff0c\u5c31\u610f\u5473\u7740”\u8be5\u8282\u70b9\u7684\u540e\u7ee7\u8282\u70b9”\u8981\u4e48\u6ca1\u6709\u513f\u5b50\uff0c\u8981\u4e48\u53ea\u6709\u4e00\u4e2a\u513f\u5b50\u3002\u82e5\u6ca1\u6709\u513f\u5b50\uff0c\u5219\u6309”\u60c5\u51b5\u2460 “\u8fdb\u884c\u5904\u7406\uff1b\u82e5\u53ea\u6709\u4e00\u4e2a\u513f\u5b50\uff0c\u5219\u6309”\u60c5\u51b5\u2461 “\u8fdb\u884c\u5904\u7406\u3002<\/p>\n
\u7b2c\u4e8c\u6b65\uff1a\u901a\u8fc7”\u65cb\u8f6c\u548c\u91cd\u65b0\u7740\u8272”\u7b49\u4e00\u7cfb\u5217\u6765\u4fee\u6b63\u8be5\u6811\uff0c\u4f7f\u4e4b\u91cd\u65b0\u6210\u4e3a\u4e00\u68f5\u7ea2\u9ed1\u6811\u3002<\/strong>
\n\u56e0\u4e3a”\u7b2c\u4e00\u6b65”\u4e2d\u5220\u9664\u8282\u70b9\u4e4b\u540e\uff0c\u53ef\u80fd\u4f1a\u8fdd\u80cc\u7ea2\u9ed1\u6811\u7684\u7279\u6027\u3002\u6240\u4ee5\u9700\u8981\u901a\u8fc7”\u65cb\u8f6c\u548c\u91cd\u65b0\u7740\u8272”\u6765\u4fee\u6b63\u8be5\u6811\uff0c\u4f7f\u4e4b\u91cd\u65b0\u6210\u4e3a\u4e00\u68f5\u7ea2\u9ed1\u6811\u3002<\/p>\n
\u5220\u9664\u64cd\u4f5c\u7684\u5b9e\u73b0\u4ee3\u7801(C++\u8bed\u8a00)<\/p>\n
\n
\"\u590d\u5236\u4ee3\u7801\"<\/a><\/span><\/div>\n
\/* \r\n * \u5220\u9664\u7ed3\u70b9(node)\uff0c\u5e76\u8fd4\u56de\u88ab\u5220\u9664\u7684\u7ed3\u70b9\r\n *\r\n * \u53c2\u6570\u8bf4\u660e\uff1a\r\n *     root \u7ea2\u9ed1\u6811\u7684\u6839\u7ed3\u70b9\r\n *     node \u5220\u9664\u7684\u7ed3\u70b9\r\n *\/\r\ntemplate <class T>\r\nvoid RBTree<T>::remove(RBTNode<T>* &root, RBTNode<T> *node)\r\n{\r\n    RBTNode<T> *child, *parent;\r\n    RBTColor color;\r\n\r\n    \/\/ \u88ab\u5220\u9664\u8282\u70b9\u7684\"\u5de6\u53f3\u5b69\u5b50\u90fd\u4e0d\u4e3a\u7a7a\"\u7684\u60c5\u51b5\u3002\r\n    if ( (node->left!=NULL) && (node->right!=NULL) ) \r\n    {\r\n        \/\/ \u88ab\u5220\u8282\u70b9\u7684\u540e\u7ee7\u8282\u70b9\u3002(\u79f0\u4e3a\"\u53d6\u4ee3\u8282\u70b9\")\r\n        \/\/ \u7528\u5b83\u6765\u53d6\u4ee3\"\u88ab\u5220\u8282\u70b9\"\u7684\u4f4d\u7f6e\uff0c\u7136\u540e\u518d\u5c06\"\u88ab\u5220\u8282\u70b9\"\u53bb\u6389\u3002\r\n        RBTNode<T> *replace = node;\r\n\r\n        \/\/ \u83b7\u53d6\u540e\u7ee7\u8282\u70b9\r\n        replace = replace->right;\r\n        while (replace->left != NULL)\r\n            replace = replace->left;\r\n\r\n        \/\/ \"node\u8282\u70b9\"\u4e0d\u662f\u6839\u8282\u70b9(\u53ea\u6709\u6839\u8282\u70b9\u4e0d\u5b58\u5728\u7236\u8282\u70b9)\r\n        if (rb_parent(node))\r\n        {\r\n            if (rb_parent(node)->left == node)\r\n                rb_parent(node)->left = replace;\r\n            else\r\n                rb_parent(node)->right = replace;\r\n        } \r\n        else \r\n            \/\/ \"node\u8282\u70b9\"\u662f\u6839\u8282\u70b9\uff0c\u66f4\u65b0\u6839\u8282\u70b9\u3002\r\n            root = replace;\r\n\r\n        \/\/ child\u662f\"\u53d6\u4ee3\u8282\u70b9\"\u7684\u53f3\u5b69\u5b50\uff0c\u4e5f\u662f\u9700\u8981\"\u8c03\u6574\u7684\u8282\u70b9\"\u3002\r\n        \/\/ \"\u53d6\u4ee3\u8282\u70b9\"\u80af\u5b9a\u4e0d\u5b58\u5728\u5de6\u5b69\u5b50\uff01\u56e0\u4e3a\u5b83\u662f\u4e00\u4e2a\u540e\u7ee7\u8282\u70b9\u3002\r\n        child = replace->right;\r\n        parent = rb_parent(replace);\r\n        \/\/ \u4fdd\u5b58\"\u53d6\u4ee3\u8282\u70b9\"\u7684\u989c\u8272\r\n        color = rb_color(replace);\r\n\r\n        \/\/ \"\u88ab\u5220\u9664\u8282\u70b9\"\u662f\"\u5b83\u7684\u540e\u7ee7\u8282\u70b9\u7684\u7236\u8282\u70b9\"\r\n        if (parent == node)\r\n        {\r\n            parent = replace;\r\n        } \r\n        else\r\n        {\r\n            \/\/ child\u4e0d\u4e3a\u7a7a\r\n            if (child)\r\n                rb_set_parent(child, parent);\r\n            parent->left = child;\r\n\r\n            replace->right = node->right;\r\n            rb_set_parent(node->right, replace);\r\n        }\r\n\r\n        replace->parent = node->parent;\r\n        replace->color = node->color;\r\n        replace->left = node->left;\r\n        node->left->parent = replace;\r\n\r\n        if (color == BLACK)\r\n            removeFixUp(root, child, parent);\r\n\r\n        delete node;\r\n        return ;\r\n    }\r\n\r\n    if (node->left !=NULL)\r\n        child = node->left;\r\n    else \r\n        child = node->right;\r\n\r\n    parent = node->parent;\r\n    \/\/ \u4fdd\u5b58\"\u53d6\u4ee3\u8282\u70b9\"\u7684\u989c\u8272\r\n    color = node->color;\r\n\r\n    if (child)\r\n        child->parent = parent;\r\n\r\n    \/\/ \"node\u8282\u70b9\"\u4e0d\u662f\u6839\u8282\u70b9\r\n    if (parent)\r\n    {\r\n        if (parent->left == node)\r\n            parent->left = child;\r\n        else\r\n            parent->right = child;\r\n    }\r\n    else\r\n        root = child;\r\n\r\n    if (color == BLACK)\r\n        removeFixUp(root, child, parent);\r\n    delete node;\r\n}\r\n\r\n\/* \r\n * \u5220\u9664\u7ea2\u9ed1\u6811\u4e2d\u952e\u503c\u4e3akey\u7684\u8282\u70b9\r\n *\r\n * \u53c2\u6570\u8bf4\u660e\uff1a\r\n *     tree \u7ea2\u9ed1\u6811\u7684\u6839\u7ed3\u70b9\r\n *\/\r\ntemplate <class T>\r\nvoid RBTree<T>::remove(T key)\r\n{\r\n    RBTNode<T> *node; \r\n\r\n    \/\/ \u67e5\u627ekey\u5bf9\u5e94\u7684\u8282\u70b9(node)\uff0c\u627e\u5230\u7684\u8bdd\u5c31\u5220\u9664\u8be5\u8282\u70b9\r\n    if ((node = search(mRoot, key)) != NULL)\r\n        remove(mRoot, node);\r\n}<\/pre>\n
\"\u590d\u5236\u4ee3\u7801\"<\/a><\/span><\/div>\n<\/div>\n
\u5185\u90e8\u63a5\u53e3<\/strong>\u00a0— remove(root, node)\u7684\u4f5c\u7528\u662f\u5c06”node”\u8282\u70b9\u63d2\u5165\u5230\u7ea2\u9ed1\u6811\u4e2d\u3002\u5176\u4e2d\uff0croot\u662f\u6839\uff0cnode\u662f\u88ab\u63d2\u5165\u8282\u70b9\u3002
\n\u5916\u90e8\u63a5\u53e3<\/strong>\u00a0— remove(key)\u5220\u9664\u7ea2\u9ed1\u6811\u4e2d\u952e\u503c\u4e3akey\u7684\u8282\u70b9\u3002<\/p>\n
\u5220\u9664\u4fee\u6b63\u64cd\u4f5c\u7684\u5b9e\u73b0\u4ee3\u7801(C++\u8bed\u8a00)<\/p>\n
\n
\"\u590d\u5236\u4ee3\u7801\"<\/a><\/span><\/div>\n
\/*\r\n * \u7ea2\u9ed1\u6811\u5220\u9664\u4fee\u6b63\u51fd\u6570\r\n *\r\n * \u5728\u4ece\u7ea2\u9ed1\u6811\u4e2d\u5220\u9664\u63d2\u5165\u8282\u70b9\u4e4b\u540e(\u7ea2\u9ed1\u6811\u5931\u53bb\u5e73\u8861)\uff0c\u518d\u8c03\u7528\u8be5\u51fd\u6570\uff1b\r\n * \u76ee\u7684\u662f\u5c06\u5b83\u91cd\u65b0\u5851\u9020\u6210\u4e00\u9897\u7ea2\u9ed1\u6811\u3002\r\n *\r\n * \u53c2\u6570\u8bf4\u660e\uff1a\r\n *     root \u7ea2\u9ed1\u6811\u7684\u6839\r\n *     node \u5f85\u4fee\u6b63\u7684\u8282\u70b9\r\n *\/\r\ntemplate <class T>\r\nvoid RBTree<T>::removeFixUp(RBTNode<T>* &root, RBTNode<T> *node, RBTNode<T> *parent)\r\n{\r\n    RBTNode<T> *other;\r\n\r\n    while ((!node || rb_is_black(node)) && node != root)\r\n    {\r\n        if (parent->left == node)\r\n        {\r\n            other = parent->right;\r\n            if (rb_is_red(other))\r\n            {\r\n                \/\/ Case 1: x\u7684\u5144\u5f1fw\u662f\u7ea2\u8272\u7684  \r\n                rb_set_black(other);\r\n                rb_set_red(parent);\r\n                leftRotate(root, parent);\r\n                other = parent->right;\r\n            }\r\n            if ((!other->left || rb_is_black(other->left)) &&\r\n                (!other->right || rb_is_black(other->right)))\r\n            {\r\n                \/\/ Case 2: x\u7684\u5144\u5f1fw\u662f\u9ed1\u8272\uff0c\u4e14w\u7684\u4fe9\u4e2a\u5b69\u5b50\u4e5f\u90fd\u662f\u9ed1\u8272\u7684  \r\n                rb_set_red(other);\r\n                node = parent;\r\n                parent = rb_parent(node);\r\n            }\r\n            else\r\n            {\r\n                if (!other->right || rb_is_black(other->right))\r\n                {\r\n                    \/\/ Case 3: x\u7684\u5144\u5f1fw\u662f\u9ed1\u8272\u7684\uff0c\u5e76\u4e14w\u7684\u5de6\u5b69\u5b50\u662f\u7ea2\u8272\uff0c\u53f3\u5b69\u5b50\u4e3a\u9ed1\u8272\u3002  \r\n                    rb_set_black(other->left);\r\n                    rb_set_red(other);\r\n                    rightRotate(root, other);\r\n                    other = parent->right;\r\n                }\r\n                \/\/ Case 4: x\u7684\u5144\u5f1fw\u662f\u9ed1\u8272\u7684\uff1b\u5e76\u4e14w\u7684\u53f3\u5b69\u5b50\u662f\u7ea2\u8272\u7684\uff0c\u5de6\u5b69\u5b50\u4efb\u610f\u989c\u8272\u3002\r\n                rb_set_color(other, rb_color(parent));\r\n                rb_set_black(parent);\r\n                rb_set_black(other->right);\r\n                leftRotate(root, parent);\r\n                node = root;\r\n                break;\r\n            }\r\n        }\r\n        else\r\n        {\r\n            other = parent->left;\r\n            if (rb_is_red(other))\r\n            {\r\n                \/\/ Case 1: x\u7684\u5144\u5f1fw\u662f\u7ea2\u8272\u7684  \r\n                rb_set_black(other);\r\n                rb_set_red(parent);\r\n                rightRotate(root, parent);\r\n                other = parent->left;\r\n            }\r\n            if ((!other->left || rb_is_black(other->left)) &&\r\n                (!other->right || rb_is_black(other->right)))\r\n            {\r\n                \/\/ Case 2: x\u7684\u5144\u5f1fw\u662f\u9ed1\u8272\uff0c\u4e14w\u7684\u4fe9\u4e2a\u5b69\u5b50\u4e5f\u90fd\u662f\u9ed1\u8272\u7684  \r\n                rb_set_red(other);\r\n                node = parent;\r\n                parent = rb_parent(node);\r\n            }\r\n            else\r\n            {\r\n                if (!other->left || rb_is_black(other->left))\r\n                {\r\n                    \/\/ Case 3: x\u7684\u5144\u5f1fw\u662f\u9ed1\u8272\u7684\uff0c\u5e76\u4e14w\u7684\u5de6\u5b69\u5b50\u662f\u7ea2\u8272\uff0c\u53f3\u5b69\u5b50\u4e3a\u9ed1\u8272\u3002  \r\n                    rb_set_black(other->right);\r\n                    rb_set_red(other);\r\n                    leftRotate(root, other);\r\n                    other = parent->left;\r\n                }\r\n                \/\/ Case 4: x\u7684\u5144\u5f1fw\u662f\u9ed1\u8272\u7684\uff1b\u5e76\u4e14w\u7684\u53f3\u5b69\u5b50\u662f\u7ea2\u8272\u7684\uff0c\u5de6\u5b69\u5b50\u4efb\u610f\u989c\u8272\u3002\r\n                rb_set_color(other, rb_color(parent));\r\n                rb_set_black(parent);\r\n                rb_set_black(other->left);\r\n                rightRotate(root, parent);\r\n                node = root;\r\n                break;\r\n            }\r\n        }\r\n    }\r\n    if (node)\r\n        rb_set_black(node);\r\n}<\/pre>\n
\"\u590d\u5236\u4ee3\u7801\"<\/a><\/span><\/div>\n<\/div>\n
removeFixup(root, node, parent)\u662f\u5bf9\u5e94”\u4e0a\u9762\u6240\u8bb2\u7684\u7b2c\u4e09\u6b65”\u3002\u5b83\u662f\u4e00\u4e2a\u5185\u90e8\u63a5\u53e3\u3002<\/p>\n
 <\/p>\n
<\/a>\u7ea2\u9ed1\u6811\u7684C++\u5b9e\u73b0(\u5b8c\u6574\u6e90\u7801)<\/strong><\/h3>\n
\u4e0b\u9762\u662f\u7ea2\u9ed1\u6811\u5b9e\u73b0\u7684\u5b8c\u6574\u4ee3\u7801\u548c\u76f8\u5e94\u7684\u6d4b\u8bd5\u7a0b\u5e8f\u3002
\n(1) \u9664\u4e86\u4e0a\u9762\u6240\u8bf4\u7684”\u5de6\u65cb”\u3001”\u53f3\u65cb”\u3001”\u6dfb\u52a0”\u3001”\u5220\u9664”\u7b49\u57fa\u672c\u64cd\u4f5c\u4e4b\u540e\uff0c\u8fd8\u5b9e\u73b0\u4e86”\u904d\u5386”\u3001”\u67e5\u627e”\u3001”\u6253\u5370”\u3001”\u6700\u5c0f\u503c”\u3001”\u6700\u5927\u503c”\u3001”\u521b\u5efa”\u3001”\u9500\u6bc1”\u7b49\u63a5\u53e3\u3002
\n(2) \u51fd\u6570\u63a5\u53e3\u5927\u591a\u5206\u4e3a\u5185\u90e8\u63a5\u53e3\u548c\u5916\u90e8\u63a5\u53e3\u3002\u5185\u90e8\u63a5\u53e3\u662fprivate\u51fd\u6570\uff0c\u5916\u90e8\u63a5\u53e3\u5219\u662fpublic\u51fd\u6570\u3002
\n(3) \u6d4b\u8bd5\u4ee3\u7801\u4e2d\u63d0\u4f9b\u4e86”\u63d2\u5165”\u548c”\u5220\u9664”\u52a8\u4f5c\u7684\u68c0\u6d4b\u5f00\u5173\u3002\u9ed8\u8ba4\u662f\u5173\u95ed\u7684\uff0c\u6253\u5f00\u65b9\u6cd5\u53ef\u4ee5\u53c2\u8003”\u4ee3\u7801\u4e2d\u7684\u8bf4\u660e”\u3002\u5efa\u8bae\u5728\u6253\u5f00\u5f00\u5173\u540e\uff0c\u5728\u8349\u7a3f\u4e0a\u81ea\u5df1\u52a8\u624b\u7ed8\u5236\u4e00\u4e0b\u7ea2\u9ed1\u6811\u3002<\/p>\n
\u7ea2\u9ed1\u6811\u7684\u5b9e\u73b0\u6587\u4ef6(RBTree.h)<\/p>\n
\"\"<\/p>\n
\n
\"\u590d\u5236\u4ee3\u7801\"<\/a><\/span><\/div>\n
  1 \/**\r\n  2  * C++ \u8bed\u8a00: \u7ea2\u9ed1\u6811\r\n  3  *\r\n  4  * @author skywang\r\n  5  * @date 2013\/11\/07\r\n  6  *\/\r\n  7 \r\n  8 #ifndef _RED_BLACK_TREE_HPP_\r\n  9 #define _RED_BLACK_TREE_HPP_ \r\n 10 \r\n 11 #include <iomanip>\r\n 12 #include <iostream>\r\n 13 using namespace std;\r\n 14 \r\n 15 enum RBTColor{RED, BLACK};\r\n 16 \r\n 17 template <class T>\r\n 18 class RBTNode{\r\n 19     public:\r\n 20         RBTColor color;    \/\/ \u989c\u8272\r\n 21         T key;            \/\/ \u5173\u952e\u5b57(\u952e\u503c)\r\n 22         RBTNode *left;    \/\/ \u5de6\u5b69\u5b50\r\n 23         RBTNode *right;    \/\/ \u53f3\u5b69\u5b50\r\n 24         RBTNode *parent; \/\/ \u7236\u7ed3\u70b9\r\n 25 \r\n 26         RBTNode(T value, RBTColor c, RBTNode *p, RBTNode *l, RBTNode *r):\r\n 27             key(value),color(c),parent(),left(l),right(r) {}\r\n 28 };\r\n 29 \r\n 30 template <class T>\r\n 31 class RBTree {\r\n 32     private:\r\n 33         RBTNode<T> *mRoot;    \/\/ \u6839\u7ed3\u70b9\r\n 34 \r\n 35     public:\r\n 36         RBTree();\r\n 37         ~RBTree();\r\n 38 \r\n 39         \/\/ \u524d\u5e8f\u904d\u5386\"\u7ea2\u9ed1\u6811\"\r\n 40         void preOrder();\r\n 41         \/\/ \u4e2d\u5e8f\u904d\u5386\"\u7ea2\u9ed1\u6811\"\r\n 42         void inOrder();\r\n 43         \/\/ \u540e\u5e8f\u904d\u5386\"\u7ea2\u9ed1\u6811\"\r\n 44         void postOrder();\r\n 45 \r\n 46         \/\/ (\u9012\u5f52\u5b9e\u73b0)\u67e5\u627e\"\u7ea2\u9ed1\u6811\"\u4e2d\u952e\u503c\u4e3akey\u7684\u8282\u70b9\r\n 47         RBTNode<T>* search(T key);\r\n 48         \/\/ (\u975e\u9012\u5f52\u5b9e\u73b0)\u67e5\u627e\"\u7ea2\u9ed1\u6811\"\u4e2d\u952e\u503c\u4e3akey\u7684\u8282\u70b9\r\n 49         RBTNode<T>* iterativeSearch(T key);\r\n 50 \r\n 51         \/\/ \u67e5\u627e\u6700\u5c0f\u7ed3\u70b9\uff1a\u8fd4\u56de\u6700\u5c0f\u7ed3\u70b9\u7684\u952e\u503c\u3002\r\n 52         T minimum();\r\n 53         \/\/ \u67e5\u627e\u6700\u5927\u7ed3\u70b9\uff1a\u8fd4\u56de\u6700\u5927\u7ed3\u70b9\u7684\u952e\u503c\u3002\r\n 54         T maximum();\r\n 55 \r\n 56         \/\/ \u627e\u7ed3\u70b9(x)\u7684\u540e\u7ee7\u7ed3\u70b9\u3002\u5373\uff0c\u67e5\u627e\"\u7ea2\u9ed1\u6811\u4e2d\u6570\u636e\u503c\u5927\u4e8e\u8be5\u7ed3\u70b9\"\u7684\"\u6700\u5c0f\u7ed3\u70b9\"\u3002\r\n 57         RBTNode<T>* successor(RBTNode<T> *x);\r\n 58         \/\/ \u627e\u7ed3\u70b9(x)\u7684\u524d\u9a71\u7ed3\u70b9\u3002\u5373\uff0c\u67e5\u627e\"\u7ea2\u9ed1\u6811\u4e2d\u6570\u636e\u503c\u5c0f\u4e8e\u8be5\u7ed3\u70b9\"\u7684\"\u6700\u5927\u7ed3\u70b9\"\u3002\r\n 59         RBTNode<T>* predecessor(RBTNode<T> *x);\r\n 60 \r\n 61         \/\/ \u5c06\u7ed3\u70b9(key\u4e3a\u8282\u70b9\u952e\u503c)\u63d2\u5165\u5230\u7ea2\u9ed1\u6811\u4e2d\r\n 62         void insert(T key);\r\n 63 \r\n 64         \/\/ \u5220\u9664\u7ed3\u70b9(key\u4e3a\u8282\u70b9\u952e\u503c)\r\n 65         void remove(T key);\r\n 66 \r\n 67         \/\/ \u9500\u6bc1\u7ea2\u9ed1\u6811\r\n 68         void destroy();\r\n 69 \r\n 70         \/\/ \u6253\u5370\u7ea2\u9ed1\u6811\r\n 71         void print();\r\n 72     private:\r\n 73         \/\/ \u524d\u5e8f\u904d\u5386\"\u7ea2\u9ed1\u6811\"\r\n 74         void preOrder(RBTNode<T>* tree) const;\r\n 75         \/\/ \u4e2d\u5e8f\u904d\u5386\"\u7ea2\u9ed1\u6811\"\r\n 76         void inOrder(RBTNode<T>* tree) const;\r\n 77         \/\/ \u540e\u5e8f\u904d\u5386\"\u7ea2\u9ed1\u6811\"\r\n 78         void postOrder(RBTNode<T>* tree) const;\r\n 79 \r\n 80         \/\/ (\u9012\u5f52\u5b9e\u73b0)\u67e5\u627e\"\u7ea2\u9ed1\u6811x\"\u4e2d\u952e\u503c\u4e3akey\u7684\u8282\u70b9\r\n 81         RBTNode<T>* search(RBTNode<T>* x, T key) const;\r\n 82         \/\/ (\u975e\u9012\u5f52\u5b9e\u73b0)\u67e5\u627e\"\u7ea2\u9ed1\u6811x\"\u4e2d\u952e\u503c\u4e3akey\u7684\u8282\u70b9\r\n 83         RBTNode<T>* iterativeSearch(RBTNode<T>* x, T key) const;\r\n 84 \r\n 85         \/\/ \u67e5\u627e\u6700\u5c0f\u7ed3\u70b9\uff1a\u8fd4\u56detree\u4e3a\u6839\u7ed3\u70b9\u7684\u7ea2\u9ed1\u6811\u7684\u6700\u5c0f\u7ed3\u70b9\u3002\r\n 86         RBTNode<T>* minimum(RBTNode<T>* tree);\r\n 87         \/\/ \u67e5\u627e\u6700\u5927\u7ed3\u70b9\uff1a\u8fd4\u56detree\u4e3a\u6839\u7ed3\u70b9\u7684\u7ea2\u9ed1\u6811\u7684\u6700\u5927\u7ed3\u70b9\u3002\r\n 88         RBTNode<T>* maximum(RBTNode<T>* tree);\r\n 89 \r\n 90         \/\/ \u5de6\u65cb\r\n 91         void leftRotate(RBTNode<T>* &root, RBTNode<T>* x);\r\n 92         \/\/ \u53f3\u65cb\r\n 93         void rightRotate(RBTNode<T>* &root, RBTNode<T>* y);\r\n 94         \/\/ \u63d2\u5165\u51fd\u6570\r\n 95         void insert(RBTNode<T>* &root, RBTNode<T>* node);\r\n 96         \/\/ \u63d2\u5165\u4fee\u6b63\u51fd\u6570\r\n 97         void insertFixUp(RBTNode<T>* &root, RBTNode<T>* node);\r\n 98         \/\/ \u5220\u9664\u51fd\u6570\r\n 99         void remove(RBTNode<T>* &root, RBTNode<T> *node);\r\n100         \/\/ \u5220\u9664\u4fee\u6b63\u51fd\u6570\r\n101         void removeFixUp(RBTNode<T>* &root, RBTNode<T> *node, RBTNode<T> *parent);\r\n102 \r\n103         \/\/ \u9500\u6bc1\u7ea2\u9ed1\u6811\r\n104         void destroy(RBTNode<T>* &tree);\r\n105 \r\n106         \/\/ \u6253\u5370\u7ea2\u9ed1\u6811\r\n107         void print(RBTNode<T>* tree, T key, int direction);\r\n108 \r\n109 #define rb_parent(r)   ((r)->parent)\r\n110 #define rb_color(r) ((r)->color)\r\n111 #define rb_is_red(r)   ((r)->color==RED)\r\n112 #define rb_is_black(r)  ((r)->color==BLACK)\r\n113 #define rb_set_black(r)  do { (r)->color = BLACK; } while (0)\r\n114 #define rb_set_red(r)  do { (r)->color = RED; } while (0)\r\n115 #define rb_set_parent(r,p)  do { (r)->parent = (p); } while (0)\r\n116 #define rb_set_color(r,c)  do { (r)->color = (c); } while (0)\r\n117 };\r\n118 \r\n119 \/* \r\n120  * \u6784\u9020\u51fd\u6570\r\n121  *\/\r\n122 template <class T>\r\n123 RBTree<T>::RBTree():mRoot(NULL)\r\n124 {\r\n125     mRoot = NULL;\r\n126 }\r\n127 \r\n128 \/* \r\n129  * \u6790\u6784\u51fd\u6570\r\n130  *\/\r\n131 template <class T>\r\n132 RBTree<T>::~RBTree() \r\n133 {\r\n134     destroy();\r\n135 }\r\n136 \r\n137 \/*\r\n138  * \u524d\u5e8f\u904d\u5386\"\u7ea2\u9ed1\u6811\"\r\n139  *\/\r\n140 template <class T>\r\n141 void RBTree<T>::preOrder(RBTNode<T>* tree) const\r\n142 {\r\n143     if(tree != NULL)\r\n144     {\r\n145         cout<< tree->key << \" \" ;\r\n146         preOrder(tree->left);\r\n147         preOrder(tree->right);\r\n148     }\r\n149 }\r\n150 \r\n151 template <class T>\r\n152 void RBTree<T>::preOrder() \r\n153 {\r\n154     preOrder(mRoot);\r\n155 }\r\n156 \r\n157 \/*\r\n158  * \u4e2d\u5e8f\u904d\u5386\"\u7ea2\u9ed1\u6811\"\r\n159  *\/\r\n160 template <class T>\r\n161 void RBTree<T>::inOrder(RBTNode<T>* tree) const\r\n162 {\r\n163     if(tree != NULL)\r\n164     {\r\n165         inOrder(tree->left);\r\n166         cout<< tree->key << \" \" ;\r\n167         inOrder(tree->right);\r\n168     }\r\n169 }\r\n170 \r\n171 template <class T>\r\n172 void RBTree<T>::inOrder() \r\n173 {\r\n174     inOrder(mRoot);\r\n175 }\r\n176 \r\n177 \/*\r\n178  * \u540e\u5e8f\u904d\u5386\"\u7ea2\u9ed1\u6811\"\r\n179  *\/\r\n180 template <class T>\r\n181 void RBTree<T>::postOrder(RBTNode<T>* tree) const\r\n182 {\r\n183     if(tree != NULL)\r\n184     {\r\n185         postOrder(tree->left);\r\n186         postOrder(tree->right);\r\n187         cout<< tree->key << \" \" ;\r\n188     }\r\n189 }\r\n190 \r\n191 template <class T>\r\n192 void RBTree<T>::postOrder() \r\n193 {\r\n194     postOrder(mRoot);\r\n195 }\r\n196 \r\n197 \/*\r\n198  * (\u9012\u5f52\u5b9e\u73b0)\u67e5\u627e\"\u7ea2\u9ed1\u6811x\"\u4e2d\u952e\u503c\u4e3akey\u7684\u8282\u70b9\r\n199  *\/\r\n200 template <class T>\r\n201 RBTNode<T>* RBTree<T>::search(RBTNode<T>* x, T key) const\r\n202 {\r\n203     if (x==NULL || x->key==key)\r\n204         return x;\r\n205 \r\n206     if (key < x->key)\r\n207         return search(x->left, key);\r\n208     else\r\n209         return search(x->right, key);\r\n210 }\r\n211 \r\n212 template <class T>\r\n213 RBTNode<T>* RBTree<T>::search(T key) \r\n214 {\r\n215     search(mRoot, key);\r\n216 }\r\n217 \r\n218 \/*\r\n219  * (\u975e\u9012\u5f52\u5b9e\u73b0)\u67e5\u627e\"\u7ea2\u9ed1\u6811x\"\u4e2d\u952e\u503c\u4e3akey\u7684\u8282\u70b9\r\n220  *\/\r\n221 template <class T>\r\n222 RBTNode<T>* RBTree<T>::iterativeSearch(RBTNode<T>* x, T key) const\r\n223 {\r\n224     while ((x!=NULL) && (x->key!=key))\r\n225     {\r\n226         if (key < x->key)\r\n227             x = x->left;\r\n228         else\r\n229             x = x->right;\r\n230     }\r\n231 \r\n232     return x;\r\n233 }\r\n234 \r\n235 template <class T>\r\n236 RBTNode<T>* RBTree<T>::iterativeSearch(T key)\r\n237 {\r\n238     iterativeSearch(mRoot, key);\r\n239 }\r\n240 \r\n241 \/* \r\n242  * \u67e5\u627e\u6700\u5c0f\u7ed3\u70b9\uff1a\u8fd4\u56detree\u4e3a\u6839\u7ed3\u70b9\u7684\u7ea2\u9ed1\u6811\u7684\u6700\u5c0f\u7ed3\u70b9\u3002\r\n243  *\/\r\n244 template <class T>\r\n245 RBTNode<T>* RBTree<T>::minimum(RBTNode<T>* tree)\r\n246 {\r\n247     if (tree == NULL)\r\n248         return NULL;\r\n249 \r\n250     while(tree->left != NULL)\r\n251         tree = tree->left;\r\n252     return tree;\r\n253 }\r\n254 \r\n255 template <class T>\r\n256 T RBTree<T>::minimum()\r\n257 {\r\n258     RBTNode<T> *p = minimum(mRoot);\r\n259     if (p != NULL)\r\n260         return p->key;\r\n261 \r\n262     return (T)NULL;\r\n263 }\r\n264  \r\n265 \/* \r\n266  * \u67e5\u627e\u6700\u5927\u7ed3\u70b9\uff1a\u8fd4\u56detree\u4e3a\u6839\u7ed3\u70b9\u7684\u7ea2\u9ed1\u6811\u7684\u6700\u5927\u7ed3\u70b9\u3002\r\n267  *\/\r\n268 template <class T>\r\n269 RBTNode<T>* RBTree<T>::maximum(RBTNode<T>* tree)\r\n270 {\r\n271     if (tree == NULL)\r\n272         return NULL;\r\n273 \r\n274     while(tree->right != NULL)\r\n275         tree = tree->right;\r\n276     return tree;\r\n277 }\r\n278 \r\n279 template <class T>\r\n280 T RBTree<T>::maximum()\r\n281 {\r\n282     RBTNode<T> *p = maximum(mRoot);\r\n283     if (p != NULL)\r\n284         return p->key;\r\n285 \r\n286     return (T)NULL;\r\n287 }\r\n288 \r\n289 \/* \r\n290  * \u627e\u7ed3\u70b9(x)\u7684\u540e\u7ee7\u7ed3\u70b9\u3002\u5373\uff0c\u67e5\u627e\"\u7ea2\u9ed1\u6811\u4e2d\u6570\u636e\u503c\u5927\u4e8e\u8be5\u7ed3\u70b9\"\u7684\"\u6700\u5c0f\u7ed3\u70b9\"\u3002\r\n291  *\/\r\n292 template <class T>\r\n293 RBTNode<T>* RBTree<T>::successor(RBTNode<T> *x)\r\n294 {\r\n295     \/\/ \u5982\u679cx\u5b58\u5728\u53f3\u5b69\u5b50\uff0c\u5219\"x\u7684\u540e\u7ee7\u7ed3\u70b9\"\u4e3a \"\u4ee5\u5176\u53f3\u5b69\u5b50\u4e3a\u6839\u7684\u5b50\u6811\u7684\u6700\u5c0f\u7ed3\u70b9\"\u3002\r\n296     if (x->right != NULL)\r\n297         return minimum(x->right);\r\n298 \r\n299     \/\/ \u5982\u679cx\u6ca1\u6709\u53f3\u5b69\u5b50\u3002\u5219x\u6709\u4ee5\u4e0b\u4e24\u79cd\u53ef\u80fd\uff1a\r\n300     \/\/ (01) x\u662f\"\u4e00\u4e2a\u5de6\u5b69\u5b50\"\uff0c\u5219\"x\u7684\u540e\u7ee7\u7ed3\u70b9\"\u4e3a \"\u5b83\u7684\u7236\u7ed3\u70b9\"\u3002\r\n301     \/\/ (02) x\u662f\"\u4e00\u4e2a\u53f3\u5b69\u5b50\"\uff0c\u5219\u67e5\u627e\"x\u7684\u6700\u4f4e\u7684\u7236\u7ed3\u70b9\uff0c\u5e76\u4e14\u8be5\u7236\u7ed3\u70b9\u8981\u5177\u6709\u5de6\u5b69\u5b50\"\uff0c\u627e\u5230\u7684\u8fd9\u4e2a\"\u6700\u4f4e\u7684\u7236\u7ed3\u70b9\"\u5c31\u662f\"x\u7684\u540e\u7ee7\u7ed3\u70b9\"\u3002\r\n302     RBTNode<T>* y = x->parent;\r\n303     while ((y!=NULL) && (x==y->right))\r\n304     {\r\n305         x = y;\r\n306         y = y->parent;\r\n307     }\r\n308 \r\n309     return y;\r\n310 }\r\n311  \r\n312 \/* \r\n313  * \u627e\u7ed3\u70b9(x)\u7684\u524d\u9a71\u7ed3\u70b9\u3002\u5373\uff0c\u67e5\u627e\"\u7ea2\u9ed1\u6811\u4e2d\u6570\u636e\u503c\u5c0f\u4e8e\u8be5\u7ed3\u70b9\"\u7684\"\u6700\u5927\u7ed3\u70b9\"\u3002\r\n314  *\/\r\n315 template <class T>\r\n316 RBTNode<T>* RBTree<T>::predecessor(RBTNode<T> *x)\r\n317 {\r\n318     \/\/ \u5982\u679cx\u5b58\u5728\u5de6\u5b69\u5b50\uff0c\u5219\"x\u7684\u524d\u9a71\u7ed3\u70b9\"\u4e3a \"\u4ee5\u5176\u5de6\u5b69\u5b50\u4e3a\u6839\u7684\u5b50\u6811\u7684\u6700\u5927\u7ed3\u70b9\"\u3002\r\n319     if (x->left != NULL)\r\n320         return maximum(x->left);\r\n321 \r\n322     \/\/ \u5982\u679cx\u6ca1\u6709\u5de6\u5b69\u5b50\u3002\u5219x\u6709\u4ee5\u4e0b\u4e24\u79cd\u53ef\u80fd\uff1a\r\n323     \/\/ (01) x\u662f\"\u4e00\u4e2a\u53f3\u5b69\u5b50\"\uff0c\u5219\"x\u7684\u524d\u9a71\u7ed3\u70b9\"\u4e3a \"\u5b83\u7684\u7236\u7ed3\u70b9\"\u3002\r\n324     \/\/ (01) x\u662f\"\u4e00\u4e2a\u5de6\u5b69\u5b50\"\uff0c\u5219\u67e5\u627e\"x\u7684\u6700\u4f4e\u7684\u7236\u7ed3\u70b9\uff0c\u5e76\u4e14\u8be5\u7236\u7ed3\u70b9\u8981\u5177\u6709\u53f3\u5b69\u5b50\"\uff0c\u627e\u5230\u7684\u8fd9\u4e2a\"\u6700\u4f4e\u7684\u7236\u7ed3\u70b9\"\u5c31\u662f\"x\u7684\u524d\u9a71\u7ed3\u70b9\"\u3002\r\n325     RBTNode<T>* y = x->parent;\r\n326     while ((y!=NULL) && (x==y->left))\r\n327     {\r\n328         x = y;\r\n329         y = y->parent;\r\n330     }\r\n331 \r\n332     return y;\r\n333 }\r\n334 \r\n335 \/* \r\n336  * \u5bf9\u7ea2\u9ed1\u6811\u7684\u8282\u70b9(x)\u8fdb\u884c\u5de6\u65cb\u8f6c\r\n337  *\r\n338  * \u5de6\u65cb\u793a\u610f\u56fe(\u5bf9\u8282\u70b9x\u8fdb\u884c\u5de6\u65cb)\uff1a\r\n339  *      px                              px\r\n340  *     \/                               \/\r\n341  *    x                               y                \r\n342  *   \/  \\      --(\u5de6\u65cb)-->           \/ \\                #\r\n343  *  lx   y                          x  ry     \r\n344  *     \/   \\                       \/  \\\r\n345  *    ly   ry                     lx  ly  \r\n346  *\r\n347  *\r\n348  *\/\r\n349 template <class T>\r\n350 void RBTree<T>::leftRotate(RBTNode<T>* &root, RBTNode<T>* x)\r\n351 {\r\n352     \/\/ \u8bbe\u7f6ex\u7684\u53f3\u5b69\u5b50\u4e3ay\r\n353     RBTNode<T> *y = x->right;\r\n354 \r\n355     \/\/ \u5c06 \u201cy\u7684\u5de6\u5b69\u5b50\u201d \u8bbe\u4e3a \u201cx\u7684\u53f3\u5b69\u5b50\u201d\uff1b\r\n356     \/\/ \u5982\u679cy\u7684\u5de6\u5b69\u5b50\u975e\u7a7a\uff0c\u5c06 \u201cx\u201d \u8bbe\u4e3a \u201cy\u7684\u5de6\u5b69\u5b50\u7684\u7236\u4eb2\u201d\r\n357     x->right = y->left;\r\n358     if (y->left != NULL)\r\n359         y->left->parent = x;\r\n360 \r\n361     \/\/ \u5c06 \u201cx\u7684\u7236\u4eb2\u201d \u8bbe\u4e3a \u201cy\u7684\u7236\u4eb2\u201d\r\n362     y->parent = x->parent;\r\n363 \r\n364     if (x->parent == NULL)\r\n365     {\r\n366         root = y;            \/\/ \u5982\u679c \u201cx\u7684\u7236\u4eb2\u201d \u662f\u7a7a\u8282\u70b9\uff0c\u5219\u5c06y\u8bbe\u4e3a\u6839\u8282\u70b9\r\n367     }\r\n368     else\r\n369     {\r\n370         if (x->parent->left == x)\r\n371             x->parent->left = y;    \/\/ \u5982\u679c x\u662f\u5b83\u7236\u8282\u70b9\u7684\u5de6\u5b69\u5b50\uff0c\u5219\u5c06y\u8bbe\u4e3a\u201cx\u7684\u7236\u8282\u70b9\u7684\u5de6\u5b69\u5b50\u201d\r\n372         else\r\n373             x->parent->right = y;    \/\/ \u5982\u679c x\u662f\u5b83\u7236\u8282\u70b9\u7684\u5de6\u5b69\u5b50\uff0c\u5219\u5c06y\u8bbe\u4e3a\u201cx\u7684\u7236\u8282\u70b9\u7684\u5de6\u5b69\u5b50\u201d\r\n374     }\r\n375     \r\n376     \/\/ \u5c06 \u201cx\u201d \u8bbe\u4e3a \u201cy\u7684\u5de6\u5b69\u5b50\u201d\r\n377     y->left = x;\r\n378     \/\/ \u5c06 \u201cx\u7684\u7236\u8282\u70b9\u201d \u8bbe\u4e3a \u201cy\u201d\r\n379     x->parent = y;\r\n380 }\r\n381 \r\n382 \/* \r\n383  * \u5bf9\u7ea2\u9ed1\u6811\u7684\u8282\u70b9(y)\u8fdb\u884c\u53f3\u65cb\u8f6c\r\n384  *\r\n385  * \u53f3\u65cb\u793a\u610f\u56fe(\u5bf9\u8282\u70b9y\u8fdb\u884c\u5de6\u65cb)\uff1a\r\n386  *            py                               py\r\n387  *           \/                                \/\r\n388  *          y                                x                  \r\n389  *         \/  \\      --(\u53f3\u65cb)-->            \/  \\                     #\r\n390  *        x   ry                           lx   y  \r\n391  *       \/ \\                                   \/ \\                   #\r\n392  *      lx  rx                                rx  ry\r\n393  * \r\n394  *\/\r\n395 template <class T>\r\n396 void RBTree<T>::rightRotate(RBTNode<T>* &root, RBTNode<T>* y)\r\n397 {\r\n398     \/\/ \u8bbe\u7f6ex\u662f\u5f53\u524d\u8282\u70b9\u7684\u5de6\u5b69\u5b50\u3002\r\n399     RBTNode<T> *x = y->left;\r\n400 \r\n401     \/\/ \u5c06 \u201cx\u7684\u53f3\u5b69\u5b50\u201d \u8bbe\u4e3a \u201cy\u7684\u5de6\u5b69\u5b50\u201d\uff1b\r\n402     \/\/ \u5982\u679c\"x\u7684\u53f3\u5b69\u5b50\"\u4e0d\u4e3a\u7a7a\u7684\u8bdd\uff0c\u5c06 \u201cy\u201d \u8bbe\u4e3a \u201cx\u7684\u53f3\u5b69\u5b50\u7684\u7236\u4eb2\u201d\r\n403     y->left = x->right;\r\n404     if (x->right != NULL)\r\n405         x->right->parent = y;\r\n406 \r\n407     \/\/ \u5c06 \u201cy\u7684\u7236\u4eb2\u201d \u8bbe\u4e3a \u201cx\u7684\u7236\u4eb2\u201d\r\n408     x->parent = y->parent;\r\n409 \r\n410     if (y->parent == NULL) \r\n411     {\r\n412         root = x;            \/\/ \u5982\u679c \u201cy\u7684\u7236\u4eb2\u201d \u662f\u7a7a\u8282\u70b9\uff0c\u5219\u5c06x\u8bbe\u4e3a\u6839\u8282\u70b9\r\n413     }\r\n414     else\r\n415     {\r\n416         if (y == y->parent->right)\r\n417             y->parent->right = x;    \/\/ \u5982\u679c y\u662f\u5b83\u7236\u8282\u70b9\u7684\u53f3\u5b69\u5b50\uff0c\u5219\u5c06x\u8bbe\u4e3a\u201cy\u7684\u7236\u8282\u70b9\u7684\u53f3\u5b69\u5b50\u201d\r\n418         else\r\n419             y->parent->left = x;    \/\/ (y\u662f\u5b83\u7236\u8282\u70b9\u7684\u5de6\u5b69\u5b50) \u5c06x\u8bbe\u4e3a\u201cx\u7684\u7236\u8282\u70b9\u7684\u5de6\u5b69\u5b50\u201d\r\n420     }\r\n421 \r\n422     \/\/ \u5c06 \u201cy\u201d \u8bbe\u4e3a \u201cx\u7684\u53f3\u5b69\u5b50\u201d\r\n423     x->right = y;\r\n424 \r\n425     \/\/ \u5c06 \u201cy\u7684\u7236\u8282\u70b9\u201d \u8bbe\u4e3a \u201cx\u201d\r\n426     y->parent = x;\r\n427 }\r\n428 \r\n429 \/*\r\n430  * \u7ea2\u9ed1\u6811\u63d2\u5165\u4fee\u6b63\u51fd\u6570\r\n431  *\r\n432  * \u5728\u5411\u7ea2\u9ed1\u6811\u4e2d\u63d2\u5165\u8282\u70b9\u4e4b\u540e(\u5931\u53bb\u5e73\u8861)\uff0c\u518d\u8c03\u7528\u8be5\u51fd\u6570\uff1b\r\n433  * \u76ee\u7684\u662f\u5c06\u5b83\u91cd\u65b0\u5851\u9020\u6210\u4e00\u9897\u7ea2\u9ed1\u6811\u3002\r\n434  *\r\n435  * \u53c2\u6570\u8bf4\u660e\uff1a\r\n436  *     root \u7ea2\u9ed1\u6811\u7684\u6839\r\n437  *     node \u63d2\u5165\u7684\u7ed3\u70b9        \/\/ \u5bf9\u5e94\u300a\u7b97\u6cd5\u5bfc\u8bba\u300b\u4e2d\u7684z\r\n438  *\/\r\n439 template <class T>\r\n440 void RBTree<T>::insertFixUp(RBTNode<T>* &root, RBTNode<T>* node)\r\n441 {\r\n442     RBTNode<T> *parent, *gparent;\r\n443 \r\n444     \/\/ \u82e5\u201c\u7236\u8282\u70b9\u5b58\u5728\uff0c\u5e76\u4e14\u7236\u8282\u70b9\u7684\u989c\u8272\u662f\u7ea2\u8272\u201d\r\n445     while ((parent = rb_parent(node)) && rb_is_red(parent))\r\n446     {\r\n447         gparent = rb_parent(parent);\r\n448 \r\n449         \/\/\u82e5\u201c\u7236\u8282\u70b9\u201d\u662f\u201c\u7956\u7236\u8282\u70b9\u7684\u5de6\u5b69\u5b50\u201d\r\n450         if (parent == gparent->left)\r\n451         {\r\n452             \/\/ Case 1\u6761\u4ef6\uff1a\u53d4\u53d4\u8282\u70b9\u662f\u7ea2\u8272\r\n453             {\r\n454                 RBTNode<T> *uncle = gparent->right;\r\n455                 if (uncle && rb_is_red(uncle))\r\n456                 {\r\n457                     rb_set_black(uncle);\r\n458                     rb_set_black(parent);\r\n459                     rb_set_red(gparent);\r\n460                     node = gparent;\r\n461                     continue;\r\n462                 }\r\n463             }\r\n464 \r\n465             \/\/ Case 2\u6761\u4ef6\uff1a\u53d4\u53d4\u662f\u9ed1\u8272\uff0c\u4e14\u5f53\u524d\u8282\u70b9\u662f\u53f3\u5b69\u5b50\r\n466             if (parent->right == node)\r\n467             {\r\n468                 RBTNode<T> *tmp;\r\n469                 leftRotate(root, parent);\r\n470                 tmp = parent;\r\n471                 parent = node;\r\n472                 node = tmp;\r\n473             }\r\n474 \r\n475             \/\/ Case 3\u6761\u4ef6\uff1a\u53d4\u53d4\u662f\u9ed1\u8272\uff0c\u4e14\u5f53\u524d\u8282\u70b9\u662f\u5de6\u5b69\u5b50\u3002\r\n476             rb_set_black(parent);\r\n477             rb_set_red(gparent);\r\n478             rightRotate(root, gparent);\r\n479         } \r\n480         else\/\/\u82e5\u201cz\u7684\u7236\u8282\u70b9\u201d\u662f\u201cz\u7684\u7956\u7236\u8282\u70b9\u7684\u53f3\u5b69\u5b50\u201d\r\n481         {\r\n482             \/\/ Case 1\u6761\u4ef6\uff1a\u53d4\u53d4\u8282\u70b9\u662f\u7ea2\u8272\r\n483             {\r\n484                 RBTNode<T> *uncle = gparent->left;\r\n485                 if (uncle && rb_is_red(uncle))\r\n486                 {\r\n487                     rb_set_black(uncle);\r\n488                     rb_set_black(parent);\r\n489                     rb_set_red(gparent);\r\n490                     node = gparent;\r\n491                     continue;\r\n492                 }\r\n493             }\r\n494 \r\n495             \/\/ Case 2\u6761\u4ef6\uff1a\u53d4\u53d4\u662f\u9ed1\u8272\uff0c\u4e14\u5f53\u524d\u8282\u70b9\u662f\u5de6\u5b69\u5b50\r\n496             if (parent->left == node)\r\n497             {\r\n498                 RBTNode<T> *tmp;\r\n499                 rightRotate(root, parent);\r\n500                 tmp = parent;\r\n501                 parent = node;\r\n502                 node = tmp;\r\n503             }\r\n504 \r\n505             \/\/ Case 3\u6761\u4ef6\uff1a\u53d4\u53d4\u662f\u9ed1\u8272\uff0c\u4e14\u5f53\u524d\u8282\u70b9\u662f\u53f3\u5b69\u5b50\u3002\r\n506             rb_set_black(parent);\r\n507             rb_set_red(gparent);\r\n508             leftRotate(root, gparent);\r\n509         }\r\n510     }\r\n511 \r\n512     \/\/ \u5c06\u6839\u8282\u70b9\u8bbe\u4e3a\u9ed1\u8272\r\n513     rb_set_black(root);\r\n514 }\r\n515 \r\n516 \/* \r\n517  * \u5c06\u7ed3\u70b9\u63d2\u5165\u5230\u7ea2\u9ed1\u6811\u4e2d\r\n518  *\r\n519  * \u53c2\u6570\u8bf4\u660e\uff1a\r\n520  *     root \u7ea2\u9ed1\u6811\u7684\u6839\u7ed3\u70b9\r\n521  *     node \u63d2\u5165\u7684\u7ed3\u70b9        \/\/ \u5bf9\u5e94\u300a\u7b97\u6cd5\u5bfc\u8bba\u300b\u4e2d\u7684node\r\n522  *\/\r\n523 template <class T>\r\n524 void RBTree<T>::insert(RBTNode<T>* &root, RBTNode<T>* node)\r\n525 {\r\n526     RBTNode<T> *y = NULL;\r\n527     RBTNode<T> *x = root;\r\n528 \r\n529     \/\/ 1. \u5c06\u7ea2\u9ed1\u6811\u5f53\u4f5c\u4e00\u9897\u4e8c\u53c9\u67e5\u627e\u6811\uff0c\u5c06\u8282\u70b9\u6dfb\u52a0\u5230\u4e8c\u53c9\u67e5\u627e\u6811\u4e2d\u3002\r\n530     while (x != NULL)\r\n531     {\r\n532         y = x;\r\n533         if (node->key < x->key)\r\n534             x = x->left;\r\n535         else\r\n536             x = x->right;\r\n537     }\r\n538 \r\n539     node->parent = y;\r\n540     if (y!=NULL)\r\n541     {\r\n542         if (node->key < y->key)\r\n543             y->left = node;\r\n544         else\r\n545             y->right = node;\r\n546     }\r\n547     else\r\n548         root = node;\r\n549 \r\n550     \/\/ 2. \u8bbe\u7f6e\u8282\u70b9\u7684\u989c\u8272\u4e3a\u7ea2\u8272\r\n551     node->color = RED;\r\n552 \r\n553     \/\/ 3. \u5c06\u5b83\u91cd\u65b0\u4fee\u6b63\u4e3a\u4e00\u9897\u4e8c\u53c9\u67e5\u627e\u6811\r\n554     insertFixUp(root, node);\r\n555 }\r\n556 \r\n557 \/* \r\n558  * \u5c06\u7ed3\u70b9(key\u4e3a\u8282\u70b9\u952e\u503c)\u63d2\u5165\u5230\u7ea2\u9ed1\u6811\u4e2d\r\n559  *\r\n560  * \u53c2\u6570\u8bf4\u660e\uff1a\r\n561  *     tree \u7ea2\u9ed1\u6811\u7684\u6839\u7ed3\u70b9\r\n562  *     key \u63d2\u5165\u7ed3\u70b9\u7684\u952e\u503c\r\n563  *\/\r\n564 template <class T>\r\n565 void RBTree<T>::insert(T key)\r\n566 {\r\n567     RBTNode<T> *z=NULL;\r\n568 \r\n569     \/\/ \u5982\u679c\u65b0\u5efa\u7ed3\u70b9\u5931\u8d25\uff0c\u5219\u8fd4\u56de\u3002\r\n570     if ((z=new RBTNode<T>(key,BLACK,NULL,NULL,NULL)) == NULL)\r\n571         return ;\r\n572 \r\n573     insert(mRoot, z);\r\n574 }\r\n575 \r\n576 \/*\r\n577  * \u7ea2\u9ed1\u6811\u5220\u9664\u4fee\u6b63\u51fd\u6570\r\n578  *\r\n579  * \u5728\u4ece\u7ea2\u9ed1\u6811\u4e2d\u5220\u9664\u63d2\u5165\u8282\u70b9\u4e4b\u540e(\u7ea2\u9ed1\u6811\u5931\u53bb\u5e73\u8861)\uff0c\u518d\u8c03\u7528\u8be5\u51fd\u6570\uff1b\r\n580  * \u76ee\u7684\u662f\u5c06\u5b83\u91cd\u65b0\u5851\u9020\u6210\u4e00\u9897\u7ea2\u9ed1\u6811\u3002\r\n581  *\r\n582  * \u53c2\u6570\u8bf4\u660e\uff1a\r\n583  *     root \u7ea2\u9ed1\u6811\u7684\u6839\r\n584  *     node \u5f85\u4fee\u6b63\u7684\u8282\u70b9\r\n585  *\/\r\n586 template <class T>\r\n587 void RBTree<T>::removeFixUp(RBTNode<T>* &root, RBTNode<T> *node, RBTNode<T> *parent)\r\n588 {\r\n589     RBTNode<T> *other;\r\n590 \r\n591     while ((!node || rb_is_black(node)) && node != root)\r\n592     {\r\n593         if (parent->left == node)\r\n594         {\r\n595             other = parent->right;\r\n596             if (rb_is_red(other))\r\n597             {\r\n598                 \/\/ Case 1: x\u7684\u5144\u5f1fw\u662f\u7ea2\u8272\u7684  \r\n599                 rb_set_black(other);\r\n600                 rb_set_red(parent);\r\n601                 leftRotate(root, parent);\r\n602                 other = parent->right;\r\n603             }\r\n604             if ((!other->left || rb_is_black(other->left)) &&\r\n605                 (!other->right || rb_is_black(other->right)))\r\n606             {\r\n607                 \/\/ Case 2: x\u7684\u5144\u5f1fw\u662f\u9ed1\u8272\uff0c\u4e14w\u7684\u4fe9\u4e2a\u5b69\u5b50\u4e5f\u90fd\u662f\u9ed1\u8272\u7684  \r\n608                 rb_set_red(other);\r\n609                 node = parent;\r\n610                 parent = rb_parent(node);\r\n611             }\r\n612             else\r\n613             {\r\n614                 if (!other->right || rb_is_black(other->right))\r\n615                 {\r\n616                     \/\/ Case 3: x\u7684\u5144\u5f1fw\u662f\u9ed1\u8272\u7684\uff0c\u5e76\u4e14w\u7684\u5de6\u5b69\u5b50\u662f\u7ea2\u8272\uff0c\u53f3\u5b69\u5b50\u4e3a\u9ed1\u8272\u3002  \r\n617                     rb_set_black(other->left);\r\n618                     rb_set_red(other);\r\n619                     rightRotate(root, other);\r\n620                     other = parent->right;\r\n621                 }\r\n622                 \/\/ Case 4: x\u7684\u5144\u5f1fw\u662f\u9ed1\u8272\u7684\uff1b\u5e76\u4e14w\u7684\u53f3\u5b69\u5b50\u662f\u7ea2\u8272\u7684\uff0c\u5de6\u5b69\u5b50\u4efb\u610f\u989c\u8272\u3002\r\n623                 rb_set_color(other, rb_color(parent));\r\n624                 rb_set_black(parent);\r\n625                 rb_set_black(other->right);\r\n626                 leftRotate(root, parent);\r\n627                 node = root;\r\n628                 break;\r\n629             }\r\n630         }\r\n631         else\r\n632         {\r\n633             other = parent->left;\r\n634             if (rb_is_red(other))\r\n635             {\r\n636                 \/\/ Case 1: x\u7684\u5144\u5f1fw\u662f\u7ea2\u8272\u7684  \r\n637                 rb_set_black(other);\r\n638                 rb_set_red(parent);\r\n639                 rightRotate(root, parent);\r\n640                 other = parent->left;\r\n641             }\r\n642             if ((!other->left || rb_is_black(other->left)) &&\r\n643                 (!other->right || rb_is_black(other->right)))\r\n644             {\r\n645                 \/\/ Case 2: x\u7684\u5144\u5f1fw\u662f\u9ed1\u8272\uff0c\u4e14w\u7684\u4fe9\u4e2a\u5b69\u5b50\u4e5f\u90fd\u662f\u9ed1\u8272\u7684  \r\n646                 rb_set_red(other);\r\n647                 node = parent;\r\n648                 parent = rb_parent(node);\r\n649             }\r\n650             else\r\n651             {\r\n652                 if (!other->left || rb_is_black(other->left))\r\n653                 {\r\n654                     \/\/ Case 3: x\u7684\u5144\u5f1fw\u662f\u9ed1\u8272\u7684\uff0c\u5e76\u4e14w\u7684\u5de6\u5b69\u5b50\u662f\u7ea2\u8272\uff0c\u53f3\u5b69\u5b50\u4e3a\u9ed1\u8272\u3002  \r\n655                     rb_set_black(other->right);\r\n656                     rb_set_red(other);\r\n657                     leftRotate(root, other);\r\n658                     other = parent->left;\r\n659                 }\r\n660                 \/\/ Case 4: x\u7684\u5144\u5f1fw\u662f\u9ed1\u8272\u7684\uff1b\u5e76\u4e14w\u7684\u53f3\u5b69\u5b50\u662f\u7ea2\u8272\u7684\uff0c\u5de6\u5b69\u5b50\u4efb\u610f\u989c\u8272\u3002\r\n661                 rb_set_color(other, rb_color(parent));\r\n662                 rb_set_black(parent);\r\n663                 rb_set_black(other->left);\r\n664                 rightRotate(root, parent);\r\n665                 node = root;\r\n666                 break;\r\n667             }\r\n668         }\r\n669     }\r\n670     if (node)\r\n671         rb_set_black(node);\r\n672 }\r\n673 \r\n674 \/* \r\n675  * \u5220\u9664\u7ed3\u70b9(node)\uff0c\u5e76\u8fd4\u56de\u88ab\u5220\u9664\u7684\u7ed3\u70b9\r\n676  *\r\n677  * \u53c2\u6570\u8bf4\u660e\uff1a\r\n678  *     root \u7ea2\u9ed1\u6811\u7684\u6839\u7ed3\u70b9\r\n679  *     node \u5220\u9664\u7684\u7ed3\u70b9\r\n680  *\/\r\n681 template <class T>\r\n682 void RBTree<T>::remove(RBTNode<T>* &root, RBTNode<T> *node)\r\n683 {\r\n684     RBTNode<T> *child, *parent;\r\n685     RBTColor color;\r\n686 \r\n687     \/\/ \u88ab\u5220\u9664\u8282\u70b9\u7684\"\u5de6\u53f3\u5b69\u5b50\u90fd\u4e0d\u4e3a\u7a7a\"\u7684\u60c5\u51b5\u3002\r\n688     if ( (node->left!=NULL) && (node->right!=NULL) ) \r\n689     {\r\n690         \/\/ \u88ab\u5220\u8282\u70b9\u7684\u540e\u7ee7\u8282\u70b9\u3002(\u79f0\u4e3a\"\u53d6\u4ee3\u8282\u70b9\")\r\n691         \/\/ \u7528\u5b83\u6765\u53d6\u4ee3\"\u88ab\u5220\u8282\u70b9\"\u7684\u4f4d\u7f6e\uff0c\u7136\u540e\u518d\u5c06\"\u88ab\u5220\u8282\u70b9\"\u53bb\u6389\u3002\r\n692         RBTNode<T> *replace = node;\r\n693 \r\n694         \/\/ \u83b7\u53d6\u540e\u7ee7\u8282\u70b9\r\n695         replace = replace->right;\r\n696         while (replace->left != NULL)\r\n697             replace = replace->left;\r\n698 \r\n699         \/\/ \"node\u8282\u70b9\"\u4e0d\u662f\u6839\u8282\u70b9(\u53ea\u6709\u6839\u8282\u70b9\u4e0d\u5b58\u5728\u7236\u8282\u70b9)\r\n700         if (rb_parent(node))\r\n701         {\r\n702             if (rb_parent(node)->left == node)\r\n703                 rb_parent(node)->left = replace;\r\n704             else\r\n705                 rb_parent(node)->right = replace;\r\n706         } \r\n707         else \r\n708             \/\/ \"node\u8282\u70b9\"\u662f\u6839\u8282\u70b9\uff0c\u66f4\u65b0\u6839\u8282\u70b9\u3002\r\n709             root = replace;\r\n710 \r\n711         \/\/ child\u662f\"\u53d6\u4ee3\u8282\u70b9\"\u7684\u53f3\u5b69\u5b50\uff0c\u4e5f\u662f\u9700\u8981\"\u8c03\u6574\u7684\u8282\u70b9\"\u3002\r\n712         \/\/ \"\u53d6\u4ee3\u8282\u70b9\"\u80af\u5b9a\u4e0d\u5b58\u5728\u5de6\u5b69\u5b50\uff01\u56e0\u4e3a\u5b83\u662f\u4e00\u4e2a\u540e\u7ee7\u8282\u70b9\u3002\r\n713         child = replace->right;\r\n714         parent = rb_parent(replace);\r\n715         \/\/ \u4fdd\u5b58\"\u53d6\u4ee3\u8282\u70b9\"\u7684\u989c\u8272\r\n716         color = rb_color(replace);\r\n717 \r\n718         \/\/ \"\u88ab\u5220\u9664\u8282\u70b9\"\u662f\"\u5b83\u7684\u540e\u7ee7\u8282\u70b9\u7684\u7236\u8282\u70b9\"\r\n719         if (parent == node)\r\n720         {\r\n721             parent = replace;\r\n722         } \r\n723         else\r\n724         {\r\n725             \/\/ child\u4e0d\u4e3a\u7a7a\r\n726             if (child)\r\n727                 rb_set_parent(child, parent);\r\n728             parent->left = child;\r\n729 \r\n730             replace->right = node->right;\r\n731             rb_set_parent(node->right, replace);\r\n732         }\r\n733 \r\n734         replace->parent = node->parent;\r\n735         replace->color = node->color;\r\n736         replace->left = node->left;\r\n737         node->left->parent = replace;\r\n738 \r\n739         if (color == BLACK)\r\n740             removeFixUp(root, child, parent);\r\n741 \r\n742         delete node;\r\n743         return ;\r\n744     }\r\n745 \r\n746     if (node->left !=NULL)\r\n747         child = node->left;\r\n748     else \r\n749         child = node->right;\r\n750 \r\n751     parent = node->parent;\r\n752     \/\/ \u4fdd\u5b58\"\u53d6\u4ee3\u8282\u70b9\"\u7684\u989c\u8272\r\n753     color = node->color;\r\n754 \r\n755     if (child)\r\n756         child->parent = parent;\r\n757 \r\n758     \/\/ \"node\u8282\u70b9\"\u4e0d\u662f\u6839\u8282\u70b9\r\n759     if (parent)\r\n760     {\r\n761         if (parent->left == node)\r\n762             parent->left = child;\r\n763         else\r\n764             parent->right = child;\r\n765     }\r\n766     else\r\n767         root = child;\r\n768 \r\n769     if (color == BLACK)\r\n770         removeFixUp(root, child, parent);\r\n771     delete node;\r\n772 }\r\n773 \r\n774 \/* \r\n775  * \u5220\u9664\u7ea2\u9ed1\u6811\u4e2d\u952e\u503c\u4e3akey\u7684\u8282\u70b9\r\n776  *\r\n777  * \u53c2\u6570\u8bf4\u660e\uff1a\r\n778  *     tree \u7ea2\u9ed1\u6811\u7684\u6839\u7ed3\u70b9\r\n779  *\/\r\n780 template <class T>\r\n781 void RBTree<T>::remove(T key)\r\n782 {\r\n783     RBTNode<T> *node; \r\n784 \r\n785     \/\/ \u67e5\u627ekey\u5bf9\u5e94\u7684\u8282\u70b9(node)\uff0c\u627e\u5230\u7684\u8bdd\u5c31\u5220\u9664\u8be5\u8282\u70b9\r\n786     if ((node = search(mRoot, key)) != NULL)\r\n787         remove(mRoot, node);\r\n788 }\r\n789 \r\n790 \/*\r\n791  * \u9500\u6bc1\u7ea2\u9ed1\u6811\r\n792  *\/\r\n793 template <class T>\r\n794 void RBTree<T>::destroy(RBTNode<T>* &tree)\r\n795 {\r\n796     if (tree==NULL)\r\n797         return ;\r\n798 \r\n799     if (tree->left != NULL)\r\n800         return destroy(tree->left);\r\n801     if (tree->right != NULL)\r\n802         return destroy(tree->right);\r\n803 \r\n804     delete tree;\r\n805     tree=NULL;\r\n806 }\r\n807 \r\n808 template <class T>\r\n809 void RBTree<T>::destroy()\r\n810 {\r\n811     destroy(mRoot);\r\n812 }\r\n813 \r\n814 \/*\r\n815  * \u6253\u5370\"\u4e8c\u53c9\u67e5\u627e\u6811\"\r\n816  *\r\n817  * key        -- \u8282\u70b9\u7684\u952e\u503c \r\n818  * direction  --  0\uff0c\u8868\u793a\u8be5\u8282\u70b9\u662f\u6839\u8282\u70b9;\r\n819  *               -1\uff0c\u8868\u793a\u8be5\u8282\u70b9\u662f\u5b83\u7684\u7236\u7ed3\u70b9\u7684\u5de6\u5b69\u5b50;\r\n820  *                1\uff0c\u8868\u793a\u8be5\u8282\u70b9\u662f\u5b83\u7684\u7236\u7ed3\u70b9\u7684\u53f3\u5b69\u5b50\u3002\r\n821  *\/\r\n822 template <class T>\r\n823 void RBTree<T>::print(RBTNode<T>* tree, T key, int direction)\r\n824 {\r\n825     if(tree != NULL)\r\n826     {\r\n827         if(direction==0)    \/\/ tree\u662f\u6839\u8282\u70b9\r\n828             cout << setw(2) << tree->key << \"(B) is root\" << endl;\r\n829         else                \/\/ tree\u662f\u5206\u652f\u8282\u70b9\r\n830             cout << setw(2) << tree->key <<  (rb_is_red(tree)?\"(R)\":\"(B)\") << \" is \" << setw(2) << key << \"'s \"  << setw(12) << (direction==1?\"right child\" : \"left child\") << endl;\r\n831 \r\n832         print(tree->left, tree->key, -1);\r\n833         print(tree->right,tree->key,  1);\r\n834     }\r\n835 }\r\n836 \r\n837 template <class T>\r\n838 void RBTree<T>::print()\r\n839 {\r\n840     if (mRoot != NULL)\r\n841         print(mRoot, mRoot->key, 0);\r\n842 }\r\n843 \r\n844 #endif<\/pre>\n
\"\u590d\u5236\u4ee3\u7801\"<\/a><\/span><\/div>\n<\/div>\n<\/div>\n
\u7ea2\u9ed1\u6811\u7684\u6d4b\u8bd5\u6587\u4ef6(RBTreeTest.cpp)<\/p>\n
\"\"\u00a0View Code<\/span><\/div>\n
 <\/p>\n
<\/a>\u7ea2\u9ed1\u6811\u7684C++\u6d4b\u8bd5\u7a0b\u5e8f<\/strong><\/h3>\n
\u6d4b\u8bd5\u7a0b\u5e8f\u5df2\u7ecf\u5305\u542b\u5728\u76f8\u5e94\u7684\u5b9e\u73b0\u6587\u4ef6(MaxHeap.cpp)\u4e2d\u4e86\uff0c\u8fd9\u91cc\u5c31\u4e0d\u518d\u91cd\u590d\u8bf4\u660e\u3002\u4e0b\u9762\u662f\u6d4b\u8bd5\u7a0b\u5e8f\u7684\u8fd0\u884c\u7ed3\u679c\uff1a<\/p>\n
\n
\"\u590d\u5236\u4ee3\u7801\"<\/a><\/span><\/div>\n
== \u539f\u59cb\u6570\u636e: 10 40 30 60 90 70 20 50 80 \r\n== \u524d\u5e8f\u904d\u5386: 30 10 20 60 40 50 80 70 90 \r\n== \u4e2d\u5e8f\u904d\u5386: 10 20 30 40 50 60 70 80 90 \r\n== \u540e\u5e8f\u904d\u5386: 20 10 50 40 70 90 80 60 30 \r\n== \u6700\u5c0f\u503c: 10\r\n== \u6700\u5927\u503c: 90\r\n== \u6811\u7684\u8be6\u7ec6\u4fe1\u606f: \r\n30(B) is root\r\n10(B) is 30's   left child\r\n20(R) is 10's  right child\r\n60(R) is 30's  right child\r\n40(B) is 60's   left child\r\n50(R) is 40's  right child\r\n80(B) is 60's  right child\r\n70(R) is 80's   left child\r\n90(R) is 80's  right child<\/pre>\n
\"\u590d\u5236\u4ee3\u7801\"<\/a><\/span><\/div>\n<\/div>\n
 <\/p>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
\u539f\u6587\u5730\u5740   \u6982\u8981 \u524d\u9762\u5206\u522b\u4ecb<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"colormag_page_container_layout":"default_layout","colormag_page_sidebar_layout":"default_layout","footnotes":""},"categories":[],"tags":[119],"class_list":["post-4507","post","type-post","status-publish","format-standard","hentry","tag-03-"],"_links":{"self":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/4507","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/comments?post=4507"}],"version-history":[{"count":0,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/4507\/revisions"}],"wp:attachment":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/media?parent=4507"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/categories?post=4507"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/tags?post=4507"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}