在 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
            else:   
            #two child ondes
                if currentNode.left is not None and currentNode.right is not None:
                    currentNode.value = currentNode.right.getMinValue()      #get the left number from the right subtree
                    currentNode.right.remove(currentNode.value, currentNode) #remove that most left number by using remove() 
                                                                             #on the right currentNode
                #root node
                elif parentNode is None:
                    if currentNode.left is not None:
                        currentNode.value = currentNode.left.value
                        currentNode.right = currentNode.left.right
                        currentNode.left = currentNode.left.left
                    elif currentNode.right is not None:
                        currentNode.value = currentNode.right.value
                        currentNode.left = currentNode.right.left
                        currentNode.right = currentNode.right.right
                    #only 1 item left in BST
                    else:
                        pass
                #one child node
                elif parentNode.left == currentNode:
                    parentNode.left = currentNode.left if currentNode.left is not None else currentNode.right
                elif parentNode.right == currentNode:
                    parentNode.right = currentNode.left if currentNode.left is not None else currentNode.right
                break
        return self

    def getMinValue(self):
        currentNode = self

        while currentNode.left is not None:
            currentNode = currentNode.left
        return currentNode.value

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

while循环将遍历每个节点和运行直到没有更多节点
第一个 if 和 elif 用于查找您要删除的节点。
else 用于实际删除，它有 3 个不同的选项： currentNode 有两个子节点，您只需将其替换为右侧节点的最左侧值并删除最左侧的值来自正确noe的价值。另一种情况是 parentNode 没有父节点，这就是根节点的情况。最后一种情况是当你只有一个子节点时，你所要做的就是将 currentNode 的值更改为它的左节点或右节点（取决于它有哪个）。

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

Answer 1

when we want to delete a root node. Isn't the code supposed to also run the first condition, which is the one for two child nodes?

即使必须删除根节点，它实际上确实评估第一个条件。如果根节点同时具有左和右 child，则“选项 1”适用于它：第一个选项可以很好地处理任何具有两个 children 的节点，无论它是根节点还是不是。在此选项中无需区分根节点或 non-root 节点。

其他两个选项仅适用于不有两个children的节点。您似乎建议（也在代码注释中）只有选项 3 处理这种情况，选项 2 也处理这种情况。选项2是当node节点not有两个children and时它是根。如果根有 2 children，它将被视为选项 1。

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

Deleting a value in a Binary Search Tree iteratively in Python

python

iteration

algorithm

binary-search-tree

data-structures