delete node in binary search tree python

问题:

The code below is my implement for my binary search tree, and I want to implement delete method to remove the node. Below is my implementation, but when I perform

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

when I call delete method, it did nothing. Can someone help me to fix it. The link below is my code on github. Thank you so much for your help. 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, "")

回答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]

This might help. For complete code and better understanding go to For code Binary search Tree in Python

For explanation Notes on BST in Python As per my knowledge its working fine.