Tree, Graph란

min-heap은 완전이진트리(complete binary tree)의 일종이라고 했습니다. 그렇다면 트리란 무엇일까요?

 

Tree(트리)

트리란 노드로 이루어진 자료구조로,

• 하나의 루트 노드(node)를 가지고 있습니다.
• 루트 노드는 0개 이상의 자식 노드를 가지고 있습니다.
• 그 자식 노드 또한 0개 이상의 자식 노드를 가지고 있고, 자식 노드 역시 0개 이상의 자식 노드를 가지고 있고...

위 그림처럼 부모와 자식의 개념, 즉 계층구조를 가지고 있습니다. 그리고 배열이나 리스트와 다르게 하나의 자료 뒤에 여러 자료가 존재할 수 있는데, 이를 비선형(nonlinear) 자료구조라고 합니다. 각 노드는 어떤 자료형으로도 표현할 수 있습니다.

 

트리와 관련된 용어는 다음과 같습니다.

• 루트 노드(root node) : 부모가 없는 노드, 트리는 하나의 루트 노드 만을 가짐.
• 단말 노드(leaf node) : 자식이 없는 노드
• 내부(internal) 노드 : 단말 노드가 아닌 노드
• 간선(edge) : 노드를 연결하는 선
• 형제(sibling) : 같은 부모를 가지는 노드
• 조상 노드(ancestors node) : 임의의 노드에서 루트 노드에 이르는 경로상에 있는 노드들 (D의 조상은 B, A) 
• 노드의 크기(size) : 자신을 포함한 모든 자손 노드의 개수
• 노드의 깊이(depth) : 루트에서 어떤 노드에 도달하기 위해 커쳐야하는 간선 수
• 노드의 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합
• 노드의 차수(degree) : 각 노드에서 뻗어나온 가지의 수 (D의 차수는 2)
• 트리의 차수(degree of tree) : 트리에서 가장 큰 차수 
• 트리의 높이(height) : 가장 깊숙히 있는 노드의 깊이 (3)

배열이나 리스트와 다르게, 트리를 순회하는 방법에는 여러가지가 있습니다.

• 전위 순회

 

• 중위 순회

• 후위 순회

 

그리고 부모 노드와 자식노드를 잇는 간선(edge)이 존재합니다. 이처럼 노드와 간선이 있는 자료구조에는 그래프(graph)가 있습니다. 사실 트리는 그래프의 한 종류입니다. 그렇다면 그래프는 무엇일까요?

 

---

Graph(그래프)

노드와 노드를 잇는 간선들로 구성된 자료구조로,

• 네트워크 모델입니다.
• 노드 간에 2개 이상의 경로가 가능합니다.
• 부모-자식 관계가 없습니다.
• 순환 혹은 비순환 구조를 이룹니다.
• 방향성이 있는 그래프와 방향성이 없는 그래프가 존재합니다.

대표적으로 지하철 노선도를 그래프라고 할 수 있습니다. 위에서 살펴본 트리는 방향성이 있는 비순환 그래프(Directed Acyclic Graph)입니다.

출처: www.sisul.or.kr

그래프를 탐색하는 방법에는 BFS(너비 우선 탐색), DFS(깊이 우선 탐색)가 있습니다.

---

더 자세한 내용은.. 다음에..

앞으로 참고할 포스트

https://ko.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/describing-graphs

그래프 설명하기 (개념 이해하기) | 알고리즘 | Khan Academy

---

출처

[자료구조] 트리(Tree)란 - Heee's Development Blog

 

Tree (data structure) - Wikipedia

 

선형(Linear) / 비선형(NonLinear) 자료구조

 

[자료구조] 트리와 그래프

 

트리 순회(전위 순회, 중위 순회, 후위 순회)