[자료 구조] 비선형(Non-Linear) 자료 구조 (1) 그래프(Graph), 트리(Tree) 개요

 

 

 

포스트를 읽으실 때 참고하실 점

• 해당 카테고리의 포스트들은 C/C++ 언어를 기준으로 작성되어 다른 언어에는 적용되지 않는 내용이 일부 포함될 수 있습니다. 또한, 글의 배치나 띄어쓰기는 PC 버전 전체 화면 크기를 기준으로 작성됩니다.
• 틀린 부분이 있는 경우, 댓글이나 이메일로 연락주시면 내용을 정정하도록 하겠습니다.

 

---

 

비선형 자료 구조(non-linear data structures)

비선형(non-linear) 자료 구조란, 자료 사이의 전후 관계가 1:1이 아닌 자료 구조이다. 비선형 자료 구조는 트리(tree)와 그래프(graph)로 분류할 수 있다.

 

 

---

 

그래프(graph)

정점(vertex)과 각 정점을 연결하는 간선(edge)로 구성되는 자료 구조이다. 각각의 간선은 가중치(weight)를 가질 수 있으며(가중 그래프), 시작 정점의 위치는 고정적이지 않을 수 있다. 간선으로 연결된 정점 사이에는 순환(cycle)이 존재할 수 있으며, 인접 행렬(incidence matrix) 또는 연결 리스트 형태로 구현이 가능한 자료 구조이다.

 

간선의 진출 방향에 따라,

• 유향(directional) 그래프: 한 쪽 방향으로만 이동 가능한 간선으로 이루어진 그래프
• 무향(undirectional) 그래프: 양 쪽 방향으로 이동 가능한 간선으로 이루어진 그래프

로 분류되기도 한다.

 

 

그래프의 탐색(search)

그래프 내의 정점을 순차적으로 방문하거나, 특정한 정점을 탐색하는 방법을 의미한다. 그래프의 탐색과 관련해서는 추후에 탐색 알고리즘과 관련한 포스팅을 통해 정리할 예정이므로, 지금은 간단한 소개만 하기로 한다.

• 깊이 우선 탐색(depth-first search, DFS): 시작 정점으로부터 최대한 깊게 방문(간선 진출을 많이 수행)하는 것을 우선으로 탐색하는 방법.
• 너비 우선 탐색(breadth-first search, BFS): 시작 정점을 방문한 후, 시작 정점과 연결된 인접한 정점들을 우선으로 탐색하는 방법.

 

---

 

트리 (tree)

회로(cycle)가 없는, 연결된 그래프(graph) 형태의 자료 구조로, 아래의 그림과 같이 노드 및 가중치가 없는 간선의 형태로 일반적으로 나타낸다.

출처: 나무위키

 

 

트리 구조를 이야기할 때 등장하는 개념들

• 루트(root) 노드: 트리 내 최상위 노드
• 부모(parent) 노드: 어떤 한 노드에 대하여, 연결이 되어있는 상위의 노드
• 자식(child) 노드: 어떤 한 노드에 대하여, 연결이 되어있는 하위의 노드
• 형제(sibling) 노드: 공통된 부모 노드를 갖는 노드 간의 관계
• 노드의 차수(degree): 특정 노드가 가지는 자식 노드로의 간선의 총 개수
• 노드의 깊이(depth): 루트로부터 해당 노드까지 도달하기 위해 거쳐야 하는 간선의 수
• 레벨(level): 동일한 깊이를 가지는 노드들의 집합
• 트리의 높이(height): 트리 내에서 가장 깊이가 큰 말단 노드까지 거쳐야 하는 간선의 수
• 포레스트(forest): 트리의 집합

 

 

이진 트리 (binary tree)

트리 구조 중, 모든 노드의 차수가 2 이하인 트리 구조이다. 가장 단순한 형태의 트리 구조로, 개념적으로도 가장 중요하며 프로그래밍에서 다양하게 활용된다.

 

이진 트리는 아래와 같이 형태에 따라 분류할 수 있다.

• 완전(complete) 이진 트리: 마지막 레벨을 제외한 모든 레벨에서 노드가 꽉 차 있고, 마지막 레벨은 왼쪽부터 자식 노드가 채워져 있는 형태의 이진 트리이다.
• 정(full, or strict) 이진 트리: 모든 노드의 차수가 0 또는 2로만 구성되어 있는 이진 트리이다.
• 포화(perfect) 이진 트리: 모든 내부 노드의 차수가 2인 이진 트리이다.

 

이러한 형태적 특성으로 인해, 1) 완전 이진 트리의 경우에는 배열 형태로 구현할 때에 단순한 인덱스 계산을 통해 특정 노드의 부모 또는 자식 노드에 쉽게 접근할 수 있어 구현이 간편한 특징이 있으며, 2) 포화 이진 트리의 경우에는 높이가 $n$일 때 노드의 개수가 $2^{n+1} - 1$이다.

 

 

이진 트리의 순회(traversal)

트리의 모든 노드를 순차적으로 방문하는 순회(traversal)는 루트 노드를 언제 순회하는 지에 따라 분류된다.

• 전위(pre-order) 순회: 루트 노드 → 왼쪽 하위 부분 트리 → 오른쪽 하위 부분 트리 순으로 방문
• 중위(in-order) 순회: 왼쪽 하위 부분 트리 → 루트 노드 → 오른쪽 하위 부분 트리 순으로 방문
• 후위(post-order) 순회: 왼쪽 하위 부분 트리 → 오른쪽 하위 부분 트리 → 루트 노드 순으로 방문

 

---

 

포스트에 소개되지 않은 구체적인 내용은 1) 글 아래의 태그 또는 블로그 내 검색을 통해 활용 예시 찾아보기(코딩 문제 풀이 등), 2) 관련 링크나 구글링을 통해 따로 공부해야하는 점은 양해를 부탁드립니다.