数据结构-二叉搜索树

Wu_Candy

发布于 2022-07-04 20:10:40

1980

发布于 2022-07-04 20:10:40

文章被收录于专栏：无量测试之道

这是无量测试之道的第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

  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 
    }