提示：本篇的原文已经在github上有所更新，想看最新版的朋友们抱歉了...

二叉查找树（英语：Binary Search Tree），也称二叉搜索树、有序二叉树（英语：ordered binary tree），排序二叉树（英语：sorted binary tree）。是一种特殊类型的二叉树（每个节点最多有两个子节点的树），它执行插入和删除，以使树始终排序。

属性：“始终排序”

下面是一个二叉搜索树的例子：

注意每个左边的子节点是小于它的父节点的，并且每个右边的子节点都是大于它的父节点的。这是二叉搜索树的关键特征。

例子中，2 小于 7 ，所以它在左边； 5 大于 2 ，所以它在右边。

插入新节点

当执行插入时，我们首先将新值与根节点进行比较。如果新值较小，我们把它放到左分支；如果新值较大，我们把它放到右分支。我们以这种方式在树种一直寻找，直到找到一个合适的位置插入新值。

假设我们要插入新值 9 ：

• 我们从树的根节点（值为 7 的节点）开始，并将其与新值 9 进行比较。
• 9 > 7 ，所以我们沿着右分支并重复相同的过程，但这次在节点10上。
• 因为 9 < 10，所以我们走左分支。
• 我们已经没有值可以比较了，新值 9 应该插入在这里。

新元素插入到树中的位置只有一种可能。找到这个位置通常很快。他需要的 O(h) 的时间，其中h是树的高度。

注意: 节点的 高度 是从该节点到其最低叶所需的步骤数。整个树的高度是从根到最低叶的距离。二叉搜索树上的许多操作都是用树的高度表示的。

遵循这个简单的规则 -- 左侧的值较小，右侧的值较大 -- 我们保持树的排序方式，这样每当查询时，可以快速检查一个值是否在树中。

搜索树

为了在树中找到一个值，我们执行与插入基本上相同的步骤：

• 如果值小于当前节点，则取左侧分支。
• 如果值大于当前节点，则取右侧分支。
• 如果值等于当前节点，我们就找到了！

像大多数树操作一样，这是递归执行的，直到我们找到要查找的值，或者遍历完整个树。

如果我们在例子中查找值 5 ，它将如下所示：

由于树的结构，搜索真的很快。它的运行时间是 O(h) 。如果你有一个有100万个节点的平衡树（well-balanced tree），它只需要大约20个步骤来找到这棵树中的任何东西。（这个想法非常类似于数组中的二分搜索。）

遍历树

有时你不只想看一个节点，而是想看所有的节点。

有三种方法来遍历二叉树：

1. 按顺序（或深度优先）：首先查看节点的左子节点，然后查看节点本身，最后查看其右子节点。
2. 按节点：先看一个节点，然后看它的左右子节点。
3. 反序: 先看左右子节点，最后处理节点本身。

这里再一次发生递归。

如果按顺序遍历二叉搜索树，它会查看所有节点，就好像它们从低到高排序一样。遍历示例中的树，它会打印 1, 2, 5, 7, 9, 10 ：

删除节点

删除节点有点棘手。删除叶节点很容易，你只需要将它与父节点断开：

如果要删除的节点只有一个子节点，我们可以将该子节点链接到父节点。 所以我们只需拉出节点：

棘手部分是，当删除节点有两个子节点。为了保持树排序正确，我们必须用大于节点的最小子节点替换这个节点：

这总右子树里的最左边的子节点。需要额外搜索，最多耗时 O(h) 来找到这个孩子。

其他涉及二叉搜索树的代码相当简单(如果你理解递归),但删除节点有点棘手。

代码(方案1)

有如此多的理论。让我们看看如何能迅速实现二叉搜索树。你可以用不同的方法。首先，我将向您展示如何创建一个基于类的版本，但我们还将介绍如何使用枚举创建一个版本。

这是第一次尝试 BinarySearchTree 类:

public class BinarySearchTree<T: Comparable> {
    private(set) public var value: T
    private(set) public var parent: BinarySearchTree?
    private(set) public var left: BinarySearchTree?
    private(set) public var right: BinarySearchTree?
    
