提示：本篇的原文已经在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, 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算法俱乐部。
网友评论