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

Question

我正在学习Python 3中的算法和数据结构课程,我的讲师最近向我们介绍了二叉搜索树.但是,我无法理解删除算法.下面是我们教授的实现,但是当我最初编写自己的演绎时,我没有包含"基本案例",它仍然有效:

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。如您所见，第一个基本情况一致执行上述通用基本情况的第二个功能，而第二个基本情况执行第三个功能。