    public init(value: T) {
        self.value = value
    }
    
    public var isRoot: Bool {
        return parent == nil
    }
    
    public var isLeaf: Bool {
        return left == nil && right == nil
    }
    
    public var isLeftChild: Bool {
        return parent?.left === self
    }
    
    public var isRightChild: Bool {
        return parent?.right === self
    }
    
    public var hasLeftChild: Bool {
        return left != nil
    }
    
    public var hasRightChild: Bool {
        return right != nil
    }
    
    public var hasAnyChild: Bool {
        return hasLeftChild || hasRightChild
    }
    
    public var hasBothChildren: Bool {
        return hasLeftChild && hasRightChild
    }
    
    public var count: Int {
        return (left?.count ?? 0) + 1 + (right?.count ?? 0)
    }
}

这个类只描述了一个节点,而不是整个树。这是一个泛型类型,因此,节点可以存储任何类型的数据。它还引用其左、右子节点和父节点。

这样创建它：

let tree = BinarySearchTree<Int>(value: 7)

count 属性决定了树和子树有多少节点。这不仅仅计算节点的直接子节点，而且计算他们的子节点和他们的子节点的子节点，等等。

如果这个特定对象是根节点，则它计算整个树中有多少个节点。 最初，count = 0。

注意：因为 left，right 和 parent 是可选的，所以我们可以很好地利用 Swift 的可选链接 (?) 和 nil-coalescing运算符（??）。你也可以用 if let ，但是不那么简洁。

插入节点

一个树节点本身毫无用处,这是如何将新节点添加到树:

    public func insert(value: T) {
        insert(value: value, parent: self)
    }
    
    private func insert(value: T, parent: BinarySearchTree) {
        if value < self.value {
            if let left = left {
                left.insert(value: value, parent: left)
            } else {
                left = BinarySearchTree(value: value)
                left?.parent = parent
            }
        } else {
            if let right = right {
                right.insert(value: value, parent: right)
            } else {
                right = BinarySearchTree(value: value)
                right?.parent = parent
            }
        }
    }

像许多其他树操作一样，插入是最简单的递归实现。我们将新值与现有节点的值进行比较，并决定是将其添加到左侧分支还是右侧分支。

如果没有更多的左、右子节点要查看，我们为新节点创建一个BinarySearchTree对象，并通过设置其父节点属性将其连接到树。

注意： 因为二叉搜索树的在左边的节点较小，在右边的节点较大，你应该总是在根节点插入元素，以确保这是一个有效的二叉树！

根据例子建立完整的树:

let tree = BinarySearchTree<Int>(value: 7)
tree.insert(value: 2)
tree.insert(value: 5)
tree.insert(value: 10)
tree.insert(value: 9)
tree.insert(value: 1)

注意： 以后就会明白这么做的原因，你应该插入随机的数字。如果你按顺序插入，树不会有正确的形状。

为了方便起见，我们添加一个 init 方法，为数组中的所有元素调用 insert() ：

    public convenience init(array: [T]) {
        precondition(array.count > 0)
        self.init(value: array.first!)
        for v in array.dropFirst() {
            insert(value: v, parent: self)
        }
    }

现在你可以这样做：

let tree = BinarySearchTree<Int>(array: [7, 2, 5, 10, 9, 1])

数组中的第一个值成为树的根节点。

调试输出

当使用像这样的有些复杂的数据结构时，有人类可读的调试输出是很有用的。

extension BinarySearchTree: CustomStringConvertible {
    public var description: String {
        var s = ""
        if let left = left {
            s += "(\(left.description)) <- "
        }
        s += "\(value)"
        if let right = right {
            s += " -> (\(right.description))"
        }
        return s
    }
}

当你调用 print(tree) ，输出如下：

((1) <- 2 -> (5)) <- 7 -> ((9) <- 10)

根节点在中间。想象一下，你应该看到这确实对应于以下树：

