{"id":50973,"date":"2025-08-10T15:24:23","date_gmt":"2025-08-10T07:24:23","guid":{"rendered":"https:\/\/www.wsisp.com\/helps\/50973.html"},"modified":"2025-08-10T15:24:23","modified_gmt":"2025-08-10T07:24:23","slug":"%e7%ac%ac%e5%8d%81%e5%85%ad%e8%ae%b2%ef%bc%9aavl%e6%a0%91%e5%92%8c%e7%ba%a2%e9%bb%91%e6%a0%91","status":"publish","type":"post","link":"https:\/\/www.wsisp.com\/helps\/50973.html","title":{"rendered":"\u7b2c\u5341\u516d\u8bb2\uff1aAVL\u6811\u548c\u7ea2\u9ed1\u6811"},"content":{"rendered":"

\u76ee\u5f55<\/p>\n

1\u3001\u5e95\u5c42\u7ed3\u6784<\/p>\n

2\u3001AVL\u6811<\/p>\n

2.1\u3001\u6982\u5ff5<\/p>\n

2.2\u3001AVL\u6811\u7684\u63d2\u5165<\/p>\n

2.2.1\u3001\u53f3\u5355\u65cb<\/p>\n

2.2.2\u3001\u5de6\u5355\u65cb<\/p>\n

2.2.3\u3001\u5de6\u53f3\u5355\u65cb<\/p>\n

2.2.4\u3001\u53f3\u5de6\u5355\u65cb<\/p>\n

2.3\u3001AVL\u6811\u7684\u5220\u9664<\/p>\n

2.4\u3001AVL\u6811\u7684\u6027\u80fd<\/p>\n

2.5\u3001\u6a21\u62df\u5b9e\u73b0<\/p>\n

3\u3001\u7ea2\u9ed1\u6811<\/p>\n

3.1\u3001\u6982\u5ff5<\/p>\n

3.2\u3001\u7ea2\u9ed1\u6811\u7684\u63d2\u5165<\/p>\n

3.2.1\u3001\u60c5\u51b5\u4e00<\/p>\n

3.2.2\u3001\u60c5\u51b5\u4e8c<\/p>\n

3.2.3\u3001\u60c5\u51b5\u4e09<\/p>\n

3.3\u3001\u7ea2\u9ed1\u6811\u7684\u5220\u9664<\/p>\n

3.4\u3001\u7ea2\u9ed1\u6811\u7684\u6027\u80fd<\/p>\n

3.5\u3001\u6a21\u62df\u5b9e\u73b0<\/p>\n

4\u3001\u6a21\u62df\u5b9e\u73b0map\u548cset<\/p>\n

\n

1\u3001\u5e95\u5c42\u7ed3\u6784<\/h3>\n

\u524d\u9762\u5bf9map\u3001multimap\u3001set\u4ee5\u53camultiset\u8fdb\u884c\u4e86\u7b80\u5355\u7684\u4ecb\u7ecd，\u8fd9\u51e0\u4e2a\u5bb9\u5668\u6709\u4e2a\u5171\u540c\u70b9\u662f：\u5176\u5e95\u5c42\u90fd\u662f\u6309\u7167\u4e8c\u53c9\u641c\u7d22\u6811\u6765\u5b9e\u73b0\u7684，\u4f46\u662f\u4e8c\u53c9\u641c\u7d22\u6811\u6709\u5176\u81ea\u8eab\u7684\u7f3a\u9677，\u5047\u5982\u5f80\u6811\u4e2d\u63d2\u5165\u7684\u5143\u7d20\u6709\u5e8f\u6216\u8005\u63a5\u8fd1\u6709\u5e8f，\u4e8c\u53c9\u641c\u7d22\u6811\u5c31\u4f1a\u9000\u5316\u6210\u5355\u652f\u6811，\u65f6\u95f4\u590d\u6742\u5ea6\u4f1a\u9000\u5316\u6210O(N)，\u56e0\u6b64 map\u3001set\u7b49\u5173\u8054\u5f0f\u5bb9\u5668\u7684\u5e95\u5c42\u7ed3\u6784\u662f\u5bf9\u4e8c\u53c9\u6811\u8fdb\u884c\u4e86\u5e73\u8861\u5904\u7406，\u5373\u91c7\u7528\u7ea2\u9ed1\u6811\u6765\u5b9e\u73b0\u3002<\/p>\n

2\u3001AVL\u6811<\/h3>\n

2.1\u3001\u6982\u5ff5<\/h4>\n

\u4e8c\u53c9\u641c\u7d22\u6811\u867d\u53ef\u4ee5\u7f29\u77ed\u67e5\u627e\u7684\u6548\u7387，\u4f46\u5982\u679c\u6570\u636e\u6709\u5e8f\u6216\u63a5\u8fd1\u6709\u5e8f\u4e8c\u53c9\u641c\u7d22\u6811\u5c06\u9000\u5316\u4e3a\u5355\u652f\u6811，\u67e5 \u627e\u5143\u7d20\u76f8\u5f53\u4e8e\u5728\u987a\u5e8f\u8868\u4e2d\u641c\u7d22\u5143\u7d20，\u6548\u7387\u4f4e\u4e0b\u3002\u56e0\u6b64，\u4e24\u4f4d\u4fc4\u7f57\u65af\u7684\u6570\u5b66\u5bb6G.M.Adelson-Velskii \u548cE.M.Landis\u57281962\u5e74\u53d1\u660e\u4e86\u4e00\u79cd\u89e3\u51b3\u4e0a\u8ff0\u95ee\u9898\u7684\u65b9\u6cd5：\u5f53\u5411\u4e8c\u53c9\u641c\u7d22\u6811\u4e2d\u63d2\u5165\u65b0\u7ed3\u70b9\u540e，\u5982\u679c\u80fd\u4fdd\u8bc1\u6bcf\u4e2a\u7ed3\u70b9\u7684\u5de6\u53f3\u5b50\u6811\u9ad8\u5ea6\u4e4b\u5dee\u7684\u7edd\u5bf9\u503c\u4e0d\u8d85\u8fc71(\u9700\u8981\u5bf9\u6811\u4e2d\u7684\u7ed3\u70b9\u8fdb\u884c\u8c03\u6574)，\u5373\u53ef\u964d\u4f4e\u6811\u7684\u9ad8\u5ea6，\u4ece\u800c\u51cf\u5c11\u5e73\u5747\u641c\u7d22\u957f\u5ea6\u3002<\/p>\n

\u4e00\u68f5AVL\u6811\u6216\u8005\u662f\u7a7a\u6811，\u6216\u8005\u662f\u5177\u6709\u4ee5\u4e0b\u6027\u8d28\u7684\u4e8c\u53c9\u641c\u7d22\u6811：<\/p>\n

1\u3001\u5b83\u7684\u5de6\u53f3\u5b50\u6811\u90fd\u662fAVL\u6811\u3002<\/p>\n

2\u3001\u5de6\u53f3\u5b50\u6811\u9ad8\u5ea6\u4e4b\u5dee(\u7b80\u79f0\u5e73\u8861\u56e0\u5b50)\u7684\u7edd\u5bf9\u503c\u4e0d\u8d85\u8fc71\u3002<\/p>\n

\"\"<\/p>\n

\u5982\u679c\u4e00\u68f5\u4e8c\u53c9\u641c\u7d22\u6811\u662f\u9ad8\u5ea6\u5e73\u8861\u7684，\u5b83\u5c31\u662fAVL\u6811\u3002\u5982\u679c\u5b83\u6709n\u4e2a\u7ed3\u70b9，\u641c\u7d22\u65f6\u95f4\u590d\u6742\u5ea6O(logN)\u3002<\/p>\n

2.2\u3001AVL\u6811\u7684\u63d2\u5165<\/h4>\n

AVL\u6811\u5c31\u662f\u5728\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u57fa\u7840\u4e0a\u5f15\u5165\u4e86\u5e73\u8861\u56e0\u5b50，\u56e0\u6b64AVL\u6811\u4e5f\u53ef\u4ee5\u770b\u6210\u662f\u4e8c\u53c9\u641c\u7d22\u6811\u3002AVL\u6811\u7684\u63d2\u5165\u8fc7\u7a0b\u53ef\u4ee5\u5206\u4e3a\u4e24\u6b65：<\/p>\n

1\u3001\u6309\u7167\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u65b9\u5f0f\u63d2\u5165\u65b0\u8282\u70b9\u3002<\/p>\n

2\u3001\u8c03\u6574\u8282\u70b9\u7684\u5e73\u8861\u56e0\u5b50\u3002<\/p>\n

\u5982\u679c\u5728\u4e00\u68f5\u539f\u672c\u662f\u5e73\u8861\u7684AVL\u6811\u4e2d\u63d2\u5165\u4e00\u4e2a\u65b0\u8282\u70b9，\u53ef\u80fd\u9020\u6210\u4e0d\u5e73\u8861，\u6b64\u65f6\u5fc5\u987b\u8c03\u6574\u6811\u7684\u7ed3\u6784， \u4f7f\u4e4b\u5e73\u8861\u5316\u3002\u6839\u636e\u8282\u70b9\u63d2\u5165\u4f4d\u7f6e\u7684\u4e0d\u540c，AVL\u6811\u7684\u65cb\u8f6c\u5206\u4e3a\u56db\u79cd\u4ee5\u4e0b\u56db\u79cd：\u5206\u522b\u4e3a\u53f3\u5355\u65cb\u3001\u5de6\u5355\u65cb\u3001\u5de6\u53f3\u5355\u65cb\u3001\u53f3\u5de6\u5355\u65cb\u3002<\/p>\n

2.2.1\u3001\u53f3\u5355\u65cb<\/h5>\n

\u65b0\u8282\u70b9\u63d2\u5165\u8f83\u9ad8\u5de6\u5b50\u6811\u7684\u5de6\u4fa7（\u5de6\u5de6）：\u53f3\u5355\u65cb<\/p>\n

\u5982\u56fe\u6240\u793a：<\/p>\n

\"\"<\/p>\n

\u5176\u4e2d，a\u3001b\u3001c\u5206\u522b\u4e3a\u9ad8\u5ea6\u4e3ah\u7684AVL\u6811，h\u5927\u4e8e\u7b49\u4e8e0\u3002<\/p>\n

\u5373：\u5bf960\u8fdb\u884c\u53f3\u5355\u65cb，\u65cb\u8f6c\u5b8c\u6210\u540e\u518d\u8003\u8651\u5e73\u8861\u56e0\u5b50\u7684\u66f4\u65b0\u3002<\/p>\n

2.2.2\u3001\u5de6\u5355\u65cb<\/h5>\n

\u65b0\u8282\u70b9\u63d2\u5165\u8f83\u9ad8\u53f3\u5b50\u6811\u7684\u53f3\u4fa7（\u53f3\u53f3）：\u5de6\u5355\u65cb<\/p>\n

\u5982\u56fe\u6240\u793a：<\/p>\n

\"\"<\/p>\n

\u5176\u4e2d，a\u3001b\u3001c\u5206\u522b\u4e3a\u9ad8\u5ea6\u4e3ah\u7684AVL\u6811，h\u5927\u4e8e\u7b49\u4e8e0\u3002<\/p>\n

\u5373：\u5bf930\u8fdb\u884c\u5de6\u5355\u65cb，\u65cb\u8f6c\u5b8c\u6210\u540e\u518d\u8003\u8651\u5e73\u8861\u56e0\u5b50\u7684\u66f4\u65b0\u3002<\/p>\n

2.2.3\u3001\u5de6\u53f3\u5355\u65cb<\/h5>\n

\u65b0\u8282\u70b9\u63d2\u5165\u8f83\u9ad8\u5de6\u5b50\u6811\u7684\u53f3\u4fa7（\u5de6\u53f3）：\u5148\u5de6\u5355\u65cb\u518d\u53f3\u5355\u65cb<\/p>\n

\u5982\u56fe\u6240\u793a：<\/p>\n

\"\"<\/p>\n

\u5176\u4e2d，a\u3001d\u5206\u522b\u4e3a\u9ad8\u5ea6\u4e3ah\u7684AVL\u6811，b\u3001c\u5206\u522b\u4e3a\u9ad8\u5ea6\u4e3ah-1\u7684AVL\u6811，h\u5927\u4e8e\u7b49\u4e8e0\u3002\u5982\u679ch=0，60\u8fd9\u4e2a\u7ed3\u70b9\u5373\u662f\u65b0\u589e\u7684\u7ed3\u70b9\u3002<\/p>\n

\u5373：\u5148\u5bf930\u8fdb\u884c\u5de6\u5355\u65cb，\u7136\u540e\u518d\u5bf990\u8fdb\u884c\u53f3\u5355\u65cb，\u65cb\u8f6c\u5b8c\u6210\u540e\u518d\u8003\u8651\u5e73\u8861\u56e0\u5b50\u7684\u66f4\u65b0\u3002<\/p>\n

2.2.4\u3001\u53f3\u5de6\u5355\u65cb<\/h5>\n

\u65b0\u8282\u70b9\u63d2\u5165\u8f83\u9ad8\u53f3\u5b50\u6811\u7684\u5de6\u4fa7（\u53f3\u5de6）：\u5148\u53f3\u5355\u65cb\u518d\u5de6\u5355\u65cb<\/p>\n

\u5982\u56fe\u6240\u793a：<\/p>\n

\"\"<\/p>\n

\u5176\u4e2d，a\u3001d\u5206\u522b\u4e3a\u9ad8\u5ea6\u4e3ah\u7684AVL\u6811，b\u3001c\u5206\u522b\u4e3a\u9ad8\u5ea6\u4e3ah-1\u7684AVL\u6811，h\u5927\u4e8e\u7b49\u4e8e0\u3002\u5982\u679ch=0，60\u8fd9\u4e2a\u7ed3\u70b9\u5373\u662f\u65b0\u589e\u7684\u7ed3\u70b9\u3002<\/p>\n

\u5373：\u5148\u5bf990\u8fdb\u884c\u53f3\u5355\u65cb，\u518d\u5bf930\u8fdb\u884c\u5de6\u5355\u65cb，\u65cb\u8f6c\u5b8c\u6210\u540e\u518d\u8003\u8651\u5e73\u8861\u56e0\u5b50\u7684\u66f4\u65b0\u3002<\/p>\n

2.3\u3001AVL\u6811\u7684\u5220\u9664<\/h4>\n

\u5220\u9664\u6bd4\u63d2\u5165\u8fd8\u8981\u590d\u6742，\u5177\u4f53\u5b9e\u73b0\u53ef\u53c2\u8003\u300a\u7b97\u6cd5\u5bfc\u8bba\u300b\u6216\u300a\u6570\u636e\u7ed3\u6784（\u7528\u9762\u5411\u5bf9\u8c61\u65b9\u6cd5\u4e0eC++\u63cf\u8ff0）\u300b\u6bb7\u4eba\u6606\u7248\u3002<\/p>\n

2.4\u3001AVL\u6811\u7684\u6027\u80fd<\/h4>\n

AVL\u6811\u662f\u4e00\u68f5\u7edd\u5bf9\u5e73\u8861\u7684\u4e8c\u53c9\u641c\u7d22\u6811，\u5176\u8981\u6c42\u6bcf\u4e2a\u8282\u70b9\u7684\u5de6\u53f3\u5b50\u6811\u9ad8\u5ea6\u5dee\u7684\u7edd\u5bf9\u503c\u90fd\u4e0d\u8d85\u8fc71，\u8fd9 \u6837\u53ef\u4ee5\u4fdd\u8bc1\u67e5\u8be2\u65f6\u9ad8\u6548\u7684\u65f6\u95f4\u590d\u6742\u5ea6，\u5373O（log\u00a0(N)）\u3002<\/p>\n

2.5\u3001\u6a21\u62df\u5b9e\u73b0<\/h4>\n

template<class K, class V>
\nstruct AVLTreeNode
\n{
\nAVLTreeNode(const pair<K, V>& kv)
\n:_left(nullptr)
\n,_right(nullptr)
\n,_parent(nullptr)
\n,_kv(kv)
\n,_bf(0)
\n{}<\/p>\n

AVLTreeNode* _left;
\nAVLTreeNode* _right;
\nAVLTreeNode* _parent;<\/p>\n

pair<K, V> _kv;
\nint _bf; \/\/ \u5e73\u8861\u56e0\u5b50
\n};<\/p>\n

template<class K, class V>
\nclass AVLTree
\n{
\ntypedef AVLTreeNode<K, V> Node;
\npublic:
\nbool Insert(const pair<K, V>& kv) \/\/ \u63d2\u5165
\n{
\nif (_root == nullptr)
\n{
\n_root = new Node(kv);
\nreturn true;
\n}<\/p>\n

Node* parent = nullptr;
\nNode* cur = _root;<\/p>\n

while (cur)
\n{
\nif (cur->_kv.first < kv.first)
\n{
\nparent = cur;
\ncur = cur->_right;
\n}
\nelse if (cur->_kv.first > kv.first)
\n{
\nparent = cur;
\ncur = cur->_left;
\n}
\nelse
\n{
\nreturn false;
\n}
\n}<\/p>\n

cur = new Node(kv);
\nif (parent->_kv.first < kv.first)
\n{
\nparent->_right = cur;
\ncur->_parent = parent;
\n}
\nelse
\n{
\nparent->_left = cur;
\ncur->_parent = parent;
\n}<\/p>\n

\/*
\n* \u65b0\u7ed3\u70b9\u63d2\u5165\u540e，AVL\u6811\u7684\u5e73\u8861\u6027\u53ef\u80fd\u4f1a\u906d\u5230\u7834\u574f，\u6b64\u65f6\u5c31\u9700\u8981\u66f4\u65b0\u5e73\u8861\u56e0\u5b50，\u5e76\u68c0\u6d4b\u662f\u5426\u7834\u574f\u4e86AVL\u6811\u7684\u5e73\u8861\u6027\u3002
\n*
\n* cur\u63d2\u5165\u4e4b\u524d，parent\u7684\u5e73\u8861\u56e0\u5b50\u5206\u4e3a\u4ee5\u4e0b\u4e09\u79cd\u60c5\u51b5：-1，0，1\u3002
\n*
\n* 1\u3001\u5982\u679ccur\u63d2\u5165\u5230parent\u7684\u5de6\u4fa7，\u53ea\u9700\u8981\u7ed9parent\u7684\u5e73\u8861\u56e0\u5b50-1\u5373\u53ef\u3002
\n* 2\u3001\u5982\u679ccur\u63d2\u5165\u5230parent\u7684\u53f3\u4fa7，\u53ea\u9700\u8981\u7ed9parent\u7684\u5e73\u8861\u56e0\u5b50+1\u5373\u53ef\u3002
\n*\/<\/p>\n

while (parent)
\n{
\n\/\/ \u4fee\u6539\u5e73\u8861\u56e0\u5b50
\nif (cur == parent->_left)
\n{
\nparent->_bf–;
\n}
\nelse
\n{
\nparent->_bf++;
\n}<\/p>\n

\/*
\n* \u6b64\u65f6，parent\u7684\u5e73\u8861\u56e0\u5b50\u53ef\u80fd\u6709\u4e09\u79cd\u60c5\u51b5：0\u3001\u6b63\u8d1f1\u3001\u6b63\u8d1f2
\n*
\n* 1\u3001\u5982\u679cparent\u7684\u5e73\u8861\u56e0\u5b50\u4e3a0，\u8bf4\u660e\u63d2\u5165\u4e4b\u524dparent\u7684\u5e73\u8861\u56e0\u5b50\u4e3a\u6b63\u8d1f1，\u63d2\u5165\u540e\u88ab\u8c03\u6574\u62100，\u6b64\u65f6\u6ee1\u8db3AVL\u6811\u7684\u6027\u8d28，\u63d2\u5165\u6210\u529f\u3002
\n* \u56e0\u4e3a\u65b0\u63d2\u5165\u7684\u7ed3\u70b9\u586b\u4e0a\u4e86\u4f4e\u7684\u90a3\u4e00\u8fb9，\u4e0d\u7528\u518d\u7ee7\u7eed\u5411\u4e0a\u66f4\u65b0\u3002
\n*
\n* 2\u3001\u5982\u679cparent\u7684\u5e73\u8861\u56e0\u5b50\u4e3a\u6b63\u8d1f1，\u8bf4\u660e\u63d2\u5165\u524dparent\u7684\u5e73\u8861\u56e0\u5b50\u4e00\u5b9a\u4e3a0，\u63d2\u5165\u540e\u88ab\u66f4\u65b0\u6210\u6b63\u8d1f1，\u6b64\u65f6\u4ee5parent\u4e3a\u6839\u7684\u6811
\n* \u7684\u9ad8\u5ea6\u589e\u52a0，\u9700\u8981\u7ee7\u7eed\u5411\u4e0a\u66f4\u65b0\u3002
\n*
\n* 3\u3001\u5982\u679cparent\u7684\u5e73\u8861\u56e0\u5b50\u4e3a\u6b63\u8d1f2，\u5219parent\u7684\u5e73\u8861\u56e0\u5b50\u8fdd\u53cd\u5e73\u8861\u6811\u7684\u6027\u8d28，\u9700\u8981\u5bf9\u5176\u8fdb\u884c\u65cb\u8f6c\u5904\u7406\u3002
\n*\/<\/p>\n

if (parent->_bf == 0) \/\/ \u5e73\u8861\u56e0\u5b50\u4e3a0，\u4e0d\u7528\u518d\u5411\u4e0a\u66f4\u65b0\u5e73\u8861\u56e0\u5b50\u3002
\n{
\nbreak;
\n}
\nelse if (parent->_bf == 1 || parent->_bf == -1) \/\/ \u5e73\u8861\u56e0\u5b50\u4e3a\u6b63\u8d1f1，\u5411\u4e0a\u8c03\u6574\u3002
\n{
\ncur = parent;
\nparent = parent->_parent;
\n}
\nelse if (parent->_bf == 2 || parent->_bf == -2) \/\/ \u5e73\u8861\u56e0\u5b50\u4e3a\u6b63\u8d1f2，\u56e0\u6b64\u9700\u8981\u505a\u65cb\u8f6c\u5904\u7406
\n{
\n\/\/ \u65cb\u8f6c，\u76ee\u7684\u662f\u4fdd\u6301\u6811\u7684\u5e73\u8861
\nif (parent->_bf == 2 && cur->_bf == 1)
\n{
\nRotateL(parent); \/\/ \u5de6\u65cb
\n}
\nelse if (parent->_bf == -2 && cur->_bf == -1)
\n{
\nRotateR(parent); \/\/ \u53f3\u65cb
\n}
\nelse if (parent->_bf == 2 && cur->_bf == -1)
\n{
\nRotateRL(parent); \/\/ \u53f3\u5de6\u65cb
\n}
\nelse if (parent->_bf == -2 && cur->_bf == 1)
\n{
\nRotateLR(parent); \/\/ \u5de6\u53f3\u65cb
\n}<\/p>\n

\/\/\u65cb\u8f6c\u5b8c\u6210\u540e，\u6811\u5df2\u7ecf\u5e73\u8861\u4e86\u3002
\nbreak;
\n}
\nelse
\n{
\nassert(false);
\n}
\n}
\nreturn true;
\n}<\/p>\n

void RotateL(Node* parent) \/\/ \u5de6\u65cb
\n{
\nNode* subR = parent->_right;
\nNode* subRL = subR->_left;<\/p>\n

parent->_right = subRL;
\nsubR->_left = parent;<\/p>\n

Node* parentParent = parent->_parent;<\/p>\n

parent->_parent = subR;
\nif(subRL)
\nsubRL->_parent = parent;<\/p>\n

if (_root == parent)
\n{
\n_root = subR;
\nsubR->_parent = nullptr;
\n}
\nelse
\n{
\nif (parentParent->_left == parent)
\n{
\nparentParent->_left = subR;
\n}
\nelse
\n{
\nparentParent->_right = subR;
\n}
\nsubR->_parent = parentParent;
\n}
\nparent->_bf = subR->_bf = 0;
\n}<\/p>\n

void RotateR(Node* parent) \/\/\u53f3\u65cb
\n{
\nNode* subL = parent->_left;
\nNode* subLR = subL->_right;<\/p>\n

parent->_left = subLR;
\nif (subLR) \/\/ subLR\u53ef\u80fd\u662f\u7a7a\u7684\u3002
\nsubLR->_parent = parent;<\/p>\n

Node* parentParent = parent->_parent;<\/p>\n

subL->_right = parent;
\nparent->_parent = subL;<\/p>\n

if (_root == parent) \/\/ parent\u53ef\u80fd\u662f\u6839\u7ed3\u70b9\u3002
\n{
\n_root = subL;
\nsubL->_parent = nullptr;
\n}
\nelse \/\/ parent\u4e0d\u662f\u6839\u7ed3\u70b9，\u662f\u5b50\u6811\u3002
\n{
\nif (parentParent->_left == parent) \/\/ \u662f\u5de6\u5b50\u6811
\n{
\nparentParent->_left = subL;
\n}
\nelse \/\/ \u662f\u53f3\u5b50\u6811
\n{
\nparentParent->_right = subL;
\n}
\nsubL->_parent = parentParent;
\n}
\nsubL->_bf = parent->_bf = 0;
\n}<\/p>\n

void RotateRL(Node* parent) \/\/ \u53f3\u5de6\u65cb
\n{
\nNode* subR = parent->_right;
\nNode* subRL = subR->_left;
\nint bf = subRL->_bf;<\/p>\n

RotateR(parent->_right);
\nRotateL(parent);<\/p>\n

if (bf == 0) \/\/ subRL\u81ea\u5df1\u5c31\u662f\u65b0\u589e
\n{
\nparent->_bf = subR->_bf = subRL->_bf = 0;
\n}
\nelse if (bf == -1) \/\/ subRL\u7684\u5de6\u5b50\u6811\u65b0\u589e
\n{
\nparent->_bf = 0;
\nsubRL->_bf = 0;
\nsubR->_bf = 1;
\n}
\nelse if (bf == 1) \/\/ subRL\u7684\u53f3\u5b50\u6811\u65b0\u589e
\n{
\nparent->_bf = -1;
\nsubRL->_bf = 0;
\nsubR->_bf = 0;
\n}
\nelse
\n{
\nassert(false);
\n}
\n}<\/p>\n

void RotateLR(Node* parent) \/\/ \u5de6\u53f3\u65cb
\n{
\nNode* subL = parent->_left;
\nNode* subLR = subL->_right;
\nint bf = subLR->_bf;<\/p>\n

RotateL(parent->_left);
\nRotateR(parent);<\/p>\n

if (bf == 0)
\n{
\nsubL->_bf = subLR->_bf = parent->_bf = 0;
\n}
\nelse if (bf == 1)
\n{
\nparent->_bf = 0;
\nsubL->_bf = -1;
\nsubLR->_bf = 0;
\n}
\nelse if(bf == -1)
\n{
\nparent->_bf = 1;
\nsubL->_bf = 0;
\nsubLR->_bf = 0;
\n}
\nelse
\n{
\nassert(false);
\n}
\n}<\/p>\n

void InOrder() \/\/ \u4e2d\u5e8f\u904d\u5386
\n{
\n_InOrder(_root);
\ncout << endl;
\n}<\/p>\n

bool IsBalance() \/\/ \u662f\u5426\u662f\u5e73\u8861\u6811
\n{
\nreturn _IsBalance(_root);
\n}<\/p>\n

int Height() \/\/ \u6811\u7684\u9ad8\u5ea6
\n{
\nreturn _Height(_root);
\n}<\/p>\n

size_t Size() \/\/ \u8fd4\u56de\u5143\u7d20\u4e2a\u6570
\n{
\nreturn _Size(_root);
\n}<\/p>\n

Node* Find(const K& key) \/\/ \u67e5\u627e
\n{
\nNode* cur = _root;
\nwhile (cur)
\n{
\nif (cur->_kv.first < key)
\n{
\ncur = cur->_right;
\n}
\nelse if (cur->_kv.first > key)
\n{
\ncur = cur->_left;
\n}
\nelse
\n{
\nreturn cur;
\n}
\n}
\nreturn NULL;
\n}<\/p>\n

private:
\nvoid _InOrder(Node* root)
\n{
\nif (root == nullptr)
\nreturn;
\n_InOrder(root->_left);
\ncout << root->_kv.first << ':' << root->_kv.second << endl;;
\n_InOrder(root->_right);
\n}<\/p>\n

bool _IsBalance(Node* root)
\n{
\nif (root == nullptr)
\n{
\nreturn true;
\n}<\/p>\n

int leftHeight = _Height(root->_left);
\nint rightHeight = _Height(root->_right);<\/p>\n

if (rightHeight – leftHeight != root->_bf)
\n{
\ncout << root->_kv.first << ':' << root->_kv.second << " \u5e73\u8861\u56e0\u5b50\u5f02\u5e38" << endl;
\nreturn false;
\n}<\/p>\n

return abs(rightHeight – leftHeight) < 2
\n&& _IsBalance(root->_left)
\n&& _IsBalance(root->_right);
\n}<\/p>\n

int _Height(Node* root)
\n{
\nif (root == nullptr)
\nreturn 0;
\nint leftHeight = _Height(root->_left);
\nint rightHeight = _Height(root->_right);<\/p>\n

return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
\n}<\/p>\n

size_t _Size(Node* root)
\n{
\nif (root == nullptr)
\nreturn 0;<\/p>\n

return _Size(root->_left) + _Size(root->_right) + 1;
\n}<\/p>\n

private:
\nNode* _root = nullptr;
\n}; <\/p>\n

3\u3001\u7ea2\u9ed1\u6811<\/h3>\n

3.1\u3001\u6982\u5ff5<\/h4>\n

\u7ea2\u9ed1\u6811，\u662f\u4e00\u79cd\u4e8c\u53c9\u641c\u7d22\u6811，\u4f46\u5728\u6bcf\u4e2a\u7ed3\u70b9\u4e0a\u589e\u52a0\u4e00\u4e2a\u5b58\u50a8\u4f4d\u8868\u793a\u7ed3\u70b9\u7684\u989c\u8272，\u53ef\u4ee5\u662f\u9ed1\u8272\u6216\u8005\u662f\u7ea2\u8272\u3002 \u901a\u8fc7\u5bf9\u4efb\u610f\u4e00\u6761\u4ece\u6839\u5230\u53f6\u5b50\u7ed3\u70b9\u7684\u8def\u5f84\u4e0a\u5404\u4e2a\u7ed3\u70b9\u7740\u8272\u65b9\u5f0f\u7684\u9650\u5236，\u7ea2\u9ed1\u6811\u786e\u4fdd\u6ca1\u6709\u4e00\u6761\u8def\u5f84\u4f1a\u6bd4\u5176\u4ed6\u8def\u5f84\u957f\u51fa2\u500d，\u56e0\u800c\u662f\u63a5\u8fd1\u5e73\u8861\u7684\u3002\u5982\u4e0b\u56fe\u6240\u793a：<\/p>\n

\"\"<\/p>\n

\u7ea2\u9ed1\u6811\u7684\u6027\u8d28：<\/p>\n

1\u3001\u6bcf\u4e2a\u7ed3\u70b9\u4e0d\u662f\u7ea2\u8272\u5c31\u662f\u9ed1\u8272\u3002<\/p>\n

2\u3001\u6839\u8282\u70b9\u662f\u9ed1\u8272\u7684 \u3002<\/p>\n

3\u3001\u5982\u679c\u4e00\u4e2a\u8282\u70b9\u662f\u7ea2\u8272\u7684，\u5219\u5b83\u7684\u4e24\u4e2a\u5b69\u5b50\u7ed3\u70b9\u662f\u9ed1\u8272\u7684\u3002（\u4e5f\u5c31\u662f\u8bf4\u6811\u4e2d\u4e0d\u80fd\u51fa\u73b0\u8fde\u7eed\u7684\u7ea2\u8272\u7ed3\u70b9\u3002\u7236\u5b50\u7ed3\u70b9\u7684\u989c\u8272\u53ea\u80fd\u662f：\u9ed1+\u9ed1\u3001\u9ed1+\u7ea2\u3001\u7ea2+\u9ed1\u4e09\u79cd\u60c5\u51b5）\u3002<\/p>\n

4\u3001\u5bf9\u4e8e\u6bcf\u4e2a\u7ed3\u70b9，\u4ece\u8be5\u7ed3\u70b9\u5230\u5176\u6240\u6709\u53f6\u5b50\u7ed3\u70b9\u7684\u8def\u5f84\u4e0a，\u5747\u5305\u542b\u76f8\u540c\u6570\u76ee\u7684\u9ed1\u8272\u7ed3\u70b9 \u3002<\/p>\n

5\u3001\u6bcf\u4e2a\u53f6\u5b50\u7ed3\u70b9\u90fd\u662f\u9ed1\u8272\u7684(\u6b64\u5904\u7684\u53f6\u5b50\u7ed3\u70b9\u6307\u7684\u662f\u7a7a\u7ed3\u70b9）\u3002<\/p>\n

\u4ece\u4e0a\u9762\u7ea2\u9ed1\u6811\u7684\u6027\u8d28\u6211\u4eec\u53ef\u4ee5\u77e5\u9053，\u4ece\u6839\u8282\u70b9\u5f00\u59cb，\u5982\u679c\u5b58\u5728\u6700\u957f\u8def\u5f84\u7684\u8bdd，\u7ea2\u9ed1\u6811\u4e2d\u7684\u6700\u957f\u8def\u5f84\u662f\u4e00\u9ed1\u4e00\u7ea2\u95f4\u9694\u7684\u8def\u5f84，\u5982\u679c\u5b58\u5728\u6700\u77ed\u8def\u5f84\u7684\u8bdd，\u6700\u77ed\u7684\u8def\u5f84\u662f\u5168\u9ed1\u7ed3\u70b9\u7684\u8def\u5f84\u3002<\/p>\n

\u4ece\u6839\u8282\u70b9\u5f00\u59cb，\u5047\u8bbe\u7ea2\u9ed1\u6811\u7684\u6bcf\u6761\u8def\u5f84\u90fd\u6709N\u4e2a\u9ed1\u8272\u7ed3\u70b9，\u5219\u6bcf\u6761\u8def\u5f84\u7684\u7ed3\u70b9\u6570\u91cf\u7684\u8303\u56f4\u4e3a[N，2N]\u3002<\/p>\n

3.2\u3001\u7ea2\u9ed1\u6811\u7684\u63d2\u5165<\/h4>\n

\u7ea2\u9ed1\u6811\u662f\u5728\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u57fa\u7840\u4e0a\u52a0\u4e0a\u5176\u5e73\u8861\u9650\u5236\u6761\u4ef6，\u56e0\u6b64\u7ea2\u9ed1\u6811\u7684\u63d2\u5165\u53ef\u5206\u4e3a\u4e24\u6b65：<\/p>\n

1\u3001\u6309\u7167\u4e8c\u53c9\u641c\u7d22\u7684\u6811\u89c4\u5219\u63d2\u5165\u65b0\u8282\u70b9\u3002<\/p>\n

2\u3001\u68c0\u6d4b\u65b0\u8282\u70b9\u63d2\u5165\u540e，\u7ea2\u9ed1\u6811\u7684\u6027\u8d28\u662f\u5426\u9020\u5230\u7834\u574f\u3002<\/p>\n

\u56e0\u4e3a\u65b0\u8282\u70b9\u7684\u9ed8\u8ba4\u989c\u8272\u662f\u7ea2\u8272，\u56e0\u6b64\u5982\u679c\u5176\u53cc\u4eb2\u8282\u70b9\u7684\u989c\u8272\u662f\u9ed1\u8272，\u6ca1\u6709\u8fdd\u53cd\u7ea2\u9ed1\u6811\u4efb\u4f55\u6027\u8d28，\u5219\u4e0d\u9700\u8981\u8c03\u6574；\u4f46\u5f53\u65b0\u63d2\u5165\u8282\u70b9\u7684\u53cc\u4eb2\u8282\u70b9\u989c\u8272\u4e3a\u7ea2\u8272\u65f6，\u5c31\u8fdd\u53cd\u4e86\u6027\u8d28\u4e09\u4e0d\u80fd\u6709\u8fde\u5728\u4e00\u8d77\u7684\u7ea2\u8272\u8282\u70b9，\u6b64\u65f6\u9700\u8981\u5bf9\u7ea2\u9ed1\u6811\u5206\u60c5\u51b5\u6765\u8ba8\u8bba：\u7ea6\u5b9acur\u4e3a\u5f53\u524d\u8282\u70b9，p\u4e3a\u7236\u8282\u70b9，g\u4e3a\u7956\u7236\u8282\u70b9，u\u4e3a\u53d4\u53d4\u8282\u70b9\u3002<\/p>\n

\u6ce8\u610f：\u4e4b\u6240\u4ee5\u65b0\u7ed3\u70b9\u7684\u9ed8\u8ba4\u989c\u8272\u7ed9\u7ea2\u8272，\u539f\u56e0\u662f\u7834\u574f\u7ea2\u9ed1\u6811\u7684\u7b2c\u4e09\u6761\u6027\u8d28\u6bd4\u7834\u574f\u7ea2\u9ed1\u6811\u7684\u7b2c\u56db\u6761\u6240\u4ed8\u51fa\u7684\u4ee3\u4ef7\u5c0f\u3002<\/p>\n

3.2.1\u3001\u60c5\u51b5\u4e00<\/h5>\n

\u60c5\u51b5\u4e00：cur\u4e3a\u7ea2，p\u4e3a\u7ea2，g\u4e3a\u9ed1，u\u5b58\u5728\u4e14\u4e3a\u7ea2，\u4f8b\u5982<\/p>\n

\"\"<\/p>\n

\u5176\u4e2da\u3001b\u3001c\u3001d\u3001e\u5206\u522b\u662f\u7ea2\u9ed1\u6811\u3002<\/p>\n

\u89e3\u51b3\u65b9\u5f0f：\u5c06p\u548cu\u6539\u4e3a\u9ed1，g\u6539\u4e3a\u7ea2，\u7136\u540e\u628ag\u5f53\u6210cur，\u7ee7\u7eed\u5411\u4e0a\u8c03\u6574\u3002<\/p>\n

3.2.2\u3001\u60c5\u51b5\u4e8c<\/h5>\n

\u60c5\u51b5\u4e8c：cur\u4e3a\u7ea2，p\u4e3a\u7ea2，g\u4e3a\u9ed1，u\u4e0d\u5b58\u5728\u6216\u8005u\u5b58\u5728\u4e14\u4e3a\u9ed1，\u4f8b\u5982<\/p>\n

\"\"<\/p>\n

\u5176\u4e2da\u3001b\u3001c\u3001d\u3001e\u5206\u522b\u662f\u7ea2\u9ed1\u6811\u3002<\/p>\n

\u89e3\u51b3\u65b9\u5f0f：<\/p>\n

1\u3001\u82e5p\u4e3ag\u7684\u5de6\u5b69\u5b50，cur\u4e3ap\u7684\u5de6\u5b69\u5b50，\u5219\u9488\u5bf9p\u8fdb\u884c\u53f3\u65cb\u8f6c，\u7136\u540ep\u53d8\u9ed1，g\u53d8\u7ea2\u3002<\/p>\n

2\u3001\u82e5p\u4e3ag\u7684\u53f3\u5b69\u5b50，cur\u4e3ap\u7684\u53f3\u5b69\u5b50，\u5219\u9488\u5bf9p\u8fdb\u884c\u5de6\u65cb\u8f6c，\u7136\u540ep\u53d8\u9ed1，g\u53d8\u7ea2\u3002<\/p>\n

3.2.3\u3001\u60c5\u51b5\u4e09<\/h5>\n

\u60c5\u51b5\u4e09：cur\u4e3a\u7ea2，p\u4e3a\u7ea2，g\u4e3a\u9ed1，u\u4e0d\u5b58\u5728\u6216\u8005u\u5b58\u5728\u4e14\u4e3a\u9ed1，\u4f8b\u5982<\/p>\n

\"\"<\/p>\n

\u5176\u4e2da\u3001b\u3001c\u3001d\u3001e\u5206\u522b\u662f\u7ea2\u9ed1\u6811\u3002<\/p>\n

\u89e3\u51b3\u65b9\u5f0f：<\/p>\n

1\u3001\u82e5p\u4e3ag\u7684\u5de6\u5b69\u5b50，cur\u4e3ap\u7684\u53f3\u5b69\u5b50，\u5219\u9488\u5bf9p\u505a\u5de6\u65cb\u8f6c，\u8f6c\u6362\u4e3a\u4e86\u60c5\u51b5\u4e8c\u3002<\/p>\n

2\u3001\u82e5p\u4e3ag\u7684\u53f3\u5b69\u5b50，cur\u4e3ap\u7684\u5de6\u5b69\u5b50，\u5219\u9488\u5bf9p\u505a\u53f3\u65cb\u8f6c，\u8f6c\u6362\u6210\u4e86\u60c5\u51b5\u4e8c\u3002<\/p>\n

3.3\u3001\u7ea2\u9ed1\u6811\u7684\u5220\u9664<\/h4>\n

\u7ea2\u9ed1\u6811\u7684\u5220\u9664\u6bd4\u63d2\u5165\u8fd8\u8981\u590d\u6742，\u6709\u5174\u8da3\u53ef\u53c2\u8003：\u300a\u7b97\u6cd5\u5bfc\u8bba\u300b\u6216\u8005\u300aSTL\u6e90\u7801\u5256\u6790\u300b\u3002<\/p>\n

3.4\u3001\u7ea2\u9ed1\u6811\u7684\u6027\u80fd<\/h4>\n

\u7ea2\u9ed1\u6811\u548cAVL\u6811\u90fd\u662f\u9ad8\u6548\u7684\u5e73\u8861\u4e8c\u53c9\u6811，\u589e\u5220\u6539\u67e5\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u90fd\u662fO(log(N))，\u7ea2\u9ed1\u6811\u4e0d\u8ffd\u6c42\u7edd\u5bf9\u5e73\u8861，\u5176\u53ea\u9700\u4fdd\u8bc1\u6700\u957f\u8def\u5f84\u4e0d\u8d85\u8fc7\u6700\u77ed\u8def\u5f84\u76842\u500d，\u6240\u4ee5\u7ea2\u9ed1\u6811\u7684\u6027\u80fd\u5f80\u5f80\u6bd4AVL\u6811\u66f4\u4f18，\u800c\u4e14\u7ea2\u9ed1\u6811\u5b9e\u73b0\u6bd4\u8f83\u7b80\u5355，\u6240\u4ee5\u5b9e\u9645\u8fd0\u7528\u4e2d\u7ea2\u9ed1\u6811\u66f4\u591a\u3002<\/p>\n

\u7ea2\u9ed1\u6811\u7684\u5e94\u7528：<\/p>\n

1\u3001C++ STL\u5e93\u4e2d\u7684map\u548cset\u4ee5\u53camutil_map\u548cmutil_set\u3002<\/p>\n

2\u3001Java\u5e93\u3002<\/p>\n

3\u3001linux\u5185\u6838\u3002<\/p>\n

4\u3001\u5176\u4ed6\u4e00\u4e9b\u5e93\u3002<\/p>\n

3.5\u3001\u6a21\u62df\u5b9e\u73b0<\/h4>\n

enum Colour
\n{
\nRED,
\nBLACK
\n};<\/p>\n

template<class K, class V>
\nstruct RBTreeNode
\n{
\nRBTreeNode<K, V>* _left;
\nRBTreeNode<K, V>* _right;
\nRBTreeNode<K, V>* _parent;
\npair<K, V> _kv;<\/p>\n

Colour _col;<\/p>\n

RBTreeNode(const pair<K, V>& kv)
\n:_left(nullptr)
\n,_right(nullptr)
\n,_parent(nullptr)
\n,_kv(kv)
\n,_col(RED)
\n{}
\n};<\/p>\n

template<class K, class V>
\nclass RBTree
\n{
\ntypedef RBTreeNode<K, V> Node;
\npublic:
\nbool Insert(const pair<K, V>& kv)
\n{
\nif (_root == nullptr)
\n{
\n_root = new Node(kv);
\n_root->_col = BLACK;
\nreturn true;
\n}<\/p>\n

Node* parent = nullptr;
\nNode* cur = _root;
\nwhile (cur)
\n{
\nif (cur->_kv.first < kv.first)
\n{
\nparent = cur;
\ncur = cur->_right;
\n}
\nelse if (cur->_kv.first > kv.first)
\n{
\nparent = cur;
\ncur = cur->_left;
\n}
\nelse
\n{
\nreturn false;
\n}
\n}<\/p>\n

\/\/ \u65b0\u589e\u7ed3\u70b9
\ncur = new Node(kv);
\nif (parent->_kv.first < kv.first)
\n{
\nparent->_right = cur;
\ncur->_parent = parent;
\n}
\nelse
\n{
\nparent->_left = cur;
\ncur->_parent = parent;
\n}<\/p>\n

\/\/ \u8c03\u6574
\nwhile (parent && parent->_col == RED)
\n{
\nNode* grandfather = parent->_parent;
\nif (parent == grandfather->_left) \/\/ p\u5728g\u7684\u5de6\u8fb9
\n{
\nNode* uncle = grandfather->_right;
\nif (uncle && uncle->_col == RED) \/\/ u\u5b58\u5728\u4e14\u4e3a\u7ea2
\n{
\n\/\/ \u53d8\u8272
\nparent->_col = uncle->_col = BLACK;
\ngrandfather->_col = RED;<\/p>\n

\/\/\u7ee7\u7eed\u5411\u4e0a\u5904\u7406
\ncur = grandfather;
\nparent = cur->_parent;
\n}
\nelse \/\/ u\u4e0d\u5b58\u5728，\u6216\u8005u\u5b58\u5728\u4e14\u4e3a\u9ed1
\n{
\nif (cur == parent->_left) \/\/ cur\u5728p\u7684\u5de6\u8fb9
\n{
\nRotateR(grandfather);
\nparent->_col = BLACK;
\ngrandfather->_col = RED;
\n}
\nelse \/\/ cur\u5728p\u7684\u53f3\u8fb9
\n{
\nRotateL(parent);
\nRotateR(grandfather);
\ncur->_col = BLACK;
\ngrandfather->_col = RED;
\n}
\nbreak;
\n}
\n}
\nelse \/\/ p\u5728g\u7684\u53f3\u8fb9
\n{
\nNode* uncle = grandfather->_left;
\nif (uncle && uncle->_col == RED) \/\/ u\u5b58\u5728\u4e14\u4e3a\u7ea2
\n{
\nparent->_col = uncle->_col = BLACK;
\ngrandfather->_col = RED;<\/p>\n

cur = grandfather;
\nparent = cur->_parent;
\n}
\nelse \/\/ u\u4e0d\u5b58\u5728，\u6216\u8005u\u5b58\u5728\u4e14\u4e3a\u9ed1
\n{
\nif (cur == parent->_right) \/\/ cur\u5728p\u7684\u53f3\u8fb9
\n{
\nRotateL(grandfather);
\nparent->_col = BLACK;
\ngrandfather->_col = RED;
\n}
\nelse \/\/ cur\u5728p\u7684\u5de6\u8fb9
\n{
\nRotateR(parent);
\nRotateL(grandfather);
\ncur->_col = BLACK;
\ngrandfather->_col = RED;
\n}
\nbreak;
\n}
\n}
\n}
\n_root->_col = BLACK;
\nreturn true;
\n}<\/p>\n

void RotateL(Node* parent) \/\/ \u5de6\u65cb
\n{
\nNode* subR = parent->_right;
\nNode* subRL = subR->_left;<\/p>\n

parent->_right = subRL;
\nsubR->_left = parent;<\/p>\n

Node* parentParent = parent->_parent;<\/p>\n

parent->_parent = subR;
\nif (subRL)
\nsubRL->_parent = parent;<\/p>\n

if (_root == parent)
\n{
\n_root = subR;
\nsubR->_parent = nullptr;
\n}
\nelse
\n{
\nif (parentParent->_left == parent)
\n{
\nparentParent->_left = subR;
\n}
\nelse
\n{
\nparentParent->_right = subR;
\n}
\nsubR->_parent = parentParent;
\n}
\n}<\/p>\n

void RotateR(Node* parent) \/\/\u53f3\u65cb
\n{
\nNode* subL = parent->_left;
\nNode* subLR = subL->_right;<\/p>\n

parent->_left = subLR;
\nif (subLR)
\nsubLR->_parent = parent;<\/p>\n

Node* parentParent = parent->_parent;<\/p>\n

subL->_right = parent;
\nparent->_parent = subL;<\/p>\n

if (_root == parent)
\n{
\n_root = subL;
\nsubL->_parent = nullptr;
\n}
\nelse
\n{
\nif (parentParent->_left == parent)
\n{
\nparentParent->_left = subL;
\n}
\nelse
\n{
\nparentParent->_right = subL;
\n}
\nsubL->_parent = parentParent;
\n}
\n}<\/p>\n

void InOrder()
\n{
\n_InOrder(_root);
\ncout << endl;
\n}<\/p>\n

bool IsBalance()
\n{
\nif (_root == nullptr)
\nreturn true;<\/p>\n

if (_root->_col == RED)
\nreturn false;<\/p>\n

int refVal = 0; \/\/ \u53c2\u8003\u503c
\nNode* cur = _root;
\nwhile (cur)
\n{
\nif (cur->_col == BLACK)
\n{
\n++refVal;
\n}
\ncur = cur->_left;
\n}<\/p>\n

int blacknum = 0;
\nreturn Check(_root, blacknum, refVal);
\n}<\/p>\n

int Height()
\n{
\nreturn _Height(_root);
\n}<\/p>\n

size_t Size()
\n{
\nreturn _Size(_root);
\n}<\/p>\n

Node* Find(const K& key)
\n{
\nNode* cur = _root;
\nwhile (cur)
\n{
\nif (cur->_kv.first < key)
\n{
\ncur = cur->_right;
\n}
\nelse if (cur->_kv.first > key)
\n{
\ncur = cur->_left;
\n}
\nelse
\n{
\nreturn cur;
\n}
\n}
\nreturn NULL;
\n}<\/p>\n

private:
\nvoid _InOrder(Node* root)
\n{
\nif (root == nullptr)
\nreturn;<\/p>\n

_InOrder(root->_left);
\ncout << root->_kv.first << ':' << root->_kv.second << endl;
\n_InOrder(root->_right);
\n}<\/p>\n

bool Check(Node* root, int blacknum, const int refVal)
\n{
\nif (root == nullptr)
\n{
\nif (blacknum != refVal)
\n{
\ncout << "\u5b58\u5728\u9ed1\u8272\u7ed3\u70b9\u6570\u91cf\u4e0d\u76f8\u7b49\u7684\u8def\u5f84" << endl;
\nreturn false;
\n}
\nreturn true;
\n}<\/p>\n

if (root->_col == RED && root->_parent->_col == RED)
\n{
\ncout << "\u6709\u8fde\u7eed\u7684\u7ea2\u8272\u7ed3\u70b9" << endl;
\nreturn false;
\n}<\/p>\n

if (root->_col == BLACK)
\n{
\n++blacknum;
\n}<\/p>\n

return Check(root->_left, blacknum, refVal)
\n&& Check(root->_right, blacknum, refVal);
\n}<\/p>\n

int _Height(Node* root)
\n{
\nif (root == nullptr)
\n{
\nreturn 0;
\n}<\/p>\n

int leftHeight = _Height(root->_left);
\nint rightHeight = _Height(root->_right);<\/p>\n

return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
\n}<\/p>\n

size_t _Size(Node* root)
\n{
\nif (root == nullptr)
\nreturn 0;<\/p>\n

return _Size(root->_left) + _Size(root->_right) + 1;
\n}<\/p>\n

private:
\nNode* _root = nullptr;
\n}; <\/p>\n

4\u3001\u6a21\u62df\u5b9e\u73b0map\u548cset<\/h3>\n

set\u548cmap\u7684\u5e95\u5c42\u90fd\u662f\u7ea2\u9ed1\u6811，\u56e0\u6b64\u53ea\u9700\u5728set\u548cmap\u5185\u90e8\u5c01\u88c5\u4e00\u68f5\u7ea2\u9ed1\u6811，\u7136\u540e\u5c06\u5176\u63a5\u53e3\u5305\u88c5\u4e0b\u5373\u53ef\u3002<\/p>\n

RBTree.h：<\/p>\n

enum Colour
\n{
\nRED,
\nBLACK
\n};<\/p>\n

template<class T>
\nstruct RBTreeNode
\n{
\nRBTreeNode<T>* _left;
\nRBTreeNode<T>* _right;
\nRBTreeNode<T>* _parent;
\nT _data;<\/p>\n

Colour _col;<\/p>\n

RBTreeNode(const T& data)
\n:_left(nullptr)
\n, _right(nullptr)
\n, _parent(nullptr)
\n, _data(data)
\n, _col(RED)
\n{}
\n};<\/p>\n

template<class T, class Ref, class Ptr>
\nstruct __TreeIterator
\n{
\ntypedef RBTreeNode<T> Node;
\ntypedef __TreeIterator<T, Ref, Ptr> Self;
\nNode* _node;<\/p>\n

__TreeIterator(Node* node)
\n:_node(node)
\n{}<\/p>\n

Ref operator*()
\n{
\nreturn _node->_data;
\n}<\/p>\n

Ptr operator->()
\n{
\nreturn &_node->_data;
\n}<\/p>\n

Self& operator–()
\n{
\n\/\/ \u81ea\u5df1\u5b9e\u73b0
\n}<\/p>\n

Self& operator++()
\n{
\nif (_node->_right) \/\/ \u53f3\u4e0d\u4e3a\u7a7a
\n{
\nNode* cur = _node->_right;
\nwhile (cur->_left)
\n{
\ncur = cur->_left;
\n}
\n_node = cur;
\n}
\nelse \/\/ \u53f3\u4e3a\u7a7a
\n{
\nNode* cur = _node;
\nNode* parent = cur->_parent;
\nwhile (parent && cur == parent->_right)
\n{
\ncur = parent;
\nparent = parent->_parent;
\n}
\n_node = parent;
\n}
\nreturn *this;
\n}<\/p>\n

bool operator!=(const Self& s)
\n{
\nreturn _node != s._node;
\n}<\/p>\n

bool operator==(const Self& s)
\n{
\nreturn _node == s._node;
\n}
\n};<\/p>\n

\/\/set->RBTree<K, K, SetKeyOfT> _t;
\n\/\/map->RBTree<K, pair<const K, T>, MapKeyOfT> _t;
\ntemplate<class K, class T, class KeyOfT>
\nclass RBTree
\n{
\ntypedef RBTreeNode<T> Node;
\npublic:
\ntypedef __TreeIterator<T, T&, T*> iterator;
\ntypedef __TreeIterator<T, const T&, const T*> const_iterator;<\/p>\n

iterator begin()
\n{
\nNode* cur = _root;
\nwhile (cur && cur->_left)
\n{
\ncur = cur->_left;
\n}<\/p>\n

return iterator(cur);
\n}<\/p>\n

iterator end()
\n{
\nreturn iterator(nullptr);
\n}<\/p>\n

const_iterator begin() const
\n{
\nNode* cur = _root;
\nwhile (cur && cur->_left)
\n{
\ncur = cur->_left;
\n}<\/p>\n

return const_iterator(cur);
\n}<\/p>\n

const_iterator end() const
\n{
\nreturn const_iterator(nullptr);
\n}<\/p>\n

\/\/pair<iterator, bool> Insert(const T& data)
\npair<Node*, bool> Insert(const T& data) \/\/ \u5982\u679c\u7528\u4e0a\u9762\u7684\u4f1a\u6709\u8fed\u4ee3\u5668\u7c7b\u578b\u8f6c\u6362\u7684\u95ee\u9898\u3002
\n{
\nif (_root == nullptr)
\n{
\n_root = new Node(data);
\n_root->_col = BLACK;
\nreturn make_pair(_root, true);
\n}<\/p>\n

Node* parent = nullptr;
\nNode* cur = _root;
\nKeyOfT kot;<\/p>\n

while (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 make_pair(cur, false);
\n}
\n}<\/p>\n

\/\/ \u65b0\u589e\u7ed3\u70b9 \/\/
\ncur = new Node(data);
\nNode* newnode = cur;
\nif (kot(parent->_data) < kot(data))
\n{
\nparent->_right = cur;
\ncur->_parent = parent;
\n}
\nelse
\n{
\nparent->_left = cur;
\ncur->_parent = parent;
\n}<\/p>\n

\/\/
\nwhile (parent && parent->_col == RED)
\n{
\nNode* grandfather = parent->_parent;
\nif (parent == grandfather->_left)
\n{
\nNode* uncle = grandfather->_right;
\nif (uncle && uncle->_col == RED)
\n{
\n\/\/ \u53d8\u8272
\nparent->_col = uncle->_col = BLACK;
\ngrandfather->_col = RED;<\/p>\n

\/\/\u7ee7\u7eed\u5411\u4e0a\u5904\u7406
\ncur = grandfather;
\nparent = cur->_parent;
\n}
\nelse
\n{
\nif (cur == parent->_left)
\n{
\nRotateR(grandfather);
\nparent->_col = BLACK;
\ngrandfather->_col = RED;
\n}
\nelse
\n{
\nRotateL(parent);
\nRotateR(grandfather);
\ncur->_col = BLACK;
\ngrandfather->_col = RED;
\n}
\nbreak;
\n}
\n}
\nelse
\n{
\nNode* uncle = grandfather->_left;
\nif (uncle && uncle->_col == RED)
\n{
\nparent->_col = uncle->_col = BLACK;
\ngrandfather->_col = RED;<\/p>\n

cur = grandfather;
\nparent = cur->_parent;
\n}
\nelse
\n{
\nif (cur == parent->_right)
\n{
\nRotateL(grandfather);
\nparent->_col = BLACK;
\ngrandfather->_col = RED;
\n}
\nelse
\n{
\nRotateR(parent);
\nRotateL(grandfather);
\ncur->_col = BLACK;
\ngrandfather->_col = RED;
\n}
\nbreak;
\n}
\n}
\n}
\n_root->_col = BLACK;
\nreturn make_pair(newnode, true);
\n}<\/p>\n

void RotateL(Node* parent) \/\/ \u5de6\u65cb
\n{
\nNode* subR = parent->_right;
\nNode* subRL = subR->_left;<\/p>\n

parent->_right = subRL;
\nsubR->_left = parent;<\/p>\n

Node* parentParent = parent->_parent;<\/p>\n

parent->_parent = subR;
\nif (subRL)
\nsubRL->_parent = parent;<\/p>\n

if (_root == parent)
\n{
\n_root = subR;
\nsubR->_parent = nullptr;
\n}
\nelse
\n{
\nif (parentParent->_left == parent)
\n{
\nparentParent->_left = subR;
\n}
\nelse
\n{
\nparentParent->_right = subR;
\n}
\nsubR->_parent = parentParent;
\n}
\n}<\/p>\n

void RotateR(Node* parent) \/\/\u53f3\u65cb
\n{
\nNode* subL = parent->_left;
\nNode* subLR = subL->_right;<\/p>\n

parent->_left = subLR;
\nif (subLR)
\nsubLR->_parent = parent;<\/p>\n

Node* parentParent = parent->_parent;<\/p>\n

subL->_right = parent;
\nparent->_parent = subL;<\/p>\n

if (_root == parent)
\n{
\n_root = subL;
\nsubL->_parent = nullptr;
\n}
\nelse
\n{
\nif (parentParent->_left == parent)
\n{
\nparentParent->_left = subL;
\n}
\nelse
\n{
\nparentParent->_right = subL;
\n}
\nsubL->_parent = parentParent;
\n}
\n}
\nprivate:<\/p>\n

Node* _root = nullptr;
\n}; <\/p>\n

MyMap.h：<\/p>\n

#include "RBTree.h"<\/p>\n

namespace bit
\n{
\ntemplate<class K, class V>
\nclass map
\n{
\npublic:
\nstruct MapKeyOfT
\n{
\nconst K& operator()(const pair<K, V>& kv)
\n{
\nreturn kv.first;
\n}
\n};<\/p>\n

typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;\/\/\u4ec5key\u4e0d\u53ef\u6539
\ntypedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator; \/\/ key\u4ee5\u53cavalue\u90fd\u4e0d\u53ef\u6539<\/p>\n

iterator begin()
\n{
\nreturn _t.begin();
\n}<\/p>\n

iterator end()
\n{
\nreturn _t.end();
\n}<\/p>\n

V& operator[](const K& key)
\n{
\npair<iterator, bool> ret = insert(make_pair(key, V()));
\nreturn ret.first->second;
\n}<\/p>\n

pair<iterator, bool> insert(const pair<K, V>& kv)
\n{
\nreturn _t.Insert(kv);
\n}<\/p>\n

private:
\nRBTree<K, pair<const K, V>, MapKeyOfT> _t;
\n};
\n}<\/p>\n

MySet.h：<\/p>\n

#include "RBTree.h"<\/p>\n

namespace bit
\n{
\ntemplate<class K>
\nclass set
\n{
\npublic:
\nstruct SetKeyOfT
\n{
\nconst K& operator()(const K& key)
\n{
\nreturn key;
\n}
\n};<\/p>\n

\/\/ \u5bf9\u7c7b\u6a21\u677f\u53d6\u5185\u5d4c\u7c7b\u578b，\u52a0typename\u544a\u8bc9\u7f16\u8bd1\u5668\u8fd9\u91cc\u662f\u7c7b\u578b
\ntypedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
\ntypedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;<\/p>\n

iterator begin() const
\n{
\nreturn _t.begin();
\n}<\/p>\n

iterator end() const
\n{
\nreturn _t.end();
\n}<\/p>\n

pair<iterator, bool> insert(const K& key)
\n{
\nreturn _t.Insert(key);
\n}<\/p>\n

private:
\nRBTree<K, K, SetKeyOfT> _t;
\n};
\n} <\/p>\n","protected":false},"excerpt":{"rendered":"

\u6587\u7ae0\u6d4f\u89c8\u9605\u8bfb37\u6b21\u3002\u4e3b\u8981\u8bb2\u89e3\u5173\u4e8eAVL\u6811\u3001\u7ea2\u9ed1\u6811\u3001\u4ee5\u53ca\u5c01\u88c5\u51fa\u7684map\u548cset<\/p>\n","protected":false},"author":2,"featured_media":50964,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[55,190],"topic":[],"class_list":["post-50973","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-server","tag-c","tag-190"],"yoast_head":"\n\u7b2c\u5341\u516d\u8bb2\uff1aAVL\u6811\u548c\u7ea2\u9ed1\u6811 - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.wsisp.com\/helps\/50973.html\" \/>\n<meta property=\"og:locale\" content=\"zh_CN\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"\u7b2c\u5341\u516d\u8bb2\uff1aAVL\u6811\u548c\u7ea2\u9ed1\u6811 - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\" \/>\n<meta property=\"og:description\" content=\"\u6587\u7ae0\u6d4f\u89c8\u9605\u8bfb37\u6b21\u3002\u4e3b\u8981\u8bb2\u89e3\u5173\u4e8eAVL\u6811\u3001\u7ea2\u9ed1\u6811\u3001\u4ee5\u53ca\u5c01\u88c5\u51fa\u7684map\u548cset\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.wsisp.com\/helps\/50973.html\" \/>\n<meta property=\"og:site_name\" content=\"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\" \/>\n<meta property=\"article:published_time\" content=\"2025-08-10T07:24:23+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2025\/08\/20250810072421-689849258e514.png\" \/>\n<meta name=\"author\" content=\"admin\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"\u4f5c\u8005\" \/>\n\t<meta name=\"twitter:data1\" content=\"admin\" \/>\n\t<meta name=\"twitter:label2\" content=\"\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4\" \/>\n\t<meta name=\"twitter:data2\" content=\"14 \u5206\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/50973.html\",\"url\":\"https:\/\/www.wsisp.com\/helps\/50973.html\",\"name\":\"\u7b2c\u5341\u516d\u8bb2\uff1aAVL\u6811\u548c\u7ea2\u9ed1\u6811 - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\",\"isPartOf\":{\"@id\":\"https:\/\/www.wsisp.com\/helps\/#website\"},\"datePublished\":\"2025-08-10T07:24:23+00:00\",\"dateModified\":\"2025-08-10T07:24:23+00:00\",\"author\":{\"@id\":\"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41\"},\"breadcrumb\":{\"@id\":\"https:\/\/www.wsisp.com\/helps\/50973.html#breadcrumb\"},\"inLanguage\":\"zh-Hans\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/www.wsisp.com\/helps\/50973.html\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/50973.html#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\u9996\u9875\",\"item\":\"https:\/\/www.wsisp.com\/helps\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"\u7b2c\u5341\u516d\u8bb2\uff1aAVL\u6811\u548c\u7ea2\u9ed1\u6811\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/#website\",\"url\":\"https:\/\/www.wsisp.com\/helps\/\",\"name\":\"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\",\"description\":\"\u9999\u6e2f\u670d\u52a1\u5668_\u9999\u6e2f\u4e91\u670d\u52a1\u5668\u8d44\u8baf_\u670d\u52a1\u5668\u5e2e\u52a9\u6587\u6863_\u670d\u52a1\u5668\u6559\u7a0b\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/www.wsisp.com\/helps\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"zh-Hans\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41\",\"name\":\"admin\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"zh-Hans\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery\",\"contentUrl\":\"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery\",\"caption\":\"admin\"},\"sameAs\":[\"http:\/\/wp.wsisp.com\"],\"url\":\"https:\/\/www.wsisp.com\/helps\/author\/admin\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"\u7b2c\u5341\u516d\u8bb2\uff1aAVL\u6811\u548c\u7ea2\u9ed1\u6811 - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.wsisp.com\/helps\/50973.html","og_locale":"zh_CN","og_type":"article","og_title":"\u7b2c\u5341\u516d\u8bb2\uff1aAVL\u6811\u548c\u7ea2\u9ed1\u6811 - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","og_description":"\u6587\u7ae0\u6d4f\u89c8\u9605\u8bfb37\u6b21\u3002\u4e3b\u8981\u8bb2\u89e3\u5173\u4e8eAVL\u6811\u3001\u7ea2\u9ed1\u6811\u3001\u4ee5\u53ca\u5c01\u88c5\u51fa\u7684map\u548cset","og_url":"https:\/\/www.wsisp.com\/helps\/50973.html","og_site_name":"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","article_published_time":"2025-08-10T07:24:23+00:00","og_image":[{"url":"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2025\/08\/20250810072421-689849258e514.png"}],"author":"admin","twitter_card":"summary_large_image","twitter_misc":{"\u4f5c\u8005":"admin","\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4":"14 \u5206"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/www.wsisp.com\/helps\/50973.html","url":"https:\/\/www.wsisp.com\/helps\/50973.html","name":"\u7b2c\u5341\u516d\u8bb2\uff1aAVL\u6811\u548c\u7ea2\u9ed1\u6811 - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","isPartOf":{"@id":"https:\/\/www.wsisp.com\/helps\/#website"},"datePublished":"2025-08-10T07:24:23+00:00","dateModified":"2025-08-10T07:24:23+00:00","author":{"@id":"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41"},"breadcrumb":{"@id":"https:\/\/www.wsisp.com\/helps\/50973.html#breadcrumb"},"inLanguage":"zh-Hans","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.wsisp.com\/helps\/50973.html"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/www.wsisp.com\/helps\/50973.html#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\u9996\u9875","item":"https:\/\/www.wsisp.com\/helps"},{"@type":"ListItem","position":2,"name":"\u7b2c\u5341\u516d\u8bb2\uff1aAVL\u6811\u548c\u7ea2\u9ed1\u6811"}]},{"@type":"WebSite","@id":"https:\/\/www.wsisp.com\/helps\/#website","url":"https:\/\/www.wsisp.com\/helps\/","name":"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","description":"\u9999\u6e2f\u670d\u52a1\u5668_\u9999\u6e2f\u4e91\u670d\u52a1\u5668\u8d44\u8baf_\u670d\u52a1\u5668\u5e2e\u52a9\u6587\u6863_\u670d\u52a1\u5668\u6559\u7a0b","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.wsisp.com\/helps\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"zh-Hans"},{"@type":"Person","@id":"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41","name":"admin","image":{"@type":"ImageObject","inLanguage":"zh-Hans","@id":"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/image\/","url":"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery","contentUrl":"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery","caption":"admin"},"sameAs":["http:\/\/wp.wsisp.com"],"url":"https:\/\/www.wsisp.com\/helps\/author\/admin"}]}},"_links":{"self":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/posts\/50973","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/comments?post=50973"}],"version-history":[{"count":0,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/posts\/50973\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/media\/50964"}],"wp:attachment":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/media?parent=50973"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/categories?post=50973"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/tags?post=50973"},{"taxonomy":"topic","embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/topic?post=50973"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}