删除最小二叉搜索树 Python
Delete min binary search tree Python
我试图从 BST 中删除最小节点，所以我在树中搜索直到找到最小节点（当 root.leftnode 为 None 时），然后设置 root.rightnode到根本身以继续 BST。
问题是当我在执行此操作后检查树时，它没有显示曾经发生过删除。
有人能给我指出正确的方向吗，我们将不胜感激。
class node():
def __init__(self, key, data):
self.data = data
self.key = key
self.leftnode = None
self.rightnode = None
self.count = 1
class binarysearch():
def __init__(self):
self.size = 0
self.rootnode = None
def insert(self, key, data):
if self.rootnode is None:
self.rootnode = node(key, data)
else:
self.insertnode(self.rootnode, key, data)
def getroot(self):
return self.rootnode
def insertnode(self, root, key, data):
if root.key == key:
root.data = data
elif key < root.key:
if root.leftnode is None:
root.leftnode = node(key, data)
else:
self.insertnode(root.leftnode, key, data)
else:
if root.rightnode is None:
root.rightnode = node(key, data)
else:
self.insertnode(root.rightnode, key, data)
root.count = 1 + self.sizenode(root.leftnode) + self.sizenode(root.rightnode)
def inorder(self, root):
if root is not None:
self.inorder(root.leftnode)
print(root.key)
self.inorder(root.rightnode)
def deletemin(self):
if self.rootnode is None:
print("No nodes exist")
else:
self.deleteminnode(self.rootnode.leftnode)
def deleteminnode(self, root):
if root.leftnode is not None:
self.deleteminnode(root.leftnode)
else:
print (root.key, "deleted")
root = root.rightnode
if __name__ == '__main__':
a = binarysearch()
a.insert(7,7)
a.insert(1,1)
a.insert(8,8)
a.insert(3,3)
a.insert(9,9)
a.insert(2,2)
a.insert(4,4)
a.insert(11,11)
a.insert(10,10)
a.deletemin()
a.getnodes()
可以找到树中的所有节点，连同到该节点的路径，找到结果中的最小值，然后遍历生成的路径删除该节点：
class Tree:
def __init__(self, **kwargs):
self.__dict__ = {i:kwargs.get(i) for i in ['val', 'left', 'right']}
def get_nodes(self, current = []):
yield [''.join(current), self.val]
yield from getattr(self.right, 'get_nodes', lambda _:[])(current+['1'])
yield from getattr(self.left, 'get_nodes', lambda _:[])(current+['0'])
def __iter__(self):
yield self.val
yield from [[], self.left][bool(self.left)]
yield from [[], self.right][bool(self.right)]
def _insert_back(self, _v):
if not self.val:
self.val = _v
else:
if _v < self.val:
getattr(self.left, '_insert_back', lambda x:setattr(x, 'left', Tree(val=x)))(_v)
else:
getattr(self.right, '_insert_back', lambda x:setattr(x, 'right', Tree(val=x)))(_v)
def remove(self, _path, _to_val, last=None):
'''_to_val: if _to_val is None, then the item is removed. If not, the node value is set to _to_val'''
if _path:
getattr(self, ['left', 'right'][int(_path[0])]).remove(_path[1:], _to_val, last = self)
else:
if _to_val is None:
last.left = None
last.right = None
for i in [[], self.left][bool(self.left)]:
last._insert_back(i)
for i in [[], self.right][bool(self.right)]:
last._insert_back(i)
else:
self.val = _to_val
正在创建：
7
5 9
4 6 8 10
12
t = Tree(val = 7, left=Tree(val = 5, left=Tree(val=4), right=Tree(val=6)), right=Tree(val=9, left=Tree(val=8), right=Tree(val=10, right=Tree(val=12))))
path, _to_remove = min(t.get_nodes(), key=lambda x:x[-1])
print(f'Removing {_to_remove}')
t.remove(path, None)
print([i for i in t])
输出：
4
[7, 5, 9, 8, 10, 12]
您遇到的问题是 root = root.rightnode 仅重新绑定局部变量 root。它不会更改您引用该节点的其他地方（例如它在树中的 parent）。
要解决此问题，您需要更改递归函数的工作方式。与其期望它在最后一次调用中完成所有工作，不如 return 应该是其 parent 左节点的值。那将是节点本身，但对于最小节点，它将是它的右边 child 而不是。
def deletemin(self):
if self.rootnode is None:
print("No nodes exist")
else:
self.rootnode = self.deleteminnode(self.rootnode)
def deleteminnode(self, root):
if root.leftnode is not None:
root.leftnode = self.deleteminnode(root.leftnode)
return root
else:
return root.rightnode
关于名称的最后一点说明：使用 root 作为树中随机节点的名称有点奇怪。通常一棵树只有一个根节点，其他节点不称为 root，因为它们有 parent。不幸的是，最常规的名称 node 已被用于您的节点 class。通常classes应该给CapitalizedNames，这样lowercase_names就可以独占引用实例和其他变量。不过这只是惯例（像 list 这样的内置类型违反了规则）。如果您使用标准名称样式，其他人可能更容易理解您的代码，但 Python 不强制执行它们。它将允许您使用任何您想要的名称。即使名称 self 也不是必需的，但如果您在没有充分理由的情况下为方法的第一个参数使用不同的东西，这会非常混乱（一个很好的理由的例子：classmethods and metaclasses 的方法通常使用 cls 作为第一个参数的名称，因为 object 将是 class).
我试图从 BST 中删除最小节点，所以我在树中搜索直到找到最小节点（当 root.leftnode 为 None 时），然后设置 root.rightnode到根本身以继续 BST。
问题是当我在执行此操作后检查树时，它没有显示曾经发生过删除。
有人能给我指出正确的方向吗，我们将不胜感激。
class node():
def __init__(self, key, data):
self.data = data
self.key = key
self.leftnode = None
self.rightnode = None
self.count = 1
class binarysearch():
def __init__(self):
self.size = 0
self.rootnode = None
def insert(self, key, data):
if self.rootnode is None:
self.rootnode = node(key, data)
else:
self.insertnode(self.rootnode, key, data)
def getroot(self):
return self.rootnode
def insertnode(self, root, key, data):
if root.key == key:
root.data = data
elif key < root.key:
if root.leftnode is None:
root.leftnode = node(key, data)
else:
self.insertnode(root.leftnode, key, data)
else:
if root.rightnode is None:
root.rightnode = node(key, data)
else:
self.insertnode(root.rightnode, key, data)
root.count = 1 + self.sizenode(root.leftnode) + self.sizenode(root.rightnode)
def inorder(self, root):
if root is not None:
self.inorder(root.leftnode)
print(root.key)
self.inorder(root.rightnode)
def deletemin(self):
if self.rootnode is None:
print("No nodes exist")
else:
self.deleteminnode(self.rootnode.leftnode)
def deleteminnode(self, root):
if root.leftnode is not None:
self.deleteminnode(root.leftnode)
else:
print (root.key, "deleted")
root = root.rightnode
if __name__ == '__main__':
a = binarysearch()
a.insert(7,7)
a.insert(1,1)
a.insert(8,8)
a.insert(3,3)
a.insert(9,9)
a.insert(2,2)
a.insert(4,4)
a.insert(11,11)
a.insert(10,10)
a.deletemin()
a.getnodes()
可以找到树中的所有节点，连同到该节点的路径，找到结果中的最小值，然后遍历生成的路径删除该节点：
class Tree:
def __init__(self, **kwargs):
self.__dict__ = {i:kwargs.get(i) for i in ['val', 'left', 'right']}
def get_nodes(self, current = []):
yield [''.join(current), self.val]
yield from getattr(self.right, 'get_nodes', lambda _:[])(current+['1'])
yield from getattr(self.left, 'get_nodes', lambda _:[])(current+['0'])
def __iter__(self):
yield self.val
yield from [[], self.left][bool(self.left)]
yield from [[], self.right][bool(self.right)]
def _insert_back(self, _v):
if not self.val:
self.val = _v
else:
if _v < self.val:
getattr(self.left, '_insert_back', lambda x:setattr(x, 'left', Tree(val=x)))(_v)
else:
getattr(self.right, '_insert_back', lambda x:setattr(x, 'right', Tree(val=x)))(_v)
def remove(self, _path, _to_val, last=None):
'''_to_val: if _to_val is None, then the item is removed. If not, the node value is set to _to_val'''
if _path:
getattr(self, ['left', 'right'][int(_path[0])]).remove(_path[1:], _to_val, last = self)
else:
if _to_val is None:
last.left = None
last.right = None
for i in [[], self.left][bool(self.left)]:
last._insert_back(i)
for i in [[], self.right][bool(self.right)]:
last._insert_back(i)
else:
self.val = _to_val
正在创建：
7
5 9
4 6 8 10
12
t = Tree(val = 7, left=Tree(val = 5, left=Tree(val=4), right=Tree(val=6)), right=Tree(val=9, left=Tree(val=8), right=Tree(val=10, right=Tree(val=12))))
path, _to_remove = min(t.get_nodes(), key=lambda x:x[-1])
print(f'Removing {_to_remove}')
t.remove(path, None)
print([i for i in t])
输出：
4
[7, 5, 9, 8, 10, 12]
您遇到的问题是 root = root.rightnode 仅重新绑定局部变量 root。它不会更改您引用该节点的其他地方（例如它在树中的 parent）。
要解决此问题，您需要更改递归函数的工作方式。与其期望它在最后一次调用中完成所有工作，不如 return 应该是其 parent 左节点的值。那将是节点本身，但对于最小节点，它将是它的右边 child 而不是。
def deletemin(self):
if self.rootnode is None:
print("No nodes exist")
else:
self.rootnode = self.deleteminnode(self.rootnode)
def deleteminnode(self, root):
if root.leftnode is not None:
root.leftnode = self.deleteminnode(root.leftnode)
return root
else:
return root.rightnode
关于名称的最后一点说明：使用 root 作为树中随机节点的名称有点奇怪。通常一棵树只有一个根节点，其他节点不称为 root，因为它们有 parent。不幸的是，最常规的名称 node 已被用于您的节点 class。通常classes应该给CapitalizedNames，这样lowercase_names就可以独占引用实例和其他变量。不过这只是惯例（像 list 这样的内置类型违反了规则）。如果您使用标准名称样式，其他人可能更容易理解您的代码，但 Python 不强制执行它们。它将允许您使用任何您想要的名称。即使名称 self 也不是必需的，但如果您在没有充分理由的情况下为方法的第一个参数使用不同的东西，这会非常混乱（一个很好的理由的例子：classmethods and metaclasses 的方法通常使用 cls 作为第一个参数的名称，因为 object 将是 class).