顺便说一下，你可能想知道当你插入重复项目会发生什么？ 我们总是将它们插入到正确的分支中。 试试看！

搜索

我们现在做什么，我们在树中有一些值？搜索他们！能够快速找到项目是二叉搜索树的整个目的。 :-)

这是 search() 的实现：

    public func search(value: T) -> BinarySearchTree? {
        if value < self.value {
            return left?.search(value: value)
        } else if value > self.value {
            return right?.search(value: value)
        } else {
            return self // 找到了！
        }
    }

我希望逻辑清晰：这在当前节点（通常是根节点）处开始，并比较这些值。如果搜索值小于节点的值，我们在左分支中继续搜索；如果搜索值更大，我们在右分支中继续搜索。

当然，如果没有更多的节点可查看 -- 当左子节点或右子节点为空，那么我们返回 nil 以指示搜索值不在树中。

注意： 在Swift中，使用可选链接非常方便；当你写下 left?.search(value) 时，如果 left 是 nil ，它将自动返回 nil 。 没有必要使用 if 语句显式检查这一点。

搜索是一个递归过程，但您也可以使用简单的循环来实现：

    public func search(value: T) -> BinarySearchTree? {
        var node: BinarySearchTree? = self
        while case let n? = node {
            if value < n.value {
                node = n.left
            } else if value > n.value {
                node = n.right
            } else {
                return node
            }
        }
        return nil
    }

验证一下，你明白这两个实现是等价的。就个人而言，我喜欢使用迭代代码而不是递归代码，但你的意见可能不同。 ;-)

以下是测试搜索的方法：

tree.search(value: 5)
tree.search(value: 2)
tree.search(value: 7)
tree.search(value: 6) // nil

前三行都返回相应的 BinaryTreeNode 对象。 最后一行返回 nil ，因为没有值为 6 的节点。

注意： 如果树中有重复项，search() 总是返回“最高”节点。 这是有道理的，因为我们开始从根节点向下搜索。

遍历

记得有3种不同的方法来查看树中的所有节点嘛？ 他们是：

    public func traverseInOrder(process: (T) -> Void) {
        left?.traverseInOrder(process: process)
        process(value)
        right?.traverseInOrder(process: process)
    }
    
    public func traversePreOrder(process: (T) -> Void) {
        process(value)
        left?.traversePreOrder(process: process)
        right?.traversePreOrder(process: process)
    }

    public func traversePostOrder(process: (T) -> Void) {
        left?.traversePostOrder(process: process)
        right?.traversePostOrder(process: process)
        process(value);
    }

他们都做同样的事情，但顺序不同。 再次注意，所有的工作都是递归完成的。 由于Swift可选链接的特性，当没有左或右子节点时，对 traverseInOrder() 等的调用会被忽略。

要打印从低到高排序的树中的所有值，可以这样写：

tree.traverseInOrder{ value in print(value) }

这将打印以下内容：

1
2
5
7
9
10

你还可以向树中添加 map() 和 filter() 。 例如，下面是一个map的实现：

    public func map(formula: (T) -> T) -> [T] {
        var a = [T]()
        if let left = left { a += left.map(formula: formula) }
        a.append(formula(value))
        if let right = right { a += right.map(formula: formula) }
        return a
    }

这个闭包将调用树中每个节点上的公式，并将结果收集到数组中。 map() 按顺序来遍历树。

一个非常简单的使用 map() 的例子：

    public func toArray() -> [T] {
        return map { $0 }
    }

这将树的内容变为排好序的数组。 在 playground 上试试：

tree.toArray() // [1, 2, 5, 7, 9, 10]

作为练习，看看你是否可以实现 filter 和 reduce 。

删除节点

您已经看到删除节点可能很棘手。 我们可以通过定义一些辅助函数使代码更具可读性。

    private func reconnectParentToNode(node: BinarySearchTree?) {
        if let parent = parent {
            if isLeftChild {
                parent.left = node
            } else {
                parent.right = node
            }
        }
        node?.parent = parent
    }

对树进行更改涉及更改一系列 parent 和 left 和 right 节点。这个功能有助于，它需要当前节点的父节点（即 self ），并将其连接到另一个节点。通常，另一个节点是 self 的孩子之一。

我们还需要一个返回节点最左边的后代的方法：

   public func minimun() -> BinarySearchTree {
        var node = self
        while case let next? = node.left {
            node = next
        }
        return node
    }

要了解这是如何工作的，请看下面的树：

例如，如果我们看节点 10 ，其最左边的子节点是 6 。我们通过跟随所有的左子节点到达那里，直到没有更多的左子节点。根节点 7 的最左边的子孙是 1。因此，1 是整个树中的最小值。

我们不需要它删除，但为了完整性，这里是相反的 minimum() ：

    public func maximum() -> BinarySearchTree {
        var node = self
        while case let next? = node.right {
            node = next
        }
        return node
    }

它返回节点的最右边的后代。我们通过跟随右子节点找到它，直到结束。在上面的例子中，节点 2 的最右边的后代是 5 。整个树中的最大值为 11 ，因为这是根节点 7 的最右边的后代。

最后，我们可以编写从树中删除节点的代码：

    public func remove() -> BinarySearchTree? {
        let replacement: BinarySearchTree?
        
        if let left = left {
            if let right = right {
                replacement = removeNodeWithChildren(left: left, right: right) // 1
            } else {
                replacement = left // 2
            }
        } else if let right = right { // 3
            replacement = right
        } else {
            replacement = nil // 4
        }
        
        reconnectParentToNode(node: replacement)
        
        parent = nil
        left = nil
        right = nil
        
        return replacement
    }

它看起来不那么可怕。 ;-) 有四种情况要处理：

1.此节点有两个子节点。
2.此节点只有一个左子节点。 左子节点替换该节点。
3.此节点只有一个右子节点。 右子节点替换该节点。
4.此节点没有子节点。 我们只是断开它和父节点的联系。

首先，我们确定哪个节点将替换我们要删除的节点，然后我们调用reconnectParentToNode() 来更改左，右和父指针，使之发生。 由于当前节点不再是树的一部分，我们通过将其指针设置为nil来清除它。 最后，我们返回已替换已删除节点的节点（如果这是叶节点，则返回nil）。

这里唯一棘手的是情况1，这个逻辑有自己的帮助方法：

    private func removeNodeWithTwoChildren(left: BinarySearchTree, right: BinarySearchTree) -> BinarySearchTree {
        let successor = right.minimun()
        let _ = successor.remove()
        
        successor.left = left
        left.parent = successor
        
        if right !== successor {
            successor.right = right
            right.parent = successor
        } else {
            successor.right = nil
        }
        
        return successor
    }

如果要删除的节点有两个子节点，则必须由大于此节点值的最小子节点替换。 这恰好总是是右子节点的最左边的子节点，即 right.minimum() 。 我们将该节点从树中的原始位置取出，放到要删除的节点的位置。

试试看：

    if let node2 = tree.search(value: 2) {
        print(tree) // 删除前
        let _ = node2.remove()
        print(tree) // 删除后
    }

首先，要使用 search() 找到要删除的节点，然后在该对象上调用 remove() 。 在删除之前，树打印如下：

((1) <- 2 -> (5)) <- 7 -> ((9) <- 10)

在 remove() 之后，你将得到：

((1) <- 5) <- 7 -> ((9) <- 10)

正如你所看到的，节点 5 取代了 2。

注意：如果删除根节点会发生什么？ 在这种情况下，remove() 告诉你哪个节点已经成为新的根。 试试看：调用 tree.remove() 并看看会发生什么。

深度和高度

回想一下，节点的高度是到其最低叶的距离。 我们可以用以下函数计算：

    public func height() -> Int {
        if isLeaf {
            return 0
        } else {
            return 1 + max(left?.height() ?? 0, right?.height() ?? 0)
        }
    }

我们看看左右分支的高度，取最高的一个。 同样，这是一个递归过程。 因为结果看起来像遍历节点的所有子节点，性能是 O(n) 。

