[트리-1] 트리의 정의/ 구성 요소 / 트리와 그래프 차이점

1. 트리의 정의 

: 계층적 구조를 갖는 자료들을 표현하기 위한 자료 구조이다. 

ex) 월드컵 본선 대진표, 회사나 학교의 조직도, 인터넷 상점의 상품 분류 기준 등 

 

2. 개요 

트리는 현실 세계의 개념을 추상화해 표현하는 자료 구조로 고안되었지만, 탐색형 자료 구조로도 유용하게 쓰인다.

특정한 조건을 지키도록 구성된 트리들을 이용하면 배열이나 리스트를 사용하는 것보다 같은 작업을 더 빠르게 할 수 있기 때문이다. 

즉, 어떤 형태로 트리를 구성하느냐, 자료들을 어떻게 배치하느냐에 따라 다양한 형태의 트리가 있을 수 있으며, 이들을 이용해 다양한 문제들을 빠르게 풀 수 있다. 

---

3. 트리의 구성 요소 

- 트리는 자료가 저장된 노드(node)들이 간선(edge)으로 서로 연결되어 있는 자료 구조이다. 

노드 간에는 상/하위 관계가 있으며, 두 노드가 연결되었을 때 한 노드는 좀 더 상위, 다른 노드는 좀 더 하위에 있어야 한다. 

 

- 두 연결된 노드 중 상위 노드를 부모, 하위 노드를 자식 노드라고 부른다. 

부모 노드가 같은 두 노드는 형제 노드라고 부른다. 

다른 모든 노드들을 자손으로 갖는 딱 하나의 노드를 루트(root)라고 부른다.

반대로 자식이 하나도 없는 노드들을 리프(leaf)라고 부른다. 

---

4. 트리와 노드의 속성

- 깊이(depth) : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수 (루트가 기준, 각 노드마다 다름)

- 높이(height) : 트리에서 가장 깊숙이 있는 노드의 깊이 (자손이 없는 경우 높이는 0이다.)

- 차수(degree) : 자식 노드의 개수 

- 크기(size) : 자신을 포함한 모든 자식 노드의 개수 

---

5. 트리의 재귀적 속성

모든 트리는 루트와 루트 밑에 있는 서브 트리들의 집합이다. 

이와 같은 재귀적 속성 때문에 트리를 다루는 코드들은 대게 재귀 호출을 이용해 구현한다. 

---

6. 그래프 vs 트리 차이점 

1.  트리는 순환 구조를 갖지 않는 그래프이다.  - 제일 중요

2. 트리는 부모 노드에서 자식 노드를 가리키는 단방향뿐이다. 

3. 트리는 하나의 부모 노드를 갖는다.

4. 루트는 하나여야 한다.