[Swift/자료구조] 4. Binary Search Tree (BST) 이진탐색트리

안녕하세요

이번시간에는 이진탐색트리에 대해 알아보도록 하겠습니다.

 

---

일단 알아보기 전에, Tree 구조를 알아야 합니다

 

Tree 란?

트리는 계층적 관계를 나타냅니다.

트리는 노드로 구성되고, 노드는 서로 연결되어 있습니다.

아래와 같이 나타냅니다.

 

트리 구조 특징

- 자식노드는 특정 노드 아래의 노드이며 부모노드는 그위의 노드이다.

- 노드에는 항상 하나의 보무노드만 있지만, 여러개의 자식노드를 가질 수 있다.

- 부모가 없는 노드는 루트노드라고 함

- 트리의 포인터(가르키는 방향이라고 생각)는 순환이 아님 -> 즉 위에서 아래로 뻗어나가는 구조이지, 다시 위로 갈 수는 없음

 

이러한 구조를 그래프(Graph)라고 하고, 트리는 사실 그래프의 아주 단순한 형태

(연결리스트도 트리의 간단한 버전임)

 

그렇다면 

 

이진 탐색 트리는 무엇일까요? 

이진 탐색 트리는 트리가 항상 정렬되도록 삽입, 삭제를 수행하는 특수한 종류의 이진 트리 입니다.

이진 트리 = 각 노드에 최대 두개의 자식 

 

일반적인 규칙은 다음과 같습니다.

1. 각 노드는 최대 두개의 자식노드를 가질 수 있습니다.

2. 각 노드의 왼쪽 자식 노드의 값은 자기보다 작아야 합니다.

3. 각 노드의 오른쪽 자식 노드의 값은 자기보다 커야 합니다.

 

동작 방식 

삽입 

만약 위의 그림에서 9를 삽입하고 싶다면?

 

1. 루트 노드에서 시작하여 비교합니다.

2. 9 > 7 이므로 오른쪽으로 내려갑니다.

3. 9 < 10 이므로 왼쪽 분기로 내려갑니다.

4. 비교할 값이 없으므로 해당 위치에 삽입됩니다.

 

검색(탐색)

삽입과 비슷한 단계를 수행, 트리 구조 때문에 검색 속도가 빠름. 

1. 값이 현재 노드보다 작으면 왼쪽 노드를 가져옴

2. 값이 현재 노드보다 크면 오른쪽 노드를 가져옴

3. 값 = 현재노드, 탐색완료 

 

Swift로 구현해보기

 

삽입

class BinarySearchTree<T: Comparable> {
    var value: T
    var parent: BinarySearchTree?
    var left: BinarySearchTree?
    var right: BinarySearchTree?
    
    init(value: T) {
        self.value = value
    }
    
    func insert(_ value: T) {
        insert(value, parent: self)
    }
    
    private func insert(_ value: T, parent: BinarySearchTree) {
        if value < self.value {
            if let left = left {
                left.insert(value, parent: left)
            } else {
                left = BinarySearchTree(value: value)
                left?.parent = parent
            }
        } else {
            if let right = right {
                right.insert(value, parent: right)
            } else {
                right = BinarySearchTree(value: value)
                right?.parent = parent
            }
        }
    }
}

let tree = BinarySearchTree<Int>(value: 5)
tree.insert(6)
tree.insert(2)
tree.insert(9)
tree.insert(8)

 

위와 같이 일반적으로 재귀함수로 구현합니다.

 

검색(탐색)

요소를 빠르게 찾는 것이 이진탐색트리의 주된 목적이다. (빠르게 찾을 수 있음)

    func search(_ value: T) -> BinarySearchTree? {
        if value < self.value {
            return left?.search(value)
        } else if value > self.value {
            return right?.search(value)
        } else {
            return self
        }
    }

 

보통 루트노드에서 시작하여 값을 비교하기 시작합니다. 역시 재귀함수로 구현합니다.

일치하는 값이 없으면 nil 을 반환합니다. 

 

---

출처

https://victorqi.gitbooks.io/swift-algorithm/content/binary_search_tree_bst.html

Binary Search Tree (BST) · Swift Algorithm