[이산수학] 11강 - 트리

✅ 1. 기본사항

(1) 트리의 정의

• 트리의 종류: 트리를 기반으로 하는 여러가지 규칙이 추가된 다양한 트리가 존재함.

• 트리: 사이클이 없는 단순 연결 그래프를 트리(Tree) 라고 함.
• 단순 연결 그래프: 단순 그래프(루프, 병렬변이 존재하지 않는 그래프) + 연결 그래프(오직 하나의 연결 성분만 가지는 그래프) 를 합친 그래프를 단순 연결 그래프로 볼 수 있음.
• 즉, 단순 연결 그래프 + 사이클이 없으면 트리라고 볼 수 있음.
• 또한, Trivial tree(꼭지점 하나만 존재하는 트리), Empty tree(꼭지점 하나도 없는 비어있는 트리), Forest(한 개 이상의 트리로 구성된 그래프) 와 같은 것도 트리로 정의를 함.
• TIP: Forest 는 트리들이 여러개 존재하는 그래프를 의미할 수 있음.

• 트리 예제: 위의 4번째 빼고는 모두 트리이며, 이유는 4번째의 경우 사이클이 존재하기 때문에 트리가 아님.

• 루트 트리: 루트(v1)라 부르는 노드는 1개가 반드시 존재해야 하며, 나머지 노드들은 분리된 집합인 서브트리로 나뉨.
• 쉽게 말해, 루트 트리의 루트 노드 자식 노드는 해당 자식 노드의 또 다른 자식 노드의 루트로도 볼 수 있기 때문에 분리 된 집합에 대해서는 서브트리로 볼 수 있다는 의미임.
• 트리의 한 종류로 가장 일반적인 트리이며, 트리라는 개념에 규칙성을 더한 또 파생된 트리로 볼 수 있음.

• 루트 트리의 경우 위와 같은 형태를 띄고 있으며, A 의 서브 트리는 B집합, C집합, D집합으로 3개의 서브트리를 가지고 있음.

(2) 주요 용어

• 트리의 차수: 트리에서 차수는 그래프와 다르게 자식 노드와 연결된 차수 즉, 자식 노드의 개수만을 따짐.
• 트리의 전체 차수: 루트 노드부터 시작해서 모든 자식 노드의 차수의 전체를 구하는 것임.
• 리프 노드(단말 노드): 트리의 제일 하단에 있는 자식 노드가 없는 노드를 의미함.
• 내부 노드: 루트 노드 및 리프 노드를 제외한 나머지 노드를 내부 노드라고 부름.
• 레벨: 특정 노드의 레벨은 루트 노드에서부터 몇 번 만에 가느냐를 따지는 것임. 즉, G의 레벨은 A - B - G 이기 때문에 2임.
• 트리의 높이: 트리의 높이는 트리 전체의 높이를 의미하기 때문에 위의 예시의 트리의 높이는 3이 될 수 있음. 또한, 리프 노드의 레벨과 트리의 높이는 항상 같지만, 레벨은 특정 노드의 레벨을 볼 수 있기 때문에 높이와는 다른 개념으로 볼 수 있음.
• 트리의 무게: 리프 노드들의 개수를 의미함. 즉, 위의 예시의 경우 E,F,G,C,I,J,K 로 총 7이 트리의 무게가 됨.

(3) 트리의 표현

• 중첩된 집합: 트리를 표현 할 때, 위와 같이 집합을 중첩된 형태로 표현을 하기도 함.

• 중첩된 괄호: 괄호를 중첩해서 트리의 노드 관계를 표현하는 것임.

• 결각: 단순히 들여쓰기로 레벨을 표현해서 트리를 표현하는 것임.

• 닮은 트리: 트리의 구조는 동일하지만 노드의 데이터 내용이 서로 다를 때 이들 트리는 닮은 트리라함.

(4) 주요 정리

• 정리: n개의 꼭지점을 가지는 연결 그래프(연결성분이 한개인 그래프)가 n-1 개의 변을 가지면 해당 그래프는 트리라고함.
• 쉽게 말해, 연결 그래프가 n-1 개의 변을 가지면 사이클이 절대 만들어질 수 없기 때문에 이는 곧 트리가 되는 것임.
• 결론: 즉, n개의 꼭지점을 가지는 트리는 n-1 개의 변(간선)을 가질 수 있다는 의미로 귀결될 수 있음.

---

✅ 2. 이진 트리

(1) 이진 트리란?

• 이진 트리: 모든 노드가 0개~최대 2개의 서브 트리를 갖는 루트 트리를 의미함.
• 루트 트리와의 차이점: 루트 트리는 루트 노드가 반드시 하나 존재해야 하기 때문에 공집합일 수 없지만, 이진 트리는 공집합 일 수 있으며, 또한 루트 트리와 다르게 왼쪽과 오른쪽을 구분하는데, 이는 루트 트리의 경우 방향이 없기 때문에 단순히 아래의 자식 노드들이 들어가 있는 느낌이지만, 이진 트리의 경우 왼쪽과 오른쪽 방향을 구분함으로써 의미를 부여해놓는 것임.

