[CM201] 09. 트리 (Tree)

트리 (Tree)

 아래 세 조건들을 만족할 때, 그래프는 트리(Tree)가 됩니다.

• 연결되어 있을 것 (Connected)
• 방향이 없을 것 (Undirected)
• 회로가 아닐 것 (No simple circuit)

 만약 다른 조건은 모두 만족하지만 연결되어 있지 않다면, 숲(Forest)이라고 부르기도 합니다.

트리의 몇 가지 성질들

 정의에 따라 트리가 구성된다면, 아래 특징들을 만족함을 알 수 있습니다.

Theorem 1.
그래프 $T$가 트리라면, 두 점을 잇는 경로는 하나씩만 존재한다.

Theorem 2.
그래프 $T$가 $n$개의 점을 가지는 트리라면, 총 $n-1$개의 선을 가진다.

Theorem 3.
그래프 $T$가 트리임은 아래와 동치이다.

• $T$는 연결되어 있고(connected) 순환하지 않는다(acyclic).
• $T$는 연결되어 있고(connected) 총 $n-1$개의 선을 가진다.
• $T$는 순환하지 않고(acyclic), 총 $n-1$개의 선을 가진다.

정리2 - 증명

 다른 건 직관적으로 이해할 수 있는데, $n-1$개의 선을 가지게 된다는 사실은 조금 생각이 필요해보이죠. 수학적 귀납법을 통해 증명해보겠습니다.

 1) 기본 단계. 트리의 점 개수가 $n=1$인 경우입니다. 이 때는 어떤 선도 생길 수 없으므로(루프가 있으면 회로가 생기기 때문에 안됩니다), 선의 개수는 $n-1 = 0$개가 맞습니다.

 2) 귀납적 단계. 트리의 점 개수가 $n$개일 때 $n-1$개의 선이 있다고 가정합시다. 당연히 연결되어 있고 순환하지 않는 조건으로요. $n+1$개의 점을 가지는 트리 $T$가 있다고 할 때, 우리는 $T$ 안에서 가장 긴 경로 $P$를 찾을 수 있을 것입니다.

 $T$는 순환하지 않으니까, $P$는 회로가 될 수 없습니다. 때문에 $P$의 시작점이나 도착점은 그 차수가 1일 수 밖에 없어요. 만약 1보다 더 크다면 더 이어진 선이 있다는 뜻이고, 그렇게 된다면 $P$는 가장 긴 경로가 아니게 되니까요.

 (무엇이 되었든)시작점 또는 도착점 중 하나를 $v$라고 합시다. 이제 $T$에서 이 점을 빼 볼거에요($v$와 연결된 선도 빠지겠죠). $v$가 빠진 새로운 그래프를 $T^*$라고 할게요. 우선 $T^*$가 트리를 만족하는지 살펴봅시다. $v$는 차수가 1이므로, 어떠한 두 점도 $v$를 통해 연결되어 있지 않습니다. 따라서 원래 연결되어 있고 순환하지 않던 $T$는 $v$ 하나가 빠졌다고 해서 연결이 끊어지거나 순환 회로가 생겨나지 않을 것입니다. 따라서 $T^*$도 똑같이 트리라고 볼 수 있겠죠.

 이제 $T^*$가 몇 개의 점을 가지고 있는지 살펴봅시다. $T$의 점은 $n+1$개였고, 거기서 점 $v$를 빼내었으니 $T^*$는 $n$개의 점을 가지고 있을 것입니다. $n$개의 점을 가진 트리, 우리는 귀납적 단계 초기에 가정을 했었죠? 트리의 점 개수가 $n$개일 때 $n-1$개의 선이 있다고요. 가정대로라면, $T^*$는 $n-1$개의 선을 가지고 있겠네요.

 우리가 $T^*$를 만들 때 몇 개의 선을 뺐을까요? $v$의 차수가 1이었으니, 함께 제거된 선 또한 1개입니다. 따라서 원래 그래프 $T$에서 선의 개수는 $(n-1)+1=n$개가 되고, 점 $n+1$개의 경우에도 정리를 만족함을 보일 수 있습니다. $\Box$

