Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitc22487b

Browse files
author
ssjssh
committed
B树bugfix
1 parentb1d8411 commitc22487b

File tree

1 file changed

+62
-29
lines changed

1 file changed

+62
-29
lines changed

‎src/ssj/tree/BTree.py

Lines changed: 62 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -14,17 +14,16 @@ def __init__(self, is_leaf, keys, childs=None, parent=None):
1414
self.keys=list(sorted(keys))
1515
self.is_leaf=is_leaf
1616
self.__size=len(self.keys)
17-
ifchildsisNone:
18-
self.childs= [Noneforxinxrange(0,self.__size)]
19-
self.childs.append(None)
17+
ifnotself.is_leafandchildsisNone:
18+
self.childs= [Noneforxinxrange(0,self.__size+1)]
2019
else:
2120
self.childs=childs
2221
self.parent=parent
2322

2423
def__str__(self):
2524
return"".join(['Node(keys=',",".join(map(lambdakey:str(key),self.keys)),
26-
',leaf'ifself.is_leafelse',not leaf',
27-
',childs num=',str(len(self.childs)),')\n'])
25+
',Leaf'ifself.is_leafelse',Not Leaf',
26+
',childs num=','0'ifself.is_leafelsestr(len(self.childs)),')\n'])
2827

2928
def__len__(self):
3029
returnself.__size
@@ -35,13 +34,16 @@ def append(self, key):
3534
"""
3635
result=self.__size
3736
self.__size+=1
37+
3838
forxinxrange(0,result):
3939
ifself.keys[x]>key:
4040
self.keys.insert(x,key)
41-
self.childs.insert(x,None)
41+
ifnotself.is_leaf:
42+
self.childs.insert(x,None)
4243
returnx
4344
self.keys.append(key)
44-
self.childs.append(None)
45+
ifnotself.is_leaf:
46+
self.childs.append(None)
4547
returnresult
4648

4749
defsearch_child(self,instance):
@@ -63,23 +65,26 @@ def __init__(self, load_factor=4, *vargs):
6365
"""Constructor for BTree"""
6466
self.__root=None
6567
self.__load_factor=load_factor
66-
self.__size=len(vargs)
68+
self.__size=0
6769
map(self.insert,vargs)
6870

6971
definsert(self,key):
7072
"""
71-
节点插入的时候不需要再检测节点是不是满了，因为load_factor>=2，每次插入节点前调整都是使得节点关键字个数为load_factor-1。
72-
而插入一个关键字之后节点关键字个数是2*load_factor-1或者load_factor
73+
插入一个节点
7374
:param key:
7475
:return:
7576
"""
7677
ifself.__rootisNone:
7778
self.__root=Node(True, [key])
7879
return
80+
7981
cur_node=self.__root
8082
whilenotcur_node.is_leaf:
8183
self.__split(cur_node)
84+
# 这个地方cur_node并没有被改变，所以是可以继续搜索的。
8285
cur_node=cur_node.search_child(key)
86+
print(key)
87+
8388
left_node,right_node=self.__split(cur_node)
8489
ifleft_nodeisNoneorright_nodeisNone:
8590
# 返回None表示叶节点没有满
@@ -90,27 +95,41 @@ def insert(self, key):
9095
right_node.append(key)
9196
else:
9297
left_node.append(key)
98+
self.__size+=1
9399

94100
def__split(self,node):
101+
"""
102+
在节点满的时候分裂节点。要注意两个问题：
103+
1，根节点分裂的时候需要重新设置根节点
104+
2，叶节点是没有子节点的，一次要时刻判断
105+
:param node:
106+
:return:
107+
"""
95108
ifself.full(node):
96109
parent_node=node.parent
97110
middle_key=node.keys[self.__load_factor-1]
98111
ifparent_nodeisNone:
99112
# 处理根节点
100-
self.__root=Node(False, [])
101-
parent_node=self.__root
113+
parent_node=self.__root=Node(False, [])
114+
102115
parent_middle_index=parent_node.append(middle_key)
103-
left_node=Node(node.is_leaf,node.keys[:self.__load_factor-1],node.childs[:self.__load_factor],
116+
left_node=Node(node.is_leaf,node.keys[:self.__load_factor-1],
117+
Noneifnode.is_leafelsenode.childs[:self.__load_factor],
104118
parent_node)
105-
# 注意设定分裂节点的子节点的父指针
106-
forchildinleft_node.childs:
107-
ifchildisnotNone:
108-
child.parent=left_node
109-
right_node=Node(node.is_leaf,node.keys[self.__load_factor:],node.childs[self.__load_factor:],
119+
120+
right_node=Node(node.is_leaf,node.keys[self.__load_factor:],
121+
Noneifnode.is_leafelsenode.childs[self.__load_factor:],
110122
parent_node)
111-
forchildinright_node.childs:
112-
ifchildisnotNone:
113-
child.parent=right_node
123+
124+
# 注意设定分裂节点的子节点的父指针，因为如果node是叶节点，那么两个子节点肯定都是叶节点，反之同理
125+
ifnotnode.is_leaf:
126+
forchildinleft_node.childs:
127+
ifchildisnotNone:
128+
child.parent=left_node
129+
forchildinright_node.childs:
130+
ifchildisnotNone:
131+
child.parent=right_node
132+
114133
parent_node.childs[parent_middle_index]=left_node
115134
parent_node.childs[parent_middle_index+1]=right_node
116135
self.__root.is_leaf=False
@@ -125,6 +144,12 @@ def full(self, node):
125144

126145
@classmethod
127146
def__search(cls,root,instance):
147+
"""
148+
搜索树中节点
149+
:param root:
150+
:param instance:
151+
:return:
152+
"""
128153
cur_node=root
129154
whileTrue:
130155
cur_len=len(cur_node)
@@ -139,12 +164,20 @@ def __search(cls, root, instance):
139164
cur_node=cur_node.childs[x]
140165

141166
defmin(self):
167+
"""
168+
取出树中最小值
169+
:return:
170+
"""
142171
cur_node=self.__root
143172
whilenotcur_node.is_leaf:
144173
cur_node=cur_node.childs[0]
145174
returncur_node.keys[0]
146175

147176
defmax(self):
177+
"""
178+
取出树中最大值
179+
:return:
180+
"""
148181
cur_node=self.__root
149182
whilenotcur_node.is_leaf:
150183
cur_node=cur_node.childs[-1]
@@ -182,19 +215,19 @@ def midorder(self, f):
182215
def__str__(self):
183216
return"\n".join(self.midorder(lambdas:str(s)))
184217

185-
deftest(self):
186-
print"-"*20
187-
printself.__root
188-
printself.__root.childs[0]
189-
printself.__root.childs[1]
218+
defprocessor(self,key):
219+
pass
190220

191221

192222
defmain():
193-
btree=BTree(3,'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','R','S','T','U',
194-
'V','X','Y','Z')
195-
printbtree
223+
importrandom
224+
test= ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','R','S','T','U',
225+
'V','X','Y','Z']
226+
random.shuffle(test)
227+
btree=BTree(3,*test)
196228
printbtree.max()
197229
printbtree.min()
230+
btree.test()
198231

199232

200233
if__name__=="__main__":

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp