节点删除是BST，python实现

Question

我对 BST 中节点删除的这种实现感到好奇（有关其他 code/context，请参阅 full implementation。）这是我的理解方式：

if val < self.data 和 elif val > self.data 都是这样的情况当前节点不是要删除的节点，所以他们递归在适当的子节点上调用删除函数。
else就是我们已经找到正确的节点，需要执行删除的情况。

一个。 if self.left is None and self.right is None: return None 我不清楚这里的目标是什么。我们已经返回 None 但没有将节点值本身重新分配给 None.

b。在这一点上，我们已经排除了 both left 和 right 都不存在的可能性，因此 elif self.left is None 是一种冗长的写法 elif self.right，它returns 没错。但为什么？它不会重新分配节点本身的值。

c。我不确定为什么最后一个控制流语句是 elif self.right is None。为什么没有 else 语句？
这个 min_val, self.data, self.right 舞蹈只有在#2 中的上述控制流语句之一没有条件执行时才会发生，所以我想这是一个隐含的 else 语句。

一个。这一步实际上归结为将 self.data 最小值分配给它的右子节点，然后分配 self.right 递归函数调用的输出，它可能是来自 #2 的左、右或 None。

    def delete(self, val):
        if val < self.data:
            if self.left:
                self.left = self.left.delete(val)
        elif val > self.data:
            if self.right:
                self.right = self.right.delete(val)
        else:
            if self.left is None and self.right is None:
                return None
            elif self.left is None:
                return self.right
            elif self.right is None:
                return self.left

            min_val = self.right.find_min()
            self.data = min_val
            self.right = self.right.delete(min_val)

        return self

回答这个问题，请确认或纠正我上面的一些疑惑。

Answer 1

该算法的第一个案例是关于从树中删除节点：删除对它们的所有引用，同时保持 BST 的键顺序。

想想你会如何用铅笔和纸做这个。

如果删除的节点没有children，重画parent的指针指向空（None）。删除的节点现在从树中“切出”。维持 BST 顺序。
如果删除的节点只有一个 child，请替换 parent 的指针，使其现在指向那个 child。再次将删除的节点从树中切出，BST 键顺序保持不变。

请注意 parent 指针的替换发生在对 delete 的递归调用中。例如。通过返回 None，“没有 child” 的情况导致 parent 没有指向任何内容。 “切出”的节点最终将由 Python.

进行垃圾回收

否则你会遇到更复杂的情况：只有一个 parent 被删除的节点和两个 children。该怎么办？此特定代码找到下一个最大的 key wrt 删除的节点，并使用它来 replace 要删除的密钥。该节点根本没有被切断。然后它从右子树中删除移动的值，这确实导致其节点被删除。再次维护 BST 密钥顺序。

这种实现第三种情况的方式可以生成干净的代码，并且在 Python 中可能有意义，因为所有数据访问都是通过引用（指针）进行的。但这不是唯一的选择。另一种方法是继续与其他情况相同的模式，并实际切出包含已删除值的节点并将下一个最大的 node 移动到该位置（不仅仅是它的关键数据）。如果节点实际包含数据（而不仅仅是对它的引用）并且它非常大，那么这是一个更好的选择。它保存了所有这些数据的副本。如果作者做出了那个选择，那么 parent 的指针的 re-assignment 将有另一个 return 该节点。

节点删除是BST，python实现

Node deletion is BST, python implementation

python

recursion

binary-search-tree