Swift - Binary Trees(Data Structure)

JSLee·2022년 1월 17일

Binary Trees

Binary Trees 란 Reference 가 최대 2개인 Node들로 이루어진 Tree 구조 입니다.
일단 기존 Tree 와 같은 Node와 Reference로 이루어진 사이클에 영향을 받지 않은 데이터구조 이지만 Tree는 Reference의 갯수가 정해지지 않습니다.

Binary Trees 는 조건이 붙습니다.
모든 Node는

왼쪽 자식Node(child Node) 에는 자신(Node) 보다 "작은"값
오른쪽 자식Node(child Node) 에는 자신(Node) 보다 "큰"값

이 주어져야 합니다.
이러한 모든 조건이 충족되어야 이진탐색트리 가 됩니다. 이밖에도

Node의 value 는 중복되지 않는다.
Node의 value는 옵셔널이 아니다.

이 두가지 조건또한 있습니다.

이 Gif 를 자세히 보시면 이해 되실겁니다.
출처:(https://blog.penjee.com/5-gifs-to-understand-binary-search-tree/#binary-search-tree-insertion-node))

그럼 이진 탐색 트리를 Swift로 구현해보겠습니다.

class BinaryNode<Element> {
    var value : Element
    var leftChild : BinaryNode?
    var rightChild : BinaryNode?
    init ( _ value : Element) {
        self.value = value
    }
}

class 를 정의할때 모든 data를 받을수 있도록 Element로 하겠습니다.
그리고 앞써 조건에 있듯 value는 옵셔널이 될면 안되기에 Non Optional 입니다.

그럼 진행하기 전에 순서 순회가 어떤식으로 작동하는지 부터 알아보겠습니다.

이러한 트리일 경우 순서 순회는

0 - 1 - 5 - 7 - 8 - 9

이런식으로 진행되게 됩니다.

처음 root인 7에서 leftChild에 0으로 먼저 접근합니다.
그렇게 되면 그 Node의 부모인 1 로 접근할수 있고 그뒤 right 5 로 접근할수 있습니다.
left의 접근이 완료되었으면 다시 root로 올라갑니다. 그뒤 right 8 -> 그의 부모 9 로
접근하는 것이지요

이제 코드로 한번 살펴보겠습니다.

extension BinaryNode {
	func traverseInOrder(visit : (Element) -> Void) {
        //재귀
        leftChild?.traverseInOrder(visit: visit)
        visit(value)
        rightChild?.traverseInOrder(visit: visit)
    }
}

위 코드는 재귀적 으로 작동합니다.

그럼 한번 값을 대입하고 출력해보겠습니다.

let ten = BinaryNode(10)
let nine = BinaryNode(9)
let one = BinaryNode(1)
let two = BinaryNode(2)
let three = BinaryNode(3)
let four = BinaryNode(4)
let six = BinaryNode(6)

ten.leftChild = two
ten.rightChild = nine
nine.leftChild = one
nine.rightChild = three
two.leftChild = four
two.rightChild = six

이런식으로 트리를 만들게 되면.

이런 트리가 만들어 지고
함수를 이용해서 값을 출력해 보겠습니다.

잘 작동하게 됩니다.

여기서 문제는 기본적으로 root 나 부모 Node를 통해서 child에 접근할수 있다는 것입니다.
그럼 이문제를 보완한 방법으로
중간에 root를 걸쳐 right로 접근하는것이 아닌 left의 접근이 끝나고 바로 right로 접근한뒤에 마지막으로 root의 접근하는 방법입니다.

    func traversePostOrder(visit : (Element) -> Void) {
        leftChild?.traversePostOrder(visit: visit)
        rightChild?.traversePostOrder(visit: visit)
        visit(value)
    }

출력해보겠습니다.

또한 선주문순회 라는것이 있습니다.
이것은 root를 첫 시작으로 밑으로 쭉쭉 내려가는 것을 의미합니다.

    func traversePreOrder(visit : (Element) -> Void) {
        visit(value)
        leftChild?.traversePreOrder(visit: visit)
        rightChild?.traversePostOrder(visit: visit)
    }

Binary Search Trees

Binary Search Trees(BST) 는 이진 검색 트리로써
예를 들어 설명해보겠습니다.

첫번째 Root에서 동물인지 아닌지를 묻습니다. 그리고 대답의 따라서
왼쪽과 오른쪽으로 나뉘게 되지요
만약 동물이 아닐경우 바위가 되고 동물일 경우 털이있는지 없는지의 여부를 묻습니다.
이러한 특정 노드 각각이 다음을 나타내는 Tree Node임을 알수 있습니다.
그렇게 우리는 질문에 예,아니오 두개의 답만을 하고 즉시 결과를 확인할수 있습니다.
이것은 기본적으로 검색의 대한 결과를 굉장히 빠르게 찾을수 있다는 장점이 있습니다.

Case Study - Array vs BST

위는 배열 Array
아래는 BST
이 두가지를 가지고 비교 해보겠습니다.

일단 배열에서는 각각을 비교하며 선형검색을 수행해야 합니다.
또한 배열은 항목수가 늘어남에 따라 검색하는 시간또한 길어집니다.

그럼 BST의 경우 를 살펴보겠습니다
예를 들어 105 의 값을 찾는다는 가정하에

BST는 root를 기준으로 임무를 수행합니다.
원하는 값 - 105 는 당연히 root보다 큰 값이기 때문에 right에 위치해 있습니다.
그럼 left는 search 할 필요가 없지요
그렇기 때문에 절반이라는 시간이 줄었습니다.
또한 우리는 그냥 질문에 대답만 합니다. 105 는 77 보다 큰값인가?라는 질문에 right로 대답하면 원하는 값을 찾을수 있습니다. 값이 만약 더아래에 있다고 해도 말이지요

Insert

또한 만약 insert할 경우를 예를 들어서 비교해보겠습니다.

배열에 sort를 이용하여 0 을 insert 할 경우입니다.
int형 Array 이기 때문에 0 의 값은 당연히 첫번째 요소로 자리매김 하게 됩니다.
하지만 실제로는 0이 insert되기 위해선 다른 요소들 전부가 뒤로 이동하게 됩니다.
따라서 특정 Array에는 복잡성이 추가되게 됩니다.