注意： Swift的空合并运算符(??)可以快速处理 值为 nil 的左或右节点。 你可以用这个，或者用 if let，但这是一个更简洁。

试试看：

print(tree.height())  // 2

您还可以计算节点的深度，这是到根的距离。 这里是代码：

    public func depth() -> Int {
        var node = self
        var deges = 0
        while case let parent? = node.parent {
            node = parent
            deges += 1
        }
        return edges
    }

它向上遍历树，顺找父节点，直到我们到达根节点（其父节点为nil）。 这需要 O(h) 时间。 例：

    if let node9 = tree.search(value: 9) {
        print(node9.depth())  // 2
    }

前任和后继

二叉搜索树总是“排序”，但这并不意味着连续的数字在树中彼此相邻。

注意，你只看左子节点的话，是找不到 7 的。 左子节点是 2 ，而不是 5 。同样不是 7 后面的数字。

predecessor() 函数以顺序返回其值在当前值之前的节点：

    public func predecessor() -> BinarySearchTree<T>? {
        if let left = left {
            return left.maximum()
        } else {
            let node = self
            while case let parent? = node.parent {
                if parent.value < value {
                    return parent
                }
            }
            return nil
        }
    }

如果我们有一个左子树很容易。 在这种情况下，直接调用 predecessor() 是该子树中的最大值。 你可以在上面的图片中验证 5 确实是 7 的左分支中的最大值。

然而，如果没有左子树，那么我们必须查看我们的父节点，直到我们找到一个较小的值。 因此，如果我们想知道节点 9 的前任是什么，我们继续向上，直到我们找到具有较小值的第一个父节点，即 7 。

successor() 的代码工作方式完全相同：

    public func successor() -> BinarySearchTree<T>? {
        if let right = right {
            return right.minimum()
        } else {
            var node = self
            while case let parent? = node.parent {
                if parent.value > value {
                    return parent
                }
                node = parent
            }
            return nil
        }
    }

这两个方法的时间复杂度都是 O(h) 。

注意： 有一个很酷的变体称为“螺纹”二叉树，其中“未使用”的左和右指针被重用以在前任节点和后继节点之间建立直接链接。 非常聪明！

搜索树是否有效？

如果你想搞破坏，你可以通过调用 insert() 在一个不是根的节点，将二叉搜索树变成一个无效树，像这样：

    if let node1 = tree.search(value: 1) {
        node1.insert(value: 100)
        print(tree)
    }

根节点的值为 7 ，因此值为 100 的节点应该在树的右分支中。 但是，你不是在根的插入，而是在树的左侧分支的叶节点。 所以新的 100 节点在树的错误的地方！

结果，tree.search(100) 返回 nil 。

您可以使用以下方法检查树是否是有效的二叉搜索树：

    public func isBST(minValue: T, maxValue: T) -> Bool {
        if value < minValue || value > maxValue {
            return false
        }
        
        let leftBST = left?.isBST(minValue: minValue, maxValue: value) ?? true
        let rightBST = right?.isBST(minValue: value, maxValue: maxValue) ?? true
        return leftBST && rightBST
    }

这验证左分支确实包含小于当前节点的值，并且右分支仅包含较大的值。

调用如下：

    if let node1 = tree.search(value: 1) {
        print(tree.isBST(minValue: Int.min, maxValue: Int.max))   // true
        node1.insert(value: 100)  //破坏!!!
        print(tree.search(value: 100))  // nil
        print(tree.isBST(minValue: Int.min, maxValue: Int.max)) // false
    }

代码（解决方案2）

我们已经将二叉树节点实现为类，但也可以使用枚举。

区别在于参考语义与价值语义。 对基于类的树进行更改将更新内存中的同一个实例。 但是基于枚举的树是不可变的 - 任何插入或删除都会给你一个全新的树的副本。 哪一个最好完全取决于你想要使用哪个。

这里是如何使用枚举二叉搜索树：

