树
*树－通用目的的树形结构。
*二叉树－一种节点最多有两个孩子节点的树形结构。
二叉搜索树(BST)－以某种方式组织自己的节点的二叉树，以求较快的查询速度。
*红黑树 - 自平衡二叉搜索树
*AVL 树－一种通过旋转来维持平衡的二叉搜索树。
*堆－存储在一维数组中的二叉树，所以它不需要使用指针。很适合做为优先队列使用。
*字典树 - 一种特殊类型的树结构用来保存关联数据的结构
*B 树 - 自平衡搜索树，每个节点可以超过两个子节点
树(Tree)
这个话题已经有个辅导文章
树表示对象之间的层次关系。 这是一个树的结构：
树由节点组成，这些节点彼此连接。
节点可以连接到他们的子节点，也可以连接到他们的父节点。 子节点是给定节点下的节点; 父节点是上面的节点。 节点始终只有一个父节点，但可以有多个子节点。
没有父节点的节点是 root 节点。 没有子节点的节点是 leaf 节点。
树中的指针不能形成循环。 这不是树：
这种结构称为图。 树实际上是一种非常简单的图形式。 （类似地，链表是树的简单版本。想一想！）
本文讨论通用树。 通用树对每个节点可能有多少个子节点，或树中节点的顺序没有任何限制。
这是在Swift中的基本实现：
public class TreeNode<T> {
public var value: T
public weak var parent: TreeNode?
public var children = [TreeNode<T>]()
public init(value: T) {
self.value = value
}
public func addChild(_ node: TreeNode<T>) {
children.append(node)
node.parent = self
}
}这描述了树中的单个节点。 它包含泛型类型T，对parent节点的引用，以及子节点数组。
添加description以便打印树：
extension TreeNode: CustomStringConvertible {
public var description: String {
var s = "\(value)"
if !children.isEmpty {
s += " {" + children.map { $0.description }.joined(separator: ", ") + "}"
}
return s
}
}在 playground 创建树：
let tree = TreeNode<String>(value: "beverages")
let hotNode = TreeNode<String>(value: "hot")
let coldNode = TreeNode<String>(value: "cold")
let teaNode = TreeNode<String>(value: "tea")
let coffeeNode = TreeNode<String>(value: "coffee")
let chocolateNode = TreeNode<String>(value: "cocoa")
let blackTeaNode = TreeNode<String>(value: "black")
let greenTeaNode = TreeNode<String>(value: "green")
let chaiTeaNode = TreeNode<String>(value: "chai")
let sodaNode = TreeNode<String>(value: "soda")
let milkNode = TreeNode<String>(value: "milk")
let gingerAleNode = TreeNode<String>(value: "ginger ale")
let bitterLemonNode = TreeNode<String>(value: "bitter lemon")
tree.addChild(hotNode)
tree.addChild(coldNode)
hotNode.addChild(teaNode)
hotNode.addChild(coffeeNode)
hotNode.addChild(chocolateNode)
coldNode.addChild(sodaNode)
coldNode.addChild(milkNode)
teaNode.addChild(blackTeaNode)
teaNode.addChild(greenTeaNode)
teaNode.addChild(chaiTeaNode)
sodaNode.addChild(gingerAleNode)
sodaNode.addChild(bitterLemonNode)如果你打印出tree的值，你会得到：
beverages {hot {tea {black, green, chai}, coffee, cocoa}, cold {soda {ginger ale, bitter lemon}, milk}}这对应于以下结构：
beverages节点是根节点，因为它没有父节点。 叶子节点是黑色，绿色，柴，咖啡，可可，姜汁，苦柠檬，牛奶，因为它们没有任何子节点。
对于任何节点，您可以查看parent属性， 并按照自己的方式返回到根：
teaNode.parent // this is the "hot" node
teaNode.parent!.parent // this is the root在谈论树时，我们经常使用以下定义：
树的高度。 这是根节点和最低叶子之间的连接数。 在我们的示例中，树的高度为3，因为从根到底部需要三次跳跃。
节点的深度。 此节点与根节点之间的连接数。 例如，
tea的深度为2，因为需要两次跳跃才能到达根部。 （根本身的深度为0.）
构建树的方法有很多种。 例如，有时您根本不需要 parent 属性。 或者，您可能只需要为每个节点提供最多两个子节点 - 这样的树称为二叉树。 一种非常常见的树类型是二叉搜索树（或BST），它是二叉树的更严格版本，其中节点以特定方式排序以加速搜索。
我在这里展示的通用树非常适合描述分层数据，但它实际上取决于您的应用程序需要具备哪种额外功能。
下面是一个如何使用TreeNode类来确定树是否包含特定值的示例。 首先看一下节点自己的value属性，如果没有匹配，那么依次看看这个节点所有的子节点。 当然，这些子节点也是TreeNode，所以它们将递归地重复相同的过程：首先看看它们自己的value属性，然后看看它们的子节点。 它们的子节点也会再次做同样的事情，等等...递归和树齐头并进。
这是代码：
extension TreeNode where T: Equatable {
func search(_ value: T) -> TreeNode? {
if value == self.value {
return self
}
for child in children {
if let found = child.search(value) {
return found
}
}
return nil
}
}如何使用它的示例：
tree.search("cocoa") // returns the "cocoa" node
tree.search("chai") // returns the "chai" node
tree.search("bubbly") // nil也可以使用数组来描述树。 数组中的索引表示不同的节点，然后，创建不同节点之间的连接。 例如，如果我们有：
0 = beverage 5 = cocoa 9 = green
1 = hot 6 = soda 10 = chai
2 = cold 7 = milk 11 = ginger ale
3 = tea 8 = black 12 = bitter lemon
4 = coffee 那么我们可以使用以下数组描述树：
[ -1, 0, 0, 1, 1, 1, 2, 2, 3, 3, 3, 6, 6 ]数组中的每个项的值都是指向其父节点的指针。索引3处的项tea，其值为1，因为其父项为hot。根节点指向-1，因为它没有父节点。您只能将这些树从一个节点遍历到根节点，而不是相反。
顺便说一句，有时您会看到使用术语 forest 的算法。 显而易见，这是给予单独树对象集合的名称。 有关此示例，请参阅 union-find。
二叉树（Binary Tree）
二叉树是一种树，其中每个节点具有0,1或2个子节点。 这是一个二叉树：
子节点通常称为 左 子节点 和 右 子节点。 如果节点没有任何子节点，则称为 叶子节点。 根 是树顶部的节点（程序员习惯树颠倒了?）。
节点通常会有一个返回其父节点的连接，但这不是绝对必要的。
二叉树通常用作二叉搜索树。 在这种情况下，节点必须按特定顺序排列（左侧是较小的值，右侧是较大的值）。 但这不是所有二叉树的要求。
例如，这是一个二叉树，表示一系列算术运算，(5 * (a - 10)) + (-4 * (3 / b))：
代码
以下是在Swift中实现通用二叉树的方法：
public indirect enum BinaryTree<T> {
case node(BinaryTree<T>, T, BinaryTree<T>)
case empty
}如何使用它的一个例子，让我们构建上面算术运算树：
// leaf nodes
let node5 = BinaryTree.node(.empty, "5", .empty)
let nodeA = BinaryTree.node(.empty, "a", .empty)
let node10 = BinaryTree.node(.empty, "10", .empty)
let node4 = BinaryTree.node(.empty, "4", .empty)
let node3 = BinaryTree.node(.empty, "3", .empty)
let nodeB = BinaryTree.node(.empty, "b", .empty)
// intermediate nodes on the left
let Aminus10 = BinaryTree.node(nodeA, "-", node10)
let timesLeft = BinaryTree.node(node5, "*", Aminus10)
// intermediate nodes on the right
let minus4 = BinaryTree.node(.empty, "-", node4)
let divide3andB = BinaryTree.node(node3, "/", nodeB)
let timesRight = BinaryTree.node(minus4, "*", divide3andB)
// root node
let tree = BinaryTree.node(timesLeft, "+", timesRight)您需要反向构建树，从叶子节点开始，一直到顶部。
添加description属性以便打印树，这会很有用的：
extension BinaryTree: CustomStringConvertible {
public var description: String {
switch self {
case let .node(left, value, right):
return "value: \(value), left = [\(left.description)], right = [\(right.description)]"
case .empty:
return ""
}
}
}如果你 print(tree) 你应该看到这样的东西：
value: +, left = [value: *, left = [value: 5, left = [], right = []], right = [value: -, left = [value: a, left = [], right = []], right = [value: 10, left = [], right = []]]], right = [value: *, left = [value: -, left = [], right = [value: 4, left = [], right = []]], right = [value: /, left = [value: 3, left = [], right = []], right = [value: b, left = [], right = []]]]通过一点想象力，您可以看到树形结构。 ;-)如果你缩进它会清晰的看到：
value: +,
left = [value: *,
left = [value: 5, left = [], right = []],
right = [value: -,
left = [value: a, left = [], right = []],
right = [value: 10, left = [], right = []]]],
right = [value: *,
left = [value: -,
left = [],
right = [value: 4, left = [], right = []]],
right = [value: /,
left = [value: 3, left = [], right = []],
right = [value: b, left = [], right = []]]]另一个有用的属性是计算树中的节点数：
public var count: Int {
switch self {
case let .node(left, _, right):
return left.count + 1 + right.count
case .empty:
return 0
}
}对于示例的树，tree.count应该是12。
您经常需要对树进行的操作遍历它们，即以某种顺序查看所有节点。 遍历二叉树有三种方法：
In-order（或深度优先）： 首先查看节点的左子节点，然后查看节点本身，最后查看其右子节点。
Pre-order： 首先查看节点，然后查看其左右子节点。
Post-order： 首先查看左右子节点最后处理节点本身。
译注：这三种遍历方式分别称为：前序（Pre-order），中序（In-order），后序（Post-order）
以下是您实现的方法：
public func traverseInOrder(process: (T) -> Void) {
if case let .node(left, value, right) = self {
left.traverseInOrder(process: process)
process(value)
right.traverseInOrder(process: process)
}
}
public func traversePreOrder(process: (T) -> Void) {
if case let .node(left, value, right) = self {
process(value)
left.traversePreOrder(process: process)
right.traversePreOrder(process: process)
}
}
public func traversePostOrder(process: (T) -> Void) {
if case let .node(left, value, right) = self {
left.traversePostOrder(process: process)
right.traversePostOrder(process: process)
process(value)
}
}这些函数会被递归调用，在使用树结构时很常见。
例如，如果您按 Post-order 遍历算术运算树，您将按以下顺序查看值：
5
a
10
-
*
4
-
3
b
/
*
+叶子节点首先出现。 根节点最后出现。
您可以使用堆栈计算机来评估这些表达式，类似于以下伪代码：
tree.traversePostOrder { s in
switch s {
case this is a numeric literal, such as 5:
push it onto the stack
case this is a variable name, such as a:
look up the value of a and push it onto the stack
case this is an operator, such as *:
pop the two top-most items off the stack, multiply them,
and push the result back onto the stack
}
the result is in the top-most item on the stack
}二叉搜索树(BST)
这里有个例子
二叉搜索树是一种特殊的 二叉树 (该树每个父节点最多有两个子节点)，在插入和删除后总是保持顺序。
想了解关于树的知识？请先看这里.
“排序”树
这里有一个二叉搜索树的图:
可以看到左边子节点总是比它的父节点小，而右边子节点总是比它的父节点大。这是二叉搜索树的关键特点。
如 2 比 7 小，因此它在左边，而 5 比 2 大，因此它在右边
插入一个新节点
插入新节点时，先与根节点比较，如果较小则走 左 分支，如果较大则走 右 分支。继续如此比较操作，直到我们找到一个空节点可以插入。
比如我们需要插入一个新值 9：
从根节点开始（根节点是
7）与新值9做比较，9 > 7，向右分支下移，这次遇到的节点是10因为
9 < 10， 向左下分支移动现在没有值可以进行比较，把
9插入这里
下面是插入 9 后的树：
对于新元素只有一个位置可以插入，查找该位置非常快，需要 O(h) 时间， h 为树的高度
注意： 节点 高度 是从此节点到叶子节点的步数。树的总高度是根节点到最低叶子节点的距离。许多二叉搜索树的操作是跟树个高度有关的。
通过遵循这个简单规则 -- 小值在左边，大值在右边。我们可以保持树的顺序，所以无论什么时候我们都可以查询这个值是否在树上。
树的查找
为了查找一个值是否在树中，我们采用以下的步骤：
如果值小于当前值，取左边树
如果值大于当前值，取右边树
如果当前值等于当前节点值，就找到了！
就像大部分对树的操作，查找也是不断的递归直到找到节点或者查找结束。
下面是搜索 5 的例子：
树的搜索是很快的，是 O(h) 时间复杂度。如果是一个平衡很好的树,即使有百万的节点，也不过需要 20 步就能结束查找(和二分搜索的思想很像)。
树的遍历
有时你需要遍历所有的节点，不仅仅只查找单个节点。
共有三种方式来遍历二叉树：
中序遍历（或者 深度优先）：先访问左子树，然后访问节点本身，最后访问右子树。
前序遍历：先访问节点本身，然后访问左子树，最后访问右子树。
后序遍历：先访问左子树，然后右子树，最后节点本身。
遍历树也会用到递归。
如果你中序遍历一个二叉搜索树，遍历的结果就像从小到大排列一样。上述例子中的树遍历结果为 1, 2, 5, 7, 9, 10 :
删除节点
删除节点很简单，删除节点后，把当前的节点替换为它的左子树最大的节点或者右子树最小节点。这样树在删除后还会保持原来的顺序。在下述例子中， 10 被移除， 图2 为用 9 代替， 图3 为用 11 代替。
替换节点只会在该节点有子节点的时候才会做，如果没有子节点，你可以直接从它的父节点中移除：
代码 (方法1)
理论介绍到此为止。来看看怎么实现吧，可以使用不同的方式实现， 首先我们先试试建一个基于类的版本，随后我们再用枚举来实现。
这是一个 二叉搜索树 的类：
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)
}
}
这是一个单节点，它使用了泛型可以存储任意类型数据，它引用了一个 left 和 right 子节点以及 parent 父节点。
来试试：
let tree = BinarySearchTree<Int>(value: 7)count 是指树上有多少个节点。它不仅仅统计直接连接的子节点，还包含了它的子节点以及子节点的全部后代。如果它是根节点，那么计算的是整个树。初始值为 0。
注意： 因为left，right和parent是可选值，我们正好可以使用 Swift 的可选链 (?) 以及可选值联合运算符 (??)。 也可以使用if let的方法，但是这样代码更简练。
插入
只有一个的树节点没什么意义，让我们插入一些新的节点：
public func insert(value: T) {
if value < self.value {
if let left = left {
left.insert(value: value)
} else {
left = BinarySearchTree(value: value)
left?.parent = self
}
} else {
if let right = right {
right.insert(value: value)
} else {
right = BinarySearchTree(value: value)
right?.parent = self
}
}
}类似树的其他操作，插入操作也是递归实现的。我们比较新值与已有节点来决定是放在左子树还是右子树。
如果没有左或右子树在比较了，创建一个 BinarySearchTree 对象并和 parent 建立连接。
注意： 因为整个二叉搜索树必须保持左边是小值，右边是大值的顺序，因此插入一个新元素后必须还是一个正确的二叉树。
插入一些节点吧：
let tree = BinarySearchTree<Int>(value: 7)
tree.insert(2)
tree.insert(5)
tree.insert(10)
tree.insert(9)
tree.insert(1)
注意： 为了后面讲的更清楚，需要随机插入数字，如果排序后再插入它们，树的形状可能会不正确。
创建一个支持数组插入的快捷方法 insert() ：
public convenience init(array: [T]) {
precondition(array.count > 0)
self.init(value: array.first!)
for v in array.dropFirst() {
insert(value: v)
}
}现在简单了：
let tree = BinarySearchTree<Int>(array: [7, 2, 5, 10, 9, 1])数组中的第一个元素是树的根节点。
Debug输出
在处理一些复杂的数据结构的时候，使用一些可读的 debug 输出非常有用。
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)
} else if value > self.value {
return right?.search(value)
} else {
return self // found it!
}
}逻辑非常明确：从当前节点开始（一般是从根节点开始）比较。如果目标值比当前节点小，继续从左子树查找，如果比当前节点值大，从右子树开始查找。
如果 left 或 right 为 nil，返回 nil 表示没有查到。
注意 在 Swift 中，使用可选链非常方便。left?.search(value)中left为 nil 的时候会自动返回 nil, 不需要明确的检查。
查找是一个递归的过程，也可以用一个简单的循环代替：
public func search(value: T) -> BinarySearchTree? {
var node: BinarySearchTree? = self
while 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(5)
tree.search(2)
tree.search(7)
tree.search(6) // nil前三行返回相应的 BinaryTreeNode 对象，最后一行返回 nil, 因为没有 6 这个节点。
注意： 如果树中含有重复值， search() 函数会返回最高的节点，这也很合理，因为是从根节点开始查找的。遍历
还记得遍历树的三种方式吗？ 下面就是其实现。
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) }This prints the following:
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
}
每个树上的节点调用 formula 后的结果存入数组中。 map() 是与中序遍历一起完成的。
下面是 map() 一个简单的使用例子：
public func toArray() -> [T] {
return map { $0 }
}这个函数可以把树的存值变成一个排序后的数组，在 playground 中试一下：
tree.toArray() // [1, 2, 5, 7, 9, 10]作为练习，你来实现 filter 和 reduce 吧。
删除
先定义一些帮助函数，让代码更加易读：
private func reconnectParentTo(node: BinarySearchTree?) {
if let parent = parent {
if isLeftChild {
parent.left = node
} else {
parent.right = node
}
}
node?.parent = parent
}这个函数的作用是批量修改树的 parent, left 和 right 指针。可以把当前节点（self）的父节点重新连接另一个子节点。
我们还需要一个函数返回节点的最小值和最大值：
public func minimum() -> BinarySearchTree {
var node = self
while let next = node.left {
node = next
}
return node
}
public func maximum() -> BinarySearchTree {
var node = self
while let next = node.right {
node = next
}
return node
}
剩余代码如下：
@discardableResult public func remove() -> BinarySearchTree? {
let replacement: BinarySearchTree?
//当前节点的代替者要么是左边的最大值，要么是右边的最小值，哪一个都不会为nil
if let right = right {
replacement = right.minimum()
} else if let left = left {
replacement = left.maximum()
} else {
replacement = nil
}
replacement?.remove()
// 把要代替的节点移到当前节点位置
replacement?.right = right
replacement?.left = left
right?.parent = replacement
left?.parent = replacement
reconnectParentTo(node:replacement)
//当前节点不再是树的一部分，因此可以清理删除了
parent = nil
left = nil
right = nil
return replacement
}深度和高度
某一节点的高度是它到最低叶子节点的距离。我们可以如下计算：
public func height() -> Int {
if isLeaf {
return 0
} else {
return 1 + max(left?.height() ?? 0, right?.height() ?? 0)
}
}取左右子树的高度作为该节点的高度。递归再一次解决了这个问题。 由于需要查看所有字节，时间复杂度为 O(n) 。
注意： Swift的可选值联合运算符可以减少left和right的判空处理，你也可以用if let，但是这样代码更简练。
测试:
tree.height() // 2节点 深度 是指到根节点的距离，代码如下：
public func depth() -> Int {
var node = self
var edges = 0
while let parent = node.parent {
node = parent
edges += 1
}
return edges
}
通过 parent 指针一步一步向上遍历树，直到找到根节点（ 根节点的 parent 值为空）。时间复杂度为 O(h) ：
if let node9 = tree.search(9) {
node9.depth() // returns 2
}前驱和后继
二叉搜索树总是 排序 的，但是这不意味着树中连续的数字是相邻的。
只看 7 的左子树是无法找到它的前驱的，因为左子树是 2, 正确的前驱是 5。 后驱也是类似。
predecessor() 函数返回当前节点的前驱
public func predecessor() -> BinarySearchTree<T>? {
if let left = left {
return left.maximum()
} else {
var node = self
while let parent = node.parent {
if parent.value < value { return parent }
node = parent
}
return nil
}
}有左子树的情况下，前驱就是左子树的最大值。（因为左子树均小于当前节点值，那么左子树最大的值就是最靠近节点的值，译者注）从上图中可以看到 5 是 7 左子树中最大的值。
如果没有左子树，只能一直遍历父节点直到找到比自己小的值。(右子树都不比自己大，左子树没有，最多可能在父节点中，译者注)。想知道 9 的前驱是谁吗？通过这样的方法找到的是 7。
后继 工作方式类似，做个左右对称替换就好了：
public func successor() -> BinarySearchTree<T>? {
if let right = right {
return right.minimum()
} else {
var node = self
while let parent = node.parent {
if parent.value > value { return parent }
node = parent
}
return nil
}
}这两个方法的时间复杂度为 O(h)
注意： 线索二叉树 变通了一下，把 无用 的左右指针重新设计用来直接指向前驱和后继节点。非常有想法！树是否合法呢？
有一些做法可以破坏树的结构，在非根节点上调用 insert() 方式可能会破坏树的结构。如：
if let node1 = tree.search(1) {
node1.insert(100)
}根节点是 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(1) {
tree.isBST(minValue: Int.min, maxValue: Int.max) // true
node1.insert(100) // EVIL!!!
tree.search(100) // nil
tree.isBST(minValue: Int.min, maxValue: Int.max) // false
}代码（方案2）
我们先用类实现了一次，也可以用枚举来实现。
关键的区别就是引用类型和值类型。基于类实现的树更新时是内存的同一个实例，而枚举实现的树是不可改变的，每次插入或者删除操作后会给你一个全新的一个树的拷贝，哪一种更好呢？ 这完全取决于你要做什么。
这是我们用枚举实现的二叉搜索树：
public enum BinarySearchTree<T: Comparable> {
case Empty
case Leaf(T)
indirect case Node(BinarySearchTree, T, BinarySearchTree)
}枚举有三种：
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 var height: Int {
switch self {
case .Empty: return -1
case .Leaf: return 0
case let .Node(left, _, right): return 1 + max(left.height, right.height)
}
}插入新节点如下：
public func insert(newValue: T) -> BinarySearchTree {
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), value, right)
} else {
return .Node(left, value, right.insert(newValue))
}
}
}
在 playground 调用:
var tree = BinarySearchTree.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) -> BinarySearchTree? {
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
}
}
}大多数的函数有相同的代码结构。
调用:
tree.search(10)
tree.search(1)
tree.search(11) // nil使用如下的方法做 Debug
extension BinarySearchTree: 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))"
}
}
}打印如下：
((1 <- 2 -> 5) <- 7 -> (9 <- 10 -> .))根节点在中点，点 代表是没有子节点。
树如果不平衡了..
平衡 二叉搜索树左右子树有相同的节点。在这种情况下是理想状态，树的高度是 log(n)， n 为节点的个数。
当一个分支明显的比其他长时查找会变的很慢。在最坏的情况下，树的高度变成 n， 这样不再是二叉搜索树，更像是 链表。时间复杂度变成 O(n)， 性能会差很多，非常糟糕。
一种方法是随机插入使得二叉搜索树保持平衡。一般情况下应该能保持树的平衡，但是这样无法保证，实际也确实如此。
另一种方式是使用 自平衡 的二叉搜索树。这种数据结构能在插入或删除后调整树的平衡。如 AVL树 和 红黑树。
更多
Binary Search Tree on Wikipedia
红黑树(Red-Black Tree)
A red-black tree (RBT) is a balanced version of a Binary Search Tree guaranteeing that the basic operations (search, predecessor, successor, minimum, maximum, insert and delete) have a logarithmic worst case performance.
红黑树（RBT）是二叉搜索树的平衡版本，保证基本操作（搜索，前驱，后继，最小，最大，插入和删除）具有对数最坏情况的性能。
Binary search trees (BSTs) have the disadvantage that they can become unbalanced after some insert or delete operations. In the worst case, this could lead to a tree where the nodes build a linked list as shown in the following example:
二叉搜索树（BST）的缺点是它们在一些插入或删除操作之后可能变得不平衡。 在最坏的情况下，这可能会变成链表的树，如以下示例所示：
译注：链表可看作是树的简单版本。
a
\
b
\
c
\
dTo prevent this issue, RBTs perform rebalancing operations after an insert or delete and store an additional color property at each node which can either be red or black. After each operation a RBT satisfies the following properties:
为了防止出现此问题，RBT在插入或删除后执行重新平衡操作，并在每个节点上存储额外颜色属性，可以是红色或黑色。 每次操作后，RBT都满足以下属性：
Properties
性质
Every node is either red or black
The root is black
Every leaf (nullLeaf) is black
If a node is red, then both its children are black
For each node, all paths from the node to descendant leaves contain the same number of black nodes
每个节点都是红色或黑色
根节点是黑色的
叶节点（nullLeaf）都是黑色的
如果节点为红色，则其子节点均为黑色
对于每个节点，从节点到后代叶子的所有路径都包含相同数量的黑色节点
Property 5 includes the definition of the black-height of a node x, bh(x), which is the number of black nodes on a path from this node down to a leaf not counting the node itself.
From [CLRS]
性质5包括节点x的黑色高度的定义，bh(x)，它是从该节点到不计算节点本身的叶子的路径上的黑色节点的数量。（来自 [CLRS]）
译注： CLRS 是指《算法导论》，CLRS是四位作者的首字母组合。
Methods
方法
Nodes:
nodeX.getPredecessor()Returns the inorder predecessor of nodeXnodeX.getSuccessor()Returns the inorder successor of nodeXnodeX.minimum()Returns the node with the minimum key of the subtree of nodeXnodeX.maximum()Returns the node with the maximum key of the subtree of nodeX
Tree:search(input:)Returns the node with the given key valueminValue()Returns the minimum key value of the whole treemaxValue()Returns the maximum key value of the whole treeinsert(key:)Inserts the key value into the treedelete(key:)Delete the node with the respective key value from the treeverify()Verifies that the given tree fulfills the red-black tree properties
The rotation, insertion and deletion algorithms are implemented based on the pseudo-code provided in [CLRS]
节点：
nodeX.getPredecessor()返回未排序的前驱节点nodeX.getSuccessor()返回inorder的后继节点nodeX.minimum()返回具有nodeX子树最小键的节点nodeX.maximum()返回具有nodeX子树的最大键的节点
树：search(input:)返回具有给定键值的节点minValue()返回整个树的最小键值maxValue()返回整个树的最大键值insert(key:)将键值插入树中delete(key:)使用树中相应的键值删除节点verify()验证给定的树是否满足红黑树属性
旋转，插入和删除算法基于[CLRS]中提供的伪代码实现
Implementation Details
实现细节
For convenience, all nil-pointers to children or the parent (except the parent of the root) of a node are exchanged with a nullLeaf. This is an ordinary node object, like all other nodes in the tree, but with a black color, and in this case a nil value for its children, parent and key. Therefore, an empty tree consists of exactly one nullLeaf at the root.
为方便起见，所有指向子节点的nil指针或节点的父节点（根节点的父节点）都与nullLeaf交换。 这是一个普通的节点对象，就像树中的所有其他节点一样，但是使用黑色，在这种情况下，它的子节点是父节点和键的nil值。 因此，空树在根处只包含一个nullLeaf。
Rotation
旋转
Left rotation (around x):
Assumes that x.rightChild y is not a nullLeaf, rotates around the link from x to y, makes y the new root of the subtree with x as y's left child and y's left child as x's right child, where n = a node, [n] = a subtree
左旋（围绕x）：
假设x的右子节点（x.rightChild）y不是nullLeaf，围绕从x到y的链接旋转，使y成为子树的新根节点，x为y的左子节点，y的左子节点（[B]）为x的右子节点，其中 n = a node, [n] = a subtree。
| |
x y
/ \ ~> / \
[A] y x [C]
/ \ / \
[B] [C] [A] [B]Right rotation (around y):
Assumes that y.leftChild x is not a nullLeaf, rotates around the link from y to x, makes x the new root of the subtree with y as x's right child and x's right child as y's left child, where n = a node, [n] = a subtree
右旋（围绕y）：
假设y的左子节点（y.leftChild）x不是nullLeaf，围绕从y到x的链接旋转，使x成为子树的新根节点，其中y为x的右子节点，x的右子节点为y的左子节点，其中 n = a node, [n] = a subtree。
| |
x y
/ \ <~ / \
[A] y x [C]
/ \ / \
[B] [C] [A] [B]As rotation is a local operation only exchanging pointers it's runtime is O(1).
由于旋转是仅交换指针的本地操作，因此它的运行时为O(1)。
Insertion
插入
We create a node with the given key and set its color to red. Then we insert it into the the tree by performing a standard insert into a BST. After this, the tree might not be a valid RBT anymore, so we fix the red-black properties by calling the insertFixup algorithm.
The only violation of the red-black properties occurs at the inserted node z and its parent. Either both are red, or the parent does not exist (so there is a violation since the root must be black).
我们用给定的键创建一个节点，并将其颜色设置为红色。 然后我们通过在BST中执行标准插入将其插入树中。 在此之后，树可能不再是有效的RBT，因此我们通过调用insertFixup算法来修复红黑属性。
唯一违反红黑属性的情况发生在插入的节点z及其父节点上。 两者都是红色，或者父级不存在（存在违规，因为根必须是黑色）。
We have three distinct cases:
Case 1: The uncle of z is red. If z.parent is left child, z's uncle is z.grandparent's right child. If this is the case, we recolor and move z to z.grandparent, then we check again for this new z. In the following cases, we denote a red node with (x) and a black node with {x}, p = parent, gp = grandparent and u = uncle
我们有三个不同的案例：
案例1： z的叔节点是红色的。 如果z.parent是左子节点，z的叔节点是z.grandparent的右子节点。 如果是这种情况，我们重新着色并将z移动到z.grandparent，然后我们再次检查这个新z。 在下面的例子中，我们用 (x)表示红色节点，用{x}表示黑色节点，p = 父节点，gp = 祖父节点，u = 叔节点
| |
{gp} (newZ)
/ \ ~> / \
(p) (u) {p} {u}
/ \ / \ / \ / \
(z) [C] [D] [E] (z) [C] [D] [E]
/ \ / \
[A] [B] [A] [B]
Case 2a: The uncle of z is black and z is right child. Here, we move z upwards, so z's parent is the newZ and then we rotate around this newZ. After this, we have Case 2b.
案例2a： z的叔节点是黑色，z是右子节点。 在这里，我们将z向上移动，假设z的父级是newZ，然后我们围绕这个newZ旋转。 在此之后，我们有下面案例2b。
| |
{gp} {gp}
/ \ ~> / \
(p) {u} (z) {u}
/ \ / \ / \ / \
[A] (z) [D] [E] (newZ) [C] [D] [E]
/ \ / \
[B] [C] [A] [B]
Case 2b: The uncle of z is black and z is left child. In this case, we recolor z.parent to black and z.grandparent to red. Then we rotate around z's grandparent. Afterwards we have valid red-black tree.
案例2b： z的叔节点是黑色而z是左子节点。 在这种情况下，我们将z.parent重新着色为黑色，将z.grandparent重新着色为红色。 然后我们围绕z的祖父母转动。 之后我们有了有效的红黑树。
| |
{gp} {p}
/ \ ~> / \
(p) {u} (z) (gp)
/ \ / \ / \ / \
(z) [C] [D] [E] [A] [B] [C] {u}
/ \ / \
[A] [B] [D] [E]
Running time of this algorithm:
Only case 1 may repeat, but this only h/2 steps, where h is the height of the tree
Case 2a -> Case 2b -> red-black tree
Case 2b -> red-black tree
As we perform case 1 at most O(log n) times and all other cases at most once, we have O(log n) recolorings and at most 2 rotations.
The overall runtime of insert is O(log n).
该算法的运行时间：只有案例1可以重复，但这只有h/2步，其中h是树的高度
案例2a -> 案例2b -> 红黑树
案例2b -> 红黑树
由于我们在最多O(log n)次执行情况1并且所有其他情况最多执行一次，我们有O(log n)重新着色并且最多2次旋转。
插入操作的整个运行时间为O(log n)。
Deletion
删除
We search for the node with the given key, and if it exists we delete it by performing a standard delete from a BST. If the deleted nodes' color was red everything is fine, otherwise red-black properties may be violated so we call the fixup procedure deleteFixup.
Violations can be that the parent and child of the deleted node x where red, so we now have two adjacent red nodes, or if we deleted the root, the root could now be red, or the black height property is violated.
We have 4 cases: We call deleteFixup on node x
Case 1: The sibling of x is red. The sibling is the other child of x's parent, which is not x itself. In this case, we recolor the parent of x and x.sibling then we left rotate around x's parent. In the following cases s = sibling of x, (x) = red, {x} = black, |x| = red/black.
我们使用给定key搜索节点，如果存在，我们通过从BST执行标准删除来删除它。 如果删除的节点的颜色为红色，则一切正常，否则可能会违反红黑属性，因此我们调用修复程序deleteFixup。
违规可能使是已删除节点x的父节点和子节点都为红色，因此我们现在有两个相邻的红色节点，或者如果我们删除了根节点，而新根节点可能是红色，或者违反了黑色高度属性。
我们有4种情况：我们在节点x上调用 deleteFixup
案例1： x的兄弟节点是红色的。 兄弟节点是x的父节点的另子节点，而不是x本身。 在这种情况下，我们重新着色x和x.sibling的父节点，然后我们围绕x的父级旋转。 在下列情况下，s = x的兄弟节点，（x）= 红色，{x} = 黑色，|x| = 红色/黑色。
| |
{p} {s}
/ \ ~> / \
{x} (s) (p) [D]
/ \ / \ / \
[A] [B] [C] [D] {x} [C]
/ \
[A] [B]
Case 2: The sibling of x is black and has two black children. Here, we recolor x.sibling to red, move x upwards to x.parent and check again for this newX.
案例2： x的兄弟节点是黑色，有两个黑色子节点。 在这里，我们将x.sibling重新着色为红色，将x向上移动到x.parent并再次检查此newX。
| |
|p| |newX|
/ \ ~> / \
{x} {s} {x} (s)
/ \ / \ / \ / \
[A] [B] {l} {r} [A] [B] {l} {r}
/ \ / \ / \ / \
[C][D][E][F] [C][D][E][F]
Case 3: The sibling of x is black with one black child to the right. In this case, we recolor the sibling to red and sibling.leftChild to black, then we right rotate around the sibling. After this we have case 4.
案例3： x的兄弟节点是黑色，右边有一个黑色子节点。 在这种情况下，我们将兄弟重新着色为红色和sibling.leftChild为黑色，然后我们右旋转兄弟。 在此之后我们有案例4。
| |
|p| |p|
/ \ ~> / \
{x} {s} {x} {l}
/ \ / \ / \ / \
[A] [B] (l) {r} [A] [B] [C] (s)
/ \ / \ / \
[C][D][E][F] [D]{e}
/ \
[E] [F]
Case 4: The sibling of x is black with one red child to the right. Here, we recolor the sibling to the color of x.parent and x.parent and sibling.rightChild to black. Then we left rotate around x.parent. After this operation we have a valid red-black tree. Here, ||x|| denotes that x can have either color red or black, but that this can be different to |x| color. This is important, as s gets the same color as p.
案例4： x的兄弟节点是黑色，右边是一个红色的孩子。 在这里，我们将兄弟重新着色为x.parent和x.parent以及sibling.rightChild的颜色为黑色。 然后我们左右旋转x.parent。 在此操作之后，我们有一个有效的红黑树。 这里，||x|| 表示x可以是红色或黑色，但这可能与|x|不同 颜色。 这很重要，因为s与p具有相同的颜色。
| |
||p|| ||s||
/ \ ~> / \
{x} {s} {p} {r}
/ \ / \ / \ / \
[A] [B] |l| (r) {x} |l| [E] [F]
/ \ / \ / \ / \
[C][D][E][F] [A][B][C][D]
Running time of this algorithm:
Only case 2 can repeat, but this only h many times, where h is the height of the tree
Case 1 -> case 2 -> red-black tree
Case 1 -> case 3 -> case 4 -> red-black tree
Case 1 -> case 4 -> red-black treeCase 3 -> case 4 -> red-black tree
Case 4 -> red-black tree
As we perform case 2 at most O(log n) times and all other steps at most once, we have O(log n) recolorings and at most 3 rotations.
The overall runtime of delete is O(log n).
该算法的运行时间：只有情况2可以重复，但这只有很多次，其中h是树的高度
案例1 -> 案例2 -> 红黑树
案例1 -> 案例3 -> 案例4 -> 红黑树
案例1 -> 案例4 -> 红黑树案例3 -> 案例4 -> 红黑树
案例4 -> 红黑树
由于我们在最多O(log n)次执行情况2并且所有其他步骤最多执行一次，因此我们有O(log n)重新着色并且最多3次旋转。
删除的总体运行时间是O(log n)。
资源：
[CLRS] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. 《算法导论》, 第三版. 2009