14.二进制搜索树¶

binary search tree，或BST，是一种数据结构，便于快速查找、插入和删除操作。考虑下面的决策树，选择一方就放弃了另一方的所有可能性，将问题减半。

一旦你做出决定并选择了一个分支，就不会再回头了。你一直走下去，直到你在一个叶子节点上做出最终决定。二叉树让你做同样的事情。具体来说，二进制搜索树对你在前一章看到的二进制树施加了两条规则：

left child节点的值必须小于其parent的值。
因此，right child的值必须大于或等于其parent的值。

二进制搜索树使用这个属性来节省你执行不必要的检查。因此，查找、插入和删除的平均时间复杂度为O(log n)，这比线性数据结构如数组和链接列表要快得多。

在本章中，你将了解BST相对于数组的优点，并像往常一样，从头开始实现数据结构。

案例研究：数组与BST的对比¶

为了说明使用BST的威力，你将查看一些常见的操作，并比较数组与二进制搜索树的性能。

考虑一下以下两个集合：

查询¶

对于一个未排序的数组，只有一种方法可以进行元素查找。你需要从一开始就检查数组中的每个元素：

这就是为什么array.contains(_:)是一个O(n)操作。

而二进制搜索树则不是这样：

每次搜索算法访问BST中的一个节点时，它可以安全地做出这两个假设：

如果搜索值less than当前值，它一定在left子树中。
如果搜索值greater than当前值，它必须在right子树中。

通过利用BST的规则，你可以避免不必要的检查，并在每次做决定时将搜索空间减半。这就是为什么BST中的元素查找是一个O(log n)操作。

插入¶

插入操作的性能优势遵循类似的故事。假设你想在一个集合中插入0：

在数组中插入数值就像插入现有的队伍。在你选择的位置后面的所有人都需要通过洗牌来为你腾出空间。

在上面的例子中，零被插入到数组的前面，导致所有其他元素向后移动一个位置。插入一个数组的时间复杂度为O(n)。

插入到二进制搜索树中则要舒服得多：

通过利用BST的规则，你只需要进行三次遍历就可以找到插入的位置，而且你不需要把所有的元素都洗一遍! 在BST中插入元素也是一个O(log n)的操作。

删除¶

与插入类似，删除数组中的一个元素也会引发元素的洗牌：

这种行为也与排队的比喻相得益彰。如果你离开了队伍的中间，你后面的人就需要向前洗牌以占据空位。

下面是从BST中删除一个值的情况：

很好，很简单当你要删除的节点有子节点时，会有一些复杂的问题需要处理，但你会在后面研究这个问题。即使有这些复杂情况，从BST中删除一个元素仍然是一个O(log n)的操作。

二进制搜索树极大地减少了添加、删除和查找操作的步骤。现在你明白了使用二进制搜索树的好处，你可以进入实际的实现过程。

实施¶

打开本章的启动项目。在其中，你会发现你在前一章创建的BinaryNode类型。创建一个名为BinarySearchTree.swift的新文件，并在该文件中添加以下内容：

public struct BinarySearchTree<Element: Comparable> {

  public private(set) var root: BinaryNode<Element>?

  public init() {}
}

extension BinarySearchTree: CustomStringConvertible {

  public var description: String {
    guard let root = root else { return "empty tree" }
    return String(describing: root)
  }
}

根据定义，二进制搜索树只能持有Comparable的值。

Note

你可以通过使用闭包进行比较来放松对Comparable的要求。在这里使用Comparable是为了保持简单，并把重点放在二叉树的核心概念上。

接下来，你会看到insert方法。

插入元素¶

根据BST的规则，左边的子节点必须包含小于当前节点的值。右边子节点必须包含大于或等于当前节点的值。你将在尊重这些规则的前提下实现insert方法。

在BinarySearchTree.swift中添加以下内容：

extension BinarySearchTree {

  public mutating func insert(_ value: Element) {
    root = insert(from: root, value: value)
  }

