[Swift] 이진 탐색 트리

안녕하세요. 밀쿄입니다.

오늘은 이진 탐색 트리에 대해서 알아보겠습니다.

이진 탐색트리는 두 자료구조를 결합한 자료 구조 입니다.

그 자료 구조 중 하나는 탐색이 빠르지만 삽입 삭제가 안되고 

다른 하나는 삽입 삭제는 빠르지만 탐색에 O(n)이란 복잡성을 가지고 있습니다.

그래서 그 두개를 합쳐서 탐색이 빠르고 삽입삭제가 빠른걸 만들고자 고안이 되었습니다.

그래서 그 두 개가 무엇인지 궁금하실텐데 바로 이진 트리와 연결리스트입니다.

자 그럼 이진 탐색 트리에 대해 본격적으로 알아보겠습니다

 

이진 탐색트리는 다음과 같은 특징을 가지고 있습니다.

각 노드의 왼쪽 서브트리에 있는 노드의 값은 부모 노드보다 그 값이 작다.

각 노드의 오른쪽 서브트리에 있는 노드의 값은 부모 노드보다 그 값이 크다

 

들어가기전에 스위프트에 대표적인 자료 구조인 Array와 비교해서 효율이 얼마나 나오는지 살펴보겠습니다.

먼저 탐색부터 살펴보겠습니다

Array는 탐색할 때 앞에서부터 모든 요소를 체크하게 됩니다. 따라서 O(n)의 효율을 갖습니다,

그럼 이진 탐색 트리는 어떨까요?

찾는 값이 현재 노드값보다 작으면 왼쪽으로 크면 오른쪽으로 탐색할 것 입니다.

따라서 불필요한 요소 체크를 안하게될 것이고 탐색 속도가 절반으로 줄어들겠죠. 따라서 O(log n)의 효율을 갖습니다.

두 번째 삽입을 살펴보겠습니다.

이번에도 역시 Array부터 보겠습니다,

만약에 우리가 0번째에 삽입을 한다면 모든 값이 뒤로 밀려나므로 O(n)의 효율을 가지게됩니다.

그럼 이진 탐색트리는 어떨까요?

일단 탐색을 하고 마지막 노드 끝에 삽입을 하게 됩니다 따라서 O(log n)의 효율을 갖습니다.

삭제 역시 마찬가지입니다.

Array는 O(n)의 효율을 이진 탐색트리는  O(log n)의 효율을 갖습니다.

단 이것은 평균적인 값이고 최악의 경우 이진탐색트리가 한쪽으로 치우치면  O(n)의 효율을 갖게됩니다.

 

그럼 바로 한 번 구현을 해보도록 합시다.

public struct BinarySearchTree<Element> {
    public var root: BinaryNode<Element>?
    public init() { }
}
public class BinaryNode<Element> {
    public var value: Element
    public var leftChild: BinaryNode?
    public var rightChild: BinaryNode?
    
    public init(value: Element) {
        self.value = value
    }
}

제일 기본이 되는 뼈대 입니다.

노드 하나가 값과 왼쪽 자식과 오른쪽 자식을 가지기 때문에 이렇게 만들어 줍시다.

이제 여기서 연산을 덧붙여 나가봅시다.

먼저 살펴볼 연산은 삽입 연산 입니다.

먼저 생각을 해봅시다. 1이라는 노드에 2를 넣는다고 말이죠

먼저 1이란 노드가 있으므로 현재 root는 1을 가지고 있는 노드가 됩니다.

그러므로 root의 leftChild나 rightChild는 nil인 상태가 되게됩니다.

악필인거 죄송합니다. ㅠㅠ

2는 1보다 크므로 오른쪽에 들어가야합니다.

if value < node.value {
    node.leftChild = insert(from: node.leftChild, value: value)
} else {
    node.rightChild = insert(from: node.rightChild, value: value)
}

즉 nil값을 가질때 삽입을 하게 하면 됩니다. ( 현재 1의 rightChild는 nil 입니다. )

guard let node = node else {
    return BinaryNode(value: value)
}

그렇게 rightchild를 바꿔준 root를 현재 root와 바꿔주면 됩니다.

쉽게말하면서 현재 value가 1, leftChild, rightChild가 nil인 저 root와

valuer가 1 leftchild는 nil rightChild는 value가 2, leftChild, rightChild가 nil인 상태를 가지는 root로 바꿔주면 되는겁니다.

root = insert(from: root, value: value)

삽입 연산자 입니다.

여기서 아마 다음과 같은 에러가 나실껍니다.

"Binary operator '<' cannot be applied to two 'Element' operands"

BinarySearchTree에 Element가 Comparable의 채택하고 있지 않아서 비교할수 없기 때문에 나는 에러입니다.

선언부로 다시 돌아가셔서 다음과 같이 수정해줍시다.

public struct BinarySearchTree<Element: Comparable>

에러를 하고 출력을 해봅시다