신장 트리 (Spanning tree)

 어떤 그래프 $G$에 대해서 모든 점을 포함하는 하위 트리가 있을 때, 그 트리를 신장 트리(Spanning tree)라고 부릅니다. 신장 트리가 존재한다면 그 그래프는 연결되어 있다고 볼 수 있으며, 그 반대도 성립합니다.

신장 트리는 그래프 순회를 통해 쉽게 찾을 수 있습니다. 순회 방법중 대표적인 것은 깊이 우선 탐색(Depth First Search, DFS)과 너비 우선 탐색(Breath First Search, BFS)이 있습니다. 이에 대한 것은 ‘알고리즘’ 포스트에서 더 자세히 다루겠습니다.

루트 트리 (Rooted tree)

 앞서 제시한 트리의 정의를 보면, 그 이름처럼 나무(tree)를 연상시키기는 어렵지 않나요? 뻗어져 나가 갈라지는 구조를 가지긴 했지만 나무보다는 뭐랄까, 아메바같잖아요.

 그래서 좀더 나무 같은 모습이 되도록 트리를 재정의해봅시다. 자고로 나무라면 그 근원이 되는 뿌리가 있어야 하는 법이죠. 트리의 한 점에게 루트(root)라는 역할을 부여해봅시다. 그렇다면 이 그래프는 출발점을 가진 루트 트리(Rooted tree)가 되어 한 곳에서 한 방향으로 뻗어나가는 모습이 될 것입니다.

 이제 좀 트리같지 않나요?

이진 트리 (Binary tree)

 이진 트리(Binary tree)는 트리의 특별한 형태로, 하나의 노드가 최대 두 개의 자식을 가질 수 있습니다. 모든 노드가 0개 혹은 2개의 자식을 가진다면 가득 채워져 있다(Full binary tree)고 하고, 모든 잎 노드의 높이가 동일하다면 균형 잡혀 있다(Balanced binary tree)고 말합니다.

 좀 더 일반적으로 가면, 하나의 노드가 최대 m개의 자식을 가질 수 있는 m-항 트리(m-ary tree)를 정의할 수도 있습니다.

Theorem 4.
가득 찬 m-ary 트리의 $i$개의 내부 노드를 가질 때, 총 $mi + 1$개의 노드와 $(m-1)i + 1$개의 잎 노드를 가진다.

Theorem 5.
가득 찬 m-ary 트리의 높이가 $h$일 때, 최대 $m^h$개의 잎 노드를 가질 수 있다.

동형사상 (Isomorphism)

 그래프에서의 동형사상에 대해 기억하나요? 트리 또한 그래프의 일종이니, 똑같이 동형사상에 대해 이야기해볼 수 있습니다. 정의는 그래프에서 다루었던 그것과 동일합니다. 두 트리 $T_1 = (V_1, E_1)$, $T_2 = (V_2, E_2)$가 있을 때 각각의 점과 선들이 대응되는 일대일 함수 $f: V_1 \rightarrow V_2$ 와 $g: E_1 \rightarrow E_2$ 가 다음을 만족한다면, 동형사상이라고 말할 수 있습니다.

\[e=(w, v) \in E_1 \; \leftrightarrow \; g(e)=(f(v), f(w)) \in E_2\]

루트 트리에서

 루트 트리는 일반적인 트리에 조건이 또 하나 붙죠. 루트로 지정된 노드가 존재합니다. 따라서 루트 트리의 동형사상에는 한 가지 조건이 더 추가됩니다. 두 트리 $T_1, T_2$의 루트가 각각 $r_1, r_2$일 때,

\[f(r_1) = r_2\]

이진 트리에서

 이어서 이진 트리는 루트 트리에 더해 자식이 둘 까지 존재할 수 있다는 조건이 추가됩니다. 때문에 이진 트리의 동형 사상은 왼쪽 자식과 오른쪽 자식의 위치가 그대로 보존되어야 한다는 조건이 더해집니다.

\[f(v_{1left}) = v_{2left}, \; f(v_{1right}) = v_{2right}\]