  private func insert(from node: BinaryNode<Element>?, value: Element)
      -> BinaryNode<Element> {
    // 1
    guard let node = node else {
      return BinaryNode(value: value)
    }
    // 2
    if value < node.value {
      node.leftChild = insert(from: node.leftChild, value: value)
    } else {
      node.rightChild = insert(from: node.rightChild, value: value)
    }
    // 3
    return node
  }
}

第一个insert方法是暴露给用户的，而第二个方法将作为一个私有的辅助方法使用：

这是一个递归方法，所以它需要一个终止递归的基本情况。如果当前节点是nil，你已经找到了插入点，可以返回一个新的BinaryNode。
因为Element类型是可比较的，你可以进行比较。这个if语句控制下一个insert调用应该以哪种方式遍历。如果新值小于当前值，你在left子上调用insert。如果新值大于或等于当前值，你将在right子上调用insert。
返回当前节点。这使得node = insert(from: node, value: value)形式的赋值成为可能，因为insert将创建node（如果它是nil）或者返回node（它不是nil）。

回到Playground页面，在底部添加以下内容：

example(of: "building a BST") {
  var bst = BinarySearchTree<Int>()
  for i in 0..<5 {
    bst.insert(i)
  }
  print(bst)
}

你应该看到以下输出：

---Example of: building a BST---
    ┌──4
  ┌──3
  │ └──nil
 ┌──2
 │ └──nil
┌──1
│ └──nil
0
└──nil

那棵树看起来有点不平衡，但它确实遵循了规则。然而，这种树的布局有不理想的后果。在处理树木时，你总是想实现平衡的格式：

一个不平衡的树会影响性能。如果你在你创建的不平衡树中插入5，就会变成O(n)操作：

你可以创建被称为自我平衡的结构，使用巧妙的技术来保持平衡的结构，但我们会把这些细节留到第16章"AVL树"。现在，你将建立一个样本树，并注意防止它变得不平衡。

在Playground页面的top添加以下计算变量：

var exampleTree: BinarySearchTree<Int> {
  var bst = BinarySearchTree<Int>()
  bst.insert(3)
  bst.insert(1)
  bst.insert(4)
  bst.insert(0)
  bst.insert(2)
  bst.insert(5)
  return bst
}

将你的example函数替换为以下内容：

example(of: "building a BST") {
  print(exampleTree)
}

你应该在控制台看到以下内容：

---Example of: building a BST---
 ┌──5
┌──4
│ └──nil
3
│ ┌──2
└──1
 └──0

好多了!

寻找元素¶

在BST中寻找一个元素需要你遍历其节点。通过使用你在前一章学到的现有的遍历机制，可以想出一个相对简单的实现。

在BinarySearchTree.swift的底部添加以下内容：

extension BinarySearchTree {

  public func contains(_ value: Element) -> Bool {
    guard let root = root else {
      return false
    }
    var found = false
    root.traverseInOrder {
      if $0 == value {
        found = true
      }
    }
    return found
  }
}

接下来，回到Playground页面，测试一下这个问题：

example(of: "finding a node") {
  if exampleTree.contains(5) {
    print("Found 5!")
  } else {
    print("Couldn’t find 5")
  }
}

你应该在控制台看到以下内容：

---Example of: finding a node---
Found 5!

顺序内遍历的时间复杂度为O(n)；因此，contains的这个实现的时间复杂度与在未排序的数组中进行穷举搜索的时间复杂度相同。然而，你可以做得更好。

优化`contains`¶

你可以依靠BST的规则来避免不必要的比较。回到 BinarySearchTree.swift中，将contains方法更新为以下内容：

public func contains(_ value: Element) -> Bool {
  // 1
  var current = root
  // 2
  while let node = current {
    // 3
    if node.value == value {
      return true
    }
    // 4
    if value < node.value {
      current = node.leftChild
    } else {
      current = node.rightChild
    }
  }
  return false
}

首先将current设置为root节点。
当current不是nil时，检查当前节点的值。
如果value等于你要找的东西，返回true。
否则，决定你是要检查左边还是右边的孩子。

在平衡的二进制搜索树中，contains的这个实现是一个O(log n)操作。

