이진 검색 트리 파이썬, 구현 구현

Question

파이썬에서 이진 검색 트리를 구현하려고하는데 삭제할 솔루션을 찾을 수 없습니다. 항목이 리프에 있으면 간단하지만 삭제하려는 항목에 다른 하위 항목이있는 2 명의 하위 항목이있는 경우 어떻게됩니까? 후임자를 어떻게 찾을 수 있습니까? 간단한 재귀 적 솔루션이 있습니까?

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

모두 삭제를 구현합니다. 둘 다 정렬 된 또는 정렬되지 않은 입력을 잘 처리합니다.

Red-Black 트리 모듈에는 RedBlackTree가 상속하는 BinaryTree 클래스가 있습니다.