在Python中迭代删除二叉搜索树中的值

Question

我目前正在学习数据结构和算法以及 BST 的课程。我已经让代码可以工作并理解其中的大部分内容，但我有一个关于删除功能的问题。这就是我的代码的样子：

class BST:

    def __init__(self, value):

        self.value = value

        self.left = None

        self.right = None

    def insert(self, value):

        currentNode = self

        while True:

            if value < currentNode.value:

                if currentNode.left is None:

                    currentNode.left = BST(value)

                    break

                else:

                    currentNode = currentNode.left

            else:

                if currentNode.right is None:

                    currentNode.right = BST(value)

                    break

                else:

                    currentNode = currentNode.right

        return self

    def contains(self, value):

        currentNode = self

        while currentNode is not None:

            if value < currentNode.value:

                currentNode = currentNode.left

            elif value > currentNode.value:

                currentNode = currentNode.right

            else:

                return True

        return False

    def remove(self, value, parentNode = None):

        currentNode = self

        while currentNode is not None:

            if value < currentNode.value:

                parentNode = currentNode

                currentNode = currentNode.left  

            elif value > currentNode.value:

                parentNode = currentNode

                currentNode = currentNode.right

            #Found the node

据我了解，对于删除功能：

1. 循环while将迭代每个节点并运行，直到没有更多的节点

2. 第一个if和elif用于查找您要删除的节点。

3. 适用else于实际删除，有 3 个不同的选项：要么currentNode有两个子节点，要么将其替换为右侧节点的最左侧值，然后从右侧节点中删除该最左侧值。另一种情况是parentNode没有父节点，这将是根节点的情况。currentNode最后一种情况是，当您只有一个子节点时，您所要做的就是更改其左节点或右节点的值（取决于它有哪一个）。

我不清楚的是条件背后的逻辑，以及当我们想要删除节点时它是如何工作的root。代码不是应该也运行第一个条件，即两个子节点的条件吗？我几乎可以肯定这不应该发生，并且该条件应该只适用于其特殊情况。我看了一遍又一遍的视频解释，但我就是无法掌握其中的窍门。

Answer 1

当我们想要删除根节点时。代码不是应该也运行第一个条件，即两个子节点的条件吗？即使必须删除根节点，它实际上也会评估第一个条件。如果根节点同时具有左子节点和右子节点，则“选项 1”适用于它：第一个选项可以很好地处理具有两个子节点的任何节点，无论它是否是根节点。在此选项中不需要区分根节点或非根节点。其他两个选项仅适用于没有两个子节点的节点。您似乎建议（也在代码注释中）只有选项 3 可以处理这种情况，但选项 2 也可以。选项2适用于当节点node没有两个子节点并且它是根节点时。如果根有 2 个孩子，则将被视为选项 1。