二進制搜索樹Python，實現刪除

Question

我想在python中實現一個二叉搜索樹，但我找不到刪除的解決方案。如果該項目在葉子中，那很簡單，但是如果我想要刪除的項目有兩個也有其他子項的子項，該怎麼辦？如何才能找到它的繼任者，以便我可以取代它？有沒有簡單的遞歸解決方案？

class Node: 

    def __init__(self, data=None, left=None, right=None): 
     self.data = data 
     self.left = left 
     self.right = right  


class BinarySearchTree: 


    def __init__(self, root=None): 
     self.root = Node(root) 


    def add(self, data, node): 

     if node == None: 
      node = Node(data) 
      return True 

     if data < node.data: 
      if node.left == None: 
       node.left = Node(data) 
       return True 
      else: 
       self.add(data, node.left) 
     elif data > node.data: 
      if node.right == None: 
       node.right = Node(data) 
       return True 
      else: 
       self.add(data, node.right) 


    def preorder(self, node): 
     if node != None: 
      print(node.data) 
      self.preorder(node.left) 
      self.preorder(node.right) 

    def inorder(self, node): 
     if node != None: 
      self.inorder(node.left) 
      print(node.data) 
      self.inorder(node.right) 

    def postorder(self, node): 
     if node != None: 
      self.postorder(node.left) 
      self.postorder(node.right) 
      print(node.data) 


    def retreive(self,item): 

     node = self.root 

     while node != None: 
      if node.data == item: 
       break 
      elif item < node.data: 
       if node.left != None: 
        if node.left.data == item: 
         node.left = None 
         return True 
       node = node.left 
      else: 
       if node.right != None: 
        if node.right.data == item: 
         node.right= None 
         return True 
       node = node.right 

     if node == None:     
      return False 

tree = BinarySearchTree() 
root=Node(3) 
tree.add(55,root) 
tree.add(5,root) 
tree.add(13,root) 
tree.add(2,root) 
tree.add(3,root) 
tree.preorder(root) 
tree.postorder(root) 
tree.inorder(root) 

此外，如果您對我迄今爲止撰寫的內容有任何建議，我會非常感激。提前致謝。

Answer 1

如果這不是功課，你可以使用其中的一個：

1. https://pypi.python.org/pypi/treap/
2. https://pypi.python.org/pypi/red-black-tree-mod

兩個都執行刪除操作。兩者都能很好地處理分類或未分類的輸入。

紅黑樹模塊有一個RedBlackTree繼承的BinaryTree類。