• 이진 트리에서는 왼쪽 자식 노드 또는 오른쪽 자식 노드에 있는 트리들은 전혀 다른 것으로 간주함.
• 방향성이 존재하기 때문에 위의 예시에선 가운데의 개념은 허용하지 않음.

• 이진 트리의 최대 노드 수: 이진 트리 T의 높이가 h개일 때, T의 최대 노드 수는 1 + 2 + 4 + 8 + ... 2의 승으로 올라가기 때문에 그 값들을 모두 더하면 구할 수 있음.

(2) 완전 이진 트리

• 완전 이진 트리: 트리에서 레벨 0부터 트리의 리프 노드까지 왼쪽 노드부터 차례로 모두 채워진 이진 트리를 의미함.

• 정리1: 완전 이진 트리는 최대로 왼쪽부터 채우기 때문에 같은 노드 수를 갖는 트리가 존재한다면 해당 완전 이진 트리는 제일 최소의 높이를 가지는 트리가 될 수 있음.
• 정리2: n개의 노드를 갖는 이진 트리의 최소 높이 또한 위와 같이 구할 수 있음.
• 쉽게 말해, n = 7 이면 1, 2, 4, 8 ... 로 갈 때, 1 + 2 + 4 = 7 이기 때문에 높이는 2가 되는 것임.

• 이진 트리의 높이: n = 14 일 경우 1,2,4,8,16,... 으로 늘어나는 과정에서 각 높이는 0,1,2,3.. 으로 정해지기 때문에 1 + 2 + 4 + 8 = 15 이며, n(14) 는 15안에 포함이 되기 떄문에 높이는 3이 되는 것임.

(3) 포화 이진 트리

• 포화 이진 트리: 이진 트리 구조에서 모든 노드가 채워진 이진 트리를 의미함.
• 즉, 노드의 개수가 당연히 항상 1,2,4,8,16... 으로 될 수 밖에 없음.

(4) 이진 트리 종합 예제

• (1) 1,2,4,8,16 까지가 높이 = 4 이기 때문에 모두 더한 값인 1 + 2 + 4 + 8 + 16 = 31 이 최대 노드수가 됨.
• (2) 1,2,4,8,16,32 까지 높이 = 5 이며, 1 + 2 + 4 + 8 + 16 + 32 = 63 이기 때문에 60개의 노드로는 완전 이진 트리 정도만 만들 수 있으며, 포화 이진 트리는 60과 63이 다르기 때문에 존재하지 않음.
• (3) 8개의 노드는 1 + 2 + 4 + 8 = 15(높이3)에 속하기 때문에 최소한의 높이는 3으로 볼 수 있음.
• (4) 1 + 2 + 4 = 8, 6개의 노드는 포함이 가능하며, 이진 트리 또는 완전 이진 트리는 가능함. ( 포화는 불가능 )

---

✅ 3. 이진 탐색 트리

(1) 이진 탐색 트리 - 정의

• 이진 탐색 트리: 이진 트리에 탐색을 위한 규칙을 추가한 트리로 볼 수 있음.
• 자세한 규칙은 이진 트리에서 모든 노드들은 탐색을 위한 키값을 가지고 있어야 하며, 모든 부모 노드의 왼쪽 자식은 부모 노드보다 키 값이 작아야 하며, 오른쪽 자식 노드는 부모 노드보다 키 값이 커야하는 특징이 있음.
• 즉, 임의의 노드 왼쪽 서브트리의 키값들은 임의의 노드 보다 작아야 하며, 오른쪽 서브트리는 임의의 노드 보다 커야함.

(2) 이진 탐색 트리 구성 - 예제

• Key 값이 7, 3, 9, 6, 2, 4, 8, 1, 5 순으로 들어온다면, 이진 탐색 트리에선 먼저 7이 루트에 들어가게 되며, 3은 7보다 작기 때문에 왼쪽 서브트리로 들어가고, 9는 7보다 크기 때문에 오른쪽 서브트리로 들어가며, 이런식으로 반복해서 들어가게 됨.
• 또한, Key 값이 1,2,...9 순으로 들어오게 된다면, 모두 오른쪽 서브트리로 들어가는 경사 이진 탐색 트리가 만들어 질 수 있음.

• Key 값 A, B, C, D가 존재하며, 들어오는 순서에 따라서 위와같이 이진 탐색 트리의 구성은 달라질 수 있음.

(3) 이진 탐색 트리 검색

• 이진 탐색 트리 검색(알고리즘): 주어진 키값(찾을 값)을 통해서 루트 노드에서 비교를 하며 내려가는데, 키값과 비교할 노드의 값의 대소를 비교 한 뒤, 비교 노드보다 작다면 왼쪽, 크다면 오른쪽으로 가는 원리로 이진 탐색 트리에서 값을 찾을 수 있음.

