介绍
二叉搜索树是一种特殊的 二叉树 。二叉搜索树有以下特性：
-
左边子节点的值小于父节点的；
-
右边子节点的值大于或等于父节点的
比如如下所示：
由于二叉搜索树有这些特性，所以对于已经排序好的数据它能够很好的提高数据的查找，添加，删除操作的性能，时间复杂度都是O(log n)。
实现
代码实现是在 二叉树 的基础上添加的。
这是前面二叉树实现的完整代码：
class BinaryNode<Element> {
var value: Element
var leftChild: BinaryNode? // 左节点
var rightChild: BinaryNode? // 右节点
init(value: Element) {
self.value = value
}
}
extension BinaryNode {
func traverseInOrder(visit: (Element) -> Void) {
leftChild?.traverseInOrder(visit: visit)
visit(value)
rightChild?.traverseInOrder(visit: visit)
}
func traversePreOrder(visit: (Element) -> Void) {
visit(value)
leftChild?.traversePreOrder(visit: visit)
rightChild?.traversePreOrder(visit: visit)
}
func traversePostOrder(visit: (Element) -> Void) {
leftChild?.traversePostOrder(visit: visit)
rightChild?.traversePostOrder(visit: visit)
visit(value)
}
}
extension BinaryNode {
// O(n)
var height: Int {
if leftChild == nil && rightChild == nil { return 0 }
return 1 + max(leftChild?.height ?? 0, rightChild?.height ?? 0)
}
}
extension BinaryNode: CustomStringConvertible {
public var description: String {
diagram(for: self)
}
private func diagram(for node: BinaryNode?,
_ top: String = "",
_ root: String = "",
_ bottom: String = "") -> String {
guard let node = node else {
return root + "nil\n"
}
if node.leftChild == nil && node.rightChild == nil {
return root + "\(node.value)\n"
}
return diagram(for: node.rightChild,
top + " ", top + "┌──", top + "│ ")
+ root + "\(node.value)\n"
+ diagram(for: node.leftChild,
bottom + "│ ", bottom + "└──", bottom + " ")
}
}
复制代码节点插入
由于二叉搜索树的左节点的值小于右节点的值，所以每次对比都是要插入的节点比较左右节点的值的大小，然后递归比较完，直到找到添加节点的位置。
二叉搜索树的基本代码：
struct BinarySearchTree<Element: Comparable> {
var root: BinaryNode<Element>?
}
extension BinarySearchTree: CustomStringConvertible {
var description: String {
guard let root = root else {
return "empty tree"
}
return String(describing: root)
}
}
复制代码实现代码：
extension BinarySearchTree {
mutating func insert(_ value: Element) {
root = insert(from: root, value: value)
}
private func insert(from node: BinaryNode<Element>?, value: Element) -> BinaryNode<Element>? {
// 如果节点位置已经为空了，创建新节点，这个就是插入的位置
guard let node = node else {
return BinaryNode(value: value)
}
if value < node.value {
// 左节点赋值&更新
node.leftChild = insert(from: node.leftChild, value: value)
} else {
// 右节点赋值&更新
node.rightChild = insert(from: node.rightChild, value: value)
}
return node
}
}
复制代码可以看到插入数据操作每次都是对比一边的数据，时间复杂为 O(log n)，如果是数组数据结构的插入，那么插入位置后面的所有元素都需要后移一位，时间复杂度为 O(n)。
测试插入操作：
func insertTest() {
var tree = BinarySearchTree<Int>()
tree.insert(5)
tree.insert(2)
tree.insert(3)
tree.insert(0)
tree.insert(7)
tree.insert(8)
print("before inserting:")
print(tree)
tree.insert(6) // 插入 6
print("after inserting:")
print(tree)
}
复制代码输出；
before inserting:
┌──8
┌──7
│ └──nil
5
│ ┌──3
└──2
└──0
after inserting:
┌──8
┌──7
│ └──6
5
│ ┌──3
└──2
└──0
复制代码节点查询
查询某个节点是否存在，一个直接的解决办法就是遍历所有的节点，看能否查找到。比如：
extension BinarySearchTree {
func contains(_ value: Element) -> Bool {
guard let root = root else {
return false
}
var found = false
// O(n)
root.traverseInOrder { node in
if node == value {
found = true
}
}
return found
}
}
复制代码但是这是一个 O(n) 操作。
利用二叉搜索树的特性优化后的代码实现是这样的：
extension BinarySearchTree {
func contains(_ value: Element) -> Bool {
var current = root
// O(log n)
while let node = current {
if node.value == value {
return true
}
if value < node.value {
current = node.leftChild
} else {
current = node.rightChild
}
}
return false
}
}
复制代码节点删除
删除节点就需要要比插入和查询复杂了，需要考虑以下情况。
- 该节点是叶子节点
这个删除的时候方便，直接把它删除就好了。
- 该节点有一个子节点
解决的办法是子节点替换原来的节点位置。
- 该节点有两个子节点
根据二叉搜索树的特性，把右节点位置最小的节点移动替换要删除的节点位置，再删除原来替换的最小节点。
比如：
要删除节点1，那么把节点2的值替换到节点1，再删除节点2，使二叉搜索树删除节点以后还是一棵二叉搜索树。
代码实现：
extension BinaryNode {
// 找到最小节点
var min: BinaryNode {
leftChild?.min ?? self
}
}
extension BinarySearchTree {
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 {
// 叶子节点
if node.leftChild == nil && node.rightChild == nil {
return nil
}
// 只有一个右节点
if node.leftChild == nil {
return node.rightChild
}
// 只有一个左节点
if node.rightChild == nil {
return node.leftChild
}
// 有两个子节点，替换位置，删除替换后右节点的树中的最小节点
node.value = node.rightChild!.min.value
node.rightChild = remove(node: node.rightChild, value: node.value)
} else if value < node.value {
node.leftChild = remove(node: node.leftChild, value: value)
} else {
node.rightChild = remove(node: node.rightChild, value: value)
}
return node
}
}
复制代码练习
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
实现代码：
extension BinaryNode where Element: Comparable {
var isBinarySearchTree: Bool {
return isBST(self, min: nil, max: nil)
}
private func isBST(_ tree: BinaryNode<Element>?, min: Element?, max: Element?) -> Bool {
guard let tree = tree else {
return true
}
if let min = min, min >= tree.value {
return false
} else if let max = max, max < tree.value {
return false
}
return isBST(tree.leftChild, min: min, max: tree.value) &&
isBST(tree.rightChild, min: tree.value, max: max)
}
}
复制代码
