基本概念

二叉排序树（Binary Sort Tree），又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树。

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 它的左、右子树也分别为二叉排序树。

二叉排序树查找

• Swift代码实现

//二叉树结点
class BinaryTreeNode {
    var data: Int                   //结点存储数据
    var leftChild: BinaryTreeNode?  //左孩子指针
    var rightChild: BinaryTreeNode? //右孩子指针
    
    //初始化方法
    init(data: Int) {
        self.data = data
    }
}

//二叉排序树查找结果
class SearchResult {
    //存储查找的结点，如果查找成功就是当前查找成功的结点
    var searchNode: BinaryTreeNode?
    
    //存储当前查找结点的直接父母结点
    var parentNode: BinaryTreeNode?
    
    //查找成功为true,查找失败为false
    var isFound: Bool = false
}

/**
 * 二叉排序树查找
 * @param currentRoot 当前二叉排序树的根结点或子树的根结点
 * @param parentNote  currentRoot的父母结点，如果currentRoot是整个二叉排序树的根结点，则该参数为nil
 * @param key         查找的关键字
 *
 * @return            返回查找的结果对象 
 */
 fileprivate func searchBST(currentRoot: BinaryTreeNode?,
                               parentNode: BinaryTreeNode?,
                               key: Int) -> SearchResult {
        let searchResult = SearchResult()
        
        //查找失败，返回该结点的父母结点（便于插入）
        if currentRoot == nil {
            searchResult.parentNode = parentNode
            searchResult.isFound = false
            return searchResult
        }
        
        //查找成功，返回查找成功的结点，将isFound设置为true
        if key == currentRoot!.data {
            searchResult.searchNode = currentRoot
            searchResult.parentNode = parentNode
            searchResult.isFound = true
            return searchResult
        }
        
        if key < currentRoot!.data { //在左子树继续查找
            return searchBST(currentRoot:currentRoot?.leftChild, parentNode: currentRoot, key: key)
        } else { //在右子树继续查找
            return searchBST(currentRoot:currentRoot?.rightChild, parentNode: currentRoot, key: key)
        }
 }

• 图示查找过程
  

二叉排序树插入

• Swift代码实现

/**
 * 二叉排序树插入
 * @param parentNote 待插入结点的父母结点
 * @param key        待插入的数据
 */
fileprivate func insertBST(parentNode: BinaryTreeNode?, key: Int) {
        //创建结点
        let node = BinaryTreeNode(data: key)
        
        //如果parentNote为nil,说明当前二叉排序树为空树
        guard parentNode != nil else {
            rootNode = node //待插入结点更新为整个二叉排序树的根结点
            return
        }
        
        if key < parentNode!.data { //插入为左孩子
            parentNode?.leftChild = node
        } else { //插入为右孩子
            parentNode?.rightChild = node
        }
}

• 图示插入过程
  

二叉排序树创建

• Swift代码实现
  二叉排序树的创建就是不断查找和插入的过程。

/**
 * 根据提供的集合创建二叉排序树
 */
fileprivate func createBST() {
        for key in items {
            //查找key
            let searchResult = searchBST(currentRoot: rootNode, parentNode: nil, key: key)
            
            //如果查找失败，则插入到二叉排序树上
            if !searchResult.isFound {
                insertBST(parentNode: searchResult.parentNode, key: key)
            }
        }
}

二叉排序树删除

删除叶子结点或仅有左右子树之一的结点

• Swfit代码实现

/**
 * 待删除的结点是叶子结点或者只有一个孩子
 * @param searchResult 待删除结点搜索结果
 * @param subNote      待删除结点孩子
 */
fileprivate func deleteNodeWithZeroOrOneChild(searchResult: SearchResult, subNode: BinaryTreeNode?) {
        //将待删除结点的左右孩子指针置空
        searchResult.searchNode?.leftChild = nil
        searchResult.searchNode?.rightChild = nil
        
        guard let parentNode = searchResult.parentNode else { //如果待删除结点为整个二叉排序树的根结点
            rootNode = subNode //更新根结点
            return
        }
        
        if searchResult.searchNode!.data < parentNode.data { //待删除结点的孩子成为待删除结点父母结点的左孩子
            parentNode.leftChild = subNode
        } else { //待删除结点的孩子成为待删除结点父母结点的右孩子
            parentNode.rightChild = subNode
        }
}
    

• 图示删除过程

删除左右子树都有的结点

• Swift代码实现

/**
 * 待删除的结点有左右子树
 *
 * 这边以待删除结点右子树最左边的结点(最小)覆盖、删除为例。然取左子树最右边的结点亦可！！！
 */
fileprivate func deleteNodeWithTwoChild(searchResult: SearchResult) {
        //初始化游标结果对象，用于存储右子树最小结点（最左边）
        let cursorResult = SearchResult()
        cursorResult.parentNode = searchResult.searchNode
        cursorResult.searchNode = searchResult.searchNode?.rightChild
        cursorResult.isFound = false
        
        //寻找待删除结点右子树最左边的结点
        while cursorResult.searchNode?.leftChild != nil {
            cursorResult.parentNode = cursorResult.searchNode
            cursorResult.searchNode = cursorResult.searchNode?.leftChild
        }
        
        //将右子树最左边的结点赋值给待删除结点
        searchResult.searchNode!.data = cursorResult.searchNode!.data
        
        //删除右子树最左边的结点
        deleteBST(searchResult: cursorResult)
}
    

• 图示删除过程

总结

• 二叉排序树是以链接的方式存储，保持了链接存储结构在执行插入或删除操作时不用移动元素的优点，只要找到合适的插入和删除位置后，仅需修改链接指针即可。插入删除的时间性能比较好。
• 而对于二叉排序树的查找，走的就是从根结点到要查找结点的路径，其比较次数等于给定值的结点在二叉排序树的层数。极端情况，最少为1次，即根结点就是要找的结点，最多也不会超过数的深度。
• 也就是说，二叉排序树的查找性能取决于二叉排序树的形状。因插入和删除亦依赖于查找，故而，如何构建一棵平衡的二叉排序树（深度与完全二叉树相同，即深度最小）显得尤为重要。
• 本篇博客只对二叉排序树的核心代码进行了介绍，完整实例请移步github