使用递归删除二叉搜索树

Question

从二叉搜索树中删除节点时，您可以用左侧最大的 child 或右侧最小的 child 替换节点。

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

@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
}

以上代码包括以下步骤：

1. 寻找替换节点。
2. 让替换节点参考删除节点的左右child。
3. 将移除节点的左右child作为替换节点引用parent。
4. 让替换节点将已删除节点的 parent 作为自己的 parent。
5. 清理。

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

Answer 1

直观地了解发生了什么可能会有所帮助。假设您从这棵树开始并想要删除橙色根节点

您在橙色节点上调用remove：

• self 是 橙色。
• replacement是右子树的最小值-蓝色节点。

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

• self 是 蓝色
• replacement 为零，因为 blue 既没有左也没有右 children
• 您在 nil 上致电 remove（或者更确切地说，您没有致电，因为 ?）
• 同样，所有其他赋值都被跳过，因为可选值都是nil
调用
• reconnectParent(node: nil) 来修复蓝色 parent 的 left/right 链接（这将导致 green.left 被分配 nil）
• 你return蓝色

树现在看起来像：

您现在在对 remove 的初始调用处退出并继续执行。记住，

• self 是 橙色。
• replacement是blue节点。

接下来的步骤是：

• blue.right = orange.right
• blue.left = orange.left
• orange.right.parent = blue
• orange.left.parent = blue
• orange.reconnectParentTo(node:blue) - 这什么都不做，因为 orange 没有 parent
• orange.parent = nil
• orange.right = nil
• orange.left = nil
• Return 来自 remove - 这是对 remove 的初始调用，所以我们已经退出所有递归

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