数据结构-二叉搜索树

思考

在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

  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
        }
}

添加元素的方法，也就是构建二叉树方法

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()，

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。

欢迎关注【无量测试之道】公众号，回复【领取资源】,
Python编程学习资源干货、
Python+Appium框架APP的UI自动化、
Python+Selenium框架Web的UI自动化、
Python+Unittest框架API自动化、

资源和代码免费送啦~
文章下方有公众号二维码，可直接微信扫一扫关注即可。

备注：我的个人公众号已正式开通，致力于测试技术的分享，包含：大数据测试、功能测试，测试开发，API接口自动化、测试运维、UI自动化测试等，微信搜索公众号：“无量测试之道”，或扫描下方二维码：

添加关注，让我们一起共同成长！