[알고리즘] 알고리즘 뽀개기 (6) : 트리

알고리즘 뽀개기 Step 6 : 트리

알고리즘을 최대한 간단하면서 빼먹는 부분이 없게 복습 및 요약하기 위해 포스팅을 하려고 합니다 :)

해당 내용은 백준 알고리즘 강의를 기반으로 작성되었습니다.
추천한 문제는 일부만 해설되어있으며, 언어는 Kotlin 입니다.

트리

• 자료 구조의 일종으로, 사이클이 존재하지 않는 그래프
• 정점의 개수가 V라면, 간선의 개수가 V-1
• 루트(root) : 특정 정점으로부터 아래로 방향을 정할 수 있다
  • 위의 트리에서는 1을 루트로 볼 수 있다.
• 부모(parent) : 1은 2,3의 부모이며, 2는 4,5의 부모이다.
• 자식(child) : 2는 1의 자식이며, 4는 2의 자식이다.
  • 3의 자식은 6,7이다.
• 단말 정점(leaf node) : 트리의 마지막 노드를 말함
  • 위 트리의 단말 정점은 4,5,6,7이다.
• 형제 (sibling) : 같은 부모의 노드를 말함
  • 4와 5는 형제이다.
• 깊이 (depth) : 루트에서부터의 거리를 말한다. (루트이 깊이를 0이나 1로 한다)
  • 위 트리는 깊이가 2 혹은 3이다. (0부터 일 경우 2)
• 높이 (height) : 깊이 중, 가장 큰 값
  • 트리에서 각 단말 정점들의 깊이가 같지 않을 수 있다. 따라서, 트리의 높이에 대한 값이 존재.
• 조상/자손 : p -> q 로 갈 수 있을 때, 루트보다 가까운 노드가 p 이면, p는 q의 조상이며, q는 p의 자손이다.
• 이진 트리 : 자식을 최대 2개씩만 가지고 있는 트리 (위의 트리는 이진 트리이다.)

트리의 표현

• 트리는 그래프의 종류이기 때문에, 그래프와 같은 방식으로 저장할 수 있다.
• 트리의 모든 노드는 부모를 하나 혹은 0개 (루트일 경우)만 가지기 때문에, 부모만 저장하는 방식으로 저장 가능
• 부모가 0개인 경우는 트리의 루트로, -1 이나 0으로 저장하는 방식 사용
  
• 이진 트리의 경우 A[V][2] 사이즈의 배열로 표현가능
  • A[i][0]에 왼쪽 자식을, A[i][1]에 오른쪽 자식을 저장할 수 있다.

트리의 순회

• 트리에서도 그래프와 같이 DFS, BFS 의 방법을 사용할 수 있지만, 트리에서 사용 가능한 세가지 방법으로 순회가 가능하다.
  • 프리오더 (pre-order) : 노드 방문을 처음에 한다
    • 노드를 방문
    • 왼쪽 자식 노드를 루트로 하는 서브 트리 프리오더 순회
    • 그 후, 오른쪽 자식 노드를 루트로 하는 서브 트리 프리오더 순회
  • 인오더 (in-order) : 노드 방문을 순회 중간에 한다
    • 왼쪽 자식 노드를 루트로 하는 서브 트리 인오더 순회
    • 노드 방문
    • 오른쪽 자식 노드를 루트로 하는 서브 트리 인오더 순회
  • 포스트 오더(post-order) : 노드 방문을 마지막에 한다
    • 왼쪽 자식 노드를 루트로 하는 서브 트리 포스트오더 순회
    • 오른쪽 자식 노드를 루트로 하는 서브 트리 포스트오더 순회
    • 노드 방문

해당 트리를 각 순회 방법으로 탐색 할 경우 아래와 같다.

• pre-order : ABDEGCF
• in-order : DBGEACF
• post-order : DGEBFCA

트리의 탐색

• 트리는 사이클이 없는 그래프이기 때문에, 임의의 두 정점 사이의 경로는 1개이므로, 해당 거리가 최단 거리가 될 것이다. 따라서, BFS 알고리즘을 이용해 최단거리를 구할 수 있다.

트리의 지름

• 트리에 존재하는 모든 경로 중, 가장 긴 것의 길이를 트리의 지름이라고 한다.
• 트리의 지름은 탐색 2번으로 구할 수 있다.
  • 탐색 1 : 투르에서 모든 정점까지의 거리를 구한다. 이때, 가장 먼 거리였던 정점을 A라고 하고 이를 기억한다.
  • 탐색 2 : A를 루트라고하고 모든 정점까지의 거리를 구한다. 이때 구한 가장 먼 거리가 지름이다.

복습 문제

트리의 순회 (1991번)

코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val tree = mutableMapOf<String, Pair<String?,String?>>()
    tree["A"] = Pair(null, null)

    //first 가 left node, second가 right node가 된다.
    for (i in 1..n) {
        val (parent, leftChild, rightChild)  = readLine().split(" ").map { it.toString() }
        val left = if (leftChild == ".") {
            null
        } else {
            leftChild
        }

        val right = if (rightChild == ".") {
            null
        } else {
            rightChild
        }

        tree[parent] = Pair(left, right)

        if (left != null && !tree.containsKey(left)) {
            tree[left] = Pair(null, null)
        }

        if (right != null && !tree.containsKey(right)) {
            tree[right] = Pair(null, null)
        }
    }

    fun travel(order : Order, node: String, result : String) : String {
        var tmpResult : String = result
        if (order == Order.PRE_ORDER) {
            tmpResult += node
        }

        tree[node]?.first?.let { leftChild ->
            tmpResult = travel(order, leftChild, tmpResult)
        }

        if (order == Order.IN_ORDER) {
            tmpResult += node
        }

        tree[node]?.second?.let { rightChild ->
            tmpResult = travel(order, rightChild, tmpResult)
        }

        if (order == Order.POST_ORDER) {
            tmpResult += node
        }

        return tmpResult
    }

    println(travel(Order.PRE_ORDER, "A", ""))
    println(travel(Order.IN_ORDER, "A", ""))
    println(travel(Order.POST_ORDER, "A", ""))
}

enum class Order {
    PRE_ORDER, IN_ORDER, POST_ORDER
}