Python BST节点删除函数异常：误删多节点及重复附加问题排查

问题现象 #

• 删除值45时，误删了45、30、20三个节点
• 删除值40时，未删除目标节点40，反而删除了40之后的所有节点，并重复附加30、20、45节点

问题定位 #

调试发现以下代码段是删除45时误删20和30的直接原因：

if node.right is None and node.left is None:
    pn.right = None
    pn.left = None

相关函数实现 #

删除根节点函数 remove_start_node #

def remove_start_node(self) -> bool:
    """
    删除BST的根节点。首先检查BST是否为空，或者是否只有根节点存在。
    如果为空，返回False；如果只有根节点，直接删除根节点；
    否则，找到根节点的中序后继（右子树的最左子节点）。
    如果被删除的节点只有左子树，左节点成为子树的根节点。
    """
    if self._root is None:
        return False
    if self._root.left is None and self._root.right is None:
        self._root = None
    elif self._root.right is None:  # 检查是否只有左子树存在
        self._root = self._root.left
    else:
        subtree = self._root.right
        par_tree = subtree
        while subtree.left is not None:  # 遍历找到中序后继（最左子节点）
            par_tree = subtree
            subtree = subtree.left
        if subtree != self._root.right:  # 重建树结构
            par_tree.left = subtree.right
            subtree.right = self._root.right
        subtree.left = self._root.left
        self._root = subtree
    return True

删除普通节点函数 remove #

def remove(self, value) -> bool:
    """
    遍历BST并删除目标值，同时重建BST结构。
    首先检查BST是否为空、是否只有一个节点，以及值是否存在于BST中。
    如果为空，返回False；如果只有一个节点，删除根节点；否则，找到当前节点的中序后继（当前节点右子树的最左子节点）。
    如果被删除的节点只有左子树，当前节点成为左子树的根节点。
    """
    if not self.contains(value):  # 检查值是否存在
        return False
    if self._root is None:  # 检查BST是否为空
        return False
    if self._root.value == value:  # 检查值是否匹配根节点
        self.remove_start_node()
        return True

    # 遍历树直到找到目标值
    x = self._root
    pn = None
    while x is not None:  # 遍历树
        if x.value == value:
            node = x
            break
        elif value < x.value:
            pn = x
            x = x.left
        else:
            pn = x
            x = x.right

    # 如果后继节点没有子节点，将父节点的子节点设为None
    if node.right is None and node.left is None:
        pn.right = None
        pn.left = None
    elif node.right is None:  # 如果后继节点只有左子节点，将父节点指向其子节点
        pn.right = node.left
    else:  # 找到后继节点后，遍历到最左子节点
        subtree = node.right
        par_tree = subtree
        while subtree.left is not None:
            par_tree = subtree
            subtree = subtree.left
        if subtree != node.right:  # 重建树结构
            par_tree.left = subtree.right
            subtree.right = node.right
        pn.right = subtree  # 将父节点指向新的子树
        temp = node.left  # 保存被删除节点的其他子树
        node = subtree  # 用后继节点替换当前节点
        node.left = temp  # 重新附加剩余子树
    return True

测试案例 #

-------------------------------
输入  : BST前序遍历 { 1, 2, 3 } 删除: 1
结果 : BST前序遍历 { 2, 3 }
输入  : BST前序遍历 { 1, 2, 3 } 删除: 2
结果 : BST前序遍历 { 1, 3 }
输入  : BST前序遍历 { 1, 2, 3 } 删除: 3
结果 : BST前序遍历 { 1, 2 }
输入  : BST前序遍历 { 50, 40, 30, 20, 45, 60, 70, 80 } 删除: 0
结果 : BST前序遍历 { 50, 40, 30, 20, 45, 60, 70, 80 }
**输入  : BST前序遍历 { 50, 40, 30, 20, 45, 60, 70, 80 } 删除: 45
结果 : BST前序遍历 { 50, 40, 60, 70, 80 }
输入  : BST前序遍历 { 50, 40, 30, 20, 45, 60, 70, 80 } 删除: 40
结果 : BST前序遍历 { 50, 40, 30, 20, 45, 30, 20, 45, 30, 20 }**
输入  : BST前序遍历 { 50, 40, 30, 20, 45, 60, 70, 80 } 删除: 30
结果 : BST前序遍历 { 50, 40, 30, 20, 20, 60, 70, 80 }

疑问 #

请问我在节点重连的逻辑中哪里出错了？

内容的提问来源于stack exchange，提问作者310ToPoona