二叉搜索树

群组
欢迎加入群组,闲聊工作&技术&问题等

二叉查找树定义

二叉搜索树也叫二叉查找树(Binary Search Tree)是二叉树的一个类型.二叉搜索树具有以下性质:
1)若任意节点的左子树不空,则左子树上所有节点的值均小于它根节点的值;
2)若任意节点的右子树不空,则右子树上所有节点的值均大于它根节点的值;
3)任意节点的左右子树也分别为二叉查找树;
4)没有键值相等的节点.
二叉查找树相比去其他数据结构的优势在于查找,插入的时间复杂度较低,为O(logn).二叉查找树是基础数据结构,长用于构建更为抽象的数据结构,如集合,关联数组等.搜索,插入,删除的复杂度等于树高,期望O(logn),最坏O(n),虽然二叉查找树的最坏效率是O(n),但它支持动态查询,而且一些改进版的二叉查找树可以使树高为O(logn),从而将最坏效率将至O(logn),如AVL树,红黑树等.
二叉查找树的存储结构常用二叉链表来构建.

二叉搜索树

二叉查找树实现

这里二叉查找树的存储结构我们用的是上一节定义的二叉树.

// MARK: - 二叉查找树
class BinarySearchTree<T:Comparable> {

    private(set) var root:BinaryTree<T>?

    // MARK: - 构造函数
    init() {

    }
}

查找

查找逻辑:
1)从根节点开始查找,如果待查找的值等于根节点的值,直接返回;
2)如果待查找的值小于根节点的值,则在根节点的左子树执行查找;
3)如果待查找的值大于根节点的值,则在根节点的右子树执行查找;
4)递归执行以上步骤

/// 查找例程
    ///
    /// - Parameter value: 待查找的值
    /// - Returns: 查找到的值
    func find(value:T) -> BinaryTree<T>? {
       guard let node = binaryTree else { return nil }

        if node.value == value {
            return node
        } else if value < node.value {
            return find(binaryTree: node.leftChildNode, value: value)
        } else {
            return find(binaryTree: node.rightChildNode, value: value)
        }
    }

在我们的示例中,查找128:
数组需要对整个列表进行查找,逐个元素比较128是否相等;
二叉搜索树则先比较和根元素120比较,128比120大,则在120的右子树查找,然后找到130,128比130小,则在130的左子树找,最终找到.

插入

插入逻辑:
1)先创建一个新节点,如果新节点的值与根节点的值相等,则插入到根节点位置;
2)如果新节点的值小于等于根节点的值,则将新节点赋值给根节点的左子树;
3)如果新节点的值大于根节点的值,则将新节点赋值给根节点的右子树;
4)递归执行以上步骤.

/// 插入例程
    ///
    /// - Parameter value: 插入的值
    /// - Returns: 插入后返回的二叉查找树
    func insert(value:T) -> Void {
        root = insert(root: root, value: value)
    }

    private func insert(root binaryTree:BinaryTree<T>?, value:T) -> BinaryTree<T>? {
        guard let node = binaryTree else { return BinaryTree(value: value) }
        if value <= node.value {
            node.leftChildNode = insert(root: node.leftChildNode, value: value)
        } else {
            node.rightChildNode = insert(root: node.rightChildNode, value: value)
        }
        return node
    }

删除

删除逻辑:
1)删除的节点是叶子节点,直接删除;
2)删除的节点只有一个儿子,则将其儿子赋值给当前节点
3)删除的节点有两个儿子,则需要将此节点替换为左子树最大的子节点或者右子树最小子节点

func delete(value:T) -> Void {
        root = delete(binaryTree: root, value: value)
    }

    private func delete(binaryTree:BinaryTree<T>?, value:T) -> BinaryTree<T>? {
        guard let node = binaryTree else { return nil }
        if node.value == value {

            // 左右节点都为空
            if node.leftChildNode == nil && node.rightChildNode == nil {
                return nil
            }

            // 左右节点有一个为空
            if node.leftChildNode == nil {
                return node.rightChildNode
            }

            if node.rightChildNode == nil {
                return node.leftChildNode
            }

            // 左右节点都不为空
            // 将左子树中最小的节点赋值给当前节点
            node.value = (node.rightChildNode?.minNode.value)!

            // 删除右子树中最小节点
            node.rightChildNode = delete(binaryTree: node.rightChildNode, value: node.value)

        } else if value < node.value {
            node.leftChildNode = delete(binaryTree: node.leftChildNode, value: value)
        } else {
            node.rightChildNode = delete(binaryTree: node.rightChildNode, value: value)
        }

        return node
    }

最小值

最小值一直遍历二叉搜索树的左子树,直到左子树为空.

/// 最小值
    ///
    /// - Returns: 最小值节点
    func min() -> BinaryTree<T>? {
        guard let node = root else { return nil }
        var tmp = node

        while tmp.leftChildNode != nil {
            tmp = tmp.leftChildNode!
        }
        return tmp
    }

最大值

最大值一直遍历二叉搜索树右子树,直到右子树为空

/// 最大值
    ///
    /// - Returns: 最大值节点
    func max() -> BinaryTree<T>? {
        guard let node = root else { return nil }
        var tmp = node
        while tmp.rightChildNode != nil {
            tmp = node.rightChildNode!
        }
        return tmp
    }

源码地址

        这里的实现代码已放到GitHub,测试用例详见DataStructureAlgorithmTests.swift文件

参考文献

《数据结构与算法分析C语言描述》(Data Structures and Algorithm Analysis in C:Second Edition)–译者: 冯舜玺
https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9


  转载请注明: waitwalker 二叉搜索树

 上一篇
AVL树 AVL树
群组欢迎加入群组,闲聊工作&技术&问题等 AVL树定义AVL树是一个带平衡条件的二叉搜索树.AVL树得名于它的发明者G. M. Adelson-Velsky和Evgenii Landis,他们在1962年的论文《An al
下一篇 
Swift 5 新增特性 Swift 5 新增特性
群组欢迎加入群组,闲聊工作&技术&问题等 ABI稳定Swift 社区最近最重大的新闻应该就是 ABI 稳定了.ABI稳定就是binary接口稳定,也就是运行的时候只要是Swift5或者以上的编译器编译出来的binary,就
2019-04-26
  目录