var bst = BinarySearchTree<Int>()
for index in 0 ..< 5 {
    bst.insert(index)
}

print(bst.root?.value ?? "NIL")
print(bst.root?.leftChild?.value ?? "NIL")
print(bst.root?.rightChild?.value ?? "NIL")
print(bst.root?.rightChild?.rightChild?.value ?? "NIL")
print(bst.root?.rightChild?.rightChild?.rightChild?.value ?? "NIL")
print(bst.root?.rightChild?.rightChild?.rightChild?.rightChild?.value ?? "NIL")
//출력
//0
//NIL
//1
//2
//3
//4

rightChild에만 값이 삽입이 된 것을 확인할 수 있습니다. 이렇게되면 아까말한 효율이 안 좋은 경우가 됩니다.( O(n) )

그렇기 떄문에 트리는 좌우 균형이 어느정도 맞는게 좋습니다. 

그 다음은 검색을 구현해보겠습니다.

검색은 쉽개 생각합시다. 탐색하다가 값이 일치하면 그 값이 찾는값이겠죠?

extension BinarySearchTree {
    public func findValue(_ value: Element) -> Bool {
        var currentNode = root
        
        while let node = currentNode {
            
            if node.value == value {
                return true
            }
            
            if node.value > value {
                currentNode = node.leftChild
            } else {
                currentNode = node.rightChild
            }
        }
        
        return false
    }
}

이제 삭제연산에 대해서 알아봅시다. 삭제 연산은 경우의 수가 나뉘기 떄문에 다소 복잡합니다. 

자식 노드가 없을경우, 자식 노드가 하나만 있는경우, 자식  노드가 다 있는 경우 총 세가지 입니다.

여기서 9를 삭제한다고 하면 어떻게 해야할까요?

그냥 9를 지워버리면 될 것 같죠? 네 그렇습니다 저녀석만 삭제하고 연결을 끊으면 됩니다.

즉. 잎새노드의 경우에는 그냥 잎새노드만 삭제하면 끝입니다. 말그대로 잎새이기 때문에 자식을 가지지 않으므로 그냥 삭제하면 됩니다.

그렇다면 그 다음 경우인 자식을 하나 가진 노드의 경우엔 어떻게 할까요?

16을 10과 연결한 후에 12를 삭제합니다. 

이렇듯 자식을 하나 가진 노드 경우에는 삭제하기 전에 삭제할 노드의 자식을 삭제한 노드의 부모노드랑 연결해주면 됩니다. 그리고 삭제.

문제는 자식을 두 개 가진 노드입니다. 이 경우가 좀 복잡합니다..

방법은 크게 두가지 입니다. 오른쪽 노드에서 젤 작은 값을 옮기거나 왼쪽 노드에서 젤 큰값을 옮기거나

다음 그래프를 보겠습니다.

여기서 12를 삭제한다고 생각해봅시다. 12를 삭제하면 12의 오른쪽 노드 중에 젤 작은 값은 20 입니다.

그렇다면 여기서 20을 옮겨봅시다.

이렇게 되겠죠? 이러면 우리는 20을 삭제 해야합니다.

자식 노드가 하나 있으니까 20이랑 24를 연결하고 20을 삭제하면 되겠죠? ( 두번째 경우에서 다뤘던 거랑 같습니다 )

삭제 연산은 이렇게 하면됩니다.

소스코드로 구현해봅시다.

먼저 첫번째 경우부터 소스로 만들어 봅시다.

if node.leftChild == nil && node.rightChild == nil {
    return nil
}

간단하죠?

그 다음에 자식 노드가 하나인 경우에는 다음과 같이 해주시면 됩니다.

if node.leftChild == nil {
    return node.rightChild
}
if node.rightChild == nil {
    return node.leftChild
}

이렇게 해주시면 됩니다.

그럼 마지막 경우가 문제인것 처럼 보이는데 쉽게 생각해봅시다.

현재 node의 값을 오른쪽 노드의 최솟값으로 바꾸고 삭제 연산을 했었죠?

오른쪽 노드의 최솟값은 무엇인가요? 왼쪽 노드를 타고 가다가 더 왼쪽 노드가 nil이면 그 값이 최솟값 이겠죠?

그걸 그대로 코드로 녹여주시면 됩니다.

extension BinaryNode {
    var min: BinaryNode {
        return leftChild?.min ?? self
    }
}

node.value = node.rightChild!.min.value
node.rightChild = remove(node: node.rightChild, value: node.value)

이걸 하나의 코드로 녹이는 작업은 여러분에게 맡기겠습니다.

제가 해보니 insert에서 봤던 코드랑 유사해지네요

이렇게 BST에 대해서 알아봤습니다. 

뭔가 대게 어려웠던 기분이네요. 실제로 이거 이해하는데 2일정도 걸렸던것 같습니다...

 

제가 보고 있는 책은 다음과 같습니다

https://store.raywenderlich.com/products/data-structures-and-algorithms-in-swift

Data Structures & Algorithms in Swift