二叉搜索树(BST)删除叶子节点功能异常问题排查求助

核心原因 #

Python的函数参数为对象引用传递，你在_delete_node方法内将局部变量root赋值为None，仅修改了局部变量的指向，不会修改待删除节点父节点中存储的子节点引用，这是删除后节点仍然存在的根本原因。

代码中存在的其他关联Bug #

• 插入逻辑重复创建节点：公共insertion方法已经创建了new_node，调用私有_insertion时又创建了一次新节点，造成不必要的内存开销，逻辑冗余
• Node类重复定义了left/right和left_child/right_child两组子节点属性，插入逻辑同时给两组赋值，但删除逻辑完全没有更新父节点的对应属性，导致引用残留
• search方法逻辑错误：判断root.data > data时错误将root指向root.right，应该指向root.left，且循环条件未覆盖叶子节点匹配的场景，无法正确查询叶子节点
• 单孩子节点删除逻辑错误：仅将局部变量root指向子节点，没有关联到原节点的父节点，还错误将新节点的right/left设为None，直接打断子树
• 双孩子节点删除时get_max使用错误：应该取左子树的最大值或右子树的最小值，你当前传入待删除节点本身，取到的是待删除节点自己的值，完全无法实现替换逻辑
• 未处理待删除节点是根节点的场景

核心逻辑修正方案 #

删除节点时不要直接操作当前节点的局部变量，通过递归返回新的子节点直接赋值给父节点的对应属性，从根源上解决引用残留的问题：

# 补充右子树最小值查询方法，用于双孩子节点替换
def get_min(self, node):
    current = node
    while current.left:
        current = current.left
    return current

# 修正后的递归删除逻辑
def _delete_node(self, root, data):
    if not root:
        return None
    if root.data < data:
        root.right = self._delete_node(root.right, data)
    elif root.data > data:
        root.left = self._delete_node(root.left, data)
    else:
        # 叶子节点直接返回None，父节点会接收该值更新对应子节点属性
        if not root.left and not root.right:
            return None
        # 仅存在右孩子，返回右孩子给父节点
        elif not root.left:
            temp = root.right
            root = None
            return temp
        # 仅存在左孩子，返回左孩子给父节点
        elif not root.right:
            temp = root.left
            root = None
            return temp
        # 双孩子节点，取右子树最小值替换当前节点值，再删除右子树中的最小值节点
        temp = self.get_min(root.right)
        root.data = temp.data
        root.right = self._delete_node(root.right, temp.data)
    return root

# 修正后的入口删除方法，接收递归返回值更新根节点
def delete_node(self, data):
    if not self.root:
        return
    self.root = self._delete_node(self.root, data)

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