{"id":454,"date":"2014-08-14T22:13:00","date_gmt":"2014-08-14T14:13:00","guid":{"rendered":"http:\/\/blog.sorayuki.net\/?p=454"},"modified":"2015-04-27T23:14:31","modified_gmt":"2015-04-27T15:14:31","slug":"%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84%e4%b9%8b%e7%ba%a2%e9%bb%91%e6%a0%91","status":"publish","type":"post","link":"https:\/\/blog.sorayuki.net\/?p=454","title":{"rendered":"\u6570\u636e\u7ed3\u6784\u4e4b\u7ea2\u9ed1\u6811"},"content":{"rendered":"

\u7ea2\u9ed1\u6811\u672c\u6765\u6765\u8bf4\u5e94\u8be5\u662f\u672c\u79d1\u6570\u636e\u7ed3\u6784\u6559\u5b66\u7684\u5185\u5bb9\uff0c\u6211\u5f53\u5e74\u9886\u5230\u7684\u6559\u79d1\u4e66\u4e0a\u4e5f\u6709\u3002\u4f46\u662f\u56e0\u4e3a\u6293\u5f97\u4e0d\u4e25\uff0c\u603b\u4e4b\u6700\u540e\u662f\u4e0d\u4e86\u4e86\u4e4b\uff0c\u8fde\u6709\u6ca1\u6709\u6559\u8fc7\u90fd\u5fd8\u8bb0\u4e86\uff0c\u81ea\u5df1\u4e5f\u6ca1\u6709\u53bb\u5b66\u3002\u73b0\u5728\u8fc7\u4e86\u8fd9\u4e48\u591a\u5e74\uff0c\u5f00\u59cb\u627e\u5de5\u4f5c\u4e86\uff0c\u53d1\u73b0\u6709\u4e9b\u516c\u53f8\u4f3c\u4e4e\u633a\u7231\u95ee\u8fd9\u4e2a\u7684\uff0c\u5173\u4e8eSTL\u7684\u5b9e\u73b0\u6211\u539f\u5148\u4e00\u76f4\u4ee5\u4e3amap\u662f\u9760AVL\u6811\u5b9e\u73b0\u7684\uff0c\u5177\u4f53\u662f\u4ec0\u4e48\u4e66\u4e0a\u770b\u6765\u7684\u6211\u4e5f\u5fd8\u8bb0\u4e86\u3002\u53ea\u662f\u73b0\u5728\u77e5\u9053\u4e86\u5b83\u5176\u5b9e\u662f\u7ea2\u9ed1\u6811\u4e5f\u65e0\u6d4e\u4e8e\u4e8b\uff0c\u56e0\u4e3a\u5b8c\u5168\u6ca1\u6709\u53bb\u4e86\u89e3\u8fc7\u5b83\uff0c\u4e00\u95ee\u4e09\u4e0d\u77e5\u3002\u73b0\u5728\u5c31\u7a81\u7136\u60f3\u8d77\u6765\uff0c\u60f3\u8981\u8865\u4e00\u4e0b\u8fd9\u65b9\u9762\u7684\u77e5\u8bc6\u3002<\/p>\n

\u5728\u641c\u7d22\u5f15\u64ce\u4e0a\u9762\u627e\u4e86\u4e00\u901a\u4ee5\u540e\uff0c\u53d1\u73b0\u56fd\u5185\u7684\u8d44\u6599\u57fa\u672c\u5c31\u90a3\u4e48\u51e0\u4e2a\u7248\u672c\uff0c\u5927\u5bb6\u6284\u6765\u6284\u53bb\uff0c\u4e00\u4e0a\u6765\u5c31\u8ddf\u4f60\u8bb2\u7ea2\u9ed1\u6811\u7684\u6027\u8d28\uff0c\u4e3a\u4ec0\u4e48\u8fd9\u6837\u3001\u8fd9\u4e48\u6765\u7684\uff0c\u53ea\u5b57\u4e0d\u63d0\u3002\u770b\u7740\u5b9e\u5728\u4e5f\u5f88\u8ba9\u4eba\u90c1\u95f7\u3002\u628a\u8fd9\u4e9b\u6027\u8d28\u5565\u7684\u5168\u90e8\u786c\u8bb0\u4e0b\u6765\uff0c\u7136\u540e\u5199\u4e00\u5199\u518d\u4f53\u4f1a\u4e5f\u4e0d\u662f\u8bf4\u5c31\u4e0d\u662f\u529e\u6cd5\uff0c\u4f46\u662f\u4e2a\u4eba\u6bd4\u8f83\u8ba8\u538c\u3002\u4e8e\u662f\u5c31\u60f3\u4e0a\u7f51\u53bb\u627e\u5916\u56fd\u4eba\u5199\u7684\u6559\u5b66\u3002Bing\u641c\u7d22\u7684\u82f1\u8bed\u7248\u641cred-black tree tutorial\u8fd9\u4e2a\u5173\u952e\u8bcd\uff0c\u7136\u540e\u5c31\u627e\u4e86 http:\/\/eternallyconfuzzled.com\/tuts\/datastructures\/jsw_tut_rbtree.aspx<\/a> \u8fd9\u4e2a\u6765\u770b\u3002\u5728\u6211\u641c\u7d22\u7684\u65f6\u5019\uff0c\u8fd9\u4e2a\u662f\u7b2c\u4e00\u4e2a\u7ed3\u679c\u3002\u70b9\u8fdb\u53bb\u770b\u4e86\u4e5f\u662f\u6bd4\u8f83\u5bb9\u6613\u7406\u89e3\uff0c\u5c31\u51b3\u5b9a\u7528\u8fd9\u4e2a\u6765\u5b66\u4e86\u3002\u6700\u7ec8\u5b66\u4e60\u4e86\u5b83\u7684Bottom-up insertion\u548cTop-down deleteion\u4e24\u79cd\u64cd\u4f5c\u3002<\/p>\n

<\/p>\n

\u6211\u4e4b\u524d\u8bf4\u6211\u4e0d\u559c\u6b22\u770b\u4e00\u4e0a\u6765\u5c31\u662f\u8981\u8bb0\u90a3\u4e9b\u6027\u8d28\u7684\u6559\u5b66\u3002\u4e0a\u9762\u90a3\u4e2a\u94fe\u63a5\u91cc\u7684\u6587\u7ae0\u662f\u4eceB-tree\u5f00\u59cb\u7684\uff0c\u4ece\u8fd9\u4e2a\u5730\u65b9\u5f00\u59cb\u80fd\u591f\u8ba9\u4eba\u770b\u4e86\u5f88\u5bb9\u6613\u77e5\u9053\u662f\u600e\u4e48\u56de\u4e8b\u3002<\/p>\n

\u4e8c\u53c9\u641c\u7d22\u6811\u8fd8\u662f\u6bd4\u8f83\u5bb9\u6613\u61c2\u7684\uff0c\u4e00\u4e2a\u8282\u70b9\u4fdd\u5b58\u4e00\u4e2a\u6570\u636e\uff0c\u7136\u540e\u8fd8\u6709\u5de6\u53f3\u4e24\u4e2a\u6307\u9488\uff0c\u6bd4\u8fd9\u4e2a\u6570\u636e\u5c0f\u7684\u653e\u5728\u5de6\u6307\u9488\uff0c\u6bd4\u8fd9\u4e2a\u6570\u636e\u5927\u7684\u653e\u5728\u53f3\u6307\u9488\uff0c\u7136\u540e\u8bb8\u591a\u6570\u636e\u901a\u8fc7\u8fd9\u79cd\u65b9\u5f0f\u5173\u8054\u8d77\u6765\uff0c\u8981\u627e\u67d0\u4e2a\u6570\u636e\u7684\u65f6\u5019\uff0c\u5c31\u4e5f\u7528\u540c\u6837\u7684\u65b9\u5f0f\uff0c\u4ece\u6811\u6839\u5f00\u59cb\u8d70\uff0c\u53d1\u73b0\u5f53\u524d\u8282\u70b9\u4e0a\u7684\u6570\u636e\u6bd4\u8981\u627e\u7684\u6570\u636e\u5c0f\uff0c\u5c31\u5f80\u53f3\u8d70\uff1b\u53d1\u73b0\u5f53\u524d\u8282\u70b9\u7684\u6570\u636e\u6bd4\u8981\u627e\u7684\u6570\u636e\u5927\uff0c\u5c31\u5f80\u5de6\u8d70\u3002\u5c31\u597d\u50cf\u7efc\u827a\u8282\u76ee\u91cc\u731c\u6570\u5b57\u6e38\u620f\u7684\u65f6\u5019\u4e3b\u6301\u4eba\u8ddf\u4f60\u8bf4\u201c\u5927\u4e86\u201d\u201c\u5c0f\u4e86\u201d\u90a3\u6837\uff0c\u5728\u6700\u7406\u60f3\u72b6\u6001\u4e0b\u6bcf\u4e00\u6b21\u6bd4\u8f83\u90fd\u80fd\u8fc7\u6ee4\u6389\u6570\u636e\u96c6\u91cc\u4e00\u534a\u7684\u5185\u5bb9\uff0c\u4e00\u534a\u4e00\u534a\u53c8\u4e00\u534a\u5230\u4e86\u6700\u540e\u5269\u4e0b\u4e00\u4e2a\u7684\u65f6\u5019\u5c31\u662f\u4f60\u8981\u627e\u7684\u6570\u636e\u4e86\uff0c\u6216\u8005\u5230\u4e86\u6700\u540e\u6ca1\u6570\u636e\u4e86\u8bf4\u660e\u4f60\u8981\u627e\u7684\u4e1c\u897f\u5728\u8fd9\u4e2a\u96c6\u5408\u91cc\u6ca1\u6709\u3002<\/p>\n

B-Tree\u4e0d\u662f\u4e8c\u53c9\u7684\uff0c\u662f\u5f88\u591a\u53c9\u7684\uff0c\u6240\u4ee5\u4e0d\u80fd\u5355\u7eaf\u7528\u201c\u6bd4\u5b83\u5927\u201d\u201c\u6bd4\u5b83\u5c0f\u201d\u6765\u8bf4\u660e\uff1a\u8fd9\u4e2a\u201c\u5b83\u201d\u662f\u8c01\u554a\uff0c\u4e00\u4e2a\u8282\u70b9\u91cc\u53ef\u80fd\u4e0d\u6b62\u4e00\u4e2a\u6570\u636e\u7684\u3002B-Tree\u5462\u4e00\u4e2a\u8282\u70b9\u5927\u6982\u662f\u8fd9\u4e2a\u6837\u5b50
\"image\"<\/a>
\u4e5f\u5c31\u662f\u8bf4\uff0c\u672c\u6765\u662f\u4e00\u4e2a\u8282\u70b9\u53ea\u6709\u4e00\u4e2a\u201c\u5206\u754c\u70b9\u201d\u7684\uff0c\u73b0\u5728\u4e00\u4e2a\u8282\u70b9\u53ef\u4ee5\u6709n\u4e2a\u5206\u754c\u70b9\uff0c\u7531\u8fd9\u4e9b\u5206\u754c\u70b9\u53ef\u4ee5\u5f97\u5230n+1\u4e2a\u5b50\u6811\u3002\u8fd9\u91cc\u9762\u76845\u30018\u300112\u5c31\u662f\u5206\u754c\u70b9\uff0c\u7136\u540e\u641c\u7d22\u7684\u65f6\u5019\u5212\u5206\u51fa\u56db\u4e2a\u8303\u56f4\uff1a\u6bd45\u5c0f\u3001\u6bd45\u5927\u4f46\u662f\u6bd48\u5c0f\u3001\u6bd48\u5927\u4f46\u662f\u6bd412\u5c0f\u3001\u6bd412\u5927\u3002<\/p>\n

\u7ea2\u9ed1\u6811\u5c31\u662f\u4eceB-Tree\u53d8\u6765\u7684\uff0c\u5b83\u662f\u4ece\u4e00\u4e2a\u8282\u70b9\u6700\u591a\u80fd\u5b583\u4e2a<\/strong><\/font>\u201c\u5206\u754c\u70b9\u201d\u3001\u6700\u591a\u53ef\u4ee5\u67094\u4e2a\u5b50\u6811\u7684B-Tree\u53d8\u6765\u7684\u4e8c\u53c9\u6811\u3002\u6bcf\u4e2aB-Tree\u7684\u8282\u70b9\u5728\u7ea2\u9ed1\u6811\u91cc\u7531\u4e00\u4e2a\u9ed1\u8272\u8282\u70b9\u548c\u82e5\u5e72\u4e2a\u7ea2\u8272\u8282\u70b9\u7ec4\u6210\u3002\u4e5f\u5c31\u662f\u8bf4\u5f53\u4f5cB-Tree\u770b\u7684\u65f6\u5019\uff0c\u7ea2\u9ed1\u6811\u91cc\u7684\u7ea2\u8272\u8282\u70b9\u662f\u7b97\u5728\u5b83\u7236\u8282\u70b9\uff08\u9ed1\uff09\u91cc\u9762\u7684\u3002\u56e0\u4e3a\u662f\u6700\u591a3\u4e2a\u201c\u5206\u754c\u70b9\u201d\u7684B-Tree\uff0c\u6240\u4ee5\u53d8\u6210\u7ea2\u9ed1\u6811\u8282\u70b9\u7684\u65f6\u5019\uff0c\u5c31\u6709\u4e09\u79cd\u60c5\u51b5\uff1a\u53ea\u6709\u4e00\u4e2a\u9ed1\u8272\u8282\u70b9\u3001\u6709\u4e00\u4e2a\u9ed1\u8272\u8282\u70b9\u548c\u4e00\u4e2a\u7ea2\u8272\u8282\u70b9\u3001\u6709\u4e00\u4e2a\u9ed1\u8272\u8282\u70b9\u548c\u4e24\u4e2a\u7ea2\u8272\u8282\u70b9\u3002
\"image\"<\/a>
\u5982\u679c\u8981\u8bf4\u4e3a\u4ec0\u4e48\u6700\u540e\u4e00\u4e2a\u4e0d\u628a\u4e24\u4e2a\u7ea2\u8272\u8282\u70b9\u90fd\u753b\u5728\u540c\u4e00\u8fb9\u7684\u8bdd\uff0c\u56e0\u4e3a\u5bf9\u4e8c\u53c9\u6811\u6765\u8bf4\uff0c\u6df1\u5ea6\u662f\u8d8a\u4f4e\u8d8a\u597d\uff0c\u56e0\u4e3a\u6df1\u5ea6\u8d8a\u4f4e\u627e\u6570\u636e\u8d77\u6765\u8d8a\u5feb\uff0c\u6240\u4ee5\u5982\u679c\u9047\u4e0a\u6709\u4e24\u4e2a\u7ea2\u8272\u8282\u70b9\u90fd\u5728\u540c\u4e00\u8fb9\u7684\u60c5\u51b5\uff0c\u5c31\u8981\u628a\u5b83\u8c03\u6574\u6210\u4e24\u4e2a\u7ea2\u8272\u8282\u70b9\u5206\u522b\u5728\u4e24\u8fb9\u7684\u60c5\u51b5\u3002\u7ea2\u9ed1\u6811\u5c31\u662f\u9760\u4e0d\u505c\u5730\u8c03\u6574\uff0c\u5728\u5bf9\u5b83\u8fdb\u884c\u63d2\u5165\u3001\u5220\u9664\u7684\u8fc7\u7a0b\u4e2d\uff0c\u4fdd\u6301\u5b83\u4ee3\u8868\u7684B-Tree\u7684\u6bcf\u4e2a\u53f6\u5b50\u8282\u70b9\u90fd\u5728\u540c\u4e00\u4e2a\u6df1\u5ea6\u4e0a<\/strong><\/font>\u3002\u6240\u8c13\u201c\u4ee3\u8868\u7684B-Tree\u8282\u70b9\u201d\uff0c\u5c31\u662f\u5728\u770b\u7ea2\u9ed1\u6811\u7684\u65f6\u5019\uff0c\u8981\u628a\u7ea2\u8272\u8282\u70b9\u548c\u5b83\u4e0a\u9762\u7684\u9ed1\u8272\u8282\u70b9\u770b\u6210\u4e00\u4e2a\u6574\u4f53<\/strong><\/font>\u2026\u2026\u4e5f\u5c31\u662f\u8bf4\uff0c\u4ece\u4e0a\u5f80\u4e0b\u5728\u6570\u6df1\u5ea6\u7684\u65f6\u5019\uff0c\u9047\u5230\u9ed1\u8272\u7b97\u589e\u52a0\u4e00\u5c42\uff0c\u9047\u4e0a\u7ea2\u8272\u4e0d\u7b97\u3002\u6839\u8282\u70b9\u4e0a\u9762\u6ca1\u6709\u8282\u70b9\u4e86\uff0c\u4e0d\u80fd\u628a\u6839\u8282\u70b9\u7b97\u5728\u201c\u67d0\u4e2a\u9ed1\u8272\u8282\u70b9\u201d\u7684\u5934\u4e0a\uff0c\u6240\u4ee5\u6839\u8282\u70b9\u4e00\u5b9a\u662f\u9ed1\u8272\u7684\u3002<\/font>\u5982\u679c\u8c03\u6574\u8fc7\u7a0b\u4e2d\u6839\u8282\u70b9\u53d8\u6210\u4e86\u7ea2\u8272\uff0c\u53ef\u4ee5\u65e0\u6761\u4ef6\u628a\u5b83\u53d8\u4e3a\u9ed1\u8272<\/font><\/strong>\uff1a\u53cd\u6b63\u5df2\u7ecf\u662f\u6839\u4e86\uff0c\u6df1\u5ea6\u52a0\u4e00\u4e5f\u662f\u4e24\u8fb9\u4e00\u8d77\u52a0\u4e86\uff0c\u4e0d\u4f1a\u5f71\u54cd\u5e73\u8861\u3002<\/p>\n

\u4e0b\u56fe\u662f\u4e00\u4e2a\u6211\u5199\u7684\u7a0b\u5e8f\u4ee3\u7801\u5728\u8fd0\u884c\u8fc7\u7a0b\u4e2d\u63d2\u5165\u4e8615\u4e2a\u968f\u673a\u6570\u4e4b\u540e\u6784\u5efa\u7684\u7ea2\u9ed1\u6811\uff1a<\/p>\n

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

\u6309\u7167\u5b83\u6240\u4ee3\u8868\u7684B-Tree\u6765\u770b\uff0c\u662f\u8fd9\u6837\u7684<\/p>\n

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

\u6240\u4ee5\u5b83\u5176\u5b9e\u662f\u4e00\u4e2a\u4e09\u5c42\u7684B-Tree\u3002<\/p>\n

\u5bf9\u4e8e\u8fd9\u6837\u7684\u4e8c\u53c9\u6811\uff0c\u641c\u7d22\u662f\u4e0d\u7528\u8bf4\u4e86\uff0c\u4e8c\u53c9\u6811\u4e00\u4e2a\u5f88\u91cd\u8981\u7684\u529f\u80fd\u5c31\u662f\u62ff\u6765\u641c\u7d22\u3002\u56e0\u4e3a\u7ea2\u9ed1\u6811\u4e5f\u53ea\u662f\u4e00\u4e2a\u666e\u901a\u7684\u4e8c\u53c9\u641c\u7d22\u6811\uff0c\u6240\u4ee5\u641c\u7d22\u7684\u65f6\u5019\u548c\u5176\u4ed6\u4e8c\u53c9\u641c\u7d22\u6811\u6ca1\u6709\u533a\u522b\u3002\u91cd\u70b9\u5728\u4e8e\u63d2\u5165\u548c\u5220\u9664\u64cd\u4f5c\uff0c\u56e0\u4e3a\u8fd9\u4e24\u4e2a\u6bd4\u8f83\u9ebb\u70e6\u3002<\/p>\n

\u5148\u8bf4\u63d2\u5165\u7684\u64cd\u4f5c\u3002\u56e0\u4e3a\u6811\u662f\u6df1\u5ea6\u8d8a\u4f4e\u8d8a\u597d\uff0c\u7136\u800c\u9ed1\u8272\u7b97\u6df1\u5ea6\u800c\u7ea2\u8272\u4e0d\u7b97<\/font><\/strong>\uff0c\u4e8e\u662f\u63d2\u5165\u7684\u8282\u70b9\u6700\u7406\u60f3\u72b6\u6001\u5c31\u662f\u7ea2\u8272\uff0c\u8fd9\u6837\u4e0d\u4f1a\u589e\u52a0\u6df1\u5ea6\u3002\u4e8b\u60c5\u5f53\u7136\u6ca1\u6709\u8fd9\u4e48\u7b80\u5355\uff0c\u56e0\u4e3a\u7ea2\u8272\u8282\u70b9\u662f\u4f9d\u9644\u5728\u9ed1\u8272\u8282\u70b9\u4e0a\u7684\uff0c\u800c\u53d7\u5230\u7ea2\u9ed1\u6811\u6240\u8868\u793a\u7684B-Tree\u7684\u6bcf\u4e2a\u8282\u70b9\u6700\u591a\u53ea\u80fd\u6709\u4e09\u4e2a\u201c\u5206\u754c\u70b9\u201d\u7684\u9650\u5236\uff0c\u4e00\u4e2a\u9ed1\u8272\u8282\u70b9\u4e0a\u6700\u591a\u53ea\u80fd\u4f9d\u9644\u4e24\u4e2a\u7ea2\u8272\u8282\u70b9\uff0c\u518d\u591a\u4e0b\u53bb\u5c31\u7834\u574f\u4e86\u8fd9\u79cd\u9650\u5236\uff0c\u6240\u4ee5\u5f53\u63d2\u5165\u7684\u7ea2\u8272\u8282\u70b9\u6162\u6162\u589e\u591a\u7684\u65f6\u5019\uff0c\u8c03\u6574\u4e5f\u5c31\u4e0d\u53ef\u907f\u4e86\u3002<\/p>\n

\u8c03\u6574\u7684\u624b\u6bb5\u662f\u901a\u8fc7\u65cb\u8f6c\u4e8c\u53c9\u6811\u7684\u8282\u70b9\u3002\u4e3e\u4e2a\u4f8b\u5b50\uff0c\u4e0a\u9762\u90a3\u4e2a\u56fe\uff0c\u6709\u4e24\u4e2a\u5206\u754c\u70b9\u7684\u90a3\u4e2a\u56fe\uff0c\u5b83\u53d8\u4e3a\u7ea2\u9ed1\u6811\u8282\u70b9\u7684\u65f6\u5019\u6709\u4e24\u79cd\u8868\u793a\u65b9\u6cd5\u5bf9\u4e0d\u5bf9\uff0c\u8fd9\u4e24\u79cd\u65b9\u6cd5\u662f\u7b49\u4ef7\u7684\uff0c\u4ece\u4e00\u79cd\u8868\u793a\u6cd5\u53d8\u4e3a\u53e6\u4e00\u79cd\u8868\u793a\u6cd5\uff0c\u4e5f\u4e0d\u5f71\u54cd\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u6027\u8d28\u4e5f\u4e0d\u5f71\u54cd\u7ea2\u9ed1\u6811\u7684\u6027\u8d28\u3002\u5bf9\u4e8e\u5de6\u8fb9\u7684\u56fe\uff0c\u628a\u90a3\u4e2a8\u8f6c\u4e0b\u6765\uff0c\u8c03\u6574\u4e00\u4e0b\u989c\u8272\uff0c\u5c31\u53d8\u6210\u4e86\u53f3\u8fb9\u90a3\u4e2a\u56fe\u3002
\"image\"<\/a><\/p>\n

\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u8282\u70b9\u65cb\u8f6c\u662f\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u4e3b\u8981\u8c03\u6574\u65b9\u5f0f\uff0c\u901a\u8fc7\u8fd9\u79cd\u8c03\u6574\uff0c\u4e0d\u4f1a\u7834\u574f\u4e8c\u53c9\u641c\u7d22\u6811\u201c\u5de6\u8fb9\u8282\u70b9\u5c0f\u53f3\u8fb9\u8282\u70b9\u5927\u201d\u7684\u6027\u8d28\u3002\u6ce8\u610f\u65cb\u8f6c\u8fc7\u7a0b\u4e2d\uff0c\u5b50\u8282\u70b9\u4ece\u4e00\u4e2a\u7236\u8282\u70b9\u4e0b\u79fb\u52a8\u5230\u53e6\u4e00\u4e2a\u7236\u8282\u70b9\u4e0b\u7684\u53d8\u5316\uff0c\u6bd4\u5982\u5728\u4e0a\u56fe\u4e2d\uff0cb\u4ece5\u90a3\u4e2a\u8282\u70b9\u7684\u53f3\u8fb9\u53d8\u5230\u4e868\u90a3\u4e2a\u8282\u70b9\u7684\u5de6\u8fb9\uff0c\u8fd9\u6837\u7684\u53d8\u5316\u89c4\u5f8b\u3002<\/strong><\/font><\/p>\n

\u7ea2\u9ed1\u6811\u9760\u7740\u8fd9\u79cd\u65cb\u8f6c\uff0c\u53ef\u4ee5\u89e3\u51b3\u4e24\u4e2a\u7ea2\u8272\u8282\u70b9\u90fd\u5728\u540c\u4e00\u8fb9\u7684\u95ee\u9898\u3002\u4f8b\u5982\u4e0a\u9762\u5de6\u8fb9\u90a3\u4e2a\u56fe\uff0c8\u548c5\uff0c\u6211\u8981\u63d2\u5165\u4e00\u4e2a4\uff0c\u8fd9\u4e2a4\u662f\u7ea2\u8272\u8282\u70b9\uff0c\u4f46\u662f\u63d2\u5165\u7684\u5730\u65b9\u662f\u57285\u4e0b\u9762\u4e0d\u662f\u57288\u4e0b\u9762\u3002\u8fd9\u4e2aB-Tree\u8282\u70b9\u4f5c\u4e3a\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u4e00\u90e8\u5206\u6765\u8bf4\uff0c\u6548\u7387\u4e0d\u591f\u9ad8\u3002\u7ea2\u9ed1\u6811\u91cc\u89c4\u5b9a\u7ea2\u8272\u8282\u70b9\u7684\u5b50\u8282\u70b9\u4e0d\u80fd\u662f\u7ea2\u8272\u8282\u70b9<\/font><\/strong>\uff0c\u9047\u4e0a\u8fd9\u6837\u7684\u60c5\u51b5\uff0c\u5c31\u901a\u8fc7\u65cb\u8f6c\u7684\u65b9\u5f0f\u628a\u8fd9\u4e2a\u8282\u70b9\u8f6c\u6210\u7b26\u5408\u89c4\u5b9a\u7684\uff0c\u50cf\u8fd9\u6837\uff1a\uff08\u6ce8\uff1a\u8fd9\u91cc\u7684b\u5176\u5b9e\u662f\u7a7a\u7684\u8282\u70b9\uff0c\u5c31\u662f\u4e0d\u5b58\u5728\u7684\uff0c\u56e0\u4e3a\u5982\u679cb\u662f\u5b58\u5728\u7684\uff0c\u90a3\u5fc5\u7136\u662f\u9ed1\u8272\u8282\u70b9\uff0c\u8fd9\u6837\u5c31\u4e0d\u6ee1\u8db3\u6240\u6709\u53f6\u5b50\u8282\u70b9\u5728B-Tree\u91cc\u6df1\u5ea6\u76f8\u540c\u7684\u89c4\u5b9a\u4e86\u3002c\u4e5f\u662f\u540c\u6837\u7684\u9053\u7406\uff0c\u56e0\u4e3a8\u4e0b\u9762\u4e0d\u80fd\u518d\u6709\u66f4\u591a\u7684\u7ea2\u8272\u8282\u70b9\u4e86\u3002\u4e3a\u4e86\u65b9\u4fbf\u8bf4\u660eb\u548cc\u6700\u7ec8\u4f1a\u5230\u54ea\u91cc\u53bb\uff0c\u8fd9\u91cc\u8fd8\u662f\u753b\u51fa\u6765\u4e86\uff0c\u56e0\u4e3a\u8bf4\u5230\u8981\u589e\u52a0\u5c42\u6570\u7684\u60c5\u51b5\u7684\u65f6\u5019\uff0c\u90a3\u4e2a4\u4e0b\u9762\u5c31\u6709\u53ef\u80fd\u8fd8\u6709\u8282\u70b9\u4e86<\/strong>\uff09
\"image\"<\/a><\/p>\n

\u65cb\u8f6c\u7684\u65f6\u5019\uff0c\u56e0\u4e3a\u6700\u4e0a\u9762\u7684\u9ed1\u8272\u8282\u70b9\u662f\u4f5c\u4e3a\u8fd9\u4e2a\u201cB-Tree\u8282\u70b9\u201d\u8868\u793a\u6210\u7ea2\u9ed1\u6811\u65f6\u7684\u201c\u6839\u8282\u70b9\uff08\u5355\u4e2aB-Tree\u8282\u70b9\u8303\u56f4\u5185\uff09\u201d\u5b58\u5728\u7684\uff0c\u6240\u4ee5\u8c03\u6574\u4e4b\u540e\uff0c\u548c\u4e0a\u4e00\u5c42\u201cB-Tree\u8282\u70b9\u201d\u8fde\u63a5\u7684\u8282\u70b9\u8fd8\u662f\u8981\u5237\u6210\u9ed1\u8272\u7684\uff0c\u800c\u5176\u4ed6\u4f5c\u4e3a\u4f9d\u9644\u5728\u8fd9\u4e2a\u9ed1\u8272\u8282\u70b9\u4e0a\u7684\u8282\u70b9\uff0c\u662f\u8981\u5237\u6210\u7ea2\u8272\u7684<\/strong><\/font>\uff0c\u6ce8\u610f\u5176\u95f4\u7684\u989c\u8272\u53d8\u5316\u3002\u4e24\u4e2a\u7ea2\u8272\u8282\u70b9\u7684\u65cb\u8f6c\u9664\u4e86\u8fd9\u79cd\u8fd8\u6709\u4e00\u79cd\u60c5\u51b5\uff0c\u6bd4\u5982\u521a\u624d\u90a3\u4e2a\uff0c\u6211\u8fd9\u6b21\u63d2\u5165\u7684\u662f6\uff0c\u5982\u679c\u4e5f\u8fd8\u662f\u50cf\u521a\u624d\u90a3\u6837\u65cb\u8f6c\uff0c\u5c31\u4f1a\u53d8\u6210\uff08\u548c\u4e0a\u9762\u4e00\u6837\uff0ca\u548cc\u5176\u5b9e\u662f\u7a7a\u7684<\/strong>\uff09
\"image\"<\/a>
\u8fd9\u90fd\u8f6c\u7684\u5565\u2026\u2026\uff08\u6276\u989d\uff09\u6240\u4ee5\u4e5f\u5c31\u662f\u8bf4\uff0c\u53ea\u6709\u5f53\u4e24\u4e2a\u7ea2\u8282\u70b9\u90fd\u5728\u540c\u4e00\u4e2a\u65b9\u5411\u7684\u65f6\u5019\uff0c\u624d\u80fd\u8fd9\u4e48\u8f6c<\/strong><\/font>
\u6240\u4ee5\u8fd9\u79cd\u4e24\u4e2a\u7ea2\u8272\u8282\u70b9\u65b9\u5411\u4e0d\u4e00\u6837\u7684\u60c5\u51b5\uff0c\u662f\u5148\u8f6c\u6210\u4e0a\u9762\u65b9\u5411\u76f8\u540c\u7684\u90a3\u4e2a\u6837\u5b50\uff0c\u7136\u540e\u518d\u8f6c\u4e00\u6b21\u628a\u5b83\u8f6c\u56de\u6765\uff0c\u5c31\u50cf\u8fd9\u6837
\"image\"
<\/a>\u4e5f\u5c31\u662f\u8bf4\u5f53\u4e24\u4e2a\u7ea2\u8282\u70b9\u5728\u4e0d\u540c\u65b9\u5411\u7684\u65f6\u5019\uff0c\u8981\u8fd9\u4e48\u8f6c\u4e24\u6b21\u3002\u6ce8\u610f\u8fd9\u4e24\u6b21\u7684\u65b9\u5411\u662f\u76f8\u53cd\u7684\u3002<\/strong>\u8fdb\u884c\u8fd9\u6837\u7684\u53cc\u65cb\u64cd\u4f5c\u4e4b\u540e\uff0c\u4ecd\u7136\u8981<\/font>\u6ce8\u610f\u989c\u8272\u7684\u53d8\u5316\uff1a\u548c\u4e0a\u4e00\u5c42\u8fde\u63a5\u7684\u8282\u70b9\u8981\u5237\u6210\u9ed1\u8272\uff0c\u5176\u4ed6\u5237\u6210\u7ea2\u8272\u3002<\/strong> <\/font><\/p>\n

\u5230\u8fd9\u91cc\u4e3a\u6b62\uff0c\u5982\u679c\u63d2\u5165\u7684\u7ea2\u8272\u7684\u4f4d\u7f6e\u4e0d\u5bf9\uff0c\u5df2\u7ecf\u77e5\u9053\u5982\u4f55\u8c03\u56de\u6765\u4e86\u3002\u4f46\u662f\u4e0d\u65ad\u8fd9\u6837\u63d2\u5165\u7ea2\u8272\u8282\u70b9\uff0c\u60f3\u60f3\u4e5f\u4e0d\u5bf9\u3002\u56e0\u4e3a\u7ea2\u8272\u8282\u70b9\u5728B-Tree\u91cc\u4e0d\u8ba1\u7b97\u6df1\u5ea6\u7684\uff0c\u4e00\u4e2aB-Tree\u4e0d\u53ef\u80fd\u4e00\u76f4\u63d2\u5165\u4e00\u76f4\u63d2\u5165\u6df1\u5ea6\u4e0d\u589e\u52a0\u3002\u53e6\u5916\u4e00\u4e2a\u9ed1\u8272\u8282\u70b9\u53ea\u80fd\u5e26\u6700\u591a\u4e24\u4e2a\u7ea2\u8272\u8282\u70b9\uff0c\u4e0d\u80fd\u518d\u591a\u4e0b\u53bb\u3002\u6240\u4ee5\u5bf9\u4e8e\u8fd9\u79cd\u5df2\u7ecf\u6ee1\u4e86\u7684\u201cB-Tree\u8282\u70b9\u201d\uff0c\u7ea2\u9ed1\u6811\u4e5f\u6709\u81ea\u5df1\u7684\u5904\u7406\u529e\u6cd5\uff1a\u628a\u5b83\u62c6\u5206\u6210\u4e24\u4e2a\u201cB-Tree\u8282\u70b9\u201d\uff0c\u7236\u8282\u70b9\u585e\u5230\u4e0a\u4e00\u5c42\u53bb\u3002\u5565\u53eb\u201c\u585e\u5230\u4e0a\u4e00\u5c42\u201d\uff1f\u7ea2\u8272\u8282\u70b9\u4e0d\u662f\u201c\u4f9d\u9644\u5728\u522b\u4eba\u8eab\u4e0a\u201d\u7684\u5417\uff0c\u90a3\u5c31\u76f4\u63a5\u628a\u7236\u8282\u70b9\u53d8\u6210\u7ea2\u8272\u8282\u70b9\uff0c\u8fd9\u5c31\u662f\u201c\u585e\u5230\u4e0a\u4e00\u5c42\u201d\u4e86\u3002\u6bd4\u5982\u4e0a\u56fe\u76846\u30015\u30018\uff0c\u5982\u679c\u8fd9\u4e2a\u65f6\u5019\u6211\u518d\u8981\u63d2\u5165\u4e00\u4e2a9\uff0c\u5c31\u8981\u8fdb\u884c\u62c6\u5206\u4e86\uff1a5\u548c8\u662f\u62c6\u51fa\u6765\u7684\u65b0\u8282\u70b9\uff0c6\u88ab\u585e\u5165\u4e0a\u4e00\u5c42\u3002\u68c0\u67e5\u662f\u5426\u6709\u4e24\u4e2a\u7ea2\u8282\u70b9\u7684\u64cd\u4f5c\u5e94\u8be5\u6700\u5148\u8fdb\u884c\uff0c\u56e0\u4e3a\u5982\u679c\u4e00\u4e2aB-Tree\u8282\u70b9\u91cc\u5df2\u7ecf\u6709\u4e09\u4e2a\u7ea2\u8282\u70b9\u4e86\uff0c\u90a3\u4e48\u600e\u4e48\u65cb\u8f6c\u90fd\u6ca1\u7528\u7684<\/strong><\/font>\u3002
\"image\"<\/a>
\u6240\u8c13\u201c\u88ab\u585e\u5165\u4e0a\u4e00\u5c42\u201d\uff0c\u4ed4\u7ec6\u8003\u8651\u4e00\u4e0b\uff0c\u5176\u5b9e\u4e0d\u5c31\u662f\u201c\u7ed9\u4e0a\u9762\u6dfb\u52a0\u4e86\u4e00\u4e2a\u65b0\u7684\u8282\u70b9\u201d\u5417\uff1f\u4e8e\u662f\u5982\u679c\u6dfb\u52a0\u4ee5\u540e\u7ea2\u8272\u8282\u70b9\u8fc7\u591a\u4e86\uff0c\u5c31\u7ee7\u7eed\u6309\u7167\u8fd9\u4e2a\u601d\u8def\u8c03\u554a\u8c03\u7ed9\u8c03\u6574\u4e0a\u53bb\uff0c\u8c03\u6574\u5230\u6839<\/strong><\/font>\u7684\u65f6\u5019\uff0c\u5982\u679c\u6839\u53d8\u6210\u7ea2\u8272\u4e86\uff0c\u5c31\u628a\u5b83\u53d8\u6210\u9ed1\u7684\uff1a\u4f60\u770b\u8fd9\u4e0bB-Tree\u7684\u6df1\u5ea6\u589e\u52a0\u4e861<\/strong><\/font>\u3002\u7ea2\u9ed1\u6811\u6240\u4ee3\u8868\u7684B-Tree\u5c31\u662f\u8fd9\u4e48\u589e\u52a0\u6df1\u5ea6\u7684\uff1a\u5982\u679c\u6839\u8282\u70b9\u662f\u7ea2\u7684\uff0c\u628a\u5b83\u53d8\u6210\u9ed1\u7684\u3002<\/p>\n

\u4ed4\u7ec6\u89c2\u5bdf\u7684\u8bdd\uff0c\u4ee5\u4e0a\u4e09\u79cd\u64cd\u4f5c\u5168\u90fd\u662f\u5728\u540c\u4e00\u4e2aB-Tree\u8282\u70b9\u5185\u5b8c\u6210\uff0c\u524d\u4e24\u4e2a\u90fd\u4e0d\u4f1a\u5f71\u54cd\u8282\u70b9\u5916\u7684\u90e8\u5206\uff0c\u90fd\u662f\u8282\u70b9\u5185\u90e8\u7684\u4e8b\uff1b\u6700\u540e\u4e00\u4e2a<\/p>\n

\u5728\u5b9e\u9645\u64cd\u4f5c\u8fc7\u7a0b\u4e2d\uff0c\u89c4\u5b9a\u6240\u6709\u5b50\u6811\uff0c\u5982\u679c\u662f\u7a7a\u5b50\u6811\uff0c\u90a3\u4e48\u5c31\u8ba4\u4e3a\u5b83\u662f\u4e00\u4e2a\u9ed1\u8272\u8282\u70b9<\/font><\/strong>\u3002\u8fd9\u6837\u53ef\u4ee5\u5728\u5199\u4ee3\u7801\u7684\u65f6\u5019\u5e26\u6765\u4e00\u4e9b\u4fbf\u5229\uff0c\u5e76\u4e14\u4e5f\u4e0d\u5f71\u54cd\u7ea2\u9ed1\u6811\u7684\u6027\u8d28\u3002\u8fd9\u6837\u5c31\u53ef\u4ee5\u5f00\u59cb\u8ba8\u8bba\u5b9e\u73b0\u4e86\u3002<\/p>\n

\u4ee5\u4e0a\u8c08\u5230\u7684\u63d2\u5165\u64cd\u4f5c\u4e2d\uff0c\u56e0\u4e3a\u63d2\u5165\u7684\u603b\u662f\u7ea2\u8272\u8282\u70b9\uff0c\u53c8\u7ea2\u8272\u8282\u70b9\u4e0d\u8ba1\u7b97\u6df1\u5ea6\uff0c\u6240\u4ee5\u53ef\u80fd\u4ea7\u751f\u7684\u4e0d\u6ee1\u8db3\u7ea2\u9ed1\u6811\u5b9a\u4e49\u7684\u60c5\u51b5\uff0c\u5c31\u53ea\u6709\u7ea2\u8272\u8282\u70b9\u8fc7\u591a\u3002\u5f52\u7eb3\u4e00\u4e0b\uff0c\u63d2\u5165\u8fc7\u7a0b\u4e2d\u4f1a\u9047\u5230\u7684\u7ea2\u8272\u8282\u70b9\u8fc7\u591a\uff0c\u4e00\u5171\u662f\u4e09\u79cd\u60c5\u51b5\u3002\u8fd9\u4e09\u79cd\u60c5\u51b5\u90fd\u662f\u6307\u201c\u5728\u540c\u4e00\u4e2a\u4ed6\u4eec\u6240\u4ee3\u8868\u7684B-Tree\u8282\u70b9\u91cc\u201d<\/p>\n

1\u3001\u628a\u4e24\u4e2a\u7ea2\u8272\u8282\u70b9\u63d2\u5230\u540c\u4e00\u8fb9\u53bb\u4e86\uff0c\u4e24\u4e2a\u7ea2\u8272\u8282\u70b9\u5728\u540c\u4e00\u4e2a\u65b9\u5411\u4e0a
2\u3001\u628a\u4e24\u4e2a\u7ea2\u8272\u8282\u70b9\u63d2\u5230\u540c\u4e00\u8fb9\u53bb\u4e86\uff0c\u4e24\u4e2a\u7ea2\u8272\u8282\u70b9\u7684\u65b9\u5411\u4e0d\u540c
3\u3001\u5df2\u7ecf\u6709\u4e24\u4e2a\u7ea2\u8272\u8282\u70b9\u4e86\uff0c\u8fd8\u518d\u5f80\u91cc\u9762\u63d2\u3002<\/p>\n

\u6700\u540e\u4e00\u79cd\u5c31\u662f\u628a\u5b83\u5206\u6210\u4e24\u4e2a\u201cB-Tree\u8282\u70b9\u201d\u3002\u6700\u540e\u4e00\u79cd\u60c5\u51b5\u6700\u5bb9\u6613\uff0c\u4e24\u4e2a\u7ea2\u7684\u6362\u6210\u9ed1\u7684\uff0c\u518d\u628a\u7236\u8282\u70b9\u505a\u6210\u7ea2\u7684\u3002<\/p>\n

\u7136\u540e\u8bf4\u8bf4\u524d\u4e24\u79cd\u60c5\u51b5\uff0c\u56e0\u4e3a\u524d\u4e24\u79cd\u60c5\u51b5\u90fd\u662f\u65cb\u8f6c\uff0c\u4e00\u4e2a\u8f6c\u4e00\u6b21\u4e00\u4e2a\u8f6c\u4e24\u6b21\uff0c\u90a3\u4e48\u5f52\u7eb3\u8d77\u6765\uff0c\u65cb\u8f6c\u64cd\u4f5c\u5c31\u662f\uff1a
\"image\"<\/a>
\u56e0\u4e3a\u65cb\u8f6c\u4e4b\u540eb\u8282\u70b9\u4f1a\u4f5c\u4e3a\u7236\u8282\u70b9\uff0c\u800ca\u4f5c\u4e3a\u5b50\u8282\u70b9\uff0c\u6240\u4ee5a\u6307\u5411b\u7684\u6307\u9488\u4e0d\u5e94\u8be5\u518d\u6307\u5411b\uff1b\u56e0\u4e3a\u5728\u65cb\u8f6c\u540e\u4f5c\u4e3ab\u7684\u5b50\u8282\u70b9\uff0c\u6240\u4ee5b\u539f\u6765\u7684\u4e00\u4e2a\u5b50\u8282\u70b9e\u5c31\u6ca1\u6709\u88ab\u6307\u4e86\u3002\u8fd9\u6837\u4e00\u53bb\u4e00\u6765\uff0c\u6b63\u597da\u539f\u6765\u6307\u5411b\u7684\u6307\u9488\u5c31\u6307\u5411\u4e86e\uff0c\u8fd9\u6837\u4e5f\u7b26\u5408e\u8981\u6bd4b\u5927\u3001\u6bd4a\u5c0f\u7684\u6761\u4ef6\u3002\u53ef\u4ee5\u770b\u5230\uff0c\u65cb\u8f6c\u8fc7\u7a0b\u4e2d\uff0cc\u7684\u5b50\u8282\u70b9\u662f\u6ca1\u6709\u88ab\u78b0\u5230\u7684\u3002\u8fd9\u6837\u8bf4\u53ef\u80fd\u6bd4\u8f83\u62bd\u8c61\uff0c\u90a3\u4e48\u5982\u679c\u4ee5C++\u4ee3\u7801\u8868\u793a\u7684\u8bdd\uff0c\u8fd9\u79cd\u65cb\u8f6c\u64cd\u4f5c\u5176\u5b9e\u662f\u548c\u201c\u8c01\u4f5c\u7236\u8282\u70b9\u201d\u76f8\u5173\u3001\u53ef\u80fd\u6709\u4e24\u4e2a\u65b9\u5411\u7684\u3002\u82e5\u5b9a\u4e49\u6811\u7684\u8282\u70b9\u5982\u4e0b<\/p>\n

template<class T>\nstruct Node\n{\n    T data;\n    bool isRed;\n    Node<T>* left;\n    Node<T>* right;\n    Node(const T& val = T()) : data(val), left(0), right(0), isRed(true) {}\n    bool IsRed() {\n        if (this == 0) return false;\n        else return isRed;\n    }\n};<\/pre>\n
\u90a3\u4e48\u5c31\u6709<\/p>\n
template<class T>\nNode<T> *Node<T>::*GetTheOther(Node<T> *Node<T>::*direction)\n{\n    if (direction == &Node<T>::left)\n        return &Node<T>::right;\n    else\n        return &Node<T>::left;\n}\n\ntemplate<class T>\nNode<T>* SingleTurn(Node<T> *root, Node<T> *Node<T>::*newRoot)\n{\n    Node<T> *Node<T>::*theOther = GetTheOther(newRoot);\n    Node<T> *tmp = root->*newRoot;\n    root->*newRoot = tmp->*theOther;\n    tmp->*theOther = root;\n    return tmp;\n}\n\ntemplate<class T>\nNode<T>* DoubleTurn(Node<T> *root, Node<T> *Node<T>::*newRoot)\n{\n    Node<T> *Node<T>::*theOther = GetTheOther(newRoot);\n    root->*newRoot = SingleTurn(root->*newRoot, theOther);\n    return SingleTurn(root, newRoot);\n}\n<\/pre>\n
\u4ee3\u7801\u4e2d\u7528\u5230\u4e86\u201c\u6307\u5411\u6210\u5458\u53d8\u91cf\u7684\u6307\u9488\u201d\uff0c\u8fd9\u6837\u5c31\u80fd\u6bd4\u8f83\u65b9\u4fbf\u5730\u8868\u793a\u201c\u4e00\u4e2a\u65b9\u5411\u201d\u548c\u201c\u53e6\u4e00\u4e2a\u65b9\u5411\u201d\u800c\u4e0d\u662f\u5199\u6b7b\u7684\u201c\u5de6\u201d\u6216\u8005\u201c\u53f3\u201d\u3002\u5982\u6b64\uff0c\u540c\u4e00\u6bb5\u4ee3\u7801\u5c31\u80fd\u64cd\u4f5c\u4e24\u4e2a\u65b9\u5411\u7684\u65cb\u8f6c\u4e86\u2026\u2026\u53cd\u6b63\u5b83\u4eec\u662f\u5bf9\u79f0\u7684\u3002\u8fd9\u4e9b\u4ee3\u7801\u5b57\u9762\u4e0a\u770b\u662f\u5f88\u6076\u5fc3\u5f88\u96be\u7406\u89e3\uff0c\u6211\u4e5f\u662f\u753b\u4e2a\u56fe\u7136\u540e\u6309\u7167\u56fe\u5199\u51fa\u6765\u7684\u3002\u6ca1\u56fe\u7684\u8bdd\u5149\u9760\u8111\u5b50\u60f3\uff0c\u5927\u6982\u4f1a\u5199\u9519\u5427\u2026\u2026<\/p>\n
\u4f3c\u4e4e\u6709\u70b9\u4e0d\u597d\u7406\u89e3\uff0c\u8bf4\u660e\u4e00\u4e0b\uff0cNode<T> *Node<T>::*newRoot\u8fd9\u4e00\u4e2a\u53c2\u6570\u4e2d\uff0c\u9996\u5148\u662f Node<T> *\uff0c\u4ee3\u8868\u53c2\u6570\u7c7b\u578b\uff0c\u662f\u6307\u5411Node<T>\u7684\u6307\u9488\uff1b\u7136\u540e\u662f Node<T>::*newRoot\uff0c\u4ee3\u8868\u6307\u5411 Node<T> \u7684\u4e00\u4e2a\u6210\u5458\u3002\u8fde\u8d77\u6765\u5c31\u662f\uff0cNode<T>\u6709\u4e00\u4e2a\u6210\u5458\u7c7b\u578b\u662fNode<T>*\uff0c\u7136\u540e\u8fd9\u662f\u4e00\u4e2a\u6307\u9488\u6307\u5411Node<T>\u7c7b\u4e2d\u7684\u4e00\u4e2a\u7c7b\u578b\u4e3aNode<T>*\u7684\u6210\u5458\u3002<\/p>\n
\u4e8e\u662f\u524d\u9762\u63d0\u5230\u7684\u63d2\u5165\u64cd\u4f5c\uff0c\u5c31\u53ef\u4ee5\u6309\u7167\u666e\u901a\u7684\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u63d2\u5165\u65b9\u6cd5\u6765\u63d2\u5165\uff0c\u63d2\u5165\u5b8c\u6bd5\u4e4b\u540e\u539f\u8def\u6cbf\u7740\u63d2\u5165\u65f6\u7ecf\u8fc7\u7684\u6240\u6709\u8282\u70b9\uff0c\u68c0\u67e5\u6709\u6ca1\u6709\u524d\u9762\u63d0\u5230\u7684\u7ea2\u8272\u592a\u591a\u6216\u8005\u7ea2\u8272\u53ea\u5728\u4e00\u8fb9\u7684\u60c5\u51b5\uff0c\u6709\u7684\u8bdd\u628a\u5b83\u4eec\u8c03\u6574\u597d\u3002\u8fd9\u6837\u63d2\u5165\u7684\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n
template<class T>\nNode<T>* Insert(Node<T> *root, const T &val)\n{\n    if (root == 0)\n        return new Node<T>(val);\n    if (root->data == val)\n        return root;\n    \n    \/\/get direction\n    Node<T> *Node<T>::*direction, *Node<T>::*theOther;\n    if (val < root->data) {\n        direction = &Node<T>::left;\n        theOther = &Node<T>::right;\n    } else {\n        direction = &Node<T>::right;\n        theOther = &Node<T>::left;\n    }\n    \n    root->*direction = Insert(root->*direction, val);\n    \n    if (root->left->IsRed() && root->right->IsRed()) {\n        root->isRed = true;\n        root->left->isRed = false;\n        root->right->isRed = false;\n    } else {\n        if ((root->*direction)->IsRed() && (root->*direction->*direction)->IsRed()) {\n            root->isRed = true;\n            root = SingleTurn(root, direction);\n            root->isRed = false;\n        } else if ((root->*direction)->IsRed() && (root->*direction->*theOther)->IsRed()) {\n            root->isRed = true;\n            root = DoubleTurn(root, direction);\n            root->isRed = false;\n        }\n    }\n    \n    return root;\n}<\/pre>\n
\u4e8c\u53c9\u6811\u5e38\u7528\u9012\u5f52\u7684\u65b9\u5f0f\u8fdb\u884c\u64cd\u4f5c\uff0c\u5728\u9012\u5f52\u7684\u64cd\u4f5c\u91cc\u9762\uff0c\u53ef\u4ee5\u8fd9\u4e48\u770b\uff1a\u6bcf\u6b21\u8c03\u7528\u81ea\u5df1\uff08\u51fd\u6570\uff09\uff0c\u8c03\u7528\u7684\u65f6\u5019\u9650\u5b9a\u4e86\u64cd\u4f5c\u8303\u56f4\uff1a\u53bb\u6389\u4e00\u5c42\u8282\u70b9\uff0c\u628a\u4e0b\u4e00\u5c42\u7684\u67d0\u4e2a\u5b50\u8282\u70b9\u5f53\u4f5c\u662f\u201c\u6839\u201d\u4f20\u8fdb\u51fd\u6570\u91cc\uff0c\u8fd9\u6837\u51fd\u6570\u7684\u64cd\u4f5c\u8303\u56f4\u5c31\u53d8\u6210\u4e86\u67d0\u4e2a\u5b50\u6811\uff1b\u5f53\u8303\u56f4\u9650\u5b9a\u5230\u67d0\u4e2a\u53f6\u5b50\u8282\u70b9\u7684\u7a7a\u4f4d\u65f6\uff0c\u5c31\u662f\u627e\u5230\u4e86\u5e94\u8be5\u63d2\u5165\u7684\u5730\u65b9\uff0c\u5c31\u53ef\u4ee5\u6dfb\u52a0\u65b0\u7684\u8282\u70b9\u3002\u63d2\u5165\u4e4b\u540e\uff0c\u5728\u4e0d\u65ad\u8c03\u6574\u7ea2\u9ed1\u6811\u5e73\u8861\u7684\u8fc7\u7a0b\u4e2d\uff0c\u628a\u8c03\u6574\u4e4b\u540e\u7684\u65b0\u201c\u6839\u201d\u8fd4\u56de\u7ed9\u4e0a\u4e00\u5c42\u9012\u5f52\uff0c\u4e0a\u4e00\u5c42\u9012\u5f52\u5c31\u628a\u8fd9\u4e2a\u65b0\u7684\u201c\u6839\u201d\u4ee3\u66ff\u4f5c\u4e3a\u53c2\u6570\u4f20\u8fdb\u51fd\u6570\u91cc\u7684\u65f6\u5019\u7684\u90a3\u4e2a\u201c\u6839\u201d\uff08\u8fd9\u65b0\u7684\u201c\u6839\u201d\u65e7\u7684\u201c\u6839\u201d\u53ef\u80fd\u4f1a\u662f\u540c\u4e00\u4e2a\u8282\u70b9\uff09\u3002<\/p>\n
\u5b57\u9762\u4e0a\u770b\uff0c\u5c31\u662f\u5148\u7528\u4e8c\u53c9\u641c\u7d22\u6811\u63d2\u5165\u7684\u65b9\u6cd5\u63d2\u5165\uff0c\u7528\u9012\u5f52\uff0c\u4e00\u5c42\u4e00\u5c42\u627e\u5230\u8981\u63d2\u5165\u7684\u4f4d\u7f6e\uff0c\u7136\u540e\u518d\u9012\u5f52\u7684\u56de\u6765\uff0c\u4e00\u5c42\u4e00\u5c42\u8c03\u6574\uff0c\u8981\u8c03\u6574\u7684\u60c5\u51b5\u5c31\u662f\u524d\u9762\u8bf4\u7684\u4e09\u79cd\u60c5\u51b5\uff0c\u8c03\u6574\u65b9\u6cd5\u5c31\u662f\u5355\u65cb\u8f6c\u548c\u53cc\u65cb\u8f6c\uff0c\u4e24\u4e2a\u7ea2\u8272\u5728\u540c\u4e00\u8fb9\u76f8\u540c\u65b9\u5411\u7528\u5355\u65cb\u8f6c\uff0c\u4e24\u4e2a\u7ea2\u8272\u5728\u540c\u4e00\u8fb9\u4f46\u65b9\u5411\u4e0d\u540c\u7528\u53cc\u65cb\u8f6c\u3002\u63d2\u5165\u5b8c\u6210\u540e\u8bb0\u5f97\u8981\u628a\u6574\u68f5\u6811\u7684\u6839\u8282\u70b9\u6807\u8bb0\u4e3a\u9ed1\u8272<\/strong><\/font>\u3002<\/p>\n
\u8fd9\u91cc\u63d2\u5165\u5b8c\u6210\u4e4b\u540e\u8c03\u6574\u7ea2\u9ed1\u6811\u7684\u90e8\u5206\u4ee3\u7801\uff0c\u6ca1\u6709\u68c0\u67e5\u5b50\u8282\u70b9\u662f\u5426\u662f\u7a7a\u7684\u3002\u56e0\u4e3a\u53ef\u4ee5\u786e\u4fdd\u7684\u662f\u201c\u8fd9\u91cc\u7684root\u4e0d\u662f\u7a7a\u201d\uff0c\u5e76\u4e14\u63d2\u5165\u662f\u63d2\u5165\u5230direction\u65b9\u5411\uff0c\u4e5f\u5c31\u662fdirection\u90a3\u4e2a\u65b9\u5411\u4e5f\u4e0d\u4f1a\u662f\u7a7a\u3002\u81f3\u4e8e\u518d\u4e0b\u4e00\u5c42\uff0c\u56e0\u4e3a\u7a7a\u8282\u70b9\u88ab\u5f53\u4f5c\u662f\u9ed1\uff0cIsRed\u8fd9\u4e2a\u51fd\u6570\u7684\u8fd9\u79cd\u5904\u7406\u65b9\u5f0f\u4e5f\u4e0d\u4f1a\u9020\u6210\u7a0b\u5e8f\u51fa\u9519\u3002\u6240\u4ee5\u8fd9\u91cc\u6ca1\u6709\u5224\u65ad\u5b50\u8282\u70b9\u662f\u4e0d\u662f\u7a7a\u7684\u4ee3\u7801\u3002<\/p>\n
\u4e8e\u662f\u63d2\u5165\u64cd\u4f5c\u5230\u8fd9\u91cc\u5c31\u7ed3\u675f\u4e86\u3002\u7b80\u5355\u4f53\u4f1a\u4e00\u4e0b\uff0c\u5c31\u662f\u7ea2\u8272\u8282\u70b9\u662f\u201c\u4f9d\u9644\u201d\u5728\u9ed1\u8272\u8282\u70b9\u4e0a\u3001\u548c\u9ed1\u8272\u8282\u70b9\u4e00\u8d77\u4ee3\u8868\u4e00\u4e2a\u201cB-Tree\u8282\u70b9\u201d\u7684\uff0c\u6240\u4ee5\u63d2\u5165\u7ea2\u8272\u8282\u70b9\u8fd9\u4e00\u79cd\u64cd\u4f5c\uff0c\u5b9e\u9645\u4e0a\u5c31\u662f\u5728\u4e00\u4e2a\u8fd9\u6837\u7684B-Tree\u4e2d\uff0c\u627e\u4e00\u4e2a\u8fd8\u6709\u7a7a\u4f4d\u7684\u8282\u70b9\uff0c\u628a\u6570\u636e\u63d2\u5165\u5230\u8fd9\u4e2a\u7a7a\u4f4d\u4e0a\u7684\u64cd\u4f5c\u3002\u5f53\u5b9e\u5728\u6ca1\u6709\u7a7a\u4f4d\u7684\u65f6\u5019\uff0c\u5c31\u4f1a\u628a\u4e00\u4e2a\u8282\u70b9\u62c6\u6210\u4e24\u4e2a\uff08\u5c31\u662f\u90a3\u4e2a\u53d8\u8272\u64cd\u4f5c\uff09\u6765\u521b\u9020\u7a7a\u4f4d\uff1b\u63d2\u5165\u4ee5\u540e\u5728\u4e8c\u53c9\u6811\u5c42\u9762\u4e0a\u6548\u7387\u4e0d\u591f\u9ad8\uff0c\u5c31\u4f1a\u5728\u8282\u70b9\u5185\u8fdb\u884c\u65cb\u8f6c\u4f7f\u5f97\u5355\u4e2a\u8282\u70b9\u5185\u5e73\u8861\u3002<\/p>\n
\u7136\u540e\u6765\u8bf4\u5220\u9664\u64cd\u4f5c\u3002\u5728\u63d2\u5165\u7684\u65f6\u5019\uff0c\u662f\u63d2\u5165\u4e00\u4e2a\u7ea2\u8272\u8282\u70b9\uff0c\u56e0\u4e3a\u6210\u529f\u63d2\u5165\u4e00\u4e2a\u7ea2\u8272\u8282\u70b9\u76f8\u5f53\u4e8e\u5728B-Tree\u7684\u67d0\u4e2a\u8282\u70b9\u7684\u7a7a\u4f4d\u91cc\u63d2\u5165\u4e86\u4e00\u4e2a\u6570\u636e\uff0c\u8fd9\u6837\u4e0d\u5f71\u54cd\u5c42\u6570\uff1b\u53ea\u5728\u5fc5\u8981\u7684\u65f6\u5019\u624d\u62c6\u8282\u70b9\u518d\u63d2\u5165\u3002\u8fd9\u6837\u7684\u8bdd\uff0c\u5982\u679c\u6211\u5220\u9664\u7684\u65f6\u5019\uff0c\u5220\u6389\u7684\u662f\u4e00\u4e2a\u7ea2\u8272\u7684\u8282\u70b9\uff0c\u90a3\u4e48\u5220\u6389\u4e4b\u524d\u548c\u5220\u6389\u4e4b\u540e\uff0c\u5c31\u80fd\u4e0d\u5bf9\u7ea2\u9ed1\u6811\u7684\u6027\u8d28\u4ea7\u751f\u5f71\u54cd\uff1a\u56e0\u4e3a\u5728B-Tree\u4e0a\u6765\u770b\uff0c\u5220\u9664\u4e00\u4e2a\u7ea2\u8272\u8282\u70b9\u5c31\u76f8\u5f53\u4e8e\u5728\u67d0\u4e2aB-Tree\u7684\u8282\u70b9\u91cc\u5220\u6389\u4e00\u4e2a\u6570\u636e\uff08\u5e76\u4e14\u8fd9\u4e2aB-Tree\u8282\u70b9\u91cc\u6709\u4e0d\u6b62\u4e00\u4e2a\u6570\u636e\uff09\u3002\u50cf\u8fd9\u6837\u7684\u64cd\u4f5c\uff0c\u662f\u4e0d\u4f1a\u5f71\u54cdB-Tree\u7684\u6df1\u5ea6\u7684\uff0c\u540c\u65f6\u4e5f\u4e0d\u53ef\u80fd\u9020\u6210\u201c\u5728\u540c\u4e00\u4e2a\u2018B-Tree\u8282\u70b9\u2019\u5185\u540c\u4e00\u8fb9\u6709\u4e24\u4e2a\u7ea2\u8272\u8282\u70b9\u201d\u7684\u60c5\u51b5\u3002\u4f46\u662f\u5728\u5220\u9664\u7684\u65f6\u5019\uff0c\u53c8\u4e0d\u662f\u603b\u662f\u79fb\u9664\u4e00\u4e2a\u7ea2\u8272\u8282\u70b9\uff0c\u6240\u4ee5\u8fd9\u91cc\u7684\u601d\u8def\u662f\uff0c\u901a\u8fc7\u5404\u79cd\u8c03\u6574\u624b\u6bb5\uff0c\u628a\u8981\u5220\u9664\u7684\u8282\u70b9\u8c03\u6210\u7ea2\u8272\u7684\uff0c\u7136\u540e\u5c31\u53ef\u4ee5\u5b89\u5fc3\u5220\u6389\u4e86<\/strong><\/font>\u3002\u8fd9\u91cc\u8bf4\u7684\u201c\u8c03\u6574\u624b\u6bb5\u201d\uff0c\u548c\u63d2\u5165\u7684\u65f6\u5019\u7c7b\u4f3c\uff0c\u5c31\u662f\u8c03\u6574\u540e\u7ea2\u9ed1\u6811\u4ecd\u7136\u662f\u7ea2\u9ed1\u6811\uff0c\u7ea2\u9ed1\u6811\u7684\u6027\u8d28\u4e0d\u53d7\u5f71\u54cd\u3002<\/p>\n
\u5728\u8fd9\u4e4b\u524d\uff0c\u5148\u8bf4\u4e00\u4e0b\u666e\u901a\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u8282\u70b9\u5220\u9664\u5427\u3002\u4e3a\u4ec0\u4e48\u8fd9\u4e48\u7b80\u5355\u7684\u4e1c\u897f\u8981\u5148\u8bf4\u4e00\u4e0b\u5462\uff01\u56e0\u4e3a\u6211\u5728\u5b66\u4e60\u7ea2\u9ed1\u6811\u4e4b\u524d\u751a\u81f3\u8fde\u666e\u901a\u7684\u4e8c\u53c9\u641c\u7d22\u6811\u8981\u600e\u4e48\u5220\u9664\u8282\u70b9\u90fd\u4e0d\u77e5\u9053\u5416\uff08\u6bb4<\/p>\n
\u5728\u4e8c\u53c9\u641c\u7d22\u6811\u91cc\u8fdb\u884c\u63d2\u5165\u64cd\u4f5c\u7684\u65f6\u5019\uff0c\u603b\u662f\u627e\u4e00\u4e2a\u5408\u9002\u7684\u5730\u65b9\u63d2\u5165\u4e00\u4e2a\u53f6\u5b50\u8282\u70b9\uff1a\u4f60\u6709\u5728\u534a\u8def\u4e0a\u5c31\u627e\u4e2a\u5751\u8e72\u7740\u5417\uff08\u7206\uff09\u8fd8\u4e0d\u90fd\u662f\u8d70\u5230\u5934\u7136\u540e\u5728\u90a3\u4e2a\u5934\u5934\u4e0a\u7c98\u4e2a\u65b0\u8282\u70b9\u3002\u5220\u9664\u53f6\u5b50\u8282\u70b9\u6211\u4e5f\u4f1a\uff0c\u4f1a\u63d2\u5165\u7684\u8bdd\u8111\u74dc\u5b50\u60f3\u60f3\u5c31\u89e3\u51b3\u95ee\u9898\u4e86\u3002\u4f46\u662f\u5982\u679c\u662f\u534a\u4e2d\u95f4\u7ed9\u4f60\u6316\u4e2a\u5751\uff0c\u5982\u679c\u8fd9\u4e2a\u5751\u53ea\u6709\u4e00\u4e2a\u5b50\u8282\u70b9\uff0c\u5de6\u5b50\u8282\u70b9\u6216\u8005\u53f3\u5b50\u8282\u70b9\uff0c\u90a3\u4e48\u76f4\u63a5\u628a\u5b83\u4e22\u5230\u8fd9\u4e2a\u5751\u91cc\u95ee\u9898\u5c31\u5b8c\u7ed3\u4e86\uff0c\u9ebb\u70e6\u5c31\u9ebb\u70e6\u5728\u5b83\u6709\u8fd9\u4e48\u4e00\u79cd\u60c5\u51b5\uff1a\u540c\u65f6\u5b58\u5728\u5de6\u53f3\u4e24\u4e2a\u5b50\u8282\u70b9\u3002\u5bf9\u4e8e\u8fd9\u79cd\u60c5\u51b5\uff0c\u51ed\u501f\u6211\u7684\u8111\u5b50\u4ed4\u7ec6\uff08\u5927\u6982\u6709\u201c\u4ed4\u7ec6\u201d\uff1f\uff09\u60f3\u4e86\u534a\u5929\uff0c\u4e0d\u77e5\u9053\u5e94\u8be5\u600e\u4e48\u529e\u3002\u540e\u6765\u5230\u7f51\u4e0a\u4e00\u641c\uff0c\u53d1\u73b0\u539f\u6765\u5f88\u7b80\u5355\uff0c\u4f60\u5c31\u5230\u5b83\u53f3\u5b50\u6811\u91cc\u627e\u6700\u5c0f\u7684\u4e00\u4e2a\u8282\u70b9\uff0c\u628a\u8fd9\u4e2a\u8282\u70b9\u548c\u4f60\u8981\u5220\u9664\u7684\u8282\u70b9\u4e92\u6362\uff0c\u7136\u540e\u628a\u8fd9\u4e2a\u8282\u70b9\u5220\u6389\u5c31\u597d\u4e86\u3002\u6240\u8c13\u53f3\u5b50\u6811\u91cc\u6700\u5c0f\u7684\u8282\u70b9\uff0c\u5c31\u662f\u5148\u5f80\u53f3\u8d70\uff0c\u7136\u540e\u4e00\u76f4\u4e00\u76f4\u5f80\u5de6\u8d70\u8d70\u5230\u5934\u3002\u65e2\u7136\u201c\u5230\u5934\u201d\u4e86\uff0c\u5c31\u8bf4\u660e\u5b83\u6ca1\u6709\u5de6\u8282\u70b9\u4e86\uff0c\u4e5f\u5c31\u662f\u6ca1\u6709\u6bd4\u5b83\u66f4\u5c0f\u7684\u4e86\uff0c\u50cf\u8fd9\u6837\u7684\u8282\u70b9\u5220\u8d77\u6765\u5c31\u5bb9\u6613\uff0c\u56e0\u4e3a\u5b83\u6ca1\u6709\u5de6\u8282\u70b9\uff0c\u6240\u4ee5\u8981\u4e48\u5df2\u7ecf\u662f\u53f6\u5b50\u8981\u4e48\u53ea\u6709\u4e00\u4e2a\u53f3\u8282\u70b9\uff0c\u5df2\u7ecf\u662f\u53f6\u5b50\u5c31\u76f4\u63a5\u628a\u5b83\u5494\u5693\u4e86\uff0c\u5982\u679c\u6709\u53f3\u8282\u70b9\u90a3\u4e48\u7528\u53f3\u8282\u70b9\u4ee3\u66ff\u5b83\u7684\u4f4d\u7f6e\u5373\u53ef\u3002\u53ef\u4ee5\u8fd9\u6837\u505a\u7684\u539f\u56e0\uff0c\u662f\u56e0\u4e3a\u8fd9\u4e2a\u4e8c\u53c9\u6811\u91cc\u5df2\u7ecf\u4e0d\u5b58\u5728\u6bd4\u8981\u5220\u9664\u7684\u8282\u70b9\u5927\u4f46\u662f\u6bd4\u8981\u4ea4\u6362\u7684\u8282\u70b9\u5c0f\u7684\u8282\u70b9\u4e86\uff1a\u7b2c\u4e00\u6b21\u5f80\u53f3\u8d70\u5c31\u662f\u628a\u8303\u56f4\u9650\u5b9a\u5728\u6bd4\u8981\u5220\u9664\u7684\u8282\u70b9\u5927\uff0c\u7136\u540e\u4e0d\u65ad\u5f80\u5de6\u8d70\u5230\u5934\u5c31\u662f\u5728\u8fd9\u4e2a\u8303\u56f4\u5185\u627e\u4e2a\u6700\u5c0f\u7684\uff0c\u6240\u4ee5\u4e0b\u6b21\u8d70\u5230\u8fd9\u91cc\uff0c\u5982\u679c\u8981\u627e\u6bd4\u8fd9\u4e2a\u5927\u7684\uff0c\u5c31\u5f80\u53f3\u8d70\uff0c\u53f3\u8fb9\u4e0d\u5b58\u5728\u6bd4\u8fd9\u4e2a\u8282\u70b9\u66f4\u5c0f\u7684\uff08\u4ee5\u524d\u6709\u4e2a\u66f4\u5c0f\u7684\uff0c\u73b0\u5728\u548c\u8981\u5220\u9664\u7684\u8282\u70b9\u6570\u636e\u4ea4\u6362\u540e\u5f53\u66ff\u6b7b\u9b3c\u53bb\u4e86\u2026\u2026\uff09\u3002\u5230\u8fd9\u91cc\uff0c\u8981\u600e\u4e48\u5728\u4e8c\u53c9\u641c\u7d22\u6811\u91cc\u9762\u5220\u9664\u4e00\u4e2a\u8282\u70b9\uff0c\u5c31\u5f88\u660e\u767d\u4e86\uff1a\u6ca1\u6709\u6216\u8005\u53ea\u6709\u4e00\u4e2a\u5b50\u8282\u70b9\u7684\uff0c\u8111\u5b50\u60f3\u60f3\u5c31\u77e5\u9053\u600e\u4e48\u505a\u4e86\uff1b\u6709\u4e24\u4e2a\u5b50\u8282\u70b9\u7684\uff0c\u5c31\u627e\u4e2a\u53ea\u6bd4\u5b83\u5927\u4e00\u70b9\u70b9\u7684\u6765\u5f53\u66ff\u6b7b\u9b3c\u2026\u2026<\/p>\n
\u6015\u8bf4\u4e0d\u6e05\u695a\uff0c\u6765\u4e2a\u56fe
\"image\"<\/a>
\u6211\u5c3d\u529b\u4e86\u2026\u2026\uff08\u6276\u989d<\/p>\n
\u524d\u9762\u5df2\u7ecf\u7ecf\u5386\u8fc7\u4e86\u63d2\u5165\u64cd\u4f5c\uff0c\u90a3\u4e48\u4e5f\u5c31\u5e9f\u8bdd\u4e0d\u591a\u8bf4\uff0c\u6765\u8c08\u8c08\u600e\u4e48\u641e\u8fd9\u4e2a\u5220\u9664\u64cd\u4f5c\u3002\u601d\u8def\u662f\u60f3\u529e\u6cd5\u628a\u201c\u5f53\u524d\u7684\u8282\u70b9\u201d\u5f04\u6210\u7ea2\u8272\u7684\uff0c\u5982\u679c\u6b63\u597d\u5f53\u524d\u8282\u70b9\u662f\u8981\u5220\u9664\u7684\u5e76\u4e14\u5e76\u4e0d\u662f\u4e24\u4e2a\u5b50\u6811\u90fd\u6709\uff0c\u90a3\u4e48\u5c31\u53ef\u4ee5\u76f4\u63a5\u5220\u4e86\uff0c\u5982\u679c\u662f\u8981\u5220\u9664\u7684\u8282\u70b9\u5e76\u4e14\u6709\u4e24\u4e2a\u5b50\u6811\uff0c\u90a3\u4e48\u5c31\u5f80\u53f3\uff0c\u7ee7\u7eed\u4e00\u8def\u628a\u8d70\u8fc7\u7684\u8282\u70b9\u8c03\u6210\u7ea2\u8272\uff0c\u76f4\u5230\u627e\u5230\u4f20\u8bf4\u4e2d\u7684\u201c\u66ff\u6b7b\u9b3c\u201d\uff0c\u6b64\u65f6\u201c\u66ff\u6b7b\u9b3c\u201d\u4e5f\u662f\u7ea2\u8272\u7684\u4e86\uff0c\u5c31\u53ef\u4ee5\u53bb\u66ff\u6b7b\u4e86\u2026\u2026\u8fd9\u6837\u8bf4\u5c82\u4e0d\u662f\u4e00\u8def\u4e0a\u4f1a\u6709\u597d\u591a\u7ea2\u8272\u8282\u70b9\u51fa\u6765\uff1f\u5176\u5b9e\u4e0d\u7136\uff0c\u56e0\u4e3a\u4f60\u5728\u5f80\u4e0b\u8d70\u7684\u65f6\u5019\u4e00\u8def\u5728\u8c03\u6574\uff0c\u521a\u521a\u4f60\u8c03\u6210\u7ea2\u8272\u7684\u8282\u70b9\u53d8\u6210\u4e86\u7236\u8282\u70b9\uff0c\u4f60\u628a\u73b0\u5728\u7684\u5f53\u524d\u8282\u70b9\u8c03\u6210\u7ea2\u8272\u7684\u65f6\u5019\u7236\u8282\u70b9\uff08\u524d\u4e00\u8f6e\u7684\u201c\u5f53\u524d\u8282\u70b9\u201d\uff09\u5c31\u53c8\u53d8\u9ed1\u8272\u4e86\uff08\u56e0\u4e3a\u8c03\u6574\u8fc7\u7a0b\u4e2d\u662f\u8981\u4fdd\u6301\u7ea2\u9ed1\u6811\u7684\u6027\u8d28\u7684\uff0c\u800c\u7ea2\u9ed1\u6811\u7684\u6027\u8d28\u5176\u4e2d\u4e00\u4e2a\u5c31\u662f\u7ea2\u8272\u8282\u70b9\u7684\u5b50\u8282\u70b9\u4e0d\u80fd\u662f\u7ea2\u8272\u8282\u70b9\uff09\u3002<\/p>\n
\u548c\u63d2\u5165\u7684\u65f6\u5019\u4e00\u6837\uff0c\u662f\u5bfb\u627e\u8981\u5220\u9664\u7684\u5143\u7d20\uff0c\u8d70\u5230\u4e00\u4e2a\u8282\u70b9\u7684\u65f6\u5019\uff0c\u6709\u8fd9\u4e48\u51e0\u79cd\u60c5\u51b5\uff1a
1\u3001\u8981\u5220\u9664\u7684\u8282\u70b9\u5c31\u662f\u5f53\u524d\u8282\u70b9
2\u3001\u8981\u5220\u9664\u7684\u8282\u70b9\u6bd4\u5f53\u524d\u8282\u70b9\u5c0f
3\u3001\u8981\u5220\u9664\u7684\u8282\u70b9\u6bd4\u5f53\u524d\u8282\u70b9\u5927
\u867d\u7136\u6709\u70b9\u5e9f\u8bdd\uff0c\u4e0d\u8fc7\u786e\u5b9e\u662f\u8fd9\u4e09\u79cd\u60c5\u51b5\u3002\u5982\u679c\u8981\u627e\u7684\u8282\u70b9\u6bd4\u5f53\u524d\u8282\u70b9\u5c0f\uff0c\u90a3\u4e48\u5c31\u5f80\u5de6\u8d70\uff1b\u6bd4\u5f53\u524d\u8282\u70b9\u5927\u90a3\u4e48\u5c31\u5f80\u53f3\u8d70\uff1b\u5982\u679c\u5c31\u662f\u5f53\u524d\u8282\u70b9\uff0c\u770b\u5f53\u524d\u8282\u70b9\u7684\u60c5\u51b5\uff0c\u5982\u679c\u6709\u4e24\u4e2a\u5b50\u6811\uff0c\u5c31\u5f80\u53f3\u8d70\uff08\u4e3a\u4e86\u53bb\u627e\u53f3\u8fb9\u6700\u5de6\u7684\uff0c\u5c31\u662f\u6bd4\u5b83\u5927\u4f46\u662f\u5728\u6bd4\u5b83\u5927\u7684\u91cc\u9762\u662f\u6700\u5c0f\u7684\uff0c\u627e\u5230\u4ee5\u540e\u628a\u6570\u636e\u548c\u8981\u5220\u9664\u7684\u8282\u70b9\u4ea4\u6362\uff09\uff1b\u5982\u679c\u53ea\u6709\u4e00\u4e2a\u5b50\u6811\uff0c\u606d\u559c\uff0c\u56e0\u4e3a\u5728\u987a\u7740\u6811\u884c\u8d70\u7684\u8fc7\u7a0b\u4e2d\uff0c\u5c06\u4f1a\u4f7f\u7528\u5404\u79cd\u65b9\u6cd5\u4fdd\u8bc1\u5f53\u524d\u8282\u70b9\u662f\u7ea2\u8272\u7684\uff0c\u56e0\u4e3a\u5f53\u524d\u8282\u70b9\u5df2\u7ecf\u88ab\u8c03\u6210\u7ea2\u8272\u4e86\uff0c\u4f60\u53ef\u4ee5\u76f4\u63a5\u5494\u5693\u4e86\u2026\u2026<\/p>\n
\u6ca1\u90a3\u4e48\u5bb9\u6613\u8ba9\u4f60\u627e\u5230\u7684\uff0c\u6240\u4ee5\u4e0d\u7ba1\u662f\u4e0a\u9762\u8bf4\u7684\u60c5\u51b52\u8fd8\u662f\u60c5\u51b53\uff0c\u90fd\u8981\u7ee7\u7eed\u5f80\u4e0b\u8d70\u3002\u5f80\u4e0b\u8d70\u7684\u65f6\u5019\uff0c\u5c31\u4f1a\u9047\u4e0a\u9ed1\u8272\u8282\u70b9\u4e86\uff0c\u8fd9\u4e2a\u65f6\u5019\u5c31\u8981\u7528\u201c\u8c03\u6574\u201d\u628a\u5b83\u8c03\u6210\u7ea2\u8272\u8282\u70b9\u3002\u56e0\u4e3a\u4e4b\u524d\u8bf4\u8fc7\uff0c\u6211\u4eec\u201c\u5047\u8bbe\u5df2\u7ecf\u628a\u5f53\u524d\u8282\u70b9\u8c03\u6210\u7ea2\u8272\u201d\u4e86\uff0c\u4e5f\u5c31\u662f\u8bf4\uff0c\u6b64\u65f6\u5f53\u524d\u8282\u70b9\u53ef\u80fd\u662f\u9ed1\u8272\uff0c\u4f46\u662f\u7236\u8282\u70b9\u662f\u521a\u624d\u8c03\u6574\u8fc7\u7684\uff0c\u662f\u7ea2\u8272<\/font><\/strong>\u3002\u501f\u52a9\u8fd9\u4e2a\u5df2\u77e5\u6761\u4ef6\uff0c\u5c31\u80fd\u628a\u5f53\u524d\u8282\u70b9\u8c03\u6210\u7ea2\u8272\u7684\u3002\u800c\u8c03\u6574\u7684\u65b9\u6cd5\uff0c\u5c31\u662f\u5728\u81ea\u5df1\u7684\u5b50\u8282\u70b9\u6216\u8005\u5144\u5f1f\u8282\u70b9\u7684\u5b50\u8282\u70b9\u90a3\u8fb9\u627e\u4e2a\u7ea2\u8272\u7684\u6765\uff0c\u7136\u540e\u628a\u8fd9\u4e2a\u7ea2\u8272\u7684\u7ed9\u5077\u8fc7\u6765<\/strong><\/font>\uff08\u4e0d\u4f1a\u662f\u5144\u5f1f\u8282\u70b9\u7684\uff0c\u56e0\u4e3a\u7236\u8282\u70b9\u662f\u7ea2\u7684\uff0c\u5144\u5f1f\u8282\u70b9\u518d\u662f\u7ea2\u7684\u5c31\u8fdd\u53cd\u7ea2\u9ed1\u6811\u6027\u8d28\u4e86\uff09\u3002\u5373\u4fbf\u8fd9\u6837\uff0c\u4e5f\u6709\u53ef\u80fd\u8fd9\u4e9b\u90fd\u627e\u8fc7\u4e86\u627e\u4e0d\u5230<\/strong><\/font>\uff0c\u5c31\u6bd4\u5982\u4e0b\u56fe\u8fd9\u6837\u3002\u6b64\u65f6\u5c31\u8981\u5229\u7528\u7236\u8282\u70b9\u7684\u7ea2\u8272\u4e86\uff0c\u628a\u4e4b\u524d\u63d2\u5165\u7684\u65f6\u5019\u7528\u7684\u62c6B-Tree\u8282\u70b9\u5927\u6cd5\u53cd\u8fc7\u6765\u7528\uff0c\u53d8\u6210\u5408B-Tree\u8282\u70b9\u5927\u6cd5\uff08\u5176\u5b9e\u5c31\u662f\u8c03\u989c\u8272\uff09\uff1a
\"image\"<\/a>
\u7b80\u76f4\u673a\u667a\u6709\u6ca1\u6709\uff0c\u4eceB-Tree\u5c42\u9762\u4e0a\u770b\uff0c\u8fd9\u4e2a\u5c31\u662f\u5148\u4ece\u4e0a\u9762\u4e00\u5c42\u62a0\u4e00\u4e2a\u6570\u636e\u51fa\u6765\u5355\u72ec\u53d8\u6210\u4e00\u4e2a\u65b0\u7684\u201cB-Tree\u8282\u70b9\u201d\uff08\u6700\u4e0a\u9762\u90a3\u4e2a\u7ea2\u7684\u53d8\u6210\u9ed1\u7684\uff09\uff0c\u7136\u540e\u628a\u4e0b\u9762\u4e00\u5c42\u7684\u4e24\u4e2a\u8282\u70b9\u7ed9\u585e\u8fdb\u8fd9\u4e2a\u201c\u65b0B-Tree\u8282\u70b9\u201d\u91cc\u53bb\uff08\u4e24\u4e2a\u9ed1\u7684\u53d8\u6210\u7ea2\u7684\uff09\uff0c\u5728\u8fd9\u4e2a\u8fc7\u7a0b\u4e2d\uff0c\u53d8\u7ea2\u7684\u4e24\u4e2a\u9ed1\u8282\u70b9\u7684\u5c42\u6b21\u5728B-Tree\u4e2d\u5176\u5b9e\u548c\u7ea2\u7684\u53d8\u6210\u9ed1\u7684\u90a3\u4e2a\u8282\u70b9\u5728B-Tree\u4e2d\u7684\u5c42\u6b21\u76f8\u540c\uff0c\u6240\u4ee5\u8fd9\u6837\u7684\u8c03\u6574\uff0cB-Tree\u7684\u6df1\u5ea6\u4e0d\u53d8\u2026\u2026\u5e76\u4e14\u8c03\u6574\u65f6\u4e5f\u6ca1\u6709\u5f71\u54cd\u7ea2\u9ed1\u6811\u7684\u6027\u8d28\uff0c\u5b8c\u74a7\u3002\u641e\u5b8c\u4ee5\u540e\uff0c\u201c\u5f53\u524d\u8282\u70b9\u201d\u5c31\u53d8\u6210\u7ea2\u7684\u4e86\uff0c\u53ef\u4ee5\u7ee7\u7eed\u4e0b\u4e00\u6b65\u64cd\u4f5c\u4e86\u3002<\/p>\n
\u7136\u540e\u518d\u6765\u8bf4\u8bf4\u627e\u5230\u4e86\u7684\u60c5\u51b5\u3002\u627e\u5230\u4e86\u7684\u8bdd\uff0c\u5b83\u6709\u53ef\u80fd\u5728\u5404\u79cd\u5730\u65b9\uff0c\u6bd4\u5982\u5728\u5f53\u524d\u8282\u70b9\u4e0b\u9762\uff0c\u53c8\u6bd4\u5982\u5728\u5144\u5f1f\u8282\u70b9\u4e0b\u9762\u3002\u8fd9\u4e24\u79cd\u60c5\u51b5\u8981\u5206\u5f00\u5904\u7406\u3002<\/p>\n
\u5148\u6765\u7ea2\u8272\u8282\u70b9\u5728\u5f53\u524d\u8282\u70b9\u4e0b\u9762\u7684\u60c5\u51b5\u3002\u5f53\u524d\u8282\u70b9\u4e0b\u9762\u6709\u5de6\u53f3\u4e24\u4e2a\u5b50\u8282\u70b9\uff0c\u5982\u679c\u4f60\u6b63\u597d\u8981\u5f80\u7ea2\u8272\u8282\u70b9\u90a3\u4e2a\u65b9\u5411\u8d70\uff0c\u4e07\u4e8b\u987a\u5229\u4f60\u53ef\u4ee5\u76f4\u63a5\u8d70\u4e86\uff0c\u4e0d\u7528\u8c03\u6574\uff0c\u56e0\u4e3a\u5f53\u524d\u8282\u70b9\u5df2\u7ecf\u6ca1\u6709\u5229\u7528\u4ef7\u503c\uff0c\u867d\u7136\u4f60\u8d70\u4e0b\u4e00\u6b65\u7684\u65f6\u5019\uff0c\u7236\u8282\u70b9\uff08\u4e5f\u5c31\u662f\u73b0\u5728\u7684\u5f53\u524d\u8282\u70b9\uff09\u4e0d\u662f\u7ea2\u8272\uff0c\u4f46\u662f\u7ea2\u4e0d\u7ea2\u65e0\u6240\u8c13\uff0c\u56e0\u4e3a\u4e0b\u4e00\u6b65\u4f60\u5c06\u8981\u8ba9\u5b83\u7ea2\u7684\u5df2\u7ecf\u7ea2\u4e86\u3002\u5982\u679c\u7ea2\u8272\u8282\u70b9\u548c\u4f60\u8981\u8d70\u7684\u4e0b\u4e00\u6b65\u7684\u65b9\u5411\u662f\u76f8\u80cc\u79bb\u7684\uff0c\u8fd9\u65f6\u8fd8\u662f\u8981\u901a\u8fc7\u8c03\u6574\u628a\u5f53\u524d\u8282\u70b9\u8c03\u6210\u7ea2\u8272\u7684\u3002\u65b9\u6cd5\u662f\u5728\u540c\u4e00\u4e2a\u201cB-Tree\u8282\u70b9\u201d\u5185\u4f5c\u65cb\u8f6c\uff0c\u50cf\u4e0b\u56fe\u8fd9\u6837\uff0c\u65cb\u8f6c\u4e4b\u540e\uff0c\u539f\u6765\u7684\u7ea2\u8272\u8282\u70b9\u8f6c\u5230\u4e86\u5f53\u524d\u8282\u70b9\u6240\u5728\u7684\u4f4d\u7f6e\uff08\u8fd9\u4e2a\u201cB-Tree\u8282\u70b9\u201d\u5185\u65b0\u7684root\uff09\uff0c\u800c\u201c\u5f53\u524d\u8282\u70b9\u201d\u5219\u8f6c\u5230\u4e86\u5b83\u7684\u4e0b\u9762\uff0c\u53d8\u6210\u4e86\u7ea2\u8272\u8282\u70b9\u2190\u53d8\u6210\u4e86\u7ea2\u8272\u8282\u70b9\uff01\u91cd\u70b9\uff01
\"image\"<\/a>
a\u662f\u201c\u5f53\u524d\u8282\u70b9\u201d\uff0c\u5728\u65cb\u8f6c\u4e4b\u540e\u53d8\u6210\u4e86\u7ea2\u8272\u3002\u800c\u4eceB-Tree\u7684\u89d2\u5ea6\u6765\u770b\uff0cd\u3001e\u3001c\u4ecd\u7136\u662fa\u548cb\u6784\u6210\u7684\u201cB-Tree\u8282\u70b9\uff08\u7eff\u8272\u6846\u5185\uff09\u201d\u7684\u5b50\u8282\u70b9\u3002\u8fdb\u884c\u8fd9\u4e00\u6b65\u64cd\u4f5c\u7684\u65f6\u5019\uff0c\u5982\u679c\u4ee3\u7801\u4e2d\u6709\u8bb0\u5f55\u7236\u8282\u70b9\u548c\u5f53\u524d\u8282\u70b9\u5bf9\u4e8e\u7236\u8282\u70b9\u7684\u65b9\u5411\uff0c\u5219\u8981\u8ddf\u7740\u4e00\u8d77\u8c03\u6574<\/strong><\/font>\u3002\u6ca1\u6709\u8fd9\u6837\u8c03\u6574\u7684\u8bdd\uff0c\u7a0b\u5e8f\u5f88\u6709\u53ef\u80fd\u5c31\u6b7b\u5728\u8fd9\u91cc\u4e86\u3002<\/p>\n
\u7136\u540e\u662f\u7ea2\u8272\u8282\u70b9\u5728\u5144\u5f1f\u8282\u70b9\u540d\u4e0b\u7684\u60c5\u51b5\u3002\u8fd9\u79cd\u60c5\u51b5\u7684\u65cb\u8f6c\u7275\u626f\u5230\u7236\u8282\u70b9\uff0c\u5e76\u4e14\u7531\u4e8e\u7236\u8282\u70b9\u662f\u7ea2\u8272\u8282\u70b9\uff0c\u5728\u7406\u89e3\u4e0a\u4f1a\u6bd4\u4e4b\u524d\u7684\u66f4\u52a0\u56f0\u96be\u4e00\u4e9b\u3002\u7ea2\u8272\u8282\u70b9\u5728\u5144\u5f1f\u8282\u70b9\u4e0b\u9762\u4e5f\u6709\u4e24\u79cd\u60c5\u51b5\uff1a\u5728\u5de6\u8fb9\u548c\u5728\u53f3\u8fb9\u3002\u4e3a\u4e86\u63cf\u8ff0\u65b9\u4fbf\uff0c\u5c31\u8bf4\u548c\u5f53\u524d\u8282\u70b9\u540c\u5411\u6216\u8005\u53cd\u5411\u5427\u3002\u548c\u5f53\u524d\u8282\u70b9\u540c\u5411\u6307\u7684\u662f\uff0c\u6bd4\u5982\u5f53\u524d\u8282\u70b9\u662f\u7236\u8282\u70b9\u7684\u5de6\u5b50\u8282\u70b9\uff0c\u90a3\u4e48\u201c\u4e5f\u5728\u5de6\u8fb9\u201d\u5c31\u662f\u540c\u5411\uff1b\u5982\u679c\u5f53\u524d\u8282\u70b9\u662f\u7236\u8282\u70b9\u7684\u53f3\u5b50\u8282\u70b9\uff0c\u90a3\u4e48\u201c\u4e5f\u5728\u53f3\u8fb9\u201d\u5c31\u662f\u540c\u5411\u3002\u4e8e\u662f\u5c31\u6709\u4e86\u7ea2\u8272\u8282\u70b9\u5728\u5144\u5f1f\u8282\u70b9\u4e0b\u9762\u7684\u4f4d\u7f6e\u662f\u548c\u5f53\u524d\u8282\u70b9\u540c\u5411\u548c\u53cd\u5411\u4e24\u79cd\u60c5\u51b5\u3002<\/p>\n
\u548c\u5f53\u524d\u8282\u70b9\u53cd\u5411\u7684\u60c5\u51b5\uff08\u6ce8\u610f\u6b64\u65f6a\u662f\u7236\u8282\u70b9\uff0cc\u624d\u662f\u5f53\u524d\u8282\u70b9<\/strong><\/font>\uff09\uff1a
\"image\"<\/a>
\u6ce8\u610f\u5176\u4e2d\u7eff\u8272\u7bad\u5934\u6240\u4ee3\u8868\u7684\u201c\u76f8\u53cd\u201d\u3002\u5728\u8fd9\u4e2a\u56fe\u4e2d\uff0cc\u4ee3\u8868\u5f53\u524d\u8282\u70b9\uff0ca\u662f\u5f53\u524d\u8282\u70b9\u7684\u7236\u8282\u70b9\uff0cb\u5219\u662f\u5b83\u7684\u5144\u5f1f\u8282\u70b9\uff0c\u56fe\u4e2d\u571f\u9ec4\u8272\u5708\u8d77\u6765\u7684\u90e8\u5206\u662f\u5728B-Tree\u4e2d\u5c5e\u4e8e\u540c\u4e00\u4e2a\u201cB-Tree\u8282\u70b9\u201d\u7684\u90e8\u5206\u3002\u8fd9\u79cd\u60c5\u51b5\u4e0b\uff0c\u7236\u8282\u70b9\u662f\u5c5e\u4e8e\u5f53\u524d\u8282\u70b9\u6240\u5728\u7684\u201cB-Tree\u8282\u70b9\u201d\u7684\u4e0a\u4e00\u5c42\uff0c\u800c\u6b64\u65f6\u5144\u5f1f\u201cB-Tree\u8282\u70b9\u201d\uff08\u7531b\u3001d\u7ec4\u6210\uff09\u6709\u8d85\u8fc7\u4e00\u4e2a\u7684\u6570\u636e\uff08\u4e24\u4e2a\u7ea2\u9ed1\u6811\u8282\u70b9\uff09\uff0c\u8fd9\u6837\u5c31\u53ef\u4ee5\u4ece\u4e2d\u62bd\u53d6\u4e00\u4e2a\u6570\u636e\u51fa\u6765\uff0c\u585e\u5165\u4e0a\u4e00\u5c42\u8282\u70b9\uff08b\u88ab\u585e\u5165\u4e0a\u4e00\u5c42\uff09\uff0c\u7136\u540e\u4ece\u4e0a\u4e00\u5c42\u4e2d\u628ab\u62ff\u51fa\u6765\uff0c\u653e\u5165\u5f53\u524d\u201cB-Tree\u8282\u70b9\u201d\uff08\u5c31\u662fc\uff09\uff0c\u8fd9\u6837\u201c\u5f53\u524dB-Tree\u201d\u8282\u70b9\u5c31\u6709\u4e86\u8d85\u8fc7\u4e00\u4e2a\u7684\u6570\u636e\uff08\u6709\u4e86\u4e24\u4e2a\u7ea2\u9ed1\u6811\u8282\u70b9\uff09\uff0c\u5e76\u4e14c\u4e0d\u5904\u4e8e\u8fd9\u4e2a\u5f53\u524d\u201cB-Tree\u8282\u70b9\u201d\u7684\u6839\u90e8\uff0c\u5b83\u5c31\u5982\u613f\u4ee5\u507f\u5730\u53d8\u6210\u4e86\u7ea2\u8272\u2026\u2026<\/p>\n
\u4ee5\u4e0a\u8bf4\u4e86\u90a3\u4e48\u591a\uff0c\u5176\u5b9e\u5c31\u662f\u4e00\u4e2a\u65cb\u8f6c\u64cd\u4f5c\u3002\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u65cb\u8f6c\u64cd\u4f5c\u662f\u4e0d\u4f1a\u7834\u574f\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u6027\u8d28\u7684\uff08\u5c31\u662f\u5728\u67d0\u4e2a\u8282\u70b9\u7684\u5de6\u8fb9\u7684\u6240\u6709\u76f4\u63a5\u6216\u95f4\u63a5\u7684\u5b50\u8282\u70b9\uff0c\u90fd\u8981\u6bd4\u8fd9\u4e2a\u8282\u70b9\u5c0f\uff1b\u53f3\u8fb9\u5c31\u662f\u90fd\u6bd4\u8fd9\u4e2a\u8282\u70b9\u5927\uff09\u3002\u4f46\u662f\u56e0\u4e3a\u666e\u901a\u7684\u4e8c\u53c9\u641c\u7d22\u6811\u662f\u6ca1\u6709\u989c\u8272\u7684\u6982\u5ff5\u7684\uff0c\u6240\u4ee5\u5230\u4e86\u7ea2\u9ed1\u6811\u4e0a\u9762\uff0c\u5c31\u9700\u8981\u9075\u5faa\u5b83\u6240\u4ee3\u8868\u7684B-Tree\u7684\u64cd\u4f5c\u5b88\u5219\uff0c\u597d\u597d\u5730\u8c03\u6574\u989c\u8272\u3002<\/p>\n
\u7136\u540e\u8fd8\u6709\u6700\u540e\u4e00\u79cd\u60c5\u51b5\uff1a\u548c\u5f53\u524d\u8282\u70b9\u540c\u5411\uff08\u6ce8\u610f\u6b64\u65f6a\u662f\u7236\u8282\u70b9\uff0cc\u624d\u662f\u5f53\u524d\u8282\u70b9<\/font><\/strong>\uff09
\"image\"<\/a>
\u6ce8\u610f\u5176\u4e2d\u7eff\u8272\u7684\u7bad\u5934\uff0c\u8fd9\u4e2a\u7bad\u5934\u5c31\u662f\u6240\u8c13\u7684\u201c\u548c\u5f53\u524d\u8282\u70b9\u540c\u5411\u201d\u3002\u6b64\u65f6\u5982\u679c\u5728\u201cB-Tree\u7684\u5144\u5f1f\u8282\u70b9\u201d\uff08\u5c31\u662fbe\u7ec4\u6210\u7684\u8282\u70b9\uff09\u5185\u90e8\u8fdb\u884c\u65cb\u8f6c\uff0c\u5c06\u539f\u6765\u7ea2\u8272\u8282\u70b9\u90a3\u4e2ae\u8f6c\u4e3a\u8fd9\u4e2a\u201cB-Tree\u8282\u70b9\u201d\u5185\u90e8\u7684\u6839\u8282\u70b9\uff0c\u90a3\u4e48\u539f\u6765\u7684\u6839\u8282\u70b9\u5c31\u4f1a\u8dd1\u5230\u53e6\u4e00\u8fb9\u53bb\uff0c\u5e76\u4e14\u53d8\u4e3a\u7ea2\u8272\uff0c\u2026\u2026\u5f88\u597d\uff0c\u53d8\u6210\u4e0a\u9762\u90a3\u79cd\u201c\u548c\u5f53\u524d\u8282\u70b9\u53cd\u5411\u201d\u7684\u60c5\u51b5\u4e86\uff0c\u4e8e\u662f\u5c31\u7528\u524d\u9762\u90a3\u79cd\u5904\u7406\u65b9\u5f0f\u8fdb\u884c\u65cb\u8f6c\uff0c\u5f53\u524d\u8282\u70b9\u5c31\u53d8\u7ea2\u4e86\u3002
\"image\"<\/a>
\u55ef\u6ca1\u9519\uff0c\u5176\u5b9e\u8fd8\u4e0d\u5c31\u662f\u53cc\u65cb\u2026\u2026\u2026\u2026<\/p>\n
\u521a\u624d\u4e00\u76f4\u5728\u8bf4\u5144\u5f1f\u8282\u70b9\u5144\u5f1f\u8282\u70b9\u7684\uff0c\u4f46\u662f\u6709\u6ca1\u6709\u8981\u627e\u5144\u5f1f\u8282\u70b9\u7684\u65f6\u5019\uff0c\u5144\u5f1f\u8282\u70b9\u4e0d\u5b58\u5728\u5462\uff1f\u5176\u5b9e\u662f\u4e0d\u4f1a\u7684\u3002\u56e0\u4e3a\u627e\u7ea2\u8272\u8282\u70b9\uff0c\u662f\u9996\u5148\u4ece\u81ea\u5df1\u8fd9\u91cc\u5f00\u59cb\u627e\u7684\uff0c\u53ea\u6709\u81ea\u5df1\u8fd9\u91cc\u627e\u4e0d\u5230\u7684\u65f6\u5019\u624d\u4f1a\u5f00\u59cb\u53bb\u8003\u8651\u5144\u5f1f\u8282\u70b9\u3002\u800c\u201c\u627e\u4e0d\u5230\u201d\u4e5f\u5c31\u610f\u5473\u7740\uff0c\u81ea\u5df1\u7684\u4e24\u4e2a\u5b50\u8282\u70b9\u90fd\u662f\u9ed1\u8272\u7684\u4e86\uff0c\u6839\u636e\u7ea2\u9ed1\u6811\u7684\u6027\u8d28\uff0c\u5f80\u81ea\u5df1\u8fd9\u91cc\u8d70\u6709\u4e24\u5c42\u9ed1\u8272\u8282\u70b9\uff0c\u90a3\u4e48\u5f80\u5144\u5f1f\u90a3\u8fb9\u8d70\u4e5f\u8981\u6709\u4e24\u5c42\u5144\u5f1f\u8282\u70b9\u624d\u884c\u2026\u2026\u5982\u679c\u6ca1\u6709\u5144\u5f1f\u8282\u70b9\uff0c\u90a3\u4e48\u5c31\u4e0d\u5b58\u5728\u8fd9\u201c\u4e24\u5c42\u201d\u4e86\u3002<\/p>\n
\u5220\u9664\u64cd\u4f5c\u53ea\u6709\u8fd9\u4e48\u51e0\u79cd\u60c5\u51b5\uff0c\u4f46\u662f\u521a\u624d\u8fd9\u4e9b\u5220\u9664\u64cd\u4f5c\u7684\u524d\u63d0\uff0c\u90fd\u662f\u201c\u7236\u8282\u70b9\u662f\u7ea2\u8272\u8282\u70b9\u201d\u3002\u4f46\u662f\u5728\u64cd\u4f5c\u8fc7\u7a0b\u4e2d\uff0c\u6700\u521d\u662f\u4ece\u6839\u8282\u70b9\u5f00\u59cb\u7684\uff0c\u800c\u6839\u8282\u70b9\u4e00\u5b9a\u662f\u9ed1\u8272\u3002\u4e8e\u662f\u5c31\u8981\u8003\u8651\u4e00\u4e0b\u8fd9\u4e2a\u9ed1\u8272\u8be5\u5982\u4f55\u5904\u7406\u3002\u5bf9\u4e8e\u90a3\u79cd\u8981\u53d8\u8272\u7684\u60c5\u51b5\uff0c\u5f53\u524d\u8282\u70b9\u4e3a\u6839\u8282\u70b9\uff0c\u4e0b\u9762\u4e24\u4e2a\u5b50\u8282\u70b9\u90fd\u662f\u9ed1\u8272\uff0c\u53ef\u4ee5\u5148\u628a\u6839\u8282\u70b9\u8bbe\u7f6e\u4e3a\u7ea2\u8272\uff0c\u8fd9\u6837\u5982\u679c\u9047\u4e0a\u6839\u8282\u70b9\u5f00\u59cb\u4e24\u5c42\u90fd\u662f\u5168\u9ed1\uff0c\u5c31\u53ef\u4ee5\u628a\u6839\u8282\u70b9\u5f04\u9ed1\u7136\u540e\u4e24\u4e2a\u53f6\u5b50\u5f04\u7ea2\u4e86\u3002\u800c\u5bf9\u4e8e\u5176\u4ed6\u7684\u60c5\u51b5\uff0c\u5f53\u524d\u8282\u70b9\u662f\u6839\u8282\u70b9\u7684\u65f6\u5019\uff0c\u5de6\u53f3\u5b50\u8282\u70b9\u603b\u6709\u4e00\u4e2a\u662f\u7ea2\u7684\uff0c\u90a3\u4e48\u5f80\u4e0b\u8d70\u4e86\u4e00\u6b65\u4ee5\u540e\uff0c\u5982\u679c\u6b63\u597d\u8d70\u5230\u9ed1\u8272\u8282\u70b9\uff0c\u90a3\u4e48\u5c31\u6709\u201c\u5144\u5f1f\u8282\u70b9\u662f\u7ea2\u8272\u8282\u70b9\u201d\u8fd9\u4e2a\u6761\u4ef6\uff0c\u6309\u7167\u89c4\u5219\u5904\u7406\u5c31\u884c\u3002\u6709\u53ef\u80fd\u4f1a\u95ee\uff0c\u5982\u679c\u8981\u5220\u9664\u6839\u8282\u70b9\u7684\u8bdd\u600e\u4e48\u529e\u5462\uff0c\u6839\u8282\u70b9\u662f\u9ed1\u8272\u554a\uff0c\u4f60\u53c8\u4e0d\u8c03\u5b83\u4e3a\u7ea2\u8272\u3002\u55ef\uff0c\u5176\u5b9e\u6ca1\u6709\u8fd9\u4e2a\u95ee\u9898\u7684\uff0c\u56e0\u4e3a\u6700\u540e\u79fb\u9664\u7684\u603b\u662f\u67d0\u4e2a\u6700\u4e0b\u9762\u7684\u8282\u70b9\uff0c\u5982\u679c\u5230\u4e86\u8981\u79fb\u9664\u6839\u8282\u70b9\uff0c\u90a3\u4e48\u8fd9\u4e2a\u65f6\u5019\u4e5f\u5c31\u662f\u8bf4\u6839\u8282\u70b9\u53ea\u6709\u4e00\u4e2a\u5b50\u8282\u70b9\u4e86\u2014\u2014\u7ba1\u5b83\u662f\u9ed1\u662f\u767d\uff0c\u53cd\u6b63\u6839\u8282\u70b9\u6ca1\u6709\u201c\u4e0a\u5c42\u201d\u4e86\uff0c\u5c31\u7b97\u79fb\u9664\u9ed1\u8272\u8282\u70b9\uff0c\u4e5f\u8fdd\u53cd\u7ea2\u9ed1\u6811\u7684\u6027\u8d28\u3001\u5931\u53bb\u201cB-Tree\u201d\u7684\u5e73\u8861\u3002<\/p>\n
\u4e8e\u662f\u5230\u8fd9\u91cc\uff0c\u5220\u9664\u64cd\u4f5c\u4e5f\u7ed3\u675f\u4e86\u3002\u4ed4\u7ec6\u5206\u6790\u5220\u9664\u64cd\u4f5c\uff0c\u4f1a\u53d1\u73b0\u548c\u63d2\u5165\u64cd\u4f5c\u6b63\u597d\u76f8\u53cd\uff1a\u63d2\u5165\u64cd\u4f5c\u662f\u5148\u5728\u53f6\u5b50\u5904\u63d2\u5165\u8282\u70b9\uff0c\u7136\u540e\u4e00\u5c42\u5c42\u8c03\u4e0a\u6765\u6700\u540e\u8c03\u5230\u6839\u90e8\uff1b\u800c\u5220\u9664\u64cd\u4f5c\u662f\u4e00\u5c42\u5c42\u8c03\u4e0b\u6765\uff0c\u6700\u540e\u5230\u4e86\u53ea\u6709\u4e00\u4e2a\u5b50\u8282\u70b9\u6216\u8005\u6ca1\u6709\u5b50\u8282\u70b9\u7684\u8282\u70b9\u53d8\u6210\u7ea2\u8272\uff0c\u4e4b\u540e\u628a\u8fd9\u4e2a\u7ea2\u8272\u5e72\u6389\u3002\u5e72\u6389\u4ee5\u540e\uff0c\u6ca1\u6709\u5176\u4ed6\u4e1c\u897f\u8981\u8c03\u6574\u4e86\uff0c\u6240\u4ee5\u53ef\u4ee5\u4e0d\u9700\u8981\u9012\u5f52\uff0c\u7528\u4e00\u4e2a\u5faa\u73af\uff0c\u4e00\u5c42\u5c42\u5f80\u4e0b\u3002\u5168\u90e8\u641e\u5b8c\u4ee5\u540e\uff0c\u548c\u63d2\u5165\u4e00\u6837\uff0c\u628a\u6839\u8282\u70b9\u6d82\u6210\u9ed1\u8272\u3002<\/p>\n
\u8fd9\u91cc\u9700\u8981\u6ce8\u610f\u7684\u6709\u8fd9\u4e48\u51e0\u4e2a\u65b9\u9762\uff1a
1\u3001\u53d8\u6362\u7684\u8fc7\u7a0b\u4e2d\uff0c\u6700\u9ad8\u53ef\u80fd\u6d89\u53ca\u5230\u7236\u8282\u70b9\u7684\u65cb\u8f6c\uff0c\u8fd9\u6837\u7684\u8bdd\uff0c\u5c31\u5fc5\u987b\u4fdd\u5b58\u7236\u8282\u70b9\u7684\u7236\u8282\u70b9\uff0c\u8fd9\u6837\u624d\u80fd\u5728\u7236\u8282\u70b9\u65cb\u8f6c\u4ee5\u540e\uff0c\u4e0a\u4e00\u5c42\u4ecd\u7136\u80fd\u7ee7\u7eed\u6b63\u786e\u6307\u5411\u7236\u8282\u70b9
2\u3001\u6839\u8282\u70b9\u6ca1\u6709\u7236\u8282\u70b9\uff0c\u5982\u679c\u6839\u8282\u70b9\u65cb\u8f6c\uff0c\u90a3\u4e48\u6574\u4e2a\u6811\u7684\u6839\u5c31\u53d8\u4e86\u3002\u8fd9\u91cc\u53ef\u4ee5\u7528\u4e00\u4e2a\u6280\u5de7\uff1a\u521b\u5efa\u4e00\u4e2a\u5047\u7684\u201c\u6839\u8282\u70b9\u7684\u7236\u8282\u70b9\u201d\uff0c\u628a\u6839\u8282\u70b9\u5b89\u5728\u4e0a\u9762\uff0c\u6700\u540e\u641e\u5b8c\u4e86\u518d\u628a\u6839\u8282\u70b9\u4ece\u4e0a\u9762\u5378\u4e0b\u6765\uff0c\u514d\u53bb\u5bf9\u6839\u8282\u70b9\u8fdb\u884c\u7279\u522b\u5904\u7406\u7684\u9ebb\u70e6\u3002
3\u3001\u8981\u4fdd\u5b58\u627e\u5230\u7684\u6570\u636e\u7684\u8282\u70b9\uff0c\u56e0\u4e3a\u5982\u679c\u8fd9\u4e2a\u8282\u70b9\u6709\u4e24\u4e2a\u5b50\u8282\u70b9\uff0c\u90a3\u4e48\u8981\u627e\u201c\u6574\u68f5\u6811\u91cc\u6bd4\u5b83\u5927\u4f46\u662f\u5374\u53c8\u6700\u63a5\u8fd1\u5b83\u201d\u7684\u8282\u70b9\u6765\u8fdb\u884c\u6570\u636e\u4ea4\u6362\u3002<\/p>\n
\u4e3a\u4e86\u66f4\u65b9\u4fbf\u8bf4\u660e\uff0c\u753b\u4e2a\u793a\u610f\u56fe\u8bf4\u660e\u6700\u521d\u7684\u65f6\u5019\u662f\u4ec0\u4e48\u60c5\u51b5\uff1a
\"image\"<\/a>
\u6811\u6839\u5728\u5de6\u8fb9\u6216\u8005\u5728\u53f3\u8fb9\u5176\u5b9e\u6ca1\u6709\u5f71\u54cd\u7684\u2026\u2026\u8d77\u59cb\u7684\u65f6\u5019\uff0c\u7956\u7236\u8282\u70b9\uff08grandparent\uff09\u662f\u6307\u5411NULL\uff0c\u56e0\u4e3a\u5728\u6811\u6839\u662f\u5f53\u524d\u8282\u70b9\u7684\u65f6\u5019\uff0c\u662f\u7528\u4e0d\u5230\u7956\u7236\u8282\u70b9\u7684\uff1a\u56e0\u4e3a\u6811\u6839\u6ca1\u6709\u5144\u5f1f\u8282\u70b9\u3002\u6240\u4ee5\u7a0b\u5e8f\u4e0d\u4f1a\u51fa\u9519\u3002\u5982\u679c\u6811\u6839\u7684\u4e24\u4e2a\u5b50\u8282\u70b9\u662f\u9ed1\u7684\uff0c\u90a3\u4e48\u53ef\u4ee5\u5148\u628a\u6811\u6839\u53d8\u7ea2\uff0c\u8fd9\u6837\u5728\u6700\u521d\u5224\u65ad\u7684\u65f6\u5019\u5c31\u4e0d\u4f1a\u56e0\u4e3a\u6811\u6839\u662f\u9ed1\u7684\u3001\u8981\u628a\u6811\u6839\u53d8\u7ea2\u800c\u53bb\u8e6d\u7236\u8282\u70b9\u6216\u8005\u5144\u5f1f\u8282\u70b9\u7684\u9762\u5b50\u4e86\u3002\u90a3\u4e48\u5c31\u53ef\u4ee5\u5f00\u59cb\u5199\u4ee3\u7801\u4e86\u3002<\/p>\n
template<class T>\nNode<T>* Delete(Node<T> *root, const T &val)\n{\n    Node<T> fakeParent = Node<T>();\n    fakeParent.right = root;\n    \n    Node<T> *found = 0, *foundParent = 0;\n    Node<T> *grandparent = 0, *parent = &fakeParent, *current = root;\n    Node<T> *Node<T>::*grand2parent, *Node<T>::*parent2current = &Node<T>::right, *Node<T>::*parent2found, *Node<T>::*current2next, *Node<T>::*current2other;\n    \n    if (!root->left->IsRed() && !root->right->IsRed())\n        root->isRed = true;\n    \n    while(current != 0) { \n        if (current->data <= val) { \/\/\u76f8\u7b49\u7684\u65f6\u5019\u5f80\u53f3\u8d70\uff0c\u53cd\u6b63\u4e4b\u540e\u5c31\u4e00\u5b9a\u662f\u4e00\u76f4\u5411\u5de6\u4e86\uff0c\u6bd5\u7adf\u8981\u627e\u7684\u6570\u636e\u5c0f\n            current2next = &Node<T>::right;\n            current2other = &Node<T>::left;\n        } else {\n            current2next = &Node<T>::left;\n            current2other = &Node<T>::right;\n        }\n        \n        if (!current->IsRed()) {\n            if (!(current->*current2next)->IsRed()) {\n                if ((current->*current2other)->IsRed()) {\n                    \/\/\u76ee\u6807\u8282\u70b9\u4e0d\u662f\u7ea2\u7684\u4f46\u662f\u76ee\u6807\u7ed3\u70b9\u7684\u5144\u5f1f\u8282\u70b9\u662f\u7ea2\u7684\uff0c\u90a3\u4e48\u81ea\u5df1\u8f6c\u4e00\u4e0b\uff0c\u628a\u81ea\u5df1\u53d8\u7ea2\n                    current->isRed = true;\n                    (current->*current2other)->isRed = false;\n                    parent->*parent2current = SingleTurn(current, current2other);\n                    parent = parent->*parent2current;\n                    parent2current = current2next;\n                } else {\n                    \/\/\u5230\u8fd9\u91cc\uff0c\u5f53\u524d\u8282\u70b9\u7684\u4e24\u4e2a\u5b50\u8282\u70b9\u90fd\u662f\u9ed1\u7684\u4e86\n                    Node<T> *Node<T>::*parent2sib = GetTheOther(parent2current);\n                    Node<T> *sib = parent->*parent2sib;\n                    if ((sib->*parent2current)->IsRed()) {\n                        \/\/\u5144\u5f1f\u8282\u70b9\u4e0b\uff0c\u65b9\u5411\u548c\u5f53\u524d\u8282\u70b9\u76f8\u540c\u7684\u5b50\u8282\u70b9\u662f\u7ea2\u7684\n                        parent->isRed = false;\n                        current->isRed = true;\n                        grandparent->*grand2parent = DoubleTurn(parent, parent2sib);\n                    } else if ((sib->*parent2sib)->IsRed()) {\n                        \/\/\u5144\u5f1f\u8282\u70b9\u4e0b\uff0c\u65b9\u5411\u548c\u5f53\u524d\u8282\u70b9\u76f8\u53cd\u7684\u5b50\u8282\u70b9\u662f\u7ea2\u7684\n                        sib->isRed = true;\n                        parent->isRed = false;\n                        (sib->*parent2sib)->isRed = false;\n                        current->isRed = true;\n                        grandparent->*grand2parent = SingleTurn(parent, parent2sib);\n                    } else {\n                        \/\/\u5144\u5f1f\u8282\u70b9\u4e0b\u4e5f\u662f\u4e24\u4e2a\u90fd\u9ed1\u7684\n                        parent->isRed = false;\n                        sib->isRed = true;\n                        current->isRed = true;\n                    }\n                }\n            }\n        }\n\n        if (current->data == val) {\n            found = current;\n            foundParent = parent;\n            parent2found = parent2current;\n        }\n        \n        grandparent = parent;\n        parent = current;\n        current = current->*current2next;\n\n        grand2parent = parent2current;\n        parent2current = current2next;\n    }\n    \n    \/\/\u5230\u8fd9\u91cc\uff0ccurrent\u662f\u7a7a\u7684\uff0c\u5c31\u662f\u8d70\u5230\u5934\u4e86\uff0cparent\u662f\u6700\u540e\u4e00\u4e2a\u8282\u70b9\n    \/\/\u5982\u679cparent\u4e0d\u662ffound\uff0c\u90a3\u4e48\u628aparent\u548cfound\u4ea4\u6362\n    \/\/\u56e0\u4e3aparent\u53ea\u6709\u4e00\u4e2a\u5b50\u6811\u6216\u8005\u6ca1\u6709\u5b50\u6811\u4e86\uff0c\u6240\u4ee5\u4ea4\u6362\u540e\u53ef\u4ee5\u76f4\u63a5\u5220\u6389\n    if (found != 0) {\n        if (parent != found)\n            std::swap(parent->data, found->data);\n        \n        if (parent->left == 0)\n            grandparent->*grand2parent = parent->right;\n        else\n            grandparent->*grand2parent = parent->left;\n        \n        delete parent;\n    }\n    \n    fakeParent.right->isRed = false;\n    \n    return fakeParent.right;\n}<\/pre>\n
\u8fd9\u4ee3\u7801\u770b\u7740\u597d\u957f\u597d\u6076\u5fc3\uff0c\u786e\u5b9e\u6211\u4e5f\u89c9\u5f97\u597d\u957f\uff0c\u4f46\u662f\u7531\u4e8e\u786e\u5b9e\u4f1a\u6709\u90a3\u4e48\u591a\u949f\u60c5\u51b5\u8981\u5904\u7406\uff0c\u5c06\u5c31\u7740\u770b\u5427\u2026\u2026 <\/p>\n
\u6211\u81ea\u5df1\u5199\u8fd9\u4e2a\u4ee3\u7801\u7684\u65f6\u5019\uff0c\u8c03\u8bd5\u8fc7\u7a0b\u4e2d\u88ab\u5751\u4e86\u597d\u51e0\u6b21\uff0c\u6211\u5728\u8fd9\u91cc\u5c31\u5217\u51fa\u51e0\u4e2a\u8981\u6ce8\u610f\u7684\u5730\u65b9\u5427\uff1a
1\u3001\u5904\u7406\u5144\u5f1f\u8282\u70b9\u662f\u7ea2\u8272\u7684\u60c5\u51b5\u7684\u65f6\u5019\uff0c\u65cb\u8f6c\u5f53\u524d\u8282\u70b9\u4e4b\u540e\u4e00\u5b9a\u8981\u8bb0\u5f97\u66f4\u65b0\u8bb0\u5f55\u4e0b\u6765\u7684\u7236\u8282\u70b9\u548c\u5f53\u524d\u8282\u70b9\u5728\u7236\u8282\u70b9\u4e0b\u7684\u4f4d\u7f6e\u3002\u8fd9\u4e24\u4e2a\u53d8\u91cf\u6ca1\u66f4\u65b0\u7684\u8bdd\uff0c\u4e0b\u9762\u4f1a\u6b7b\u5f97\u633a\u60e8\u7684
2\u3001\u51e0\u4e2a\u65cb\u8f6c\u8fc7\u7a0b\u6709\u70b9\u590d\u6742\uff0c\u6ce8\u610f\u5bf9\u7740\u56fe\u66f4\u65b0\u8282\u70b9\u7684\u989c\u8272\u3002\u66f4\u65b0\u989c\u8272\u5f88\u91cd\u8981\uff0c\u989c\u8272\u4f1a\u5f71\u54cd\u5404\u79cd\u8c03\u6574\u8fc7\u7a0b\u4e2d\u5bf9\u7ea2\u9ed1\u6811\u6027\u8d28\u7684\u4fdd\u6301\uff0c\u4ee5\u53ca\u4f1a\u5f71\u54cd\u5982\u4f55\u8c03\u6574\u3002\u7279\u522b\u662f\u7ea2\u8272\u8282\u70b9\u5728\u5144\u5f1f\u8282\u70b9\u4e0b\u9762\u7684\u90a3\u4e24\u4e2a\u60c5\u51b5\uff0c\u81f3\u5c11\u6211\u662f\u683d\u5728\u989c\u8272\u8c03\u9519\u4e0a\u4e86\uff1a\u56e0\u4e3a\u91cc\u9762\u5c3d\u662f\u4e00\u4e9b\u4ec0\u4e48\u201c\u540c\u5411\u201d\u201c\u53cd\u5411\u201d\u7684
3\u3001\u5f53\u6d89\u53ca\u5230\u8282\u70b9\u65cb\u8f6c\u7684\u65f6\u5019\uff0c\u4e00\u5b9a\u8981\u66f4\u65b0\u5230\u5f62\u5982\u201cxxx->xxxx\u201d\u8fd9\u6837\u7684\u5730\u65b9\uff0c\u6bd4\u5982\u65cb\u8f6c\u4e86\u7236\u8282\u70b9\uff0c\u5c31\u8981\u628a\u65cb\u8f6c\u540e\u7684\u6839\u8282\u70b9\u66f4\u65b0\u5230grandparent->*grand2parent\u4e0a\u9762\u53bb\uff0c\u5982\u679c\u53ea\u66f4\u65b0\u4e86parent\u8fd9\u4e2a\u53d8\u91cf\uff0c\u90a3\u4e48grandparent\u5230parent\u7684\u94fe\u63a5\u5c31\u65ad\u6389\u6216\u8005\u8bf4\u4e0d\u6b63\u786e\u4e86\u3002\u8fd9\u5c31\u597d\u50cf\u4f60\u5199\u4e86\u4e2aswap(int, int)\u7684\u51fd\u6570\u4e0d\u80fd\u83b7\u5f97\u9884\u671f\u6548\u679c\uff0c\u8981swap(int&, int&)\u624d\u80fd\u83b7\u5f97\u9884\u671f\u6548\u679c\u662f\u7c7b\u4f3c\u7684\u9053\u7406\u3002
4\u3001\u6700\u540e\u4ea4\u6362\u6570\u636e\u7684\u65f6\u5019\uff0c\u5982\u679c\u6ca1\u6709\u8db3\u591f\u7684\u81ea\u4fe1\uff0c\u8bf7\u4e0d\u8981\u53bb\u4ea4\u6362\u8282\u70b9\uff01\u4ea4\u6362\u4e8c\u53c9\u6811\u7684\u4e24\u4e2a\u8282\u70b9\u6ca1\u6709\u6211\u60f3\u8c61\u4e2d\u7684\u90a3\u4e48\u7b80\u5355\uff0c\u6bd4\u5982\u4f60\u9047\u4e0a\u7236\u8282\u70b9\u548c\u5b83\u7684\u5b50\u8282\u70b9\u4ea4\u6362\u7684\u65f6\u5019\u2026\u2026<\/p>\n
\u91cc\u9762\u7528\u7684\u7684\u53d8\u91cf\uff0c\u5728\u56fe\u4e0a\u7684\u8bdd\u5927\u6982\u662f\u8fd9\u4e2a\u610f\u601d
\"image\"<\/a>
\u5176\u4e2d\u4e00\u4e9b\u4ee3\u8868\u8282\u70b9\uff0c\u800c\u5728\u8fde\u63a5\u7ebf\u4e0a\u9762\u7684\u4ee3\u8868\u201c\u65b9\u5411\u201d\uff0c\u5b83\u5e76\u4e0d\u5c5e\u4e8e\u67d0\u4e2a\u6216\u67d0\u4e24\u4e2a\u7279\u5b9a\u7684\u8282\u70b9\uff0c\u5b83\u53ea\u662f\u4ee3\u8868\u65b9\u5411\uff1a\u5411\u5de6\u6216\u8005\u5411\u53f3\uff0c\u4efb\u4f55\u8282\u70b9\u90fd\u53ef\u4ee5\u7528\u8fd9\u6837\u7684\u65b9\u5411\u6765\u8fdb\u884c\u5bfc\u822a\u3002<\/p>\n
\u4ee3\u7801\u5199\u597d\u4e4b\u540e\uff0c\u60f3\u8981\u9a8c\u8bc1\u7ea2\u9ed1\u6811\u5728\u6574\u4e2a\u64cd\u4f5c\u8fc7\u7a0b\u4e2d\u662f\u4e0d\u662f\u6709\u4fdd\u6301\u7ea2\u9ed1\u6811\u7684\u6027\u8d28\uff0c\u4e5f\u5c31\u662f\u8bf4\u9a8c\u8bc1\u4ee3\u7801\u6709\u6ca1\u6709\u5199\u9519\uff0c\u53ef\u4ee5\u5199\u4e00\u4e2a\u68c0\u67e5\u51fd\u6570\uff0c\u5728\u6bcf\u6b21\u63d2\u5165\u6216\u5220\u9664\u4e4b\u540e\u90fd\u8c03\u7528\u4e00\u4e0b\u8fd9\u4e2a\u68c0\u67e5\u51fd\u6570\u6765\u68c0\u67e5\u7ea2\u9ed1\u6811\u662f\u4e0d\u662f\u6b63\u5e38\uff0c\u662f\u4e00\u4e2a\u5f88\u597d\u7684\u529e\u6cd5\u3002<\/p>\n
class RedViolation {};\nclass BlackViolation {};\nclass BinaryTreeViolation {};\n\ntemplate<class T>\nint CheckTree(Node<T>* root)\n{\n    if (root == 0)\n        return 1;\n    if (root->IsRed()) {\n        if (root->left->IsRed() || root->right->IsRed())\n            throw RedViolation();\n    }\n    if (root->left != 0 && root->left->data > root->data)\n        throw BinaryTreeViolation();\n    if (root->right != 0 && root->right->data < root->data)\n        throw BinaryTreeViolation();\n    \n    int lh, rh;\n    lh = CheckTree(root->left);\n    rh = CheckTree(root->right);\n\n    if (lh != rh)\n        throw BlackViolation();\n\n    return root->IsRed() ? lh : lh + 1;\n}<\/pre>\n
\u8fd9\u91cc\u4e00\u5171\u68c0\u67e5\u4e09\u79cd\u9519\u8bef\uff0c\u4e00\u79cd\u662f\u7ea2\u8272\u8282\u70b9\u7684\u5b50\u8282\u70b9\u662f\u7ea2\u8272\u8282\u70b9\uff0c\u4e3a\u4e86\u4fdd\u8bc1\u6548\u7387\u548c\u4e8c\u53c9\u6811\u5c42\u9762\u4e0a\u7684\u5e73\u8861\uff0c\u7ea2\u8272\u8282\u70b9\u53ea\u6709\u5144\u5f1f\u8282\u70b9\u53ef\u4ee5\u662f\u7ea2\u8272\u8282\u70b9\uff0c\u7236\u8282\u70b9\u6216\u8005\u5b50\u8282\u70b9\u90fd\u4e0d\u53ef\u4ee5\u662f\u7ea2\u8272\u8282\u70b9\uff1b\u4e00\u79cd\u662f\u68c0\u67e5\u662f\u4e0d\u662f\u7b26\u5408\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u6027\u8d28\uff0c\u5982\u679c\u65cb\u8f6c\u64cd\u4f5c\u5199\u9519\u4e86\uff0c\u90a3\u4e48\u8f6c\u51fa\u6765\u4ee5\u540e\u5c31\u4f1a\u51fa\u73b0\u4e0d\u7b26\u5408\u4e8c\u53c9\u641c\u7d22\u6811\u6027\u8d28\u7684\u60c5\u51b5\uff1b\u6700\u540e\u8fd8\u68c0\u67e5\u5728B-Tree\u5c42\u9762\u4e0a\u662f\u4e0d\u662f\u6bcf\u4e2a\u53f6\u5b50\u8282\u70b9\u90fd\u5904\u5728\u540c\u4e00\u4e2a\u9ad8\u5ea6\u4e0a\uff0c\u5c31\u662f\u8bf4\u5728B-Tree\u5c42\u9762\u4e0a\u662f\u4e0d\u662f\u5e73\u8861\u3002\u8c03\u6574\u8fc7\u7a0b\u4e2d\u5982\u679c\u7ea2\u8272\u8282\u70b9\u3001\u9ed1\u8272\u8282\u70b9\u76f8\u5173\u7684\u6027\u8d28\u88ab\u7834\u574f\uff0c\u4f46\u662f\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u6027\u8d28\u5374\u6ca1\u6709\u88ab\u7834\u574f\uff08\u6b64\u65f6\u53ef\u80fd\u9700\u8981\u5c4f\u853d\u4e00\u90e8\u5206\u68c0\u6d4b\u7684\u4ee3\u7801\uff01\u56e0\u4e3a\u53ea\u8981\u51fa\u73b0\u4efb\u610f\u4e00\u79cd\u6027\u8d28\u88ab\u7834\u574f\u5b83\u5c31\u4f1a\u505c\u6b62\u68c0\u67e5\uff0c\u8fd8\u6ca1\u68c0\u67e5\u5230\u7684\u5730\u65b9\u5e76\u4e0d\u4ee3\u8868\u5c31\u6ca1\u9519\uff01<\/strong><\/font>\uff09\uff0c\u90a3\u4e48\u6709\u53ef\u80fd\u662f\u505a\u7684\u65cb\u8f6c\u7684\u65b9\u5411\u4e0d\u7b26\u5408\u8981\u6c42\uff0c\u6216\u8005\u662f\u5237\u989c\u8272\u7684\u65f6\u5019\u5237\u9519\u4e86\u3002 <\/p>\n
\u6700\u540e\u8fd8\u8981\u68c0\u67e5\u7ea2\u9ed1\u6811\u5728\u63d2\u5165\u7684\u65f6\u5019\u4f1a\u4e0d\u4f1a\u63d2\u5165\u91cd\u590d\u7684\u8282\u70b9\u3001\u5220\u9664\u7684\u65f6\u5019\u4f1a\u4e0d\u4f1a\u6709\u4e9b\u8282\u70b9\u83ab\u540d\u6d88\u5931\u3002\u65b9\u6cd5\u4e5f\u633a\u7b80\u5355\uff0c\u5199\u4e00\u4e2a\u7edf\u8ba1\u8282\u70b9\u6570\u7684\u51fd\u6570\u3001\u5199\u4e00\u4e2a\u67e5\u627e\u8282\u70b9\u7684\u51fd\u6570\uff08\u55ef\u4e0a\u9762\u53ea\u7ed9\u4e86\u63d2\u5165\u548c\u5220\u9664\u7684\u4ee3\u7801\uff0c\u6ca1\u6709\u7edf\u8ba1\u8282\u70b9\u548c\u67e5\u627e\u8282\u70b9\u7684\u3002\u8fd9\u4e24\u4e2a\u90fd\u6bd4\u8f83\u7b80\u5355\uff0c\u4e0d\u8bf4\u5e94\u8be5\u4e5f\u6ca1\u5173\u7cfb\u5427\uff1fXD\uff09\uff0c\u63d2\u5165\u4e4b\u524d\u5148\u627e\u8fd9\u4e2a\u5143\u7d20\u6709\u6ca1\u6709\u5728\u6811\u91cc\u9762\u5e76\u7edf\u8ba1\u8282\u70b9\u6570\uff0c\u5982\u679c\u5143\u7d20\u5df2\u7ecf\u5b58\u5728\u4f46\u662f\u63d2\u5165\u4e4b\u540e\u8282\u70b9\u53d8\u591a\u4e86\uff0c\u90a3\u4e48\u63d2\u5165\u64cd\u4f5c\u6709\u95ee\u9898\uff0c\u67e5\u627e\u63d2\u5165\u4f4d\u7f6e\u7684\u65f6\u5019\u627e\u9519\u4e86\u6216\u8005\u6ca1\u6709\u5904\u7406\u5143\u7d20\u5df2\u7ecf\u5b58\u5728\u7684\u60c5\u51b5\u5427\uff1b\u5220\u9664\u4e4b\u524d\u5148\u67e5\u627e\u8282\u70b9\u662f\u5426\u5b58\u5728\u5e76\u7edf\u8ba1\u8282\u70b9\u6570\u3001\u5220\u9664\u4e4b\u540e\u770b\u770b\u8282\u70b9\u6570\u662f\u5426\u53ea\u662f\u5c11\u4e861\uff0c\u5c31\u53ef\u4ee5\u67d0\u79cd\u7a0b\u5ea6\u4e0a\u5224\u65ad\u5220\u9664\u64cd\u4f5c\u6709\u6ca1\u6709\u95ee\u9898\u3002\u4ece\u4ee3\u7801\u4e0a\u6765\u8bf4\u5e94\u8be5\u4e0d\u4f1a\u6709\u591a\u5220\u9664\u7684\u95ee\u9898\uff0c\u56e0\u4e3adelete\u53ea\u5728\u4e00\u6761\u4e0d\u5e26\u5faa\u73af\u7684\u8def\u5f84\u4e0a\u6709\u53ef\u80fd\u88ab\u8c03\u7528\u4e00\u6b21\u3002<\/p>\n
\u5f53\u7136\u8fd8\u6709\u66f4\u9ebb\u70e6\u7684\u9519\u8bef\uff0c\u5c31\u662f\u5728\u64cd\u4f5c\u8fc7\u7a0b\u4e2d\u4e8c\u53c9\u6811\u5df2\u7ecf\u4e0d\u662f\u4e8c\u53c9\u6811\uff0c\u53d8\u6210\u4e86\u6709\u73af\u56fe\u3001\u4e00\u4e2a\u8282\u70b9\u662f\u597d\u51e0\u4e2a\u5176\u4ed6\u4ec0\u4e48\u8282\u70b9\u7684\u5b50\u8282\u70b9\u8fd9\u7c7b\uff0c\u5c31\u4e0d\u600e\u4e48\u597d\u627e\u4e86\u3002\u6b64\u65f6\u53ef\u4ee5\u5199\u4e00\u4e2a\u51fd\u6570\u628a\u5f53\u524d\u7ea2\u9ed1\u6811\u7684\u60c5\u51b5\u6253\u5370\u51fa\u6765\uff0c\u4eba\u5de5\u68c0\u67e5\u2026\u2026\u867d\u7136\u5f88\u9ebb\u70e6\u5f88\u7d2f\uff0c\u4e0d\u8fc7\u6211\u6682\u65f6\u6ca1\u60f3\u51fa\u5176\u4ed6\u4ec0\u4e48\u7701\u65f6\u95f4\u7701\u529b\u7684\u505a\u6cd5\u3002<\/p>\n
\u8fd9\u4e2a\u662f\u6211\u7684\u5b8c\u6574\u4ee3\u7801\uff0c\u5e26\u6d4b\u8bd5\u51fd\u6570\u3002\u6d4b\u8bd5\u51fd\u6570\u4f1a\u4e0d\u65ad\u5faa\u73af\u63d2\u5165\u548c\u5220\u9664\u968f\u673a\u6570\uff0c\u5e76\u4e14\u6bcf\u6b21\u64cd\u4f5c\u4e4b\u540e\u90fd\u68c0\u67e5\u7ea2\u9ed1\u6811\u662f\u5426\u7b26\u5408\u8981\u6c42\uff0c\u8fd9\u662f\u4e2a\u6b7b\u5faa\u73af\uff0c\u5982\u679c\u7a0b\u5e8f\u5728\u8fd0\u884c\u4e00\u6bb5\u65f6\u95f4\u540e\uff0c\u6ca1\u6709\u62a5\u9519\u5d29\u6e83\uff0c\u5e76\u4e14\u4efb\u52a1\u7ba1\u7406\u5668\u4e2d\u67e5\u770b\u8fd9\u4e2a\u7a0b\u5e8f\u6240\u4f7f\u7528\u7684\u5185\u5b58\uff0c\u5185\u5b58\u6ca1\u6709\u4e0d\u65ad\u6500\u5347\uff0c\u90a3\u4e48\u8fd9\u4e2a\u7a0b\u5e8f\u5e94\u8be5\u662f\u6ca1\u6709\u95ee\u9898\u7684\u3002<\/p>\n
\n
 \u4e0b\u8f7d\u4ee3\u7801\u6587\u4ef6<\/a><\/p>\n<\/div>\n
\u9898\u5916\u8bdd\uff1a\u8fd9\u672c\u6765\u5e94\u8be5\u662f\u672c\u79d1\u6570\u636e\u7ed3\u6784\u8bfe\u7a0b\u4e00\u4e24\u6b21\u8bfe\u5e26\u8fc7\u8bb2\u5b8c\u7684\u4e1c\u897f\uff0c\u5374\u5b66\u4e86\u6211\u5feb\u4e24\u4e2a\u661f\u671f\u624d\u5b66\u4f1a\uff0c\u7b80\u76f4\u8981\u6ee1\u8138\u8840<\/p>\n","protected":false},"excerpt":{"rendered":"
\u7ea2\u9ed1\u6811\u672c\u6765\u6765\u8bf4\u5e94\u8be5\u662f\u672c\u79d1\u6570\u636e\u7ed3\u6784\u6559\u5b66\u7684\u5185\u5bb9\uff0c\u6211\u5f53\u5e74\u9886\u5230\u7684\u6559\u79d1\u4e66\u4e0a\u4e5f\u6709\u3002\u4f46\u662f\u56e0\u4e3a\u6293\u5f97\u4e0d\u4e25\uff0c\u603b\u4e4b\u6700\u540e\u662f\u4e0d\u4e86\u4e86\u4e4b\uff0c\u8fde … \u7ee7\u7eed\u9605\u8bfb\u6570\u636e\u7ed3\u6784\u4e4b\u7ea2\u9ed1\u6811<\/span> →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[19],"tags":[],"class_list":["post-454","post","type-post","status-publish","format-standard","hentry","category-19"],"_links":{"self":[{"href":"https:\/\/blog.sorayuki.net\/index.php?rest_route=\/wp\/v2\/posts\/454","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.sorayuki.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.sorayuki.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.sorayuki.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.sorayuki.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=454"}],"version-history":[{"count":0,"href":"https:\/\/blog.sorayuki.net\/index.php?rest_route=\/wp\/v2\/posts\/454\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.sorayuki.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=454"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.sorayuki.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=454"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.sorayuki.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=454"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}