参考链接
二叉查找树（BST）是二叉树的一个重要的应用，它在二叉树的基础上加上了这样的一个性质：对于树中的每一个节点来说，如果有左儿子的话，它的左儿子的值一定小于它本身的值，如果有右儿子的话，它的右儿子的值一定大于它本身的值。
二叉查找树的操作一般有插入、删除和查找，这几个操作的平均时间复杂度都为O(logn)，插入和查找操作很简单，删除操作会复杂一点，除此之外，因为二叉树的中序遍历是一个有序序列，就额外加上了一个中序遍历操作。
二叉查找树的应用不是很多，因为它最坏的时候跟线性表差不多，大部分会应用到它的升级版，平衡二叉树和红黑树，这两棵树都能把时间复杂度稳定在O(logn)左右。虽然不会用到，但是二叉查找树是一定要学好的，毕竟它是平衡二叉树和红黑树的基础。
接下来一步一步写一个二叉查找树模板。
第一步：节点信息
二叉查找树的节点和二叉树的节点大部分是一样的，不同的是，二叉查找树多了一个值出现的次数。如图1显示了二叉查找树的节点信息。
extension YYBSTree {
public class Node {
public var value: T
public var left: Node?
public var right: Node?
public init(value: T) {
self.value = value
}
public func unbind() {
left = nil
right = nil
}
public func cleanup() {
unbind()
}
}
}
第二步：二叉查找树类的声明
public struct YYBSTree<T: Comparable> {
public private(set) var root: Node?
public private(set) var length = 0
public var isEmpty: Bool { length == 0 }
}
第三步：插入
根据二叉查找树的性质，插入一个节点的时候，如果根节点为空，就此节点作为根节点，如果根节点不为空，就要先和根节点比较，如果比根节点的值小，就插入到根节点的左子树中，如果比根节点的值大就插入到根节点的右子树中，如此递归下去，找到插入的位置。重复节点的插入用值域中的freq标记。如图2是一个插入的过程。
二叉查找树的时间复杂度要看这棵树的形态，如果比较接近一一棵完全二叉树，那么时间复杂度在O(logn)左右，如果遇到如图3这样的二叉树的话，那么时间复杂度就会恢复到线性的O(n)了。
平衡二叉树会很好的解决如图3这种情况。
插入函数的代码如下：
mutating func insert(node: Node) {
node.unbind()
guard root != nil else {
root = node
return
}
var tmp = root
while let cur = tmp {
if cur.value == node.value {
return
} else {
if node.value < cur.value {
if cur.left == nil {
cur.left = node
break
} else {
tmp = cur.left
}
} else {
if cur.right == nil {
cur.right = node
break
} else {
tmp = cur.right
}
}
}
}
length += 1
}
第四步：查找
查找的功能和插入差不多一样，按照插入那样的方式递归下去，如果找到了，就返回这个节点的地址，如果没有找到，就返回nil。
代码如下：
func search(_ value: T) -> Node? {
var tmp = root
while let cur = tmp {
if cur.value == value {
return cur
} else {
if value < cur.value {
tmp = cur.left
} else {
tmp = cur.right
}
}
}
return nil
}
第五步：删除
删除会麻烦一点，如果是叶子节点的话，直接删除就可以了。如果只有一个孩子的话，就让它的父亲指向它的儿子，然后删除这个节点。图4显示了一棵初始树和4节点被删除后的结果。先用一个临时指针指向4节点，再让4节点的地址指向它的孩子，这个时候2节点的右儿子就变成了3节点，最后删除临时节点指向的空间，也就是4节点。
删除有两个儿子的节点会比较复杂一些。一般的删除策略是用其右子树最小的数据代替该节点的数据并递归的删除掉右子树中最小数据的节点。因为右子树中数据最小的节点肯定没有左儿子，所以删除的时候容易一些。图5显示了一棵初始树和2节点被删除后的结果。首先在2节点的右子树中找到最小的节点3，然后把3的数据赋值给2节点，这个时候2节点的数据变为3，然后的工作就是删除右子树中的3节点了，采用递归删除。
我们发现对2节点右子树的查找进行了两遍，第一遍找到最小节点并赋值，第二遍删除这个最小的节点，这样的效率并不是很高。能不能写出只查找一次就可以实现赋值和删除两个功能的函数呢？
如果删除的次数不是很多的话，有一种删除的方法会比较快一点，名字叫懒惰删除法：当一个元素要被删除时，它仍留在树中，只是多了一个删除的标记。这种方法的优点是删除那一步的时间开销就可以避免了，如果重新插入删除的节点的话，插入时也避免了分配空间的时间开销。缺点是树的深度会增加，查找的时间复杂度会增加，插入的时间可能会增加。
删除函数代码如下：
@discardableResult
mutating func delete(_ value: T) -> Bool {
var delete = root
var parent = root
while let cur = delete {
if cur.value == value {
delete = cur
break
} else {
delete = value < cur.value ? cur.left : cur.right
}
parent = cur
}
guard delete != nil else {
return false
}
/// 3，不删除，值替换
if delete?.left != nil, delete?.right != nil {
parent = delete
var min = delete?.right
while min?.left != nil {
parent = min
min = min?.left
}
/// 用最小节点替换待删除的
delete?.value = min!.value
/// 最小节点肯定没有左子树
/// 转换成删除只有一个节点的情况，parent和delete都变了
delete = min
}
/// 1,2同一种方式处理
if parent?.left === delete {
parent?.left = delete?.left ?? delete?.right
}
if parent?.right === delete {
parent?.right = delete?.left ?? delete?.right
}
/// 如果最后要删除的是root节点，root调整为左右非空子树
if delete === root {
root = parent?.left ?? parent?.right
}
delete?.unbind()
length -= 1
return true
}
第六步：中序遍历
写这个方法的目的是输出这个二叉查找树的有序序列。代码如下：
func travelInorder(_ node: Node?) {
guard let node = node else { return }
travelPreorder(node.left)
print(node.value)
travelPreorder(node.right)
}
对于二叉查找树不稳定的时间复杂度的解决方案有不少，平衡二叉树、伸展树和红黑树都可以解决这个问题，但效果是不一样的。