public enum BinarySearchTreeEnum<T: Comparable> {
    case Empty
    case Leaf(T)
    indirect case Node(BinarySearchTreeEnum<T>, T, BinarySearchTreeEnum<T>)
}

枚举有三种情况：

• Empty 空标记分支的结束（基于类的版本为此使用了 nil 引用）。
• Leaf 叶为没有孩子的叶节点。
• Node 具有一个或两个子节点的节点的节点。 这是使用关键字 indirect，以便它可以保存 BinarySearchTree 值。 没有 indirect，你不能使递归枚举。

注意： 此二叉树中的节点没有对其父节点的引用。 这不是一个重要的障碍，但它会使某些操作略为繁琐。

像往常一样，我们将递归地实现大多数功能。 我们将对每个枚举的情况略有不同。 例如，这是如何计算树中的节点数和树的高度：

    public var count: Int {
        switch self {
        case .Empty:
            return 0
        case .Leaf:
            return 1
        case let .Node(left, _, _right):
            return left.count + 1 + _right.count
        }
    }

插入新节点如下所示：

    public func insert(newValue: T) -> BinarySearchTreeEnum {
        switch self {
        case .Empty:
            return .Leaf(newValue)
        case .Leaf(let value):
            if newValue < value {
                return .Node(.Leaf(newValue), value, .Empty)
            } else {
                return .Node(.Empty, value, .Leaf(newValue))
            }
        case .Node(let left, let value, let right):
            if newValue < value {
                return .Node(left.insert(newValue: newValue), value, right)
            } else {
                return .Node(left, value, right.insert(newValue: newValue))
            }
        }
    }

在 playground 里试试看：

var tree = BinarySearchTreeEnum.Leaf(7)
tree = tree.insert(2)
tree = tree.insert(5)
tree = tree.insert(10)
tree = tree.insert(9)
tree = tree.insert(1)

注意，每次插入后，你会得到一个全新的树对象。这就是为什么你需要将结果赋值给 tree 。

这里是最重要的搜索功能：

  public func search(x: T) -> BinarySearchTreeEnum? {
      switch self {
      case .Empty:
          return nil
      case .Leaf(let y):
          return (x == y) ? self : nil
      case let .Node(left, y, right):
          if x < y {
                return left.search(x)
          } else if y < x {
              return right.search(x)
          } else {
             return self
          }
      }
  }

如你所见，这些函数中的大多数具有相同的结构。

在 playground 中试试看：

tree.search(10)
tree.search(1)
tree.search(11)   // nil

要打印树以进行调试，可以使用以下方法：

extension BinarySearchTreeEnum: CustomDebugStringConvertible {
    public var debugDescription: String {
        switch self {
        case .Empty: return "."
        case .Leaf(let value): return "\(value)"
        case .Node(let left, let value, let right):
            return "(\(left.debugDescription) <- \(value) -> \(right.debugDescription))"
        }
    }
}

当你调用 print(tree) 时，将会看到这样的输出：

((1 <- 2 -> 5) <- 7 -> (9 <- 10 -> .))

根节点在中间； . 表示在该位置没有子节点。

当树变得不平衡...

当二叉搜索树的左和右子树包含大致相同数量的节点时，它是平衡的。 在这种情况下，树的高度是 log(n)，其中 n 是节点的数量。 这是理想的情况。

然而，如果一个分支比另一个分支长得多，搜索将变得非常慢。 我们最终检索比我们理想情况下更多的值。 在最坏的情况下，树的高度可以变为 n 。 这样的树比二叉搜索树更像链表，性能降级到 O(n) 。 这可不好！

使二叉搜索树平衡的一种方法是以完全随机的顺序插入节点。 平均来说，应该可以保持树平衡。 但它不保证成功，也不总是实用。

另一个解决方案是使用自平衡二叉树。 此类型的数据结构会在插入或删除节点后调整树以保持平衡。 有关示例，请参阅AVL树和红黑树。

也可以看看

维基百科上的二叉搜索树

由 Nicolas Ameghino 和 Matthijs Hollemans 写的Swift算法俱乐部。