Swift 5.3 数据结构 —— 二叉搜索树 BinarySearchTree

二叉搜索树 BinarySearchTree

二叉搜索树是二叉树的一种，特点是左节点小于本身，本身小于右节点
leftChild.value < value < rightChild.value

1.二叉搜索树定义

因为要保持自身的特性，所以root是只读属性，二叉树里的元素必须遵守Comparable协议

public struct BinarySearchTree<Element: Comparable> {
    public private(set) var root: BinaryNode<Element>?
    public init() {}
}

2.插入方法

根据二叉搜索本身的特性，插入和搜索的速度都是很快的，小的向左，大的向右

extension BinarySearchTree {
    public mutating func insert(_ value: Element) {
        root = insert(from: root, value: value)
    }
    
    private mutating func insert(from node: BinaryNode<Element>?, value: Element) -> BinaryNode<Element> {
        guard let node = node else {
            return BinaryNode(value: value)
        }
        
        if value < node.value {
            node.leftChild = insert(from: node.leftChild, value: value)
        } else {
            node.rightChild = insert(from: node.rightChild, value: value)
        }
        
        return node
    }
}

3. 查询方法

常规的二叉树查询方法，是依次遍历每一个节点，二叉搜索树可以根据比较大小更快的完场查找遍历

public extension BinarySearchTree {
//    func contains(_ value: Element) -> Bool {
//        guard let root = root else {
//            return false
//        }
//
//        var found = false
//        root.traverseInOrder {
//            if $0 == value {
//                found = true
//            }
//        }
//        return found
//    }
    
    func contains(_ value: Element) -> Bool {
        var current = root
        while let node = current {
            if node.value == value {
                return true
            }
        
            if value < node.value {
                current = node.leftChild
            } else {
                current = node.rightChild
            }
        }
        return false
    }
}

4. 删除方法

删除节点的方法，要考虑三种情况
1）左右节点都是nil，可以直接删除
2）左节点或者右节点为nil，删除的时候，需要把子节点跟父节点对接
3）左右节点都不是nil，需要拿到右节点的最小值替换到被删除的节点，然后在右节点移除最小值

extension BinarySearchTree {
    public mutating func remove(_ value: Element) {
        
    }
    
    private func remove(node: BinaryNode<Element>?, value: Element) -> BinaryNode<Element>? {
        guard let node = node else {
            return nil
        }
        if value == node.value {
            if node.leftChild == nil && node.rightChild == nil {
                return nil
            }
            if node.leftChild == nil {
                return node.rightChild
            }
            if node.rightChild == nil {
                return node.leftChild
            }
            node.value = node.rightChild!.min.value
            node.rightChild = remove(node: node.rightChild, value: node.value)
            
        } else if value < node.value {
            node.leftChild = remove(node: node.leftChild, value: value)
        } else {
            node.rightChild = remove(node: node.rightChild, value: value)
        }
        
        return node
    }
}

github仓库地址 https://github.com/SunZhiC/DataStructuresInSwift

References

Data Structures & Algorithms in Swift by Matthijs Hollemans.
https://github.com/apple/swift-algorithms
https://github.com/raywenderlich/swift-algorithm-club