{"id":55,"date":"2013-12-14T14:24:53","date_gmt":"2013-12-14T14:24:53","guid":{"rendered":""},"modified":"2013-12-14T14:24:53","modified_gmt":"2013-12-14T14:24:53","slug":"","status":"publish","type":"post","link":"http:\/\/weizn.net\/?p=55","title":{"rendered":"\u5e73\u8861\u4e8c\u53c9\u6811"},"content":{"rendered":"

\u5e73\u8861\u4e8c\u53c9\u6811\u5b9a\u4e49(AVL)\uff1a\u5b83\u6216\u8005\u662f\u4e00\u9897\u7a7a\u6811\uff0c\u6216\u8005\u5177\u6709\u4ee5\u4e0b\u6027\u8d28\u7684\u4e8c\u53c9\u6811\uff1a\u5b83\u7684\u5de6\u5b50\u6811\u548c\u53f3\u5b50\u6811\u7684\u6df1\u5ea6\u4e4b\u5dee\u7684\u7edd\u5bf9\u503c\u4e0d\u8d85\u8fc71\uff0c\u4e14\u5b83\u7684\u5de6\u5b50\u6811\u548c\u53f3\u5b50\u6811\u90fd\u662f\u4e00\u9897\u5e73\u8861\u4e8c\u53c9\u6811\u3002<\/p>\n

\u5e73\u8861\u56e0\u5b50(bf)\uff1a\u7ed3\u70b9\u7684\u5de6\u5b50\u6811\u7684\u6df1\u5ea6\u51cf\u53bb\u53f3\u5b50\u6811\u7684\u6df1\u5ea6\uff0c\u90a3\u4e48\u663e\u7136-1<=bf<=1;<\/p>\n

\u5f88\u663e\u7136\uff0c\u5e73\u8861\u4e8c\u53c9\u6811\u662f\u5728\u4e8c\u53c9\u6392\u5e8f\u6811(BST)\u4e0a\u5f15\u5165\u7684\uff0c\u5c31\u662f\u4e3a\u4e86\u89e3\u51b3\u4e8c\u53c9\u6392\u5e8f\u6811\u7684\u4e0d\u5e73\u8861\u6027\u5bfc\u81f4\u65f6\u95f4\u590d\u6742\u5ea6\u5927\u5927\u4e0b\u964d\uff0c\u90a3\u4e48AVL\u5c31\u4fdd\u6301\u4f4f\u4e86(BST)\u7684\u6700\u597d\u65f6\u95f4\u590d\u6742\u5ea6O(logn)\uff0c\u6240\u4ee5\u6bcf\u6b21\u7684\u63d2\u5165\u548c\u5220\u9664\u90fd\u8981\u786e\u4fdd\u4e8c\u53c9\u6811\u7684\u5e73\u8861\uff0c\u90a3\u4e48\u600e\u4e48\u4fdd\u6301\u5e73\u8861\u5462\uff1f<\/p>\n

\u6211\u52aa\u529b\u770b\u4e86\u770b\u6570\u636e\u7ed3\u6784\u4e0a\u7684\u8bb2\u89e3\uff0c\u4f46\u662f\u770b\u7684\u53ea\u6655+_+\uff01\u6211\u5bf9\u4ed6\u7684\u8bb2\u89e3\u5f88\u65e0\u8bed\uff0c\u4ed6\u6240\u8c13\u7684\u201c\u65cb\u8f6c\u201d\u64cd\u4f5c\u8bb2\u7684\u4e0d\u660e\u4e0d\u767d\uff0c\u770b\u7684\u6211\u6c14\u7684\u86cb\u75bc\uff01\u4f60\u8bf4\u4f60\u65cb\u8f6c\uff0c\u4f60\u5f97\u8bf4\u6e05\u662f\u5982\u4f55\u65cb\u8f6c\uff1f\u4ee5\u90a3\u4e2a\u7ed3\u70b9\u4e3a\u4e2d\u5fc3\uff0c\u90a3\u4e9b\u6216\u8005\u8bf4\u90a3\u4e2a\u7ed3\u70b9\u8f6c\u4e86\uff0c\u90a3\u4e9b\u7ed3\u70b9\u4e0d\u52a8\u3002\u4f60\u5c31\u5728\u54ea\u91cc\u65cb\u8f6c\u6765\u65cb\u8f6c\u53bb\u7684\uff0c\u8c01\u77e5\u9053\u4f60\u662f\u548b\u8f6c\u7684\uff0c\u4f60\u5728\u54ea\u6162\u6162\u8f6c\u5427\uff01\u54e5\u8f6c\u4e0d\u8fc7\u4f60\uff0c\u53e6\u627e\u9ad8\u660e\uff01\u4e8e\u662f\u5728\u7f51\u4e0a\u627e\u554a\u627e\uff0c\u53ea\u4e3a\u60f3\u641e\u660e\u767d\u662f\u5230\u5e95\u600e\u4e48\u8f6c\u7684\uff01\u70b9\u51fb\u6253\u5f00\u94fe\u63a5<\/a>\u8ba9\u6211\u5bf9\u201c\u65cb\u8f6c\u201d\u6709\u6240\u9886\u609f\uff0c\u8868\u793a\u611f\u8c22\uff01<\/p>\n

 <\/p>\n

\u63d2\u5165\u65f6\uff1a<\/span><\/span><\/p>\n

\u90a3\u7a76\u7adf\u662f\u5982\u4f55\u201c\u8f6c\u201d\u7684\u5462\uff1f<\/span><\/p>\n

 <\/p>\n

\u9996\u5148\u5fc5\u987b\u660e\u767d\u4e00\u4e2a\u6838\u5fc3\u64cd\u4f5c\uff0c\u4e0d\u8ba9\u5b83\u53eb\u201c\u65cb\u8f6c\u201d\uff01\u800c\u53eb\u2014\u2014>\u201c\u4e24\u4e2a\u7ed3\u70b9\u7684\u53d8\u6362\u201d<\/p>\n

\u5982\u56fe\uff1a<\/p>\n

\"\"<\/p>\n

\u5c31\u62ff\u7b2c\u4e00\u4e2a\u6765\u8bf4->\u70b9100\u548c101\u7684\u53d8\u6362\uff1a<\/p>\n

\u70b9101\u5360\u636e\u70b9100\u7684\u4f4d\u7f6e\uff0c\u70b9100\u6362\u5230\u4e86101\u7684\u5bf9\u9762\u7684\u4f4d\u7f6e\uff0c\u5176\u4ed6\u70b9\u7684\u76f8\u5bf9\u4f4d\u7f6e\u4e0d\u53d8\u3002<\/p>\n

\u6211\u4eec\u53ef\u4ee5\u66f4\u76f4\u89c2\u7684\u7406\u89e3\u4e3a\uff1a\u628a101\u7ed3\u70b9\u201c\u4e0a\u63d0\u201d\u4e00\u4e0b\uff01<\/p>\n

\u5206\u6790\uff1a101>100\uff0c\u6240\u4ee5100\u53ef\u4ee5\u4f5c\u4e3a101\u7684\u5de6\u5b69\u5b50\uff1b<\/p>\n

\u4e5f\u5c31\u662f\u5728\u4e8c\u53c9\u6392\u5e8f\u6811\u4e2d\uff0c\u4e24\u4e2a\u7ed3\u70b9\u8fd9\u6837\u7684\u53d8\u6362\u64cd\u4f5c\u662f\u53ef\u884c\u7684\uff0c\u662f\u7b26\u5408\u4e8c\u53c9\u6392\u5e8f\u6811\u7684\u6027\u8d28\u3002<\/p>\n

\u4e0d\u4ec5\u8fd9\u4e2a\u7b80\u5355\u7684\u56fe\uff0c\u4efb\u4f55\u590d\u6742\u7684\u4e8c\u53c9\u6392\u5e8f\u6811\u90fd\u53ef\u4ee5\uff0c\u4f60\u53ef\u4ee5\u8bd5\u8bd5\uff0c\u4e5f\u8bb8\u4f60\u4f1a\u8bf4\u5982\u679c\u70b9101\u5de6\u8fb9\u6709\u5b69\u5b50\u600e\u4e48\u529e\uff1f\u522b\u7740\u6025~\uff0c\u5f53\u7136\u6709\u529e\u6cd5\uff01<\/p>\n

 <\/p>\n

\u4e0b\u8fb9\u6b63\u5f0f\u8bf4\u8fd9\u4e2a\u56fe\u7684\u56db\u79cd\u4e0d\u5e73\u8861\u60c5\u51b5\uff08\u63d2\u5165\u65f6\uff09\u53ca\u64cd\u4f5c\uff1a<\/p>\n

\u9996\u5148\u8fd8\u9700\u8981\u660e\u767d\u4e00\u4e2a\u6982\u5ff5->\u6700\u5c0f\u4e0d\u5e73\u8861\u5b50\u6811\u7684\u6839\u7ed3\u70b9\uff1a\u4e5f\u5c31\u662f\u5f53\u4f60\u8fdb\u884c\u63d2\u5165\u64cd\u4f5c\u65f6\uff0c\u627e\u5230\u8be5\u9700\u8981\u63d2\u5165\u7ed3\u70b9\u7684\u4f4d\u7f6e\u5e76\u63d2\u5165\u540e\uff0c\u4ece\u8be5\u7ed3\u70b9\u8d77\u5411\u4e0a\u5bfb\u627e\uff08\u56de\u6eaf\uff09\uff0c\u7b2c\u4e00\u4e2a\u4e0d\u5e73\u8861\u7684\u7ed3\u70b9\u5373\u5e73\u8861\u56e0\u5b50bf\u53d8\u4e3a-2\u62162\u3002<\/p>\n

\u4e3a\u4ec0\u4e48\u8981\u5f15\u5165\u8fd9\u4e2a\u6700\u5c0f\u4e0d\u5e73\u8861\u6839\u7ed3\u70b9\u7684\u6982\u5ff5\uff0c\u56e0\u4e3a\u5728\u63d2\u5165\u65f6\uff0c\u5bf9\u8be5\u5b50\u6811\u8fdb\u884c\u4fdd\u6301\u5e73\u8861\u64cd\u4f5c\u540e\uff0c\u5176\u5b83\u7684\u7ed3\u70b9\u7684\u5e73\u8861\u56e0\u5b50\u4e0d\u4f1a\u53d8\uff0c\u4e5f\u5c31\u662f\u6574\u68f5\u6811\u53c8\u6062\u590d\u5e73\u8861\u4e86\u3002\u4e3a\u4ec0\u4e48\u5462\uff1f<\/p>\n

\u4f60\u60f3\u60f3\u4e0d\u5e73\u8861\u70b9\u7684bf\u4e00\u5b9a\u662f-2\u62162\u5427\uff0c\u7ecf\u8fc7\u5e73\u8861\u64cd\u4f5c\u540e\uff0c\u4ed6\u4f1a\u628a\u4e00\u8fb9\u5b50\u6811\u7684\u4e00\u4e2a\u7ed3\u70b9\u5206\u7ed9\u53e6\u4e00\u8fb9\u7684\u5b50\u6811\uff0c\u4e5f\u5c31\u662f\u4e00\u8fb9\u7684\u6df1\u5ea6\u5206\u7ed9\u53e6\u4e00\u8fb9\uff0c\u8fd9\u6837\u5c31\u5e73\u8861\u4e86\uff01<\/p>\n

\u6bd4\u5982\uff0c\u63d2\u5165\u524d\uff1a\u5de6\u8fb9\u662f\u6df1\u5ea61\uff0c\u53f3\u8fb9\u6df1\u5ea6\u662f0\uff1b\u63d2\u5165\u540e\u5de6\u8fb9\u6df1\u5ea6\u662f2\uff0c\u53f3\u8fb9\u6df1\u5ea6\u662f0\uff0c\u7ecf\u8fc7\u5e73\u8861\u540e\u5de6\u8fb9\u6df1\u5ea6\u662f1\uff0c\u53f3\u8fb9\u6df1\u5ea6\u662f1\uff1b<\/p>\n

\u90a3\u4e48\u4f60\u8bf4\u63d2\u5165\u524d\u548c\u63d2\u5165\u540e\u8be5\u6839\u7ed3\u70b9\u6240\u9886\u5bfc\u7684\u5b50\u6811\u7684\u6df1\u5ea6\u53d8\u6ca1\uff1f\uff1f\u4ecd\u662f1\uff0c\u663e\u7136\u6ca1\u53d8\uff01\u90a3\u4e48\u5c31\u4ecd\u4fdd\u6301\u4e86\u8fd9\u68f5\u6811\u7684\u5e73\u8861\u4e86\uff01<\/p>\n

 <\/p>\n

\u4e0b\u9762\u5373\u56db\u79cd\u60c5\u51b5\u5206\u522b\u4e3a\uff1a\u5de6\u5de6\u3001\u53f3\u53f3\u3001\u5de6\u53f3\u3001\u53f3\u5de6\uff0c\u6bcf\u79cd\u60c5\u51b5\u53c8\u6709\u4e24\u4e2a\u56fe\uff1a\u2460\u3001\u2461\uff0c\u2460\u662f\u8be5\u60c5\u51b5\u7684\u6700\u7b80\u5355\u7684\u56fe\u5f62\uff0c\u2461\u662f\u8be5\u60c5\u51b5\u7684\u4e00\u822c\u7684\u56fe\u5f62\uff1b<\/p>\n

\u8bbex\u4e3a\u6700\u5c0f\u4e0d\u5e73\u8861\u5b50\u6811\u7684\u6839\u7ed3\u70b9\uff0cy\u4e3a\u521a\u63d2\u5165\u7684\u70b9<\/p>\n

 <\/p>\n

\u5de6\u5de6\uff1a<\/p>\n

\u5373\u5728x\u7684\u5de6\u5b69\u5b50a\u7684\u5de6\u5b69\u5b50c\u4e0a\u63d2\u5165\u4e00\u4e2a\u7ed3\u70b9y\uff08\u8be5\u7ed3\u70b9\u4e5f\u53ef\u4ee5\u662fc,\u5982\u56fe\u2460\uff09\uff0c\u5373y\u53ef\u4ee5\u662fc\uff0c\u4e5f\u53ef\u4ee5\u662fc\u7684\u5de6\u5b69\u5b50\uff08\u5982\u56fe\u2461\uff09\uff0c\u4e5f\u53ef\u4ee5\u662fc\u7684\u53f3\u5b69\u5b50\uff08\u4e0d\u5728\u753b\u51fa\uff09<\/p>\n

\"\"                                  <\/p>\n

\u56fe\u2460\u5c31\u4e0d\u7528\u8bf4\u4e86\uff0c\u7ed3\u70b9x\u548c\u7ed3\u70b9a\u53d8\u6362\uff0c\u5219\u6811\u5e73\u8861\u4e86\uff1b\u90a3\u4e48\u56fe\u2461\u5c31\u662f\u6811\u4e2d\u7684\u4e00\u822c\u60c5\u51b5\u4e86a\u7ed3\u70b9\u6709\u53f3\u5b69\u5b50d\uff0c\u90a3\u8981\u8fdb\u884cx\u548ca\u53d8\u6362\uff0c\u90a3\u4e48a\u7684\u53f3\u5b69\u5b50\u653e\u54ea\u554a\uff1f<\/p>\n

\u5f88\u7b80\u5355\uff0c\u5982\u56fe\u653e\u5728x\u7684\u5de6\u5b69\u5b50\u4e0a\uff1b\u5206\u6790\uff1ax>d,d>a,\u6240\u4ee5d\u53ef\u4f5c\u4e3ax\u7684\u5de6\u5b69\u5b50\uff0c\u4e14\u53ef\u4f5c\u4e3aa\u7684\u53f3\u5b69\u5b50\u4e2d\u7684\u5b69\u5b50\u3002\u4e0b\u8fb9\u8fd9\u6837\u7684\u7c7b\u4f3c\u60c5\u51b5\u4e0d\u518d\u4e00\u4e00\u5206\u6790\uff0c\u81ea\u5df1\u5206\u6790\u5206\u6790~<\/p>\n

\u5b9e\u73b0\uff1a\u627e\u5230\u6839\u7ed3\u70b9x\uff0c\u4e0e\u5b83\u7684\u5de6\u5b69\u5b50a\u8fdb\u884c\u4ea4\u6362\u5373\u53ef\u4f7f\u4e8c\u53c9\u6811\u6811\u518d\u6b21\u5e73\u8861\uff1b<\/p>\n

 <\/p>\n

 <\/p>\n

\u53f3\u53f3\uff1a<\/p>\n

\u5373\u5728x\u7684\u53f3\u5b69\u5b50a\u7684\u53f3\u5b69\u5b50c\u4e0a\u63d2\u5165\u4e00\u4e2a\u7ed3\u70b9y\uff08\u8be5\u7ed3\u70b9\u4e5f\u53ef\u4ee5\u662fc,\u5982\u56fe\u2460\uff09\uff0c\u5373y\u53ef\u4ee5\u662fc\uff0c\u4e5f\u53ef\u4ee5\u662fc\u7684\u53f3\u5b69\u5b50\uff08\u5982\u56fe\u2461\uff09\uff0c\u4e5f\u53ef\u4ee5\u662fc\u7684\u5de6\u5b69\u5b50\uff08\u4e0d\u5728\u753b\u51fa\uff09<\/p>\n

\"\"<\/p>\n

\u5b9e\u73b0\uff1a\u627e\u5230\u6839\u7ed3\u70b9x\uff0c\u4e0e\u5b83\u7684\u53f3\u5b69\u5b50a\u8fdb\u884c\u4ea4\u6362\u5373\u53ef\u4f7f\u4e8c\u53c9\u6811\u6811\u518d\u6b21\u5e73\u8861\uff1b<\/p>\n

 <\/p>\n

 <\/p>\n

\u5de6\u53f3\uff1a<\/p>\n

\u5373\u5728x\u7684\u5de6\u5b69\u5b50a\u7684\u53f3\u5b69\u5b50c\u4e0a\u63d2\u5165\u4e00\u4e2a\u7ed3\u70b9y\uff08\u8be5\u7ed3\u70b9\u4e5f\u53ef\u4ee5\u662fc,\u5982\u56fe\u2460\uff09\uff0c\u5373y\u53ef\u4ee5\u662fc\uff0c\u4e5f\u53ef\u4ee5\u662fc\u7684\u53f3\u5b69\u5b50\uff08\u5982\u56fe\u2461\uff09\uff0c\u4e5f\u53ef\u4ee5\u662fc\u7684\u5de6\u5b69\u5b50\uff08\u4e0d\u5728\u753b\u51fa\uff09<\/p>\n

 <\/p>\n

 <\/p>\n

\"\"<\/p>\n

\u8fd9\u4e2a\u5de6\u53f3\u548c\u4e0b\u8fb9\u7684\u53f3\u5de6\uff0c\u7a0d\u5fae\u590d\u6742\u4e86\u70b9\uff0c\u9700\u8981\u8fdb\u884c\u4e24\u6b21\u4ea4\u6362\uff0c\u624d\u80fd\u8fbe\u5230\u5e73\u8861\uff0c\u6ce8\u610f\u8fd9\u65f6y\u662fc\u7684\u53f3\u5b69\u5b50\uff0c\u6700\u7ec8y\u4f5c\u4e3ax\u7684\u5de6\u5b69\u5b50\uff1b\u82e5y\u662fc\u7684\u5de6\u5b69\u5b50\uff0c\u6700\u7ec8y\u4f5c\u4e3aa<\/p>\n

\u7684\u53f3\u5b69\u5b50\uff0c\u753b\u56fe\u5206\u6790\u4e00\u4e0b~~\u4e0b\u8fb9\u7c7b\u4f3c\uff0c\u4e0d\u518d\u6556\u8ff0\u3002<\/p>\n

 <\/p>\n

\u5b9e\u73b0\uff1a\u627e\u5230\u6839\u7ed3\u70b9x\uff0c\u8ba9x\u7684\u5de6\u5b69\u5b50a\u4e0ex\u7684\u5de6\u5b69\u5b50a\u7684\u53f3\u5b69\u5b50c\u8fdb\u884c\u4ea4\u6362\uff0c\u7136\u540e\u518d\u8ba9x\u4e0ex\u6b64\u65f6\u7684\u5de6\u5b69\u5b50c\u8fdb\u884c\u4ea4\u6362\uff0c\u6700\u7ec8\u8fbe\u5230\u5e73\u8861\uff1b<\/p>\n

 <\/p>\n

\u53f3\u5de6\uff1a<\/p>\n

\u5373\u5728x\u7684\u53f3\u5b69\u5b50a\u7684\u5de6\u5b69\u5b50c\u4e0a\u63d2\u5165\u4e00\u4e2a\u7ed3\u70b9y\uff08\u8be5\u7ed3\u70b9\u4e5f\u53ef\u4ee5\u662fc,\u5982\u56fe\u2460\uff09\uff0c\u5373y\u53ef\u4ee5\u662fc\uff0c\u4e5f\u53ef\u4ee5\u662fc\u7684\u53f3\u5b69\u5b50\uff08\u5982\u56fe\u2461\uff09\uff0c\u4e5f\u53ef\u4ee5\u662fc\u7684\u5de6\u5b69\u5b50\uff08\u4e0d\u5728\u753b\u51fa\uff09<\/p>\n

\"\"<\/p>\n

 <\/p>\n

\u5b9e\u73b0\uff1a\u627e\u5230\u6839\u7ed3\u70b9x\uff0c\u8ba9x\u7684\u53f3\u5b69\u5b50a\u4e0ex\u7684\u53f3\u5b69\u5b50a\u7684\u5de6\u5b69\u5b50c\u8fdb\u884c\u4ea4\u6362\uff0c\u7136\u540e\u518d\u8ba9x\u4e0ex\u6b64\u65f6\u7684\u53f3\u5b69\u5b50c\u8fdb\u884c\u4ea4\u6362\uff0c\u6700\u7ec8\u8fbe\u5230\u5e73\u8861\uff1b<\/p>\n

 <\/p>\n

\u4e0a\u8fb9\u7684\u56db\u79cd\u60c5\u51b5\u5305\u542b\u4e86\u6240\u6709\u63d2\u5165\u65f6\u5bfc\u81f4\u4e0d\u5e73\u8861\u7684\u60c5\u51b5\uff0c\u4e0a\u9762\u7ed9\u51fa\u7684\u4ec5\u4ec5\u662f\u4e00\u68f5\u5927\u6811\u4e2d\u7684\u6700\u5c0f\u4e0d\u5e73\u8861\u5b50\u6811\uff0c\u4e00\u5b9a\u8981\u60f3\u6e05\u695a\uff0c\u522b\u8ff7\u4e86\uff01<\/p>\n

\u53e6\u5916\u4e00\u5b9a\u8981\u6ce8\u610f\u8fd9\u4e2a\u4ea4\u6362\u64cd\u4f5c\uff0c\u6bd4\u5982a\u4e0eb\u4ea4\u6362\uff08a\u5728\u4e0a\uff0cb\u5728\u4e0b\uff09\uff0cb\u4e00\u5b9a\u8981\u5360\u636ea\u7684\u4f4d\u7f6e\uff01\u4ec0\u4e48\u610f\u601d\uff1f\u5c31\u662fb\u8981\u653e\u5728\uff08\u8986\u76d6\uff09\u50a8\u5b58a\u7684\u90a3\u5757\u5185\u5b58\u4e0a\uff0c<\/p>\n

\u518d\u901a\u4fd7\u70b9\u8bf4\uff0c\u82e5a\u662fx\u7684\u5de6\u5b69\u5b50\uff0c\u5219\u4ea4\u6362\u540eb\u8981\u505ax\u7684\u5de6\u5b69\u5b50\uff1b\u8fd9\u5c31\u662f\u6240\u8c13\u7684b\u5360\u636ea\u7684\u4f4d\u7f6e\uff01<\/p>\n

 <\/p>\n

\u90a3\u4e48\u5982\u4f55\u627e\u5230\u6700\u5c0f\u4e0d\u5e73\u8861\u5b50\u6811\u7684\u6839\u7ed3\u70b9x\uff0c\u5e76\u5224\u65ad\u51fa\u5b83\u662f\u5c5e\u4e8e\u90a3\u79cd\u60c5\u51b5\u7684\uff1f<\/span><\/p>\n

 <\/p>\n

\u63d2\u5165\u4e00\u4e2a\u7ed3\u70b9\u65f6\uff0c\u6211\u4eec\u9996\u5148\u627e\u5230\u9700\u8981\u63d2\u5165\u7684\u4f4d\u7f6e\uff0c\u5e76\u63d2\u5165\uff1b\u6570\u636e\u7ed3\u6784\u4e0a\u7528\u7684\u662f\u9012\u5f52\uff0c\u4e0d\u8981\u8bf4\u9012\u5f52\u592a\u6d6a\u8d39\u65f6\u7a7a\uff0c\u4f60\u60f3\u60f3\u4e00\u4e2a\u542b2^31\u4e2a\u7ed3\u70b9\u7684\u5e73\u8861\u4e8c\u53c9\u6811\u7684\u6df1\u5ea6\u5927\u7ea6\u662f31\u5427\uff0c\u5b83\u9012\u5f52\u518d\u591a\u4e5f\u4e0d\u5c31\u662f31\u5c42\uff01\u800c\u4e14\u9012\u5f52\u4ee3\u7801\u77ed\u5c0f\u3001\u7cbe\u608d\u3001\u5bcc\u542b\u827a\u672f\u4e4b\u7f8e\uff01\u6240\u4ee5\u6211\u8ba4\u4e3a\u5bf9\u4e8e\u8fd9\u4e2a\u5e73\u8861\u4e8c\u53c9\u6811\uff0c\u7528\u9012\u5f52\u5f88\u5408\u9002\uff01<\/p>\n

\u663e\u7136\u63d2\u5165\u4e4b\u540e\u5c31\u8981\u68c0\u67e5\u662f\u5426\u51fa\u73b0\u4e0d\u5e73\u8861\u7684\u7ed3\u70b9\uff0c\u90a3\u4e48\u5982\u4f55\u68c0\u67e5\uff1f<\/p>\n

\u6211\u4eec\u77e5\u9053\uff0c\u4f60\u63d2\u5165\u7684\u65f6\u5019\u7528\u7684\u662f\u9012\u5f52\uff0c\u4e00\u6761\u7ebf\u627e\u5230\u8981\u63d2\u7684\u4f4d\u7f6e\uff0c\u5e76\u63d2\u5165\uff1b\u90a3\u4e48\u8c01\u7684\u5e73\u8861\u56e0\u5b50\u7684\u6709\u53ef\u80fd\u53d8\u5462\uff1f<\/p>\n

\u4e0d\u96be\u60f3\u8c61\uff0c\u53ea\u6709\u8be5\u6761\u7ebf\u4e0a\u7684\u7ed3\u70b9\u7684\u5e73\u8861\u56e0\u5b50\u6709\u53ef\u80fd\u6539\u53d8\uff01\u90a3\u4e48\u6211\u4eec\u5728\u56de\u6eaf\u7684\u65f6\u5019\u4e0d\u5c31\u53ef\u4ee5\u627e\u5230\u7b2c\u4e00\u4e2a\u4e0d\u5e73\u8861\u7684\u5b50\u6811\u7684\u7ed3\u70b9\uff1f\uff01<\/p>\n

\u53ef\u662f\u6211\u4eec\u5982\u4f55\u5224\u65ad\u8be5\u7ed3\u70b9\u7684\u5e73\u8861\u56e0\u5b50\u662f\u5426\u5e94\u8be5\u6539\u53d8\uff0c\u663e\u7136\u8981\u770b\u5b83\u88ab\u63d2\u5165\u7ed3\u70b9\u7684\u4e00\u8fb9\u7684\u6df1\u5ea6\u662f\u5426\u589e\u52a0\uff1b<\/p>\n

\u5982\u4f55\u770b\u5b83\u88ab\u63d2\u5165\u7ed3\u70b9\u7684\u4e00\u8fb9\u7684\u6df1\u5ea6\u662f\u5426\u589e\u52a0\uff1f<\/p>\n

\"\"<\/p>\n

\u5982\u4e0a\u56fe\uff0c\u5982\u4f55\u770bx\u7684\u53f3\u5b69\u5b50a\uff08\u5373\u88ab\u63d2\u5165\u7ed3\u70b9\u7684\u4e00\u8fb9\uff09\u7684\u6df1\u5ea6\u589e\u52a0\uff1f\u6211\u4eec\u77e5\u9053\u5728a\u7684\u53f3\u5b69\u5b50\u4e0a\u63d2\u5165\u4e86\u7ed3\u70b9y\u90a3\u4e48a\u7684bf\u662f\u4e00\u5b9a\u8981\u51cf1<\/p>\n

\u90a3\u4e48x\u7ed3\u70b9\u7684bf\uff1f\u53ef\u6839\u636ea\u7684bf\u51b3\u5b9a\u662f\u5426\u6539\u53d8\uff01<\/p>\n

\u82e5a:bf=-1\u62161\uff0c\u90a3\u4e48a\u4e4b\u524d\u4e00\u5b9a\u4e3a0\uff0c\u8868\u793aa\u7684\u6df1\u5ea6\u589e\u52a0\u4e86\uff0c\u90a3\u4e48x\u7684bf\u53ef\u6839\u636ea\u662fx\u54ea\u4e00\u8fb9\u7684\u5b69\u5b50\u51b3\u5b9a+1\u6216-1\uff1b<\/p>\n

\u82e5a:bf=0\uff0c\u90a3\u4e48a\u4e4b\u524d\u4e00\u5b9a\u4e3a-1\u62161\uff0c\u8868\u793aa\u7684\u6df1\u5ea6\u6bcf\u589e\u52a0\uff0c\u90a3\u4e48\u4e0d\u4ec5x\u7684bf\u5c31\u4e0d\u7528\u53d8\uff0c\u8be5\u6761\u7ebf\u4e0a\u7684\u6240\u6709\u7ed3\u70b9\u7684bf\u90fd\u4e0d\u7528\u53d8\uff0c\u76f4\u63a5\u8fd4\u56de\u5373\u53ef\uff1b<\/p>\n

 <\/p>\n

\u5f53\u7136\u4e86\uff0c\u90a3\u4e48\u627e\u5230\u6700\u5c0f\u4e0d\u5e73\u8861\u5b50\u6811\u7684\u6839\u7ed3\u70b9x\u4e86\uff0c\u5982\u4f55\u5224\u65ad\u5b83\u5c5e\u4e8e\u54ea\u79cd\u4e0d\u5e73\u8861\u5462\uff1f<\/p>\n

\u2460\u6839\u636e\u4e0a\u8fb9\u7684\u51e0\u79cd\u60c5\u51b5\uff0c\u6211\u4eec\u9700\u8981\u77e5\u9053\u4e24\u4e2a\u65b9\u5411\uff0c\u5728\u56de\u6eaf\u65f6\u53ef\u4ee5\u8bb0\u5f55\u4e00\u4e0b\u8be5\u7ed3\u70b9\u5230\u4e0b\u4e00\u4e2a\u7ed3\u70b9\u7684\u65b9\u54110\uff1a\u5de6\u30011\uff1a\u53f3\u4e3a\u7b2c\u4e8c\u4e2a\u65b9\u5411\uff0c\u4f20\u9012\u7ed9\u4e0a\u4e00\u5c42\u4e2d\uff0c\u90a3\u4e48\u4e0a\u5c42\u4e2d\u7684\u65b9\u5411\u5c31\u662f\u4e00\u4e2a\u65b9\u5411\uff0c\u6709\u4e86\u8fd9\u4e24\u4e2a\u65b9\u5411\u5c31\u80fd\u786e\u5b9a\u662f\u54ea\u79cd\u4e0d\u5e73\u8861\u4e86\u3002<\/p>\n

\u8fd8\u5c31\u4e0a\u8fb9\u7684\u56fe\u8bf4\u5427~\u53ef\u4ee5\u5b9a\u4e49\u4e00\u4e2a\u5168\u5c40\u53d8\u91cfsecdirection\uff08\u7b2c\u4e8c\u4e2a\u65b9\u5411\uff09\uff0c\u4e5f\u53ef\u5728\u9012\u5f52\u4e2d\u5b9a\u4e49\u4e00\u4e2a\u5c40\u90e8\u53d8\u91cf\uff0c\u8fd4\u56de\u7ed9\u4e0a\u4e00\u5c42\u3002\u5728\u56de\u6eaf\u5230a\u4e2d\u65f6\uff0csecdirection=1\uff0c\u5230x\u7684\u65f6\u5019<\/p>\n

x->a\u7684\u65b9\u5411\u4e5f\u4e3a1\uff0c\u5b9a\u4e49firdirection=1\uff1b\u800c\u8fd9\u65f6x:bf=-2\uff1b\u90a3\u4e48\u5c31\u627e\u5230\u4e86\u6700\u5c0f\u4e0d\u5e73\u8861\u5b50\u6811\u7684\u6839\u7ed3\u70b9x\uff0c\u53c8\u77e5\u9053\u4e86\u4e24\u4e2a\u65b9\u5411\uff0c\u90a3\u4e48\u8fdb\u884c\u76f8\u5e94\u7684\u5e73\u8861\u64cd\u4f5c\u4e0d\u5c31\u884c\u4e86\u3002<\/p>\n

\u2461\u5176\u5b9e\u6211\u4ee3\u7801\u4e2d\u7684\u5c31\u662f\u6309\u7167\u2460\u5199\u7684\uff0c\u53ef\u662f\u521a\u53c8\u60f3\u4e86\uff0c\u5176\u5b9e\u4e0d\u7528\u7528\u4e2a\u53d8\u91cf\u8bb0\u5f55\u7b2c\u4e8c\u4e2a\u65b9\u5411\uff0c\u53ef\u4ee5\u6839\u636ea\u7684bf\u786e\u5b9a\u5b83\u7684\u7b2c\u4e8c\u4e2a\u65b9\u5411\uff0ca:bf=-1\u8bf4\u660e\u53f3\u5b69\u5b50\u7684\u6df1\u5ea6\u589e\u52a0\uff0cy\u52a0\u5230\u53f3\u5b69\u5b50\u4e0a\uff1b<\/p>\n

a:bf=1;\u8bf4\u660e\u5de6\u5b69\u5b50\u7684\u6df1\u5ea6\u589e\u52a0\uff0cy\u52a0\u5230\u5de6\u5b69\u5b50\u4e0a\uff1b<\/p>\n

 <\/p>\n

\u597d\u4e86\uff0c\u627e\u5230\u4e86\u6700\u5c0f\u4e0d\u5e73\u8861\u5b50\u6811\u7684\u6839\u7ed3\u70b9x\u4e86\uff0c\u4e5f\u77e5\u9053\u4e86\u90a3\u79cd\u4e0d\u5e73\u8861\uff0c\u8c03\u7528keepbalance(…)\u5c31\u4f7f\u6811\u5e73\u8861\u4e86\uff0c\u53ef\u662f\u67d0\u4e9b\u7ed3\u70b9\u7684\u5e73\u8861\u56e0\u5b50\u5728\u53d8\u6362\u662f\u53d8\u4e86~~\u548b\u529e\uff1f<\/p>\n

\u6211\u5c31\u662f\u4e00\u79cd\u4e00\u79cd\u60c5\u51b5\u63a8\u51fa\u6765\u7684\uff0c\u4e0d\u77e5\u9053\u522b\u4eba\u600e\u4e48\u53d8\u7684\uff0c\u6bcf\u4e00\u79cd\u60c5\u51b5\u90fd\u6709\u56fa\u5b9a\u7684\u51e0\u4e2a\u70b9\u53d8\u4e86\uff0c\u53d8\u6210\u4e86\u4e00\u4e2a\u56fa\u5b9a\u7684\u503c\uff01\u8c01\u6709\u66f4\u597d\u7684\u529e\u6cd5\uff0c\u8bf7\u591a\u591a\u6307\u6559\uff01<\/p>\n

 <\/p>\n

\u4e0b\u8fb9\u4e00\u4e00\u5217\u51fa\uff08\u63d2\u5165\u64cd\u4f5c\u4e2d\uff09\u53d8\u6362\u540ebf\u6539\u53d8\u7684\u7ed3\u70b9\u53ca\u503c\uff1a<\/p>\n

\u5de6\u5de6\uff1a\u524da->bf=1 \u540e x->bf=0,a->bf=0\uff1b\u53f3\u53f3\uff1a\u524da->bf=-1 \u540ex->bf=0,a->bf=0\uff1b\u663e\u7136\u5de6\u5de6\u4e0e\u53f3\u53f3\u7684x\u4e0ea\u53d8\u6362\u540e\u7684bf\u90fd\u4e3a0\uff1b<\/p>\n

\u5de6\u53f3\u3001\u53f3\u5de6\u4e2d\u7ed3\u70b9bf\u7684\u6539\u53d8\u8981\u6839\u636e\u4e4b\u524dc\u7684bf\uff01<\/p>\n

\u5de6\u53f3\uff1a\u82e5c->bf=1,\u5219x->bf=-1,a->bf=0,c->bf=0\uff1b\u82e5c->bf=-1,\u5219x->bf=0,a->bf=1,c->bf=0\uff1b\u82e5c->bf=0,\u5219x->bf=0,a->bf=0,c->bf=0\uff1b<\/p>\n

\u53f3\u5de6\uff1a\u82e5c->bf=1,\u5219x->bf=0,a->bf=-1,c->bf=0\uff1b\u82e5c->bf=-1,\u5219x->bf=1,a->bf=0,c->bf=0\uff1b\u82e5c->bf=0,\u5219x->bf=0,a->bf=0,c->bf=0\uff1b<\/p>\n

\u53ef\u4ee5\u53d1\u73b0\uff0c\u5f53\u5de6\u53f3\u3001\u53f3\u5de6\u7684c->bf\u76f8\u540c\u65f6x\u4e0ea\u7684bf\u521a\u597d\u53d6\u76f8\u53cd\u7684\u503c\u3002<\/p>\n

 <\/p>\n

\u597d\u4e86\uff0c\u5230\u73b0\u5728\u63d2\u5165\u4e00\u4e2a\u7ed3\u70b9\u7684\u4e8c\u53c9\u6811\u7ec8\u4e8e\u5e73\u8861\u4e86\uff0c\u76f8\u5e94\u7684\u5e73\u8861\u56e0\u5b50\u4e5f\u4fee\u6539\u4e86\uff01\u63d2\u5165\u7b97\u662f\u5b8c\u6210\u4e86\uff01\uff01<\/p>\n

 <\/p>\n

\u5220\u9664\u65f6\uff1a<\/span><\/span><\/p>\n

\u5220\u9664\u7c7b\u4f3c\u63d2\u5165\u7684\u64cd\u4f5c\uff0c\u86cb\u53c8\u4e0d\u540c\uff0c\u5220\u9664\u4f1a\u6709\u4e00\u4e9b\u7279\u6b8a\u60c5\u51b5\u9700\u8981\u7279\u6b8a\u5904\u7406\uff0c\u5f53\u7136\u6838\u5fc3\u64cd\u4f5c\u201c\u4fdd\u6301\u5e73\u8861\u201d\u662f\u4e0d\u53d8\u7684\uff01<\/p>\n

 <\/p>\n

\u5220\u9664\u65f6\u5c11\u4e00\u4e2a\u7ed3\u70b9\uff0c\u4e5f\u5c31\u662f\u8be5\u7ed3\u70b9\u6240\u5728\u7684\u5b50\u6811\u6df1\u5ea6\u53ef\u80fd\u4f1a\u51cf\u5c0f\uff0c\u800c\u63d2\u5165\u65f6\u591a\u4e00\u4e2a\u7ed3\u70b9\uff0c\u8be5\u7ed3\u70b9\u6240\u5728\u7684\u5b50\u6811\u6df1\u5ea6\u53ef\u80fd\u4f1a\u589e\u52a0\uff0c<\/p>\n

\u6240\u4ee5\u9012\u5f52\u5220\u9664\u4e00\u4e2a\u7ed3\u70b9\u65f6\uff0c\u56de\u6eaf\u65f6\u627e\u5230\u6700\u5c0f\u4e0d\u5e73\u8861\u5b50\u6811\u7684\u6839\u7ed3\u70b9\u65f6\uff0c\u8981\u5411\u76f8\u53cd\u7684\u65b9\u5411\u53bb\u627e\u5c5e\u4e8e\u54ea\u79cd\u60c5\u51b5\uff1b<\/p>\n

\u5982\u56fe\uff1a<\/p>\n

y\u4e3a\u8981\u5220\u9664\u7684\u7ed3\u70b9\uff1b<\/p>\n

\"\"<\/p>\n

\u56fe\u2460\uff1ay\u7ed3\u70b9\u5220\u9664\u540e\uff0c\u56de\u6eaf\u5230x\u7ed3\u70b9x:bf=-1\u53d8\u4e3ax:bf=-2\uff1b\u5219\u9700\u4ece\u76f8\u53cd\u65b9\u5411\u5373\u4ecex\u7684\u53f3\u5b69\u5b50\u7684\u65b9\u5411\u5411\u4e0b\u68c0\u67e5\u5c5e\u4e8e\u54ea\u79cd\u60c5\u51b5\uff0c\u663e\u7136\u7b2c\u4e00\u4e2a\u65b9\u5411\u4e3a1\uff1a\u53f3\uff1b<\/p>\n

\u7b2c\u4e8c\u4e2a\u65b9\u5411\u770ba:bf\u7684\u503c\u2014\u2014\u82e5\u4e3a1\u65f6\uff0c\u90a3\u5c31\u76f8\u5f53\u4e8e\u63d2\u5165\u65f6\u2018\u53f3\u5de6\u2019\u7684\u60c5\u51b5\uff1b\u82e5\u4e3a-1\u65f6\uff0c\u90a3\u5c31\u76f8\u5f53\u4e8e\u63d2\u5165\u65f6\u2018\u5de6\u5de6\u2019\u7684\u60c5\u51b5\uff1b\u53ef\u73b0\u5728a:bf\u65e2\u4e0d\u662f1\u4e5f\u4e0d\u662f-1<\/p>\n

\u800c\u662f0\uff0c\u8fd9\u5c31\u662f\u5220\u9664\u7684\u7279\u6b8a\u60c5\u51b5\u4e86\uff01\u6211\u4eec\u4e0d\u59a8\u8bd5\u8bd5\u5bf9\u4ed6\u8fdb\u884c\u7c7b\u4f3c\u4e8e\u63d2\u5165\u65f6\u7684\u2018\u53f3\u53f3\u2019\u64cd\u4f5c\uff0c\u770b\u600e\u4e48\u6837~    \u5982\u4e0a\u56fe\uff0c\u7ecf\u8fc7\u53d8\u6362\u540e\u8be5\u5b50\u6811\u5e73\u8861\u4e86\uff01\u4f46\u662f\u56e0\u5b50\u7684<\/p>\n

\u4fee\u6539\u5c31\u8ddf\u63d2\u5165\u65f6\u7684\u2018\u53f3\u53f3\u2019\u4e0d\u4e00\u6837\u4e86\uff01\u6b64\u65f6\u53d8\u4e3a\uff1ax:bf=-1,a:bf=1\uff1b\u6240\u4ee5\u6211\u4eec\u4e0d\u59a8\u5c31\u628aa:bf=0\u4e5f\u5f52\u7eb3\u4e3a\u5220\u9664\u7684\u2018\u53f3\u53f3\u2019\u6216\u2018\u5de6\u5de6\u2019\uff08\u5982\u56fe\u2461\uff0c\u4e0d\u518d\u6556\u8ff0\uff09\u64cd\u4f5c\uff1b<\/p>\n

\u90a3\u4e48\u5220\u9664\u65f6\u56e0\u5b50\u7684\u6539\u53d8\u9700\u5728\u63d2\u5165\u65f6\u56e0\u5b50\u7684\u6539\u53d8\u4e2d\u6dfb\u52a0\u4e0a\uff1a<\/p>\n

\u5de6\u5de6\uff1a\u524da:bf=0 \u540ex:bf=1,a:bf=-1\uff1b \u53f3\u53f3\uff1a\u524da:bf=0 \u540ex:bf=-1,a:bf=1\uff1b\u5176\u4ed6\u4e0d\u53d8\uff01<\/p>\n

 <\/p>\n

\u63d2\u5165\u65f6\u7ed3\u675f\u7ed3\u70b9\u5e73\u8861\u56e0\u5b50\u7684\u4fee\u6539\uff0c\u76f4\u63a5\u8fd4\u56de\uff08\u4e5f\u5c31\u662f\u8be5\u6811\u5df2\u7ecf\u5e73\u8861\u4e86\uff09\uff1a<\/p>\n

\u56de\u6eaf\u65f6\u53d1\u73b0\u513f\u5b50\u7ed3\u70b9\u7684\u5e73\u8861\u56e0\u5b50\u4e3a0\uff08\u5f53\u53d1\u73b0\u4e0d\u5e73\u8861\u7ed3\u70b9\uff0c\u5e76\u8fdb\u884c\u5e73\u8861\u64cd\u4f5c\u540e\uff0c\u5e73\u8861\u540e\u6839\u7ed3\u70b9\u7684bf\u4e00\u5b9a\u4e3a0\uff0c\u4e5f\u7ed3\u675f\u4e86\uff09<\/p>\n

\u4f46\u662f\u5220\u9664\u65f6\u7ed3\u675f\u7ed3\u70b9\u5e73\u8861\u56e0\u5b50\u7684\u4fee\u6539\uff0c\u76f4\u63a5\u8fd4\u56de\uff0c\u5c31\u4e0e\u63d2\u5165\u65f6\u4e0d\u4e00\u6837\u4e86\uff1a\u56de\u6eaf\u65f6\u53d1\u73b0\u513f\u5b50\u7ed3\u70b9\u7684\u5e73\u8861\u56e0\u5b50\u4e3a-1\u62161\uff01<\/p>\n

\u518d\u5220\u9664\u64cd\u4f5c\u4e2d\uff0c\u5e73\u8861\u4e00\u4e2a\u5b50\u6811\u540e\uff0c\u8be5\u5b50\u6811\u7684\u6df1\u5ea6\u4e0d\u4e00\u5b9a\u4e0d\u53d8\uff0c\u800c\u53ea\u6709\u4e0a\u8fb9\u90a3\u79cd\u7279\u6b8a\u60c5\u51b5\u8be5\u5b50\u6811\u7684\u6df1\u5ea6\u4e0d\u53d8\uff0c\u5176\u4ed6\u90fd\u4f1a\u53d8\uff01<\/p>\n

\u53ef\u4ee5\u60f3\u8c61\uff0c\u5176\u5b9e\u662f\u5f88\u7b80\u5355\u7684\u9053\u7406\uff1a\u9664\u4e86\u7279\u6b8a\u60c5\u51b5\u5176\u4ed6\u90fd\u4e0e\u63d2\u5165\u7684\u60c5\u51b5\u4e00\u6a21\u4e00\u6837\uff0c\u8bf4\u767d\u4e86\u5c31\u662f\u628a\u6df1\u5ea6\u5927\u7684\u5b50\u6811\uff08\u6839\u7ed3\u70b9\u7684\u5176\u4e2d\u4e00\u4e2a\uff09\u5411\u6df1\u5ea6\u5c0f\u5b50\u6811\u8d21\u732e\u4e00\u4e2a\u6df1\u5ea6\uff0c<\/p>\n

\u90a3\u4e48\u8fd9\u6837\u4e00\u6765\uff0c\u8be5\u5b50\u6811\uff08\u5bf9\u4e8e\u6839\u7ed3\u70b9\u6240\u9886\u5bfc\u7684\u6811\uff09\u7684\u6df1\u5ea6\u662f\u4e0d\u662f\u6bd4\u539f\u6765\u7684\u5c0f1\u4e86\uff1f\uff01\u6240\u4ee5\u8981\u7ee7\u7eed\u5411\u4e0a\u4e00\u4e2a\u4e00\u4e2a\u8fdb\u884c\u68c0\u7d22\uff0c\u76f4\u5230\u6839\u7ed3\u70b9\u4e3a\u6b62\uff01<\/p>\n","protected":false},"excerpt":{"rendered":"

\u5e73\u8861\u4e8c\u53c9\u6811\u5b9a\u4e49(AVL)\uff1a\u5b83\u6216\u8005\u662f\u4e00\u9897\u7a7a\u6811\uff0c\u6216\u8005\u5177\u6709\u4ee5\u4e0b\u6027\u8d28\u7684\u4e8c\u53c9\u6811\uff1a\u5b83\u7684\u5de6\u5b50\u6811\u548c\u53f3\u5b50\u6811\u7684\u6df1\u5ea6\u4e4b\u5dee\u7684\u7edd\u5bf9\u503c\u4e0d\u8d85\u8fc71\uff0c\u4e14\u5b83\u7684\u5de6\u5b50\u6811\u548c\u53f3\u5b50\u6811\u90fd\u662f\u4e00\u9897\u5e73\u8861\u4e8c\u53c9\u6811\u3002<\/p>\n

\u5e73\u8861\u56e0\u5b50(bf)\uff1a\u7ed3\u70b9\u7684\u5de6\u5b50\u6811\u7684\u6df1\u5ea6\u51cf\u53bb\u53f3\u5b50\u6811\u7684\u6df1\u5ea6\uff0c\u90a3\u4e48\u663e\u7136-1<=bf<=1;<\/p>\n

\u5f88\u663e\u7136\uff0c\u5e73\u8861\u4e8c\u53c9\u6811\u662f\u5728\u4e8c\u53c9\u6392\u5e8f\u6811(BST)\u4e0a\u5f15\u5165\u7684\uff0c\u5c31\u662f\u4e3a\u4e86\u89e3\u51b3\u4e8c\u53c9\u6392\u5e8f\u6811\u7684\u4e0d\u5e73\u8861\u6027\u5bfc\u81f4\u65f6\u95f4\u590d\u6742\u5ea6\u5927\u5927\u4e0b\u964d\uff0c\u90a3\u4e48AVL\u5c31\u4fdd\u6301\u4f4f\u4e86(BST)\u7684\u6700\u597d\u65f6\u95f4\u590d…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[326],"tags":[],"class_list":["post-55","post","type-post","status-publish","format-standard","hentry"],"yoast_head":"\n\u5e73\u8861\u4e8c\u53c9\u6811 - Wayne's Blog<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"http:\/\/weizn.net\/?p=55\" \/>\n<meta property=\"og:locale\" content=\"zh_CN\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"\u5e73\u8861\u4e8c\u53c9\u6811 - Wayne's Blog\" \/>\n<meta property=\"og:description\" content=\"\u5e73\u8861\u4e8c\u53c9\u6811\u5b9a\u4e49(AVL)\uff1a\u5b83\u6216\u8005\u662f\u4e00\u9897\u7a7a\u6811\uff0c\u6216\u8005\u5177\u6709\u4ee5\u4e0b\u6027\u8d28\u7684\u4e8c\u53c9\u6811\uff1a\u5b83\u7684\u5de6\u5b50\u6811\u548c\u53f3\u5b50\u6811\u7684\u6df1\u5ea6\u4e4b\u5dee\u7684\u7edd\u5bf9\u503c\u4e0d\u8d85\u8fc71\uff0c\u4e14\u5b83\u7684\u5de6\u5b50\u6811\u548c\u53f3\u5b50\u6811\u90fd\u662f\u4e00\u9897\u5e73\u8861\u4e8c\u53c9\u6811\u3002\u5e73\u8861\u56e0\u5b50(bf)\uff1a\u7ed3\u70b9\u7684\u5de6\u5b50\u6811\u7684\u6df1\u5ea6\u51cf\u53bb\u53f3\u5b50\u6811\u7684\u6df1\u5ea6\uff0c\u90a3\u4e48\u663e\u7136-1<=bf<=1;\u5f88\u663e\u7136\uff0c\u5e73\u8861\u4e8c\u53c9\u6811\u662f\u5728\u4e8c\u53c9\u6392\u5e8f\u6811(BST)\u4e0a\u5f15\u5165\u7684\uff0c\u5c31\u662f\u4e3a\u4e86\u89e3\u51b3\u4e8c\u53c9\u6392\u5e8f\u6811\u7684\u4e0d\u5e73\u8861\u6027\u5bfc\u81f4\u65f6\u95f4\u590d\u6742\u5ea6\u5927\u5927\u4e0b\u964d\uff0c\u90a3\u4e48AVL\u5c31\u4fdd\u6301\u4f4f\u4e86(BST)\u7684\u6700\u597d\u65f6\u95f4\u590d...\" \/>\n<meta property=\"og:url\" content=\"http:\/\/weizn.net\/?p=55\" \/>\n<meta property=\"og:site_name\" content=\"Wayne's Blog\" \/>\n<meta property=\"article:published_time\" content=\"2013-12-14T14:24:53+00:00\" \/>\n<meta property=\"og:image\" content=\"http:\/\/pic002.cnblogs.com\/images\/2011\/330710\/2011111511570656.jpg\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"\u4f5c\u8005\" \/>\n\t<meta name=\"twitter:data1\" content=\"zinan\" \/>\n\t<meta name=\"twitter:label2\" content=\"\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4\" \/>\n\t<meta name=\"twitter:data2\" content=\"2 \u5206\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebSite\",\"@id\":\"http:\/\/weizn.net\/#website\",\"url\":\"http:\/\/weizn.net\/\",\"name\":\"Wayne's Blog\",\"description\":\"\",\"publisher\":{\"@id\":\"http:\/\/weizn.net\/#\/schema\/person\/e88bc12c590502d8b6249326f960b264\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"http:\/\/weizn.net\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"zh-Hans\"},{\"@type\":\"ImageObject\",\"@id\":\"http:\/\/weizn.net\/?p=55#primaryimage\",\"inLanguage\":\"zh-Hans\",\"url\":\"http:\/\/pic002.cnblogs.com\/images\/2011\/330710\/2011111511570656.jpg\",\"contentUrl\":\"http:\/\/pic002.cnblogs.com\/images\/2011\/330710\/2011111511570656.jpg\"},{\"@type\":\"WebPage\",\"@id\":\"http:\/\/weizn.net\/?p=55#webpage\",\"url\":\"http:\/\/weizn.net\/?p=55\",\"name\":\"\\u5e73\\u8861\\u4e8c\\u53c9\\u6811 - Wayne's Blog\",\"isPartOf\":{\"@id\":\"http:\/\/weizn.net\/#website\"},\"primaryImageOfPage\":{\"@id\":\"http:\/\/weizn.net\/?p=55#primaryimage\"},\"datePublished\":\"2013-12-14T14:24:53+00:00\",\"dateModified\":\"2013-12-14T14:24:53+00:00\",\"breadcrumb\":{\"@id\":\"http:\/\/weizn.net\/?p=55#breadcrumb\"},\"inLanguage\":\"zh-Hans\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"http:\/\/weizn.net\/?p=55\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"http:\/\/weizn.net\/?p=55#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\\u9996\\u9875\",\"item\":\"http:\/\/weizn.net\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"\\u5e73\\u8861\\u4e8c\\u53c9\\u6811\"}]},{\"@type\":\"Article\",\"@id\":\"http:\/\/weizn.net\/?p=55#article\",\"isPartOf\":{\"@id\":\"http:\/\/weizn.net\/?p=55#webpage\"},\"author\":{\"@id\":\"http:\/\/weizn.net\/#\/schema\/person\/e88bc12c590502d8b6249326f960b264\"},\"headline\":\"\\u5e73\\u8861\\u4e8c\\u53c9\\u6811\",\"datePublished\":\"2013-12-14T14:24:53+00:00\",\"dateModified\":\"2013-12-14T14:24:53+00:00\",\"mainEntityOfPage\":{\"@id\":\"http:\/\/weizn.net\/?p=55#webpage\"},\"wordCount\":382,\"commentCount\":0,\"publisher\":{\"@id\":\"http:\/\/weizn.net\/#\/schema\/person\/e88bc12c590502d8b6249326f960b264\"},\"image\":{\"@id\":\"http:\/\/weizn.net\/?p=55#primaryimage\"},\"thumbnailUrl\":\"http:\/\/pic002.cnblogs.com\/images\/2011\/330710\/2011111511570656.jpg\",\"articleSection\":[\"\\u6570\\u636e\\u7ed3\\u6784\\u53ca\\u7b97\\u6cd5\"],\"inLanguage\":\"zh-Hans\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"http:\/\/weizn.net\/?p=55#respond\"]}]},{\"@type\":[\"Person\",\"Organization\"],\"@id\":\"http:\/\/weizn.net\/#\/schema\/person\/e88bc12c590502d8b6249326f960b264\",\"name\":\"zinan\",\"logo\":{\"@id\":\"http:\/\/weizn.net\/#personlogo\"}}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"\u5e73\u8861\u4e8c\u53c9\u6811 - Wayne's Blog","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":"http:\/\/weizn.net\/?p=55","og_locale":"zh_CN","og_type":"article","og_title":"\u5e73\u8861\u4e8c\u53c9\u6811 - Wayne's Blog","og_description":"\u5e73\u8861\u4e8c\u53c9\u6811\u5b9a\u4e49(AVL)\uff1a\u5b83\u6216\u8005\u662f\u4e00\u9897\u7a7a\u6811\uff0c\u6216\u8005\u5177\u6709\u4ee5\u4e0b\u6027\u8d28\u7684\u4e8c\u53c9\u6811\uff1a\u5b83\u7684\u5de6\u5b50\u6811\u548c\u53f3\u5b50\u6811\u7684\u6df1\u5ea6\u4e4b\u5dee\u7684\u7edd\u5bf9\u503c\u4e0d\u8d85\u8fc71\uff0c\u4e14\u5b83\u7684\u5de6\u5b50\u6811\u548c\u53f3\u5b50\u6811\u90fd\u662f\u4e00\u9897\u5e73\u8861\u4e8c\u53c9\u6811\u3002\u5e73\u8861\u56e0\u5b50(bf)\uff1a\u7ed3\u70b9\u7684\u5de6\u5b50\u6811\u7684\u6df1\u5ea6\u51cf\u53bb\u53f3\u5b50\u6811\u7684\u6df1\u5ea6\uff0c\u90a3\u4e48\u663e\u7136-1<=bf<=1;\u5f88\u663e\u7136\uff0c\u5e73\u8861\u4e8c\u53c9\u6811\u662f\u5728\u4e8c\u53c9\u6392\u5e8f\u6811(BST)\u4e0a\u5f15\u5165\u7684\uff0c\u5c31\u662f\u4e3a\u4e86\u89e3\u51b3\u4e8c\u53c9\u6392\u5e8f\u6811\u7684\u4e0d\u5e73\u8861\u6027\u5bfc\u81f4\u65f6\u95f4\u590d\u6742\u5ea6\u5927\u5927\u4e0b\u964d\uff0c\u90a3\u4e48AVL\u5c31\u4fdd\u6301\u4f4f\u4e86(BST)\u7684\u6700\u597d\u65f6\u95f4\u590d...","og_url":"http:\/\/weizn.net\/?p=55","og_site_name":"Wayne's Blog","article_published_time":"2013-12-14T14:24:53+00:00","og_image":[{"url":"http:\/\/pic002.cnblogs.com\/images\/2011\/330710\/2011111511570656.jpg"}],"twitter_card":"summary_large_image","twitter_misc":{"\u4f5c\u8005":"zinan","\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4":"2 \u5206"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebSite","@id":"http:\/\/weizn.net\/#website","url":"http:\/\/weizn.net\/","name":"Wayne's Blog","description":"","publisher":{"@id":"http:\/\/weizn.net\/#\/schema\/person\/e88bc12c590502d8b6249326f960b264"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"http:\/\/weizn.net\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"zh-Hans"},{"@type":"ImageObject","@id":"http:\/\/weizn.net\/?p=55#primaryimage","inLanguage":"zh-Hans","url":"http:\/\/pic002.cnblogs.com\/images\/2011\/330710\/2011111511570656.jpg","contentUrl":"http:\/\/pic002.cnblogs.com\/images\/2011\/330710\/2011111511570656.jpg"},{"@type":"WebPage","@id":"http:\/\/weizn.net\/?p=55#webpage","url":"http:\/\/weizn.net\/?p=55","name":"\u5e73\u8861\u4e8c\u53c9\u6811 - Wayne's Blog","isPartOf":{"@id":"http:\/\/weizn.net\/#website"},"primaryImageOfPage":{"@id":"http:\/\/weizn.net\/?p=55#primaryimage"},"datePublished":"2013-12-14T14:24:53+00:00","dateModified":"2013-12-14T14:24:53+00:00","breadcrumb":{"@id":"http:\/\/weizn.net\/?p=55#breadcrumb"},"inLanguage":"zh-Hans","potentialAction":[{"@type":"ReadAction","target":["http:\/\/weizn.net\/?p=55"]}]},{"@type":"BreadcrumbList","@id":"http:\/\/weizn.net\/?p=55#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\u9996\u9875","item":"http:\/\/weizn.net\/"},{"@type":"ListItem","position":2,"name":"\u5e73\u8861\u4e8c\u53c9\u6811"}]},{"@type":"Article","@id":"http:\/\/weizn.net\/?p=55#article","isPartOf":{"@id":"http:\/\/weizn.net\/?p=55#webpage"},"author":{"@id":"http:\/\/weizn.net\/#\/schema\/person\/e88bc12c590502d8b6249326f960b264"},"headline":"\u5e73\u8861\u4e8c\u53c9\u6811","datePublished":"2013-12-14T14:24:53+00:00","dateModified":"2013-12-14T14:24:53+00:00","mainEntityOfPage":{"@id":"http:\/\/weizn.net\/?p=55#webpage"},"wordCount":382,"commentCount":0,"publisher":{"@id":"http:\/\/weizn.net\/#\/schema\/person\/e88bc12c590502d8b6249326f960b264"},"image":{"@id":"http:\/\/weizn.net\/?p=55#primaryimage"},"thumbnailUrl":"http:\/\/pic002.cnblogs.com\/images\/2011\/330710\/2011111511570656.jpg","articleSection":["\u6570\u636e\u7ed3\u6784\u53ca\u7b97\u6cd5"],"inLanguage":"zh-Hans","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["http:\/\/weizn.net\/?p=55#respond"]}]},{"@type":["Person","Organization"],"@id":"http:\/\/weizn.net\/#\/schema\/person\/e88bc12c590502d8b6249326f960b264","name":"zinan","logo":{"@id":"http:\/\/weizn.net\/#personlogo"}}]}},"_links":{"self":[{"href":"http:\/\/weizn.net\/index.php?rest_route=\/wp\/v2\/posts\/55","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/weizn.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/weizn.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/weizn.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/weizn.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=55"}],"version-history":[{"count":0,"href":"http:\/\/weizn.net\/index.php?rest_route=\/wp\/v2\/posts\/55\/revisions"}],"wp:attachment":[{"href":"http:\/\/weizn.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=55"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/weizn.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=55"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/weizn.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=55"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}