使用递归删除二进制搜索树

Question

从二叉查找树中删除节点时，您可以将节点替换为左侧的最大子节点或右侧的最小子节点。

我很难理解以下实现执行删除操作的方式。

@discardableResult public func remove() -> BinarySearchTree? {
  let replacement: BinarySearchTree?

  // Replacement for current node can be either biggest one on the left or
  // smallest one on the right, whichever is not nil
  if let right = right {
    replacement = right.minimum()
  } else if let left = left {
    replacement = left.maximum()
  } else {
    replacement = nil
  }

  // Recursion
  replacement?.remove()

  // Place the replacement on current node's position
  replacement?.right = right
  replacement?.left = left
  right?.parent = replacement
  left?.parent = replacement
  reconnectParentTo(node:replacement)

  // The current node is no longer part of the tree, so clean it up.
  parent = nil
  left = nil
  right = nil

  return replacement
}

上面的代码包括以下步骤：

< li >查找替换节点。 < li >让替换节点引用已删除节点的左右子节点。 < li >让已删除节点的左右子节点将替换节点作为父节点。 < li >让替换节点引用已删除节点的父节点作为自己的父节点。 < li >清理。

我有困难的部分特别是递归。据我所知，递归的基本情况是替换=nil，因为只要有右子或左子，递归就会继续发生。然而，当替换应该引用替换节点时，它怎么能是nil？同时，如果替换不是nil，递归如何停止？

Answer 1

它可能有助于直观地看到发生了什么。假设您从这棵树开始，并希望删除橙色根节点

在橙色节点上调用remove：

< li> self为橙色。 < li> replacement是右边子树(蓝色节点)的最小值。

通过在蓝色上调用remove来递归：

< li> self是蓝色的 < li> replacement为零，因为blue既没有左子系也没有右子系 < li >您在< code>nil上调用< code>remove(或者说您没有调用，因为？) < li >同样，跳过所有其他赋值，因为可选值都是< code>nil 调用< Li > < code > reconnect parent(node:nil)来修复blue的父对象的左/右链接(这将导致< code>green.left被赋值为< code>nil) < li >您返回蓝色

树现在如下所示：

现在，您在最初调用< code>remove时退出，执行继续。记住，

• 自我是橙色的。
• 替换是蓝色节点。

接下来的步骤是：

• <代码>蓝色。右=橙色。右
• <代码>蓝色。left=橙色。左
• orange.right。父级=蓝色
• orange.left。父级=蓝色
• <代码>橙色。reconnectParentTo（节点：蓝色）-这不起作用，因为橙色没有父级
• <代码>橙色。父级=nil
• <代码>橙色。右=无
• <代码>橙色。左=零
• 从remove返回-这是对remove的初始调用，因此我们退出了所有递归

这给我们留下了最后一棵树：