在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。這更像是一個樣式問題，而不是那些實際上對使用代碼有害的東西，比如名稱可能會變成這樣。）