[Swift] Binary Search Tree ( 이진 탐색 트리 ) 를 Swift로 구현해보자 + search / insert / delete

일단 나는 Binary Tree랑 Binary Search Tree 랑 늘 헷갈리니까 개념부터 명확히! 

 ( 출처 https://stackoverflow.com/questions/6380231/difference-between-binary-tree-and-binary-search-tree ) 

그니까 이진트리는 부모가 왼쪽 자식, 오른쪽 자식 ( 총 두개의 leaf ) 를 가질 수 있는 트리이다

이진 탐색트리는 현재 있는 노드보다 작은 값이 왼쪽에, 큰 값이 오른쪽에 있는 이진트리이다

아래와 같은 BST를 구현해보자 

// https://www.raywenderlich.com/990-swift-algorithm-club-swift-binary-search-tree-data-structure 참고 

// recursive enum 은 indirect 키워드 적어줘야함
indirect enum BinaryTree{
    case empty
    case node(left:BinaryTree,data:Int,right:BinaryTree)
}
 
 
let tree:BinaryTree = .node(
    left: .node(
        left:.node(left:.empty,data:1,right:.empty),
        data:2,
        right:.node(left:.empty,data:3,right:.empty)),
    data:4,
    right: .node(
        left:.node(left:.empty,data:5,right:.empty),
        data:6,
        right:.node(left:.empty,data:7,right:.empty))
)

1) 어떤 데이터가 BST에 있는 지 Search 해보자  ( where절은 정말 편하다 >_< ) 

extension BinaryTree{
    func hasData(_ data:Int)->Bool{
        switch self {
        case .empty:
            return false
        case let .node(_, nodeData, _) where data == nodeData:
            return true
        case let .node(left,nodeData,_) where data < nodeData:
            return left.hasData(data)
        case let .node(_,nodeData,right) where data > nodeData:
            return right.hasData(data)
        default:
            return false
        }
    }
}

결과를 확인하면...

 

print(tree.hasData(6))  // true
print(tree.hasData(10)) // false

2) 새로운 데이터를 BST 에 Insert해보자 

to be continued...