• 주어진 키값(찾을 키값)이 9인 경우, 루트 노드와 비교 후 10보다 작기 때문에 왼쪽 서브트리로 내려가고, 8보단 크기 때문에 오른쪽 서브트리로 내려간 뒤, 12보단 작기 때문에 왼쪽 서브트리로 내려갔는데 9와 동일한 값이 존재하므로 알고리즘 종료됨.

(4) 이진 탐색 트리 검색 - 효율적인 이진 탐색 트리

• 효율적인 이진 탐색 트리의 경우 비교횟수가 가장 적은것이 곧 효율적인 이진 탐색 트리가 될 수 있음.
• 위의 예시의 경우 경사 이진 트리보단, 균형잡힌 이진 트리가 효율적인 이진 탐색 트리로 볼 수 있는데, 이말은 즉슨 루트의 높이가 낮은 트리의 경우가 결국 효율적인 탐색 트리로 볼 수 있음.

• 비교 횟수 기대값: 가장 많이 나올 확률이 높은 데이터가 A, 가장 적게 나올 확률이 높은 데이터가 D일 경우에는 경사 이진 탐색 트리의 경우가 효율적일 수 있음.

• 허프만 코딩: 데이터 압축 알고리즘 중 하나로써, 내부적으로 이진 트리를 사용하며, 대표적인 이진 트리의 활용 사례임.

---

✅ 4. 트리의 활용

(1) 최소 신장 트리(MST)

• 신장 트리: 그래프 G의 모든 꼭지점을 연결하는 사이클이 존재하지 않는 G의 부분 그래프로 볼 수 있음.
• 쉽게 말해, 그래프 내의 모든 정점의 꼭지점이 연결이 되어있으며, 사이클이 존재하지 않는 부분적인 그래프를 신장 트리로 봄.

• 신장 트리 예제: 위와같이 A,B,C,D의 정점을 가지는 그래프가 존재할 때, 아래와 같이 모든 정점이 연결은 되어있으면서 간선 하나를 뺌으로써 사이클이 존재하지 않도록하는 부분 그래프를 신장 트리라함.

• 최소 신장 트리: 그래프 G의 모든 변의 가중치의 합이 가장 작은 부분 그래프를 최소 신장 트리라 함.

• 최소 신장 트리 사용처: 대부분 컴퓨터 네트워크 또는 교통망 같은데에서 사용이 됨.
• 네트워크나 교통망을 구축할 때 가장 중요한 요소는 거리에따른 예산(비용)이기 때문에, 최소 비용으로 모든 지점을 연결하기 위해서 최소 신장 트리를 활용하는 것임.

• 그래프에서 신장 트리의 수는 꼭지점(정점)의 개수가 커짐에 따라 기하급수적으로 증가함.
• 이러한 그래프 하나 안에서 발생하는 여러 신장 트리 중 가중치가 가장 작은 신장 트리를 구하는 것은 쉽지 않기 때문에, 신장 트리를 구하기 위한 알고리즘이 여러개 나오게 됨.

(2) 최소 신장 트리(MST) - Kruskal 알고리즘

• Kruskal 알고리즘: 그래프의 모든 변의 가중치값을 오름차순으로 정렬을 시키며, 가장 작은 가중치의 변부터 차례대로 트리에 추가하는 방식이며, 사이클이 발생하면 추가하지 않고, 모든 꼭지점이 연결될 때까지 반복하는 알고리즘임.

• 반복 된 결과로는 위와 같은 결과를 얻을 수 있음.

(3) 최소 신장 트리(MST) - Prim 알고리즘

• Prim 알고리즘: 크루스칼 알고리즘은 모든 변을 빼서 오름차순으로 정렬 한 뒤, 트리를 구성하는 방식이었다면, Prim 알고리즘은 이와 다르게 임의의 꼭지점 하나를 기반으로 인접한 정점 중 가중치가 가장 작은 정점을 연결 하는데, 이때 사이클이 발생하지 않아야 하는 조건에 부합해야 연결이 되는 방식이며, 이것이 반복적으로 이뤄지면서 MST를 구하는 방식임.

• Prim 알고리즘 예제: 위와 같이 시작 정점이 G라면, G의 인접한 정점 중 가중치가 가장 작은 3을 통해 F부터 시작함.
• (1) G의 인접한 정점 중 가중치가 가장 작은 F를 방문 노드로 만듬.
• (2) G, F 인접한 정점 중 가중치가 가장 작으면서, 방문하지 않은 노드인 E 방문
• (3) G, F, E 인접한 정점 중 가중치가 가장 작으면서, 방문하지 않은 노드인 B 방문
• (4) G, F, E, B 인접한 정점 중 가중치가 가장 작으면서, 방문하지 않은 노드인 A 방문
• (5) G, F, E, B 인접한 정점 중 가중치가 가장 작으면서, 방문하지 않으 노드인 D 방문
• 이후에도 사이클이 발생하지 않아야 한다는 규칙을 지키면서 반복적으로 방문을 하는 것임.