使用Python编写B+树的删除操作代码

mid = int(math.ceil(parentNode.order / 2)) - 1 parentdash.values = parentNode.values[mid + 1:] parentdash.keys = parentNode.keys[mid + 1:] value_ = parentNode.values[mid] if (mid == 0): parentNode.values = parentNode.values[:mid + 1] else: parentNode.values = parentNode.values[:mid] parentNode.keys = parentNode.keys[:mid + 1] for j in parentNode.keys: j.parent = parentNode for j in parentdash.keys: j.parent = parentdash self.insert_in_parent(parentNode, value_, parentdash) # 删除节点 def delete(self, value, key): node_ = self.search(value) temp = 0 for i, item in enumerate(node_.values): if item == value: temp = 1 if key in node_.keys[i]: if len(node_.keys[i]) 1: node_.keys[i].pop(node_.keys[i].index(key)) elif node_ == self.root: node_.values.pop(i) node_.keys.pop(i) else: node_.keys[i].pop(node_.keys[i].index(key)) del node_.keys[i] node_.values.pop(node_.values.index(value)) self.deleteEntry(node_, value, key) else: print( Value not in Key ) return if temp == 0: print( Value not in Tree ) return # 删除条目 def deleteEntry(self, node_, value, key): if not node_.check_leaf: for i, item in enumerate(node_.keys): if item == key: node_.keys.pop(i) break for i, item in enumerate(node_.values): if item == value: node_.values.pop(i) break if self.root == node_ and len(node_.keys) == 1: self.root = node_.keys[0] node_.keys[0].parent = None del node_ return elif (len(node_.keys) int(math.ceil(node_.order / 2)) and node_.check_leaf == False) or (len(node_.values) int(math.ceil((node_.order - 1) / 2)) and node_.check_leaf == True): is_predecessor = 0 parentNode = node_.parent PrevNode = -1 NextNode = -1 PrevK = -1 PostK = -1 for i, item in enumerate(parentNode.keys): if item == node_: if i 0: PrevNode = parentNode.keys[i - 1] PrevK = parentNode.values[i - 1] if i len(parentNode.keys) - 1: NextNode = parentNode.keys[i + 1] PostK = parentNode.values[i] if PrevNode == -1: ndash = NextNode value_ = PostK elif NextNode == -1: is_predecessor = 1 ndash = PrevNode value_ = PrevK else: if len(node_.values) + len(NextNode.values) node_.order: ndash = NextNode value_ = PostK else: is_predecessor = 1 ndash = PrevNode value_ = PrevK if len(node_.values) + len(ndash.values) node_.order: if is_predecessor == 0: node_, ndash = ndash, node_ ndash.keys += node_.keys if not node_.check_leaf: ndash.values.append(value_) else: ndash.nextKey = node_.nextKey ndash.values += node_.values if not ndash.check_leaf: for j in ndash.keys: j.parent = ndash self.deleteEntry(node_.parent, value_, node_) del node_ else: if is_predecessor == 1: if not node_.check_leaf: ndashpm = ndash.keys.pop(-1) ndashkm_1 = ndash.values.pop(-1) node_.keys = [ndashpm] + node_.keys node_.values = [value_] + node_.values parentNode = node_.parent for i, item in enumerate(parentNode.values): if item == value_: p.values[i] = ndashkm_1 break else: ndashpm = ndash.keys.pop(-1) ndashkm = ndash.values.pop(-1) node_.keys = [ndashpm] + node_.keys node_.values = [ndashkm] + node_.values parentNode = node_.parent for i, item in enumerate(p.values): if item == value_: parentNode.values[i] = ndashkm break else: if not node_.check_leaf: ndashp0 = ndash.keys.pop(0) ndashk0 = ndash.values.pop(0) node_.keys = node_.keys + [ndashp0] node_.values = node_.values + [value_] parentNode = node_.parent for i, item in enumerate(parentNode.values): if item == value_: parentNode.values[i] = ndashk0 break else: ndashp0 = ndash.keys.pop(0) ndashk0 = ndash.values.pop(0) node_.keys = node_.keys + [ndashp0] node_.values = node_.values + [ndashk0] parentNode = node_.parent for i, item in enumerate(parentNode.values): if item == value_: parentNode.values[i] = ndash.values[0] break if not ndash.check_leaf: for j in ndash.keys: j.parent = ndash if not node_.check_leaf: for j in node_.keys: j.parent = node_ if not parentNode.check_leaf: for j in parentNode.keys: j.parent = parentNode