@@ -55,6 +55,11 @@ def search_child(self, instance):
5555return self .childs [x ]
5656return self .childs [self .__size ]
5757
58+ def leaf_remove (self ,index ):
59+ if self .is_leaf :
60+ del self .keys [index ]
61+ self .__size -= 1
62+
5863
5964class BTree (object ):
6065"""
@@ -83,18 +88,25 @@ def insert(self, key):
8388self .__split (cur_node )
8489# 这个地方cur_node并没有被改变，所以是可以继续搜索的。
8590cur_node = cur_node .search_child (key )
86- print (key )
8791
8892left_node ,right_node = self .__split (cur_node )
8993if left_node is None or right_node is None :
9094# 返回None表示叶节点没有满
9195cur_node .append (key )
9296else :
93- if left_node .keys [- 1 ]< key :
97+ # 找到左右节点的共同关键字
98+ parent_key = None
99+ parent = left_node .parent
100+ for i in xrange (len (parent )):
101+ if parent .childs [i ]is left_node :
102+ parent_key = parent .keys [i ]
103+
104+ if parent_key <= key :
94105# 说明left_node中的所有节点都比key小，所以把新节点插入到右边
95106right_node .append (key )
96107else :
97108left_node .append (key )
109+
98110self .__size += 1
99111
100112def __split (self ,node ):
@@ -137,6 +149,11 @@ def __split(self, node):
137149return None ,None
138150
139151def search (self ,instance ):
152+ """
153+ 查找一个元素的位置，位置使用一个tuple表示，前面一个元素是Node，后面一个元素是元素的位置
154+ :param instance:
155+ :return:(Node, index)
156+ """
140157return self .__search (self .__root ,instance )
141158
142159def full (self ,node ):
@@ -156,7 +173,7 @@ def __search(cls, root, instance):
156173x = 0
157174while x < cur_len and cur_node .keys [x ]< instance :
158175x += 1
159- if cur_node .keys [x ]== instance :
176+ if x < cur_len and cur_node .keys [x ]== instance :
160177return cur_node ,x
161178elif cur_node .is_leaf :
162179return None ,None
@@ -183,7 +200,7 @@ def max(self):
183200cur_node = cur_node .childs [- 1 ]
184201return cur_node .keys [- 1 ]
185202
186- def midorder (self ,f ):
203+ def mid_order (self ,f ):
187204"""
188205 B树中序遍历
189206 :param f:
@@ -212,22 +229,191 @@ def midorder(self, f):
212229cur_node = cur_node .childs [0 ]
213230return result
214231
232+ def delete (self ,key ):
233+ """
234+ 删除一个关键字
235+ :param key:
236+ :return:
237+ """
238+ node ,index = self .search (key )
239+ if node is None :
240+ return False
241+
242+ return self .__delete (node ,index )
243+
244+ def __delete (self ,node ,index ):
245+ if node is None :
246+ return False
247+
248+ if node .is_leaf :
249+ self .__size -= 1
250+
251+ if self .will_starve (node ):
252+ # 检查是否能从兄弟节点借一个元素，会检查左右两个节点。如果不能从兄弟节点借，那么就只能和兄弟节点合并了
253+ change_index ,bro_node ,bro_index = self .__check_brother_borrow (node )
254+ if bro_node is None :
255+ del node .keys [index ]
256+
257+ self .__merge_brother (node )
258+ else :
259+ parent = node .parent
260+ node .keys [index ]= parent .keys [change_index ]
261+ parent .keys [change_index ]= bro_node .keys [bro_index ]
262+ bro_node .leaf_remove (bro_index )
263+ else :
264+ # 删除之后节点还是有效的B树节点，因此直接从B树中删除元素
265+ node .leaf_remove (index )
266+ else :
267+ # 如果节点删除发生在内部节点上，那么先把后继节点上的关键字移动到被删除的元素的位置上，然后把后继节点删除
268+ succ ,succ_index = self .__successor (node ,index )
269+ node .keys [index ]= succ .keys [succ_index ]
270+ # 因为调用了自己，所有并没有把size减一
271+ return self .__delete (succ ,succ_index )
272+ return True
273+
274+ def __successor (self ,node ,i ):
275+ """
276+ 查找在node的i处的节点的关键字的后继节点,位置使用一个元祖表示，前面的一个元素是node,后面的是index
277+ 如果返回None表示没有后继，也就是说是最大元素
278+ :param node:
279+ :param i:
280+ :return:(Node,index)|None
281+ """
282+ if not node .is_leaf :
283+ child_node = node .childs [i + 1 ]
284+ while not child_node .is_leaf :
285+ child_node = child_node .childs [0 ]
286+ return self .__successor (child_node ,- 1 )
287+ else :
288+ if i < len (node )- 1 :
289+ return node ,i + 1
290+ else :
291+ return None ,None
292+
293+ def will_starve (self ,node ):
294+ """
295+ 检查一个节点的元素是否小于load_factor,这样的话如果在删除一个关键字节点就不符合B树的节点定义了
296+ :param node:
297+ :return:
298+ """
299+ return len (node )< self .__load_factor
300+
301+ def successor (self ,key ):
302+ """
303+ 查找关键字的后继节点,位置使用一个元祖表示，前面的一个元素是node,后面的是index
304+ 如果返回None表示没有后继，也就是说是最大元素
305+ :param key:
306+ :return:(Node,index)|None
307+ """
308+ node ,index = self .search (key )
309+ if node is None :
310+ return None ,None
311+ return self .__successor (node ,index )
312+
215313def __str__ (self ):
216- return "\n " .join (self .midorder (lambda s :str (s )))
314+ return "\n " .join (self .mid_order (lambda s :str (s )))
315+
316+ def test (self ):
317+ node = self .successor ('0' )
318+ print (node )
319+
320+ def __check_brother_borrow (self ,node ):
321+ """
322+ 检查左右的兄弟节点是否能够借出节点
323+ int:父节点中交换元素的位置
324+ Node:要借出元素的节点
325+ int：借出元素的位置
326+
327+ 如果不能借出，那么返回(None,None,None)
328+ :param node:
329+ :return:(int,Node,int)|(None,None,None)
330+ """
331+ parent = node .parent
332+ node_index = - 1
333+ # 寻找node在parent的位置
334+ for i in xrange (len (parent .childs )):
335+ if parent .childs [i ]is node :
336+ node_index = i
217337
218- def processor (self ,key ):
219- pass
338+ # 先从左边的兄弟节点借
339+ if node_index >= 1 and not self .will_starve (parent .childs [node_index - 1 ]):
340+ return node_index - 1 ,parent .childs [node_index - 1 ],- 1
341+
342+ if node_index >= 0 and not self .will_starve (parent .childs [node_index + 1 ]):
343+ return node_index ,parent .childs [node_index + 1 ],0
344+
345+ return None ,None ,None
346+
347+ def __merge_brother (self ,node ):
348+ parent = node .parent
349+ if parent is self .__root and len (parent .keys )> 0 :
350+ return
351+
352+ node_index = - 1
353+ # 寻找node在parent的位置
354+ for i in xrange (len (parent .childs )):
355+ if parent .childs [i ]is node :
356+ node_index = i
357+
358+ # 合并只和长度较小的节点合并
359+ smaller_node = None
360+ is_left = True
361+ if node_index >= 1 :
362+ smaller_node = parent .childs [node_index - 1 ]
363+
364+ if node_index >= 0 and (smaller_node is None or len (smaller_node )> parent .childs [node_index + 1 ]):
365+ smaller_node = parent .childs [node_index + 1 ]
366+ is_left = False
367+
368+ # 只有在必要的时候才合并
369+ if len (smaller_node )< self .__load_factor - 1 or len (node )< self .__load_factor - 1 :
370+ if is_left :
371+ new_keys = smaller_node .keys
372+ new_keys .append (parent .keys [node_index - 1 ])
373+ new_keys .extend (node .keys )
374+ else :
375+ new_keys = node .keys
376+ new_keys .append (parent .keys [node_index - 1 ])
377+ new_keys .extend (smaller_node .keys )
378+
379+ new_childs = None
380+ if not node .is_leaf :
381+ if is_left :
382+ new_childs = smaller_node .childs
383+ new_childs .extend (node .childs )
384+ else :
385+ new_childs = node .childs
386+ new_childs .extend (smaller_node .childs )
387+
388+ new_node = Node (node .is_leaf ,new_keys ,new_childs ,parent )
389+
390+ # 从父节点中删除被拿到子节点的节点
391+ if is_left :
392+ del parent .childs [node_index - 1 ]
393+ del parent .keys [node_index - 1 ]
394+ parent .childs [node_index - 1 ]= new_node
395+ else :
396+ del parent .childs [node_index + 1 ]
397+ del parent .keys [node_index + 1 ]
398+ parent .childs [node_index ]= new_node
399+
400+ # 处理根节点,然后调用递归调用合并父节点
401+ if parent is self .__root and len (parent .keys ):
402+ new_node .parent = None
403+ self .__root = new_node
404+ else :
405+ self .__merge_brother (parent )
220406
221407
222408def main ():
223409import random
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' ]
410+ test = ['O' ,'J' ,'S' ,'Y' ,'C' ,'M' ,'B' ,'R' ,'N' ,'F' ,'L' ,'Z' ,'U' ,'Q' ,'A' ,'G' ,'V' ,'E' ,'D' ,'W' ,'I' ,
411+ 'H' ,'T' ,'K' ,'X' ,'P' ]
412+
226413random .shuffle (test )
227414btree = BTree (3 ,* test )
228- print btree .max ()
229- print btree .min ()
230- btree .test ()
415+ print (btree .delete ('O' ))
416+ print (btree )
231417
232418
233419if __name__ == "__main__" :
