删除 BST 中有两个 children 的节点

Question

我已经实现了一个二叉搜索树，它工作正常，除了我必须删除一个有两个 children 的节点的情况。以下是我的删除方法代码：

def find(self, node):
        curr = node
        while curr.left is not None:
            curr = curr.left
        return curr

def delete(self, key):
        node_to_remove = self._search(key, self.root)
        if node_to_remove.left is None and node_to_remove.right is None:
            #Then we identify this as a leaf node
            if node_to_remove is node_to_remove.parent.left:
                #Setting the parent's reference to this to None
                node_to_remove.parent.left = None 
            elif node_to_remove is node_to_remove.parent.right:
                node_to_remove.parent.right = None
                
                
        #2nd Case --> Two child
        elif node_to_remove.left and node_to_remove.right:
            minimum = self.find(node_to_remove.right)
            node_to_remove = minimum
            self.delete(minimum.key)
            
        #3rd Case -> One child
        else:
            if node_to_remove.left:
                node_to_remove.left.parent = node_to_remove.parent
                node_to_remove.parent.left = node_to_remove.left
            elif node_to_remove.right:
                node_to_remove.right.parent = node_to_remove.parent
                node_to_remove.parent.right = node_to_remove.right

关于如何解决第二种情况的任何指标都将提供巨大帮助！

Answer 1

您需要获取更深的已删除节点的值并将其分配给具有两个子节点的节点。所以那个块应该是这样的：

    elif node_to_remove.left and node_to_remove.right:
        minimum = self.find(node_to_remove.right)
        self.delete(minimum.key)
        node_to_remove.key = minimum.key

其他备注

当根具有要删除的值并且它没有两个子项时，您的代码将运行进入异常。在这种情况下，您的代码想要访问根节点没有的父节点。此外，这样的删除应该导致 this.root.

的不同值

这是建议的更正：

    def delete(self, key):
        node_to_remove = self._search(key, self.root)
        if node_to_remove.left is None and node_to_remove.right is None:
            if node_to_remove is self.root:
                self.root = None
            elif node_to_remove is node_to_remove.parent.left:
                node_to_remove.parent.left = None 
            elif node_to_remove is node_to_remove.parent.right:
                node_to_remove.parent.right = None
                
                
        #2nd Case --> Two child
        elif node_to_remove.left and node_to_remove.right:
            minimum = self.find(node_to_remove.right)
            self.delete(minimum.key)
            node_to_remove.key = minimum.key
            
            
        #3rd Case -> One child
        else:
            if node_to_remove.left:
                node_to_remove.left.parent = node_to_remove.parent
                if node_to_remove is self.root:
                    self.root = node_to_remove.left
                else:
                    node_to_remove.parent.left = node_to_remove.left
            elif node_to_remove.right:
                node_to_remove.right.parent = node_to_remove.parent
                if node_to_remove is self.root:
                    self.root = node_to_remove.right
                else:
                    node_to_remove.parent.right = node_to_remove.right

第二个评论：你的树是线程化的（即它有 parent 个引用）。可以对 non-threaded 树执行此操作，而且代码更少。

删除 BST 中有两个 children 的节点

Deleting a node with two children in BST

binary-search-tree

data-structures

python-3.x

其他备注