我的 BST 删除方法有什么问题？

Question

编辑：由于某种原因，我无法附上我正在使用的 BST 的照片，但您可以使用此链接查看它：https://ibb.co/zhsCSrg

我正在使用二叉搜索树，并且正在为函数removeLessThan编写伪代码，该函数将“node”和“value”作为输入。该函数应该删除所有值小于“值”的节点。

所以这个电话：

root = removeLessThan(root, value);

应该从 BST 中删除所有值小于“value”的节点。

这是我尝试编写该方法：

removeLessThan(node, value)

    if (node == null)
        return null
    
    if (node.value >= value)
        node.left = removeLessThan(node.left, value)
    
    else if (node.value < value)
        node.left = removeLessThan(node.left, value)
        node.right = removeLessThan(node.right, value)
        node = null
    
    return node

我认为从底部开始删除值小于“value”的节点，然后继续向上递归是一个好主意。因此，如果“值”是 30 并且我们正在使用我在此处附加的 BST，我们向左一直向下遍历到 5 并删除该节点，然后继续向上。然而，chatgpt 告诉我我的代码是错误的。我不明白这个解释，而且还说的不正确。

有人可以向我解释为什么我的方法是错误的，以及什么是更好的主意？

我尝试想象附加 BST 后会发生什么。

Answer 1

错误在于

node.value < value

的情况。在那里，您总是返回

null

，但该节点的右子树中仍然可能存在需要保留在树中的值。事实上，它们是您分配给

node.right

的节点，就在通过设置

node = null

丢弃该节点之前。相反，您应该保留分配给

node.right

的内容，但返回。

没有错，但

else

块中没有必要有条件：这是唯一剩下的可能性。

所以这样做：

removeLessThan(node, value)

    if (node == null)
        return null
    
    if (node.value >= value)
        node.left = removeLessThan(node.left, value)
    else
        node = removeLessThan(node.right, value)
    
    return node