移除元素¶

删除元素是一个比较棘手的问题，因为你需要处理一些不同的情况。

案例1：叶子结点¶

删除一个叶子节点是很简单的，只要把叶子节点分离出来就可以了。

然而，对于非叶子节点，你必须采取额外的步骤。

案例2：有一个孩子的节点¶

当删除有一个孩子的节点时，你需要将这一个孩子与树的其他部分重新连接起来：

案例3：有两个孩子的节点¶

有两个子节点的情况比较复杂，所以一个更复杂的树的例子可以更好地说明如何处理这种情况。假设你有下面这棵树，你想删除值25：

简单地删除节点就会出现两难的局面：

你有两个子节点（12和37）需要重新连接，但父节点只有一个子节点的空间。为了解决这个问题，你将通过执行交换来实现一个巧妙的变通方法。

当删除一个有两个孩子的节点时，用其right子树中最小的节点替换你删除的节点。根据BST的规则，这就是右边子树的leftmost节点：

值得注意的是，这将产生一个valid的二进制搜索树。因为新的节点是右边子树中最小的，所以右边子树中的所有节点仍然会大于或等于新的节点。因为新节点来自右子树，所以左子树中的所有节点都将小于新节点。

执行交换后，你可以简单地删除你复制的值，只是一个叶子节点。

这将照顾到删除有两个孩子的节点。

实现¶

打开BinarySearchTree.swift来实现remove。在文件的底部添加以下代码：

private extension BinaryNode {

  var min: BinaryNode {
    leftChild?.min ?? self
  }
}

extension BinarySearchTree {

  public mutating func remove(_ value: Element) {
    root = remove(node: root, value: value)
  }

  private func remove(node: BinaryNode<Element>?, value: Element)
    -> BinaryNode<Element>? {
    guard let node = node else {
      return nil
    }
    if value == node.value {
      // more to come
    } else if value < node.value {
      node.leftChild = remove(node: node.leftChild, value: value)
    } else {
      node.rightChild = remove(node: node.rightChild, value: value)
    }
    return node
  }
}

这对你来说应该很熟悉。你使用了与insert相同的递归设置和一个私有的辅助方法。你还为BinaryNode添加了一个递归的min属性，以找到子树中的最小节点。在if value == node.value子句中处理了不同的移除情况：

// 1
if node.leftChild == nil && node.rightChild == nil {
  return nil
}
// 2
if node.leftChild == nil {
  return node.rightChild
}
// 3
if node.rightChild == nil {
  return node.leftChild
}
// 4
node.value = node.rightChild!.min.value
node.rightChild = remove(node: node.rightChild, value: node.value)

如果该节点是一个叶子节点，你只需返回nil，从而删除当前节点。
如果该节点没有左边的子节点，你返回node.rightChild来重新连接右边的子树。
如果节点没有右边的子节点，你返回node.leftChild来重新连接左边的子树。
这种情况下，要删除的节点既有左子又有右子。你用右子树中最小的值替换该节点的值。然后你在右边的子节点上调用remove来删除这个被替换的值。

回到Playground页面，通过编写以下内容测试remove：

example(of: "removing a node") {
  var tree = exampleTree
  print("Tree before removal:")
  print(tree)
  tree.remove(3)
  print("Tree after removing root:")
  print(tree)
}

你应该在控制台看到以下输出：

---Example of: removing a node---
Tree before removal:
 ┌──5
┌──4
│ └──nil
3
│ ┌──2
└──1
 └──0

Tree after removing root:
┌──5
4
│ ┌──2
└──1
 └──0

关键点¶

二进制搜索树是一个强大的数据结构，用于保存sorted数据。
二进制搜索树的元素必须是可比较的。你可以使用一个通用的约束条件或者通过提供闭包来执行比较来实现这一点。
二进制搜索树中的insert、remove和contains方法的时间复杂度为O(log n)。
当树变得不平衡时，性能将下降到O(n)。这是不可取的，所以你将在第16章学习一种自平衡的二进制搜索树，称为AVL树。