удалить узел в двоичном дереве поиска python

Question

Код ниже - это мое приложение для моего двоичного дерева поиска, и я хочу реализовать метод удаления для удаления узла. Ниже приводится моя реализация, но когда я выполняю

bst = BSTRee() 
bst.insert(5) 
bst.insert(11) 
bst.insert(3) 
bst.insert(4) 
bst.insert(12) 
bst.insert(2) 
bst.delete(3) 

Когда я вызываю метод удаления, он ничего не сделал. Может кто-нибудь помочь мне исправить это. Ниже приведен мой код на github. Большое вам спасибо за вашу помощь. https://github.com/hly189/sort/blob/master/tree/BST.py

class BSTreeNode 
    def ____init__(self, value): 
     self.value = value 
     self.left = None 
     self.right = None 

    def insert(self,key): 
     if self.value == key: 
      print ("the node already exists") 
      return False 
     elif self.value > key: 
      if self.left is not None: 
       return self.left.insert(key) 
      else: 
       self.left = BSTreeNode(key) 
       return True 
     else: 
      if self.right is not None: 
       return self.right.insert(key) 
      else: 
       self.right = BSTreeNode(key) 
       return False 

    def delete(self, node, k): 
      if node == None: 
       return None 
      elif node.value == k: 
       if node.left is None and node.right is None: 
       return None 
      elif node.left is None: 
       return node.right 
      elif node.right is None: 
       return node.left 
      else: 
       node.value = get_min(node.right) 
       node.right.delete(node.right,node.value) 
      elif k < node.value: 
       node.left.delete(node.left,k) 
      else: 
       node.right.delete(node.right,k) 
      return node 

class BSTree: 
    def __init__(self): 
      self.root = None 

    def delete(self,key): 
      self.root.delete(self.root,key) 

    def insert(self,data): 
      if self.root: 
       self.root.insert(data) 
      else: 
       self.root = BSTreeNode(data) 
       return True 
    def find_min(self,node): 
      current_node = node 
      while current_node.left: 
       current_node = current_node.left 
      return current_node 


def get_min(node): 
    current_node = node 
    while current_node.left: 
     current_node = current_node.left 
    return str(current_node.value) 

def print_helper(root, indent): 
    if root is not None: 
     print_helper(root.right, indent + " ") 
     print (indent + str(root.value)) 
     print_helper(root.left, indent + " ") 

def print_tree(root): 
    print_helper(root, "") 

Answer 1

def delete(self, key): 
    """ delete the node with the given key and return the 
    root node of the tree """ 

    if self.key == key: 
     # found the node we need to delete 

     if self.right and self.left: 

      # get the successor node and its parent 
      [psucc, succ] = self.right._findMin(self) 

      # splice out the successor 
      # (we need the parent to do this) 

      if psucc.left == succ: 
       psucc.left = succ.right 
      else: 
       psucc.right = succ.right 

      # reset the left and right children of the successor 

      succ.left = self.left 
      succ.right = self.right 

      return succ     

     else: 
      # "easier" case 
      if self.left: 
       return self.left # promote the left subtree 
      else: 
       return self.right # promote the right subtree 
    else: 
     if self.key > key:   # key should be in the left subtree 
      if self.left: 
       self.left = self.left.delete(key) 
      # else the key is not in the tree 

     else:      # key should be in the right subtree 
      if self.right: 
       self.right = self.right.delete(key) 

    return self 

def _findMin(self, parent): 
    """ return the minimum node in the current tree and its parent """ 

    # we use an ugly trick: the parent node is passed in as an argument 
    # so that eventually when the leftmost child is reached, the 
    # call can return both the parent to the successor and the successor 

    if self.left: 
     return self.left._findMin(self) 
    else: 
     return [parent, self] 

Это может помочь. Для полного кода и лучшего понимания перейти к Для кода Binary search Tree in Python

Для объяснения Notes on BST in Python По моим сведениям его работает отлично.