在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 

另一个问题是更微妙的。问题是，你无法删除root你在第1种情况下要做的方式（以及__deleteMinValueToRightSubtree帮助方法中的情况4）。您正在将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或代理类时非常有用，并且您无法提前知道哪些属性可能会发生冲突。对于普通的代码，它只是让事情变得烦人。如果你想将一个方法标记为私有，只需使用一个前导下划线。这在语言层面上没有做任何事情，但这是一个惯例。其他程序员（以及文档工具）会知道以这种方式命名的函数不是公共API的一部分。 （另一个或许更弱的惯例是对大多数变量和方法使用lowercase_names_with_underscores而不是camelCaseNames。这更像是一个样式问题，而不是那些实际上对使用代码有害的东西，比如名称可能会变成这样。）