这是无量测试之道的第159篇原创
思考
在n个动态的整数中搜索某个整数?(查看其是否存在) 假设使用动态数组存放元素，从第 0 个位置开始遍历搜索，平均时间复杂度:O(n)。如果维护一个有序的动态数组，使用二分搜索，最坏时间复杂度:O(logn) 但是添加、删除的平均时间复杂度是 O(n) 针对这个需求，有没有更好的方案? 今天我们主要讲的就是二叉搜索树，使用二叉搜索树，添加、删除、搜索的最坏时间复杂度均可优化至:O(logn)。
概念
树是一种数据结构，比如二叉树、B树、红黑树等等，也有3叉树等等。但是并不是每种树都用实际的作用。树这种数据结构之所以在编程中很有作用，是因为它的某些独特的特性刚好满足一些实际的需求。那我们今天开始先学习二叉搜索树。 二叉搜索树是二叉树的一种，是应用非常广泛的一种二叉树，英文简称为 BST(Binary Search Tree) 。又被称为:二叉查找树、二叉排序树。
特性 ：
- 任意一个节点的值都大于其左子树所有节点的值
- 任意一个节点的值都小于其右子树所有节点的值
- 它的左右子树也是一棵二叉搜索树
作用和要求 ：
- 二叉搜索树可以大大提高搜索数据的效率
- 二叉搜索树存储的元素必须具备可比较性 比如 int、double 等 如果是自定义类型，需要指定比较方式 不允许为 null 下图就是一个二叉搜素树：【可以对照下图来理解二叉搜索树的星性质】
如何构建一个二叉搜素树
案例：比如将数字12 插入到上述的这颗二叉树中，那么它的插入思路是什么了？
- 找到父结点parent
- 创建新的结点
- parent.left = node 或者 parent.right= node
具体的我们来走一下：
- 12 先和根结点的值13进行相比，12<13,所以，12在根结点的左子树上
- 12与root.left的结点相比较，也就是9。12>9,所以12在以9为根结点的右子树上
- 所以12与node(9).right也就是11进行比较，12>11，所以12在node(11)结点的右边
- 最后发现node(11).right == null ,所以12 就插到node(11)的right结点上
插入后的二叉搜索树，也满足二叉搜素树的性质
编码实现
二叉树，可以使用数组或者链表的数据结构来存储这些结点信息。本文的代码使用的是链表这种数据结构。【其中T是泛型】 定以一个结点类Node
代码语言：javascript复制 class Node<T: MyCompareable> {
var element: T
var left: Node<T>?
var right: Node<T>?
var parent: Node<T>?
init(_ element: T, _ parent: Node<T>?) {
self.element = element
self.parent = parent
}
}
添加元素的方法，也就是构建二叉树方法
代码语言：javascript复制func add(element: T) {
//添加第一个结点
if root == nil {
root = createNode(element: element, parent: nil)
return
}
var node = root
var parent = root
var cmp = 0
while node != nil {
guard let cNode = node else { return }
cmp = bstCompare(e11:element, e12: cNode.element)
parent = node
if cmp > 0 {
node = cNode.right
}else if cmp < 0 {
node = cNode.left
}else {
node?.element = element
return
}
}
//插入到父结点的哪个位置
let newNode = createNode(element: element, parent: parent)
if cmp > 0 {
parent?.right = newNode
}else {
parent?.left = newNode
}
afterAdd(node: node)
capacity = 1
}
其中bstCompare()，
代码语言：javascript复制1. e1==e2，return 0
2. e1 > e2, return 1
3. e1 < e2, return -1
private func bstCompare(e11: T, e12: T) -> Int {
return T.compare(e1:e11, e2: e12)// 相等就==0
}
代码解析
- 开始插入结点时，root == null,所以直接创建结点node，并root= node ，然后返回
- 然后插入第二个结点，如果第二个结点的值小于root的值，则第二个结点为root的左结点，反之为右结点。
- 后序插入第三、第四...个结点，就像插入结点12一样。找到其父结点，然后插入即可。
总结
今天主要介绍了二叉搜索树这种数据结构和特性，以及如何构建一颗二叉搜索树。最后提示下，如果使用中序遍历这颗二叉搜素树，你会得到一个升序的list。
