티스토리 뷰

반응형



일단 나는 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 참고 






1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 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))
)
cs




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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
        }
    }
}
cs



결과를 확인하면...

 

1
2
print(tree.hasData(6))  // true
print(tree.hasData(10)) // false
cs



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



to be continued... 

반응형
댓글