비동형성 (Non-isomorphism)

 7장에서 말했듯이 다시 한 번, 두 트리가 서로 동형사상인지 파악할 때 무작정 모양을 바꿔가며 확인하는 것은 상당히 까다로운 일입니다. 그래서 어떤 때는 두 트리가 동형사상이 아니다는 것을 증명하는게 더 빠를 때도 있습니다. 게다가 트리는 그래프와 달리 루트 노드나 자식과 부모 사이의 관계 등 지켜야 하는 조건이 더 많으니 완전히 다른 모습의 트리를 세는 것이 더 쉬울 수도 있습니다. 그리고 상당히 적은 수의 점에 대해서는 직접 모양을 세면서 확인할 수도 있고요.

Theorem 6.
점의 개수가 5개인 트리는 3개의 서로 다른 비동형 트리를 가진다.

Theorem 7.
점의 개수가 4개인 루트 트리는 4개의 서로 다른 비동형 트리를 가진다.

Theorem 8.
점의 개수가 3개인 이진 트리는 5개의 서로 다른 비동형 트리를 가진다.

 실제로 조건이 추가되는 트리, 루트 트리, 이진 트리의 순서대로 비동형 트리의 종류가 늘어나는 것을 볼 수 있습니다. 심지어 점의 개수가 더 적더라도요! 특히 이 이진 트리에 대해서는, 이렇게 일반화 해볼 수 있겠습니다.

Theorem 9.
점의 개수가 $n$개인 이진 트리가 $C_n$개의 서로 다른 비동형 트리를 가진다고 할 때, 아래가 성립한다.
\(C_n = \sum_{k=0}^{n-1}{C_kC_{n-k-1}} \quad (C_0 = 1, C_1 = 1)\)

트리들의 재귀적 정의

 그림을 훑어보면 짐작할 수 있듯이, 트리는 부분이 전체를 닮은 모양을 나타냅니다. 그래서 트리를 확장시키기 용이하도록 그 모양을 재귀적으로 정의할 수도 있습니다. $r_i$를 트리 $T_i$의 루트 노드라고 했을 때, 각 트리는 아래와 같이 정의될 수 있습니다.

	기본 단계	재귀 단계
루트 트리	점 $r$	트리 $T_i \; (i=1, 2, …, n)$와 새로운 점 $r$에 대해 $(r, r_i) \in T$인 트리 $T$
이진 트리	빈 트리 $\emptyset$	이진 트리 $T_i \; (i=1, 2)$와 새로운 점 $r$에 대해 $(r, r_i) \in T$인 트리 $T$
채워진 이진 트리	점 $r$	채워진 이진 트리 $T_i \; (i=1, 2)$와 새로운 점 $r$에 대해 $(r, r_i) \in T$인 트리 $T$

 재귀적 표현에 대해서는 이미 6장에서 살펴보았으니, 다시 참고해도 좋을 것 같습니다.

트리의 활용 방법

 우리는 앞서 그래프를 사용하여 여러가지 경로 문제들을 해결해보았습니다. 여기서 트리를 사용하면, 좀더 복잡한 상황의 문제들도 도식화해서 풀어낼 수 있습니다.

이진 탐색 트리 (Binary Search Tree, BST)

 탐색을 위해 구성한 특수한 조건의 이진 트리를 이진 탐색 트리(Binary Search Tree, BST)라고 합니다.

 이진 탐색 트리의 각 노드는 그 값의 대소관계에 따라 정렬되어 있습니다. 어떤 노드의 값을 $e$라고 했을 때, 그 노드의 왼쪽 하위 트리는 모두 $e$보다 작은 값을 가지고, 오른쪽 하위 트리는 모두 $e$보다 큰 값을 가지게 되는 식입니다.

 원하는 값을 찾으려면, 노드마다 간단한 문답을 하면 됩니다. 내가 찾고자 하는 값이 현재 노드의 값보다 큰지 작은지를 물어보는 것이죠. 만약 작다면, 왼쪽 자식으로 내려가면 됩니다. 반대로 크다면, 오른쪽 자식으로 내려가겠죠. 둘 다 아니라면? 그 노드가 우리가 찾던 노드가 되겠죠!

