python - 二叉搜索树删除中基本情况的目的

Question

我正在学习 Python 3 中的算法和数据结构类(class)，我的讲师最近向我们介绍了二叉搜索树。但是，我无法理解删除算法。下面是我们学到的实现，但是当我最初编写自己的演绎版时，我没有包含“基本案例”但它仍然有效:

def remove(self, data):
    if self.root:
        self.root = self.remove_node(data, self.root)

def remove_node(self, data, node):
     if node is None:
        return node
    if data < node.data:
        node.leftChild = self.remove_node(data, node.leftChild)
    elif data > node.data:
        node.rightChild = self.remove_node(data, node.rightChild)
    else:
        if not node.rightChild and not node.leftChild:
            print('removing leaf node')
            del node
            return None
        if not node.leftChild:
            print('removing node with single right child')
            tempNode = node.rightChild
            del node
            return tempNode
        elif not node.rightChild:
            print('removing node with single left child')
            tempNode = node.leftChild
            del node
            return tempNode
        print('removing node with two children')
        tempNode = self.get_predecessor(node.leftChild)
        node.data = tempNode.data
        node.leftChild = self.remove_node(tempNode.data, node.leftChild)
    return node

现在，除了下面的声明之外，所有这些对我来说都是有意义的:

if node is None:
    return node

当我们之前了解基本案例时，我们被告知它们本质上是我们算法的导出点。但是，我不明白给定代码中的情况如何。首先，我不明白一个节点怎么可能是空的，即使它是空的，我们为什么要返回一个空节点？据我所知，此检查在整个递归中没有任何作用，因为我们似乎没有像在任何其他递归函数中那样“向它递归”。非常感谢您的解释!

Answer 1

一般情况下，基本案例服务于一个或多个目的，这些包括；

1. 防止函数无限递归
2. 防止函数在极端情况下抛出错误
3. 计算/返回一个值/结果给递归树中更高层的调用者

对于树删除，第一点并不是真正的问题(因为递归树将只有有限数量的节点 - 与您递归的树相同)。您将在这里关注第 2 点和第 3 点。

在你的函数中，你确实有一个基本情况——事实上，你有两个(感谢@user2357112)——

1. 未找到值部分，由

   指定

   if node is None:
       return node
   

   和，

2. 找到值的部分，由您在 else 语句中的代码指定，执行实际删除。

为了使行为与递归情况保持一致，未找到值的基本情况返回 None。如您所见，第一个基本案例是一致的，执行上述通用基本案例的第二个功能，而第二个基本案例执行第三个功能。