[Swift] 트리(Tree)

🌲 트리(Tree)란?

그래프의 부분집합으로, 사이클이 없는 하나의 연결 그래프를 뜻한다.
여기서 사이클이 없다는 말은 순환하지 않는다는 뜻으로, 트리는 최상위 노드인 루트 노드에서 자식 노드로 뻗어나가는 계층 데이터 구조를 이루고 있다.

위 사진에서 왼쪽은 트리, 오른쪽은 그래프다. 눈에 띄는 차이점은

• 트리는 계층 구조를 이루고 순환하는 구조를 포함하지 않는다는 점
• 그래프는 계층 구조 없이 순환하는 구조(사이클)를 포함하고 있다는 점

이 되겠다. 그 밖에도 차이점을 정리해보자면 다음과 같다.

	트리	그래프
방향성	방향 그래프 (위에서 아래로)	방향 그래프, 무방향 그래프 모두 존재
사이클	사이클이 불가능한 비순환 그래프	사이클이 있는 순환 그래프, 사이클이 없는 비순환 그래프 모두 존재
루트 노드	단 한개의 루트 노드 존재	루트 노드라는 개념 자체가 없음
부모-자식	모든 자식 노드는 하나의 부모 노드를 가짐 부모-자식 관계 존재	부모-자식이라는 개념 자체가 없음
모델	계층 모델	네트워크 모델
간선의 수	노드 당 연결된 간선의 수는 무조건 1개 이상 노드가 N인 트리는 항상 (N-1)의 간선을 가짐	0개 이상 (없어도 무방) 그래프에 따라 간선의 수가 다름
방향성	방향 그래프 (위에서 아래로)	방향 그래프, 무방향 그래프 모두 존재

트리를 구현하기 위한 코드는 다음과 같다.

public class TreeNode<T> {
  public var value: T 

  public weak var parent: TreeNode? 
  public var children = [TreeNode<T>]() 

  public init(value: T) {
    self.value = value
  }

  public func addChild(_ node: TreeNode<T>) { /
    children.append(node)
    node.parent = self 
  }
}

이진트리 (Binary Tree)

이진 트리는 각 노드에서 최대 두 개의 자식 노드만 지닐 수 있는 트리로, 최대 라는 단어가 중요하다. 꼭 두 개의 자식 노드를 가지지 않아도 된다! 이진 트리 안에서도 여러 개의 트리가 나뉘는데, 자세한 건 밑에서 살펴보겠다.

풀 이진 트리

각 노드는 자식 노드를 갖지 않던지, 자식 노드를 2개 가져야 한다. 말 그대로 정말 풀(full) 이진 트리다.

완전 이진 트리

마지막 단계를 제외한 모든 단계의 노드가 완전히 채워져 있는 상태의 트리다. 마지막 단계의 노드는 좌측부터 채워져야 한다는 제약도 있다.

퍼펙트 이진 트리

모든 내부 노드는 2개의 자식 노드를 가지고 있어야 한다. 또한 모든 잎(leaf) 노드를 동일한 깊이를 가져야 한다.

균형 이진 트리

노드가 삭제되거나 삽입될 경우 편향된 이진 트리가 되는 것을 막기 위해, 잎 노드까지의 깊이를 작게 유지하도록 하는 트리다.
편향된 이진 트리가 되지 않도록 하는 이유는 이진 탐색 트리의 규칙 때문이다. 이진 탐색 트리에서는 부모 노드를 기준으로 왼쪽에 있는 노드는 부모 노드보다 작아야 하고, 오른쪽에 있는 노드는 부모 노드보다 커야 한다. 그런데 트리의 깊이가 깊어지면 탐색해야 하는 횟수가 늘어나고, 이 경우 시간 복잡도는 O(n) 이 된다.
이러한 경우를 피하기 위해 높이를 최소로 유지해야 하고, 최소로 유지하기 위해 균형 이진 트리를 이용한다. 이 경우 시간 복잡도는 O(logn) 이다.

위 사진은 15를 삽입했을 때 어떻게 균형 이진 트리에서 깊이를 작게 유지하는지 보여주는 예시다.

이진 탐색 트리

위에서도 잠깐 설명했는데, 이진 탐색 트리는 다음과 같은 조건을 가지고 있는 트리다.

1. 부모 노드를 기준으로 왼쪽에 있는 자식 노드는 모두 부모 노드보다 작은 값을 가진다.
2. 부모 노드를 기준으로 오른쪽에 있는 자식 노드는 모두 부모 노드보다 큰 값을 가진다.

이진 탐색 트리에서 데이터를 검색하거나 추가하거나 삭제할 때, 트리의 깊이(depth)가 얼마나 되냐에 따라 시간복잡도는 O(n) 에서 O(logn) 의 값을 가질 수 있다. 시간복잡도는 위에서 설명했으니 넘어가겠다.

🔁 이진탐색트리(BST)의 순회 방식

트리는 크게 세 개의 순회 방식을 가질 수 있다. 이때 순회 방식이란 특정한 순서에 따라 노드를 방문하는 것으로, pre-order, post-order, in-order가 있다. 이름이 저렇게 붙여진 이유는 루트 노드를 어떤 순서로 방문하냐에 따라 바뀌는 것 같은데, pre-order는 루트 노드를 먼저, in-order는 루트 노드를 중간에, post-order는 루트 노드를 제일 마지막에 방문한다. 자세한 설명은 밑에서!

Pre-order (전위 순회)

Pre-order 방식은 루트 노드 -> 왼쪽 노드 -> 오른쪽 노드 순서로 서브트리를 방문한다. 이 때 방문은 재귀적으로 이루어지는데, 위 사진을 보면 대략적으로 어떤 프로세스를 가지고 있는지 알 수 있다.

코드로 구현한 방식은 다음과 같다.

func PreOrder(node: BinaryTreeNode?) {
    guard let node = node else {
        return
    }
    print(node.value)
    BinaryTreeNode.PreOrder(node: node.leftChild)
    BinaryTreeNode.PreOrder(node: node.rightChild)
}

In-order (전위 순회)

사진을 보면 알겠지만 노드가 오름차순으로 출력되는 것을 볼 수 있다.
In-order 방식은 왼쪽 노드 -> 루트 노드 -> 오른쪽 노드 순서로 서브트리를 재귀적으로 방문하기 때문에, 노드의 값은 작은 값부터 큰 값까지 정렬되어 출력된다.

코드는 다음과 같다.

func InOrder(node: BinaryTreeNode?) {
    guard let node = node else {
        return
    }
    BinaryTreeNode.InOrder(node: node.leftChild)
    print(node.value)
    BinaryTreeNode.InOrder(node: node.rightChild)
}

Post-order (후위 순회)

Post-order 방식은 왼쪽 노드 -> 오른쪽 노드 -> 루트 노드 순서로 서브트리를 재귀적으로 방문한다.

코드는 다음과 같다.

func PostOrder(node: BinaryTreeNode?) {
    guard let node = node else {
        return
    }
    BinaryTreeNode.PostOrder(node: node.leftChild)
    BinaryTreeNode.PostOrder(node: node.rightChild)
    print(node.value)
}

참고자료

Binary Trees (Part 4) - Discussing (in) Depth-First Traversals
[자료구조] 트리(Tree)란
[swift] 트리 / 그래프
[Swift] 스터디 5주차 - 트리 구조 기반의 알고리즘