Swift - BST(구현)

JSLee·2022년 1월 17일
0

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)

굿!!!!!!!!!

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를 Remove 할경우는 9의 child들은 어떻게 될까요??

이런식으로 child를 root에 연결시키면 됩니다.
하지만 만약

이런 복잡한 Tree에서
25를 remove 하게 된다면 어떻게 될까요?

이런식으로 leaf의 가장 작은 값이 remove되는 자리에 replace되어 자리잡습니다.

 // 가장 작은값
    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
    }
profile
iOS/Android/FE/BE

0개의 댓글