그래프(Graph)와 트리(Tree)의 차이점 완벽 정리

프로그래밍에서 데이터 타입(data type)이란 사용자가 활용하고자 하는 데이터의 종류와 성격을 의미합니다. 컴파일러나 인터프리터는 이 데이터 타입을 기준으로 메인 메모리에 적절한 저장 공간을 할당하게 됩니다. 이렇게 데이터를 저장하기 위해 우리는 데이터의 성격에 따라 다양한 자료구조(data structure)를 사용하는데, 데이터는 크게 선형(Linear)과 비선형(Non-linear)으로 분류됩니다. 특히 비선형 데이터를 효과적으로 표현하기 위해 고안된 개념이 바로 그래프(Graph)와 트리(Tree)입니다.

그래프와 트리는 둘 다 비선형 데이터를 표현한다는 점에서 노드(Node)와 엣지(Edge)로 구성된다는 공통점을 가지고 있습니다. 하지만 두 자료구조 사이에는 몇 가지 중요한 차이점이 존재합니다.

그래프와 트리의 주요 차이점

1. 정의

그래프는 비선형 데이터를 시각적으로 표현한 것으로, 데이터는 노드로 나타내고 노드 간의 관계는 연결 경로, 즉 엣지(Edge)로 나타냅니다.

반면 트리 역시 비선형 데이터를 표현하지만, 계층(hierarchy) 구조라는 맥락에서 사용됩니다. 데이터는 노드로 표현되며, 바로 아래에 위치한 후속 데이터는 자식 노드(child node)라고 부릅니다.

2. 구현 방식

비선형 데이터를 표현할 때 그래프는 노드들이 서로 연결되어 있을 수도 있고 그렇지 않을 수도 있으며, 심지어 노드 간에 셀프 루프(self-loop)가 존재할 수도 있습니다.

반면 트리는 루트 노드(첫 번째 노드)를 제외한 모든 노드가 반드시 부모 노드를 가져야 하며, 어떤 노드도 다른 노드와 연결되지 않은 채 홀로 존재할 수 없습니다. 또한 트리는 계층적 구조로 데이터를 표현하기 때문에 루프나 셀프 루프가 발생할 수 없습니다.

3. 데이터 검색

그래프는 셀프 루프를 포함할 수 있기 때문에 순회(traversal) 방식으로 데이터를 검색하기가 상대적으로 어렵습니다. 사용자가 원하는 데이터에 도달하려면 노드들을 하나씩 연결해 가며 찾아가야 합니다.

반면 트리는 데이터가 계층적으로 연결된 노드 형태로 표현되므로, 순회 검색을 통해 트리의 특정 레벨에서 원하는 데이터를 체계적으로 찾을 수 있습니다.

4. 부모-자식 관계

그래프는 데이터를 계층적으로 표현하지 않기 때문에 노드 간에 부모-자식 관계가 존재하지 않습니다. 따라서 그래프에는 부모 노드나 자식 노드라는 개념 자체가 없습니다.

반면 트리는 데이터를 계층적으로 표현하므로 노드 간에 부모-자식 관계가 성립하며, 실제로 부모 노드와 자식 노드가 명확히 구분되어 존재합니다.

5. 상호 포함 관계

그래프의 관점에서 보면, 모든 그래프가 트리인 것은 아닙니다. 즉, 그래프 중에는 트리가 아닌 것들이 많습니다.

반면 트리의 관점에서 보면, 모든 트리는 그래프입니다. 트리는 그래프의 한 종류에 해당하는 특수한 형태라고 할 수 있습니다.

6. 활용 분야

그래프의 대표적인 활용 분야는 그래프 색칠(graph coloring)과 작업 스케줄링(job scheduling)입니다.

반면 트리의 대표적인 활용 분야는 정렬(sorting)과 순회(traversing)입니다.

핵심 차이점 요약 표