호프만 코딩 (Huffman coding)

 그런데 말입니다, 만약 값 자체가 아니라 그 값이 가지는 특정 수치를 기준으로 탐색을 하려면 어떻게 해야 할까요? 가령, 중요도가 가장 높은 값이거나 가장 자주 등장하는 값 같은 경우가 되겠네요. 이진 탐색 트리를 사용한다면, 어쩔 수 없이 모든 값을 순회한 후 최대치를 가지는 노드를 선택해야 할 것입니다. 하지만 호프만 코딩(Huffman coding)을 사용한다면, 최소한의 비트만으로 노드들을 가중치에 맞게 정렬시킬 수 있습니다.

 여기 여섯개의 노드와 각각에 해당하는 가중치가 있습니다.

 여기서 가장 작은 값을 가지는 노드 두 개를 골라, 그 둘을 자식으로 가지는 루트 노드를 만들어줍시다. 두 값 중 큰 값은 왼쪽, 작은 값은 오른쪽으로 오도록 합니다. 그리고 왼쪽 값은 0, 오른쪽 값은 1이라는 비트를 부여합니다(이 비트가 어떤 역할을 하는 지는 나중에 알게 되니, 일단 넘어가요). 루드의 값은 두 값을 더한 값이 됩니다.

 이 과정을 계속 반복해보도록 하죠. 모든 노드가 연결될 때까지요.

 연결된 이진 트리가 완성되었다면, 이제 루트에서 각 노드로 내려오면서 숫자를 부여할 수 있습니다. 높이 2인 E(10)와 F(00)는 두 자리, 높이 3인 A(111), B(110), C(011)는 세 자리의 비트를 가지게 됩니다. 이 방법은 노드들이 (이 경우에는)내림차순대로 정렬된다는 장점도 있지만, 더 중요한 것은 사용하는 비트가 최소가 되도록 설정할 수 있다는 것입니다. 자주 사용되는 노드의 비트는 작게 부여함으로서 평균적으로 사용되는 비트의 수를 최소화하게 됩니다. 만약 가중치가 출현 빈도를 뜻한다면, 이 예시에서 우리가 평균적으로 사용하게 될 비트 수는

\[3 \times 0.08 + 3 \times 0.10 + 3 \times 0.12 + 3 \times 0.15 + 2 \times 0.20 + 2 * \times 0.35 = 2.45\]

  3비트보다 적은 2.45비트가 됩니다.

의사 결정 트리 (Decision tree)

 의사 결정 트리(Decision tree)는 어떤 상황에 대한 결정에 따라 다음 행동을 취하도록 설계한 트리입니다. 이진 탐색 트리와 비슷해 보이지만, 값들을 탐색/삽입/삭제하기 용이하도록 설계된 데이터 구조인 이진 탐색 트리와는 달리 사용자가 임의로 부여한 규칙에 따라 행동을 취한다는 점에서 다른 구조라고 할수 있습니다.

 의사 결정 트리(Decision tree)에서 하나의 노드는 하나의 질문을 던집니다. 예/아니오로 대답할 수 있는 질문일 수도 있고, 여러 답이 나오는 다지선다일 수도 있습니다. 어쨌거나 각각의 대답은 하나의 선으로 이어지고, 선은 또 다른 질문으로 이어지게 됩니다. 계속되는 문답 끝에 잎 노드는 적절한 답을 내놓게 됩니다.

 이런 문제를 생각해봅시다. 다섯개의 동전이 있습니다. 이들은 모두 겉보기에 같아 보이지만, 한 동전은 가짜 동전이어서 다른 것들보다 가볍거나 무겁습니다. 우리는 다섯 동전 중 두 개를 골라 서로 무게를 비교하여 어느 쪽이 더 무거운지(혹은 같은 무게인지) 판별할 수 있습니다. 최소한의 시행으로 가짜 동전을 알아낼 수 있을까요? 이 문제도 의사 결정 트리를 구성해보면 쉽게 풀 수 있습니다.

 다섯 개의 동전에 1 부터 5까지의 번호를 부여합니다. 그리고 두 동전을 비교하여 어느쪽이 무거운 지 비교하는 과정을 하나의 노드로 나타냅니다. 가능한 답은 무겁다/가볍다/똑같다 세 가지가 될 수 있으니, 하나의 노드는 최대 세 개의 선을 가질 수 있습니다. 그 선으로 이어지는 자식들은 또 다른 두 동전을 비교하게 되겠죠? 그렇게 가능한 경우의 수를 좁히다보면 다른 동전과 무게가 다른 가짜 동전을 특정할 수 있게 될 것입니다.