BST

コード実装
Binary Node

class BinaryNode<Element> {
    var value : Element
    var left : BinaryNode?
    var right : BinaryNode?
    
    init(value : Element) {
        self.value = value
    }
}
extension BinaryNode : CustomStringConvertible {
    public var description: String {
        return diagram(for: self)
    }
    private func diagram(for node: BinaryNode?,
                         _ top: String = "",
                         _ root: String = "",
                         _ bottom: String = "") -> String {
       guard let node = node else {
            return root + "nil\n"
        }
        if node.left == nil && node.right == nil {
            return root + "\(node.value)\n"
        }
        return diagram(for: node.right, top + " ", top + "┌──", top + "│ ")
            + root + "\(node.value)\n"
            + diagram(for: node.left, bottom + "│ ", bottom + "└──", bottom + " ")
    }

}

BST

struct BinarySearchTrees<Element : Comparable> {
    private(set) var root : BinaryNode<Element>?
    init() { }
}
extension BinarySearchTrees : CustomStringConvertible {
    var description: String {
        guard let root = root else { return "Empty tree "}
        return String(describing: root)
    }
}
extension BinarySearchTrees {
    mutating func insert(_ value : Element) {
        root = insert(from: root, value: value)
    }
    private func insert(from node : BinaryNode<Element>?,value : Element) -> BinaryNode<Element> {
        guard let node = node else {
            return BinaryNode(value: value)
        }
        if value < node.value {
            node.left = insert(from: node.left, value: value)
        }else {
            node.right = insert(from: node.right, value: value)
        }
        return node
    }
}

値を入力して実行を試みる

var bst = BinarySearchTrees<Int>()
bst.insert(3)
bst.insert(1)
bst.insert(4)
bst.insert(0)
bst.insert(2)
bst.insert(5)
print(bst)

Good!!!!!!!!!

Search

func contains(_ value : Element) -> Bool {
        var current = root
        while let node = current {
            if node.value == value {
                return true
            }
            if value < node.value {
                current = node.left
            }else {
                current = node.right
            }
        }
        return false
    }

Remove

このようなBSTで、9のchild達が9を移動しようとしたらどうなりますか?

このようにchildをルートに接続します.
でももし.

この複雑な木の中で
25を外したらどうなりますか?

これにより、leafの最小値がremoveに置き換えられます.

 // 가장 작은값
    var min :  BinaryNode {
        return left?.min ?? self
    }

Node Classの最小値に保存する変数.

mutating func remove(_ value : Element) {
        root = remove(node : root , value : value)
    }
    private func remove(node : BinaryNode<Element>? ,value : Element) -> BinaryNode<Element>? {
        guard let node = node else { return nil }
        
        if value == node.value {
            if node.left == nil && node.right == nil {
                return nil
            }
            if node.left == nil {
                return node.right
            }
            if node.right == nil {
                return node.left
            }
            node.value = node.right!.min.value
            node.right = remove(node: node.right, value: node.value)
        }else if value < node.value {
            node.left = remove(node: node.left, value: value)
        }else{
            node.right = remove(node: node.right, value: value)
        }
        return node
    }