[이산수학] 그래프 - 트리

 

 

그래프 - 트리

---

1. 트리(Tree)

트리는 그래프의 한 종류로, 계층 구조를 나타내는 비순환(=사이클이 없는) 연결 그래프입니다. 순환하지 않더라도 방향은 존재할 수 있기 때문에, 방향이 있는 트리는 방향 트리(directed tree)라고 합니다.

 

또한, 트리는 특정 노드를 기점으로 부분집합 개념의 트리로 분리할 수 있는데, 이를 "서브트리(subtree)"라고 합니다.

 

2. 기본 용어

2.1. 노드(Node)

노드는 트리에서 데이터를 저장하는 역할을 합니다. 또한, 각 노드들은 하나 이상의 다른 노드와 연결되며 서로 관계를 형성하게 됩니다.

 

2.2. 루트(Root)

루트는 트리의 최상위 노드를 의미합니다.

 

2.3. 부모 / 자식 / 형제 노드(Parent / Child / Sibling node)

부모 노드는 특정 노드의 바로 위에 위치하는 노드를 의미합니다. 반대로 자식 노드는 특정 노드의 바로 아래에 위치하는 노드를 의미합니다. 즉, 부모-자식 관계의 노드는 방향을 가진 관계로 생각할 수 있습니다. 또한 트리는 비순환 연결 그래프이므로, 루트 노드를 제외한 모든 노드는 하나의 부모 노드를 가지고 있습니다. 그리고 형제 노드는 같은 부모 노드를 가지는 자식 노드들의 관계를 의미합니다.

 

2.4. 리프(Leaf)

리프는 자식이 없는 노드를 의미합니다. 그리고 트리의 모든 리프 노드의 개수를 "트리의 무게(weight of a tree)"라고 정의합니다.

 

2.5. 차수(Degree)

노드의 차수는 해당 노드에 연결되어 있는 자식 노드 수를 의미합니다. 즉, 리프 노드의 차수는 0이 됩니다. 그리고 트리의 차수는 트리 내 노드의 차수 중 최댓값으로 정의합니다.

 

2.6. 레벨(Level)

노드의 레벨은 트리의 루트 노드로부터 해당 노드까지의 경로길이를 의미합니다. 그리고 트리 내 노드의 레벨 중 최댓값은 "트리의 높이(height of a tree)"라고 정의합니다.

 

3. 이진 트리(Binary tree)

이진 트리는 공집합이거나 모든 노드가 최대 2개의 자식 노드만을 가지는 트리입니다. 즉, 트리의 최대 차수는 2이고 높이가 k인 트리가 가질 수 있는 최대 노드의 수는 2^k+1 - 1입니다. 이진 트리는 데이터를 효율적으로 저장, 검색하는 등 트리 기반의 자료 구조 및 알고리즘에서 중요하게 사용되는 트리의 대표 유형입니다.

 

각 노드의 자식 노드는 왼쪽, 오른쪽을 구분하여 왼쪽 자식(left child), 오른쪽 자식(right child)으로 구분하며, 이진 트리 내 각 서브 트리도 이진 트리가 되는 재귀적인 구조를 가집니다.

 

3.1. 완전 이진 트리(Complete binary tree)

마지막 레벨을 제외한 모든 노드가 이진 트리가 가질 수 있는 최대 노드 배치를 가지며, 마지막 레벨은 노드가 왼쪽부터 오른쪽으로 순서대로 채워져 있는 이진 트리를 의미합니다.

레벨3 완전 이진 트리

 

3.2. 포화 이진 트리(Full binary tree)

포화 이진 트리는 마지막 레벨을 제외한 모든 노드가 자식 노드를 2개씩 가지고 있는 이진 트리를 의미합니다.

포화 이진 트리

 

3.3. 경사 이진 트리(Skewed binary tree)

모든 노드가 왼쪽 자식만 가지거나 오른쪽 자식만 가지는 한 쪽으로 치우쳐진 트리입니다.

경사 이진 트리

 

3.4. 이진 탐색 트리(Binary search tree)

이진 탐색 트리는 각 노드 입장에서 ①왼쪽 서브 트리에 있는 노드들은 해당 노드보다 값이 작으며, ②오른쪽 서브 트리에 있는 노드들은 해당 노트보다 큰 값으로 구성된 이진 트리를 의미합니다.

이진 탐색 트리

 

이진 탐색 트리는 특정한 값을 찾는데 최적화되어 있습니다. 일반적인 경우 완전 이진 트리로 구성된 이진 탐색 트리는 시간 복잡도가 O(log_n)입니다. 하지만, 경사 이진 트리 형태로 구성되어 있으면 O(n)이 되는 등 트리의 구조에 따라 시간 복잡도가 달라질 수 있으므로 트리 구조를 잘 구성하는 것이 필요합니다. 또한, 각 노드에 저장된 데이터들에 접근하는 빈도에 따라서도 꼭 완전 이진 트리로 구성하는 것이 정답이 아닐 수 있습니다.

 

4. 신장 트리(Spanning tree)

신장 트리는 임의의 그래프 내 모든 꼭짓점을 포함하면서 사이클은 존재하지 않는 부분 그래프를 의미합니다. 그래프의 변에 가중치가 존재할 경우 신장 트리를 구성하는 방법에 따라 포함되는 변의 합이 달라질 수 있는데, 이때 총 가중치가 가장 작은 신장 트리를 "최소 신장 트리(minimum spanning tree)"라고 합니다.

 

그래프의 최소 신장 트리를 찾는 알고리즘은 대표적으로 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘이 있습니다.

---

연관 게시글

[이산수학] 그래프

[이산수학] 그래프

---

참조

•