Уже несколько недель у меня возникла проблема с алгоритмом удаления B-дерева, точнее, в функции слияния, и я не могу понять, как ее исправить...
Это полная функция удаления
class BTree:
def __init__(self, k, root):
self.L = (k/2) + 1
self.U = k + 1
self.root = root
def delete(self, value):
node = self.search(self.root, value)[0]
if node == None:
print("Value not found")
else:
if node.isLeaf:
node.removeKey(value)
if not self.respectMinKeys(node):
self.rebalanceTree(node)
else:
index = node.getKeys().index(value)
node.removeKey(value)
self.deleteFromInternalNode(node, index)
def deleteFromInternalNode(self, node, index):
inorder_predecessor = self.getPredecessor(node.getChildren()[index])
inorder_successor = self.getSuccessor(node.getChildren()[index+1])
if self.canBorrow(inorder_predecessor):
new_key = inorder_predecessor.getKeys().pop(-1)
node.insert(new_key)
else:
new_key = inorder_successor.getKeys().pop(0)
node.insert(new_key)
if node.getParent() == None:
self.root = node
if not self.respectMinKeys(inorder_successor):
self.rebalanceTree(inorder_successor)
def rebalanceTree(self, node):
parent = node.getParent()
siblings = parent.getChildren()
node_index = siblings.index(node)
if parent.getChildren().index(node) != 0 and self.canBorrow(siblings[node_index-1]):
neighbour_key = siblings[node_index-1].getKeys().pop(-1)
parent_key = parent.getKeys().pop(node_index-1)
parent.insert(neighbour_key)
node.insert(parent_key)
elif parent.getChildren().index(node) != (len(parent.getChildren()) - 1) and self.canBorrow(siblings[node_index+1]):
neighbour_key = siblings[node_index+1].getKeys().pop(0)
parent_key = parent.getKeys().pop(node_index)
node.insert(parent_key)
parent.insert(neighbour_key)
else:
if node_index !=0:
index = node_index-1
else:
index = node_index
parent_key = parent.getKeys().pop(index)
node.insert(parent_key)
self.mergeNodes(parent, index, index+1)
if not self.respectMinKeys(parent):
self.rebalanceTree(parent)
def mergeNodes(self, node, i, j):
children = node.getChildren()
children.getKeys().extend(children[j].getKeys())
if children.getChildren() != []:
self.migrateChildren(children, children[j])
node.children.pop(j)
if not self.respectMinKeys(node):
self.rebalanceTree(node)
def migrateChildren(self, providing_node, receiving_node):
if not self.respectNbChildren(receiving_node):
index = len(receiving_node.getChildren())-1
receiving_node.getChildren().extend(providing_node.getChildren())
self.mergeNodes(receiving_node, index, index+1)
def respectNbChildren(self, node):
return len(node.getKeys()) == len(node.getChildren()) - 1
def getPredecessor(self,node):
if node.isLeaf:
return node
return self.getPredecessor(node.getChildren()[-1])
def getSuccessor(self,node):
if node.isLeaf:
return node
return self.getSuccessor(node.getChildren()[0])
Ошибка следующая:
in mergeNodes
children.getKeys().extend(children[j].getKeys())
IndexError: list index out of range
Это код класса узла
class Node:
def __init__(self, keys, children, parent=None):
self.children = children
self.parent = parent
self.isLeaf = False
self.keys = keys
if len(self.children) == 0:
self.isLeaf = True
Я пробовал использовать разные подходы, чтобы исправить это, но каждый раз индекс все равно выходит за пределы диапазона.
Это код, который я вызываю< /p>
from Node import *
from BTree import *
import time
root = Node(keys=[], children=[])
tree = BTree(2, root)
values_to_insert = [2, 4, 5, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 7, 9, 11, 13]
values_to_delete = [14, 10, 20, 18, 16, 24, 6]
for value in values_to_insert:
tree.insert(value)
tree.graphviz(tree.getRoot())
for value in values_to_delete:
tree.delete(value)
print(value)
tree.graphviz(tree.getRoot())
И ошибка полного стека
14
10
20
Traceback (most recent call last):
File "C:\Users\louki\Desktop\S6\PROJET\projet-s6-g2-jlilou-loukili\files\displaytree1.py", line 15, in
tree.delete(value)
File "C:\Users\louki\Desktop\S6\PROJET\projet-s6-g2-jlilou-loukili\files\BTree.py", line 304, in delete
self.rebalanceTree(node)
File "C:\Users\louki\Desktop\S6\PROJET\projet-s6-g2-jlilou-loukili\files\BTree.py", line 345, in rebalanceTree
self.mergeNodes(parent, index, index+1)
File "C:\Users\louki\Desktop\S6\PROJET\projet-s6-g2-jlilou-loukili\files\BTree.py", line 351, in mergeNodes
children.getKeys().extend(children[j].getKeys())
IndexError: list index out of range
Подробнее здесь: https://stackoverflow.com/questions/782 ... n-a-b-tree
