Python 官方文档:入门教程 => 点击学习
B树,和二叉搜索树很像,每个节点可以包含多个节点,但B树的子节点可以超过两个。 B树数据结构 B树可以在单个节点中存储许多键,并且可以有多个子节点。 B树搜索算法BtreeSearch(x,k) i=1 while i≤
B树,和二叉搜索树很像,每个节点可以包含多个节点,但B树的子节点可以超过两个。
B树可以在单个节点中存储许多键,并且可以有多个子节点。
BtreeSearch(x,k)
i=1
while i≤n[x]and k≥keyi[x]
do i=i+1
if i n[x]and k=keyi[x]
then return(x,i)
if leaf[x]
then return NIL
else
return BtreeSearch(ci[x],k)
指定K=17,从根节点开始,将k与根进行比较。
ķ>11,转到根的右子节点;比较k和16,因为>16,比较k和下一个键18。
由于k<18,k介于16和18之间。在16的右子节点或18左子节点中搜索,k被发现。
class BTreenode:
def __init__(self,leaf=False):
self.leaf=leaf
self.keys=[]
self.child=[]
class BTree:
def __init__(self,t):
self.root=BTreeNode(True)
self.t=t
def insert(self,k):
root=self.root
if len(root.keys)==(2*self.t)-1:
temp=BTreeNode()
self.root=temp
temp.child.insert(0,root)
self.split_child(temp,0)
self.insert_non_full(temp,k)
else:
self.insert_non_full(root,k)
def insert_non_full(self,x,k):
i=len(x.keys)-1
if x.leaf:
x.keys.append((None,None))
while i>=0 and k[0]<x.keys<i>[0]:
x.keys[i+1]=x.keys<i>
i-=1
x.keys[i+1]=k
else:
while i>=0 and k[0]<x.keys<i>[0]:
i-=1
i+=1
if len(x.child<i>.keys)==(2*self.t)-1:
self.split_child(x,i)
if k[0]>x.keys<i>[0]:
i+=1
self.insert_non_full(x.child<i>,k)
def split_child(self,x,i):
t=self.t
y=x.child<i>
z=BTreeNode(y.leaf)
x.child.insert(i+1,z)
x.keys.insert(i,y.keys[t-1])
z.keys=y.keys[t:(2*t)-1]
y.keys=y.keys[0:t-1]
if not y.leaf:
z.child=y.child[t:2*t]
y.child=y.child[0:t-1]
def print_tree(self,x,l=0):
print("Level",l,"",len(x.keys),end=":")
for i in x.keys:
print(i,end="")
print()
l+=1
if len(x.child)>0:
for i in x.child:
self.print_tree(i,l)
def search_key(self,k,x=None):
if x is not None:
i=0
while i<len(x.keys)and k>x.keys<i>[0]:
i+=1
if i<len(x.keys)and k==x.keys<i>[0]:
return(x,i)
elif x.leaf:
return None
else:
return self.search_key(k,x.child<i>)
else:
return self.search_key(k,self.root)
def main():
B=BTree(3)
for i in range(10):
B.insert((i,2*i))
B.print_tree(B.root)
if B.search_key(8)is not None:
print("\nFound")
else:
print("\nNot Found")
if __name__=='__main__':
main()
--结束END--
本文标题: 深入解析B树算法及其Python实现
本文链接: https://www.lsjlt.com/news/556637.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-03-01
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0