CS : Data Structure : Tree & Graph

Tree

 

 

1.

노드(node)와 노드를 연결하는 간선(edge)으로 이루어진 자료 구조이다.

 

2.

하나의 루트 노드(root node)를 가진다.

루트 노드는 0개 이상의 자식 노드를 가진다.

 

3.

트리에서는 사이클(cycle)이 존재할 수 없다.

 

4.

그래프(graph)의 한 종류이고, 트리를 '사이클이 없는 하나의 연결 그래프'라고 표현할 수 있다.

 

5.

노드의 수 : N

간선의 수 : N-1

 

6.

임의의 두 노드 간의 경로는 유일하다.

 

7. 종류

• 이진 트리 (Binary Tree) : 각 노드가 최대 두 개의 자식을 갖는 트리
• 이진 탐색 트리 (Binary Search Tree) : 모든 왼쪽 자식 노드 <= N <= 모든 오른쪽 자식 노드

 

 

 

---

 

 

 

Graph

 

1.

• 정점 (Vertex) : 노드와 같은 개념
• 간선 (Edge) : 노드를 연결하는 선
• 인접 정점 (Adjacent Vertex) : 간선에 의해 직접 연결된 정점
• 정점의 차수 (Degree) : 무방향 그래프에서, 하나의 정점에 인접한 정점의 수
  • 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배

 

2.

2개 이상의 경로가 가능하다.

 

3.

루트 노드라는 개념이 없고, 부모와 자식 개념 역시 없다.

 

4. 오일러 경로

• 그래프에 존재하는 모든 간선을 한 번만 통과하여 처음 정점으로 돌아오는 경로
• 그래프의 모든 정점에 연결된 간선의 수가 '짝수'일 때만 오일러 경로가 존재한다.

 

 

 

---

 

 

Tree와 Graph 비교