在python中的二进制搜索树中实现删除时出现问题

Question

我已经实现了二进制搜索树的删除功能。其思想是声明一个私有函数，该函数使用一个额外的参数将self.root抽象为root。在私有删除功能中，它将进行条件检查，并确保root等于需要删除的数据。在条件检查之后，我写下了3个不同的删除案例。编译代码时没有错误消息，也没有删除任何插入的节点。

class Node(object):
def __init__(self, data, left=None, right=None, parent=None):
self.left = left  
self.data = data
self.right = right   

class Tree(object):
def __init__(self):
self.root = Node(None)
def delete(self,newData):
if self.root.data == None:
print 'The tree is empty'
else:
self.__delete(self.root, newData)
def __delete(self, root, newData):
# if newData smaller than root.data, change root to root.left, recursive call
if newData < root.data:
if root.left:
self.__delete(root.left, newData)
else:
return False
# if newData larger than root.data, change root to root.right, recursive call
elif newData > root.data:
if root.right:
self.__delete(root.right, newData)
else:
return False
elif newData == root.data:
#case 1, root has no child
if root.left is None and root.right is None:
root = None
#case 2, root has one child (left)
elif root.left is not None and root.right is None:
root.data = root.left.data
root.left = None
#case 3, root has one child (right)
elif root.right is not None and root.left is None:
root.data = root.right.data
root.right = None
#case 4, root has both children,
# find the smallest node in the right subtree, and swipe value
# delete smallest node in the right subtree
else:
root.data = self.__minValueToRightSubtree(root.right).data
self.__deleteMinValueToRightSubtree(root.right)
else:
print "Can't find this number"
def __minValueToRightSubtree(self, root):
if root.left is None:
return root
else:
return self.__minValueToRightSubtree(root.left)
def __deleteMinValueToRightSubtree(self, root):
if root.left is None:
root = None
return root
else:
self.__minValueToRightSubtree(root.left)

Answer 1

不幸的是，递归函数的基本情况都不能正常工作。有两种错误(每个错误重复两次，有一些变化)：

第一个问题很简单。在情况2和3中，您将从单个子节点复制数据，然后删除对该节点的引用。但是，如果子节点有自己的子节点，这将不会起到正确的作用。如果你的树保证是平衡的，也许你可以假设它没有孩子，但对于一般的BST，你不能假设。更好的版本是：

#case 2, root has one child (left)
elif root.left is not None and root.right is None:
root.data = root.left.data
root.right = root.left.right
root.left = root.left.left
#case 3, root has one child (right)
elif root.right is not None and root.left is None:
root.data = root.right.data
root.left = root.left.left
root.right = root.left.right

另一个问题更为微妙。问题是，不能像在情况1中(以及在__deleteMinValueToRightSubtreehelper方法中的情况4)那样删除root。您将None分配给root，如果Python以C++和Java相同的方式传递参数(通过引用)，这可能会起作用。但是Python做参数的方式与那些语言不同。Python参数是"通过赋值"传递的，这意味着函数中的参数是一个局部变量，绑定到调用方传入的同一对象。当您执行root = None时，您只修改了局部变量，而不是树结构。

有多种方法可以解决此问题。哪种方式最好取决于您实现的其他细节。

如果Node对象具有parent引用，则可以使用这些引用来取消节点与其父节点的链接(尽管对于没有父节点的根节点需要特殊情况)。我看到Node构造函数的一个parent参数，但你似乎没有使用它。如果你把它连接起来，删除节点的代码会相对容易。

#case 1, root has no child
if root.left is None and root.right is None
if root.parent is None: # root is the root node of the whole tree
self.root = None
elif root.parent.left is root:
root.parent.left = None
else: # elif root.parent.right is root:
root.parent.right = None
#...
#case 4, root has both children,
# find the smallest node in the right subtree, and swipe value
# delete smallest node in the right subtree
else:
min_right_node = self.__minValueToRightSubtree(root.right)
root.data = min_right_node.data       # no need to recurse twice
if min_right_node is self.right:      # we can use the same node reference for
self.right = None                 # both steps (swiping value and deleting)
else:
min_right_node.parent.left = min_right_node.right

如果你没有父链接，你可以改变递归的逻辑，这样你就可以return一个修改过的树，调用方将其分配给它正在递归的节点。这将需要你改变错误处理，因为返回值被用来表示成功或失败。如果找不到目标，我建议提出一个例外。

def delete(self,newData):
if self.root.data == None: # should this be testing `self.root is None`?
print 'The tree is empty'
else:
self.root = self.__delete(self.root, newData) # use return value
def __delete(self, root, newData):
# if newData smaller than root.data, change root to root.left, recursive call
if newData < root.data:
if root.left:
root.left = self.__delete(root.left, newData)
else:
raise ValueError("Can't find this number")
# if newData larger than root.data, change root to root.right, recursive call
elif newData > root.data:
if root.right:
root.right = self.__delete(root.right, newData)
else:
raise ValueError("Can't find this number")
elif newData == root.data:
#case 1, root has no child
if root.left is None and root.right is None:
return None
#case 2, root has one child (left)
elif root.left is not None and root.right is None:
return root.left
#case 3, root has one child (right)
elif root.right is not None and root.left is None:
return root.right
#case 4, root has both children,
# find the smallest node in the right subtree, and swipe value
# delete smallest node in the right subtree
else:
root.right, root.data = __delete_min(root.right)
return root
else:
print "Can't find this number"
def __delete_min(self, root): # returns a (node, minimum value) 2-tuple
if root.left is None:
return root.right, root.data
else:
root.left, minval = self.__delete_min(root.left)
return root, minval

关于命名的最后一句话：对私有函数使用双下划线名称是个坏主意。该语法调用Python的"名称篡改"系统，该系统将名称转换为引用定义引用它们的代码的类。当您在编写mixin或代理类时，它很有用，而且您无法提前知道哪些属性可能会发生冲突。不过，对于普通代码来说，这只会让事情变得烦人。如果要将一个方法标记为private，只需使用一个前导下划线。这在语言层面上没有任何作用，但这是一种惯例。其他程序员(和文档工具)会知道，以这种方式命名的函数不是公共API的一部分。(另一个可能较弱的约定是，对于大多数变量和方法，使用lowercase_names_with_underscores而不是camelCaseNames。这更多的是一个风格问题，而不是像名称篡改那样对使用代码有害的问题。)