{"id":199646,"date":"2025-05-06T09:10:08","date_gmt":"2025-05-06T01:10:08","guid":{"rendered":"https:\/\/server.hk\/cnblog\/199646\/"},"modified":"2025-05-06T09:10:08","modified_gmt":"2025-05-06T01:10:08","slug":"python%e5%ae%9e%e7%8e%b0b%e6%a0%91%e7%ae%97%e6%b3%95%e8%af%a6%e7%bb%86%e8%a7%a3%e6%9e%90","status":"publish","type":"post","link":"https:\/\/server.hk\/cnblog\/199646\/","title":{"rendered":"Python\u5b9e\u73b0B\u6811\u7b97\u6cd5\u8be6\u7ec6\u89e3\u6790"},"content":{"rendered":"<p><b><\/b> <\/p>\n<h1>Python\u5b9e\u73b0B\u6811\u7b97\u6cd5\u8be6\u7ec6\u89e3\u6790<\/h1>\n<p>\u4f60\u5728\u5b66\u4e60\u76f8\u5173\u7684\u77e5\u8bc6\u5417\uff1f\u672c\u6587\uff0c\u4e3b\u8981\u4ecb\u7ecd\u7684\u5185\u5bb9\u5c31\u6d89\u53ca\u5230\uff0c\u5982\u679c\u4f60\u60f3\u63d0\u5347\u81ea\u5df1\u7684\u5f00\u53d1\u80fd\u529b\uff0c\u5c31\u4e0d\u8981\u9519\u8fc7\u8fd9\u7bc7\u6587\u7ae0\uff0c\u5927\u5bb6\u8981\u77e5\u9053\u7f16\u7a0b\u7406\u8bba\u57fa\u7840\u548c\u5b9e\u6218\u64cd\u4f5c\u90fd\u662f\u4e0d\u53ef\u6216\u7f3a\u7684\u54e6\uff01<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/www.17golang.com\/uploads\/20240201\/170674596365bae06b1a9bb.jpg\" class=\"aligncenter\"><\/p>\n<p>B\u6811\uff0c\u548c\u4e8c\u53c9\u641c\u7d22\u6811\u5f88\u50cf\uff0c\u6bcf\u4e2a\u8282\u70b9\u53ef\u4ee5\u5305\u542b\u591a\u4e2a\u8282\u70b9\uff0c\u4f46B\u6811\u7684\u5b50\u8282\u70b9\u53ef\u4ee5\u8d85\u8fc7\u4e24\u4e2a\u3002<\/p>\n<h3>B\u6811\u6570\u636e\u7ed3\u6784<\/h3>\n<p>B\u6811\u53ef\u4ee5\u5728\u5355\u4e2a\u8282\u70b9\u4e2d\u5b58\u50a8\u8bb8\u591a\u952e\uff0c\u5e76\u4e14\u53ef\u4ee5\u6709\u591a\u4e2a\u5b50\u8282\u70b9\u3002<\/p>\n<h3>B\u6811\u641c\u7d22\u7b97\u6cd5<\/h3>\n<pre>BtreeSearch(x,k)\r\n  i=1\r\n  while i\u2264n[x]and k\u2265keyi[x]\r\n      do i=i+1\r\n  if i n[x]and k=keyi[x]\r\n      then return(x,i)\r\n  if leaf[x]\r\n      then return NIL\r\n  else\r\n      return BtreeSearch(ci[x],k)<\/pre>\n<h3>B\u6811\u641c\u7d22\u793a\u4f8b<\/h3>\n<p>\u6307\u5b9aK=17\uff0c\u4ece\u6839\u8282\u70b9\u5f00\u59cb\uff0c\u5c06k\u4e0e\u6839\u8fdb\u884c\u6bd4\u8f83\u3002<\/p>\n<p>\u0137&gt;11\uff0c\u8f6c\u5230\u6839\u7684\u53f3\u5b50\u8282\u70b9\uff1b\u6bd4\u8f83k\u548c16\uff0c\u56e0\u4e3a&gt;16\uff0c\u6bd4\u8f83k\u548c\u4e0b\u4e00\u4e2a\u952e18\u3002<\/p>\n<p>\u7531\u4e8ek&lt;18\uff0ck\u4ecb\u4e8e16\u548c18\u4e4b\u95f4\u3002\u572816\u7684\u53f3\u5b50\u8282\u70b9\u621618\u5de6\u5b50\u8282\u70b9\u4e2d\u641c\u7d22\uff0ck\u88ab\u53d1\u73b0\u3002<\/p>\n<h3>Python\u5b9e\u73b0B\u6811<\/h3>\n<pre>class BTreeNode:\r\n   def __init__(self,leaf=False):\r\n   self.leaf=leaf\r\n   self.keys=[]\r\n   self.child=[]\r\n\r\nclass BTree:\r\n   def __init__(self,t):\r\n   self.root=BTreeNode(True)\r\n   self.t=t\r\n\r\ndef insert(self,k):\r\n   root=self.root\r\n   if len(root.keys)==(2*self.t)-1:\r\n      temp=BTreeNode()\r\n      self.root=temp\r\n      temp.child.insert(0,root)\r\n      self.split_child(temp,0)\r\n      self.insert_non_full(temp,k)\r\n   else:\r\n      self.insert_non_full(root,k)\r\n\r\ndef insert_non_full(self,x,k):\r\n   i=len(x.keys)-1\r\n   if x.leaf:\r\n      x.keys.append((None,None))\r\n      while i&amp;gt;=0 and k[0]&amp;lt;x.keys&lt;i&gt;[0]:\r\n         x.keys[i+1]=x.keys&lt;i&gt;\r\n         i-=1\r\n      x.keys[i+1]=k\r\n   else:\r\n      while i&amp;gt;=0 and k[0]&amp;lt;x.keys&lt;i&gt;[0]:\r\n      i-=1\r\n      i+=1\r\n   if len(x.child&lt;i&gt;.keys)==(2*self.t)-1:\r\n      self.split_child(x,i)\r\n   if k[0]&amp;gt;x.keys&lt;i&gt;[0]:\r\n      i+=1\r\n   self.insert_non_full(x.child&lt;i&gt;,k)\r\n\r\ndef split_child(self,x,i):\r\n   t=self.t\r\n   y=x.child&lt;i&gt;\r\n   z=BTreeNode(y.leaf)\r\n   x.child.insert(i+1,z)\r\n   x.keys.insert(i,y.keys[t-1])\r\n   z.keys=y.keys[t:(2*t)-1]\r\n   y.keys=y.keys[0:t-1]\r\n   if not y.leaf:\r\n      z.child=y.child[t:2*t]\r\n      y.child=y.child[0:t-1]\r\n\r\ndef print_tree(self,x,l=0):\r\n   print(\"Level\",l,\"\",len(x.keys),end=\":\")\r\n   for i in x.keys:\r\n   print(i,end=\"\")\r\n   print()\r\n   l+=1\r\n   if len(x.child)&amp;gt;0:\r\n      for i in x.child:\r\n         self.print_tree(i,l)\r\n\r\ndef search_key(self,k,x=None):\r\n   if x is not None:\r\n      i=0\r\n      while i&amp;lt;len(x.keys)and k&amp;gt;x.keys&lt;i&gt;[0]:\r\n      i+=1\r\n   if i&amp;lt;len(x.keys)and k==x.keys&lt;i&gt;[0]:\r\n      return(x,i)\r\n   elif x.leaf:\r\n      return None\r\n   else:\r\n      return self.search_key(k,x.child&lt;i&gt;)\r\n   else:\r\n      return self.search_key(k,self.root)\r\n\r\ndef main():\r\n   B=BTree(3)\r\n   for i in range(10):\r\n        B.insert((i,2*i))\r\n\r\n   B.print_tree(B.root)\r\n\r\n   if B.search_key(8)is not None:\r\n      print(\"\\nFound\")\r\n   else:\r\n      print(\"\\nNot Found\")\r\n\r\nif __name__=='__main__':\r\n   main()<\/pre>\n<p>\u6587\u4e2d\u5173\u4e8eB\u6811\u7684\u6982\u5ff5\u7684\u77e5\u8bc6\u4ecb\u7ecd\uff0c\u5e0c\u671b\u5bf9\u4f60\u7684\u5b66\u4e60\u6709\u6240\u5e2e\u52a9\uff01\u82e5\u662f\u53d7\u76ca\u532a\u6d45\uff0c\u90a3\u5c31\u52a8\u52a8\u9f20\u6807\u6536\u85cf\u8fd9\u7bc7\u300aPython\u5b9e\u73b0B\u6811\u7b97\u6cd5\u8be6\u7ec6\u89e3\u6790\u300b\u6587\u7ae0\u5427\uff0c\u4e5f\u53ef\u5173\u6ce8\u4e3b\u673a\u5b9d\u8d1d\u516c\u4f17\u53f7\u4e86\u89e3\u76f8\u5173\u6280\u672f\u6587\u7ae0\u3002<\/p>\n<p> \u7248\u672c\u58f0\u660e \u672c\u6587\u8f6c\u8f7d\u4e8e\uff1a\u7f51\u6613\u4f0f\u7fb2 \u5982\u6709\u4fb5\u72af\uff0c\u8bf7\u8054\u7cfb \u5220\u9664 <\/p>\n<dl>\n<dt>\n <\/dt>\n<\/dl>\n","protected":false},"excerpt":{"rendered":"<p>Python\u5b9e\u73b0B\u6811\u7b97\u6cd5\u8be6\u7ec6\u89e3\u6790&#46;&#46;&#46;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[101],"tags":[],"class_list":["post-199646","post","type-post","status-publish","format-standard","hentry","category-database"],"_links":{"self":[{"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/posts\/199646","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/comments?post=199646"}],"version-history":[{"count":0,"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/posts\/199646\/revisions"}],"wp:attachment":[{"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/media?parent=199646"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/categories?post=199646"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/tags?post=199646"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}