그래프와 트리는 데이터 사이의 관계를 표현하는 자료구조입니다. 트리는 특별한 조건을 만족하는 그래프이며, 두 개념을 완전히 별개의 구조로 이해하면 관계를 놓치기 쉽습니다.
그래프
그래프는 정점(vertex)과 정점 사이를 연결하는 간선(edge)으로 구성됩니다. 사람과 친구 관계, 도시와 도로, 작업과 의존 관계 등을 표현할 수 있습니다.
- 방향 그래프: 간선에 방향이 있습니다.
- 무방향 그래프: 양방향 관계를 표현합니다.
- 가중치 그래프: 간선에 거리나 비용 같은 값이 있습니다.
일반적인 그래프는 사이클이 있을 수도 없을 수도 있고, 일부 정점끼리 연결되지 않을 수도 있습니다. 두 정점 사이의 경로도 없거나 여러 개일 수 있습니다.
트리
그래프 이론에서 트리는 연결되어 있고 사이클이 없는 무방향 그래프입니다. 정점이 N개인 비어 있지 않은 트리는 간선이 N - 1개이고, 임의의 두 정점 사이에 단순 경로가 정확히 하나 있습니다.
자료구조에서는 한 정점을 루트로 정해 계층적으로 다루는 경우가 많습니다.
- 루트: 계층의 시작점
- 부모와 자식: 루트를 기준으로 연결된 상하 관계
- 리프: 자식이 없는 노드
- 깊이: 루트에서 해당 노드까지의 간선 수
루트를 정한 트리는 부모에서 자식 방향으로 표현할 수 있지만, “모든 트리는 방향 그래프”라고 정의하는 것은 부정확합니다.
같은 정점으로 비교하기
정점이 A, B, C, D이고 간선이 A-B, A-C, C-D이면 모든 정점이 연결되고 사이클이 없으므로 트리입니다.
여기에 B-D를 추가하면 A-B-D-C-A라는 사이클이 생깁니다. 여전히 그래프이지만 더 이상 트리는 아닙니다.
| 기준 | 일반 그래프 | 트리 |
|---|---|---|
| 연결성 | 연결되지 않을 수 있음 | 모든 정점이 연결됨 |
| 사이클 | 있을 수 있음 | 없음 |
| 두 정점 사이의 단순 경로 | 없거나 여러 개 가능 | 정확히 하나 |
| 대표 용도 | 도로망, 친구 관계 | 계층 구조, 탐색 구조 |
트리와 이진 트리
트리가 반드시 자식을 두 개 이하로 가지는 것은 아닙니다. 그 조건을 추가한 것이 이진 트리입니다. 이진 탐색 트리는 여기에 값의 대소 관계에 대한 규칙을 더한 구조입니다.
참고