단순 연결 그래프: 단순 그래프(루프, 병렬변이 존재하지 않는 그래프) + 연결 그래프(오직 하나의 연결 성분만 가지는 그래프) 를 합친 그래프를 단순 연결 그래프로 볼 수 있음.
즉, 단순 연결 그래프 + 사이클이 없으면트리라고 볼 수 있음.
또한, 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 방문
