트리(Tree)와 그래프(Graph) 비교하기

트리 및 그래프 데이터 구조는 모두 데이터를 계층적 방식으로 구성하는 방법이다. 그러나 이들은 다른 유형의 문제에 적합한 몇 가지 주요 차이점을 가지고 있다.

 

트리(Tree)

트리는 부모-자녀 관계로 배열된 노드로 구성된 계층적 데이터 구조다. 각 노드에는 상위 노드가 없는 루트 노드를 제외하고 단일 상위 노드가 있다. 자식 노드는 방향 에지(Edge)를 통해 부모에 연결된다. 트리 구조는 종종 파일 시스템이나 패밀리 트리와 같은 계층적 관계를 나타내는 데 사용된다.

다음은 파이썬으로 작성한 트리 구조의 예다.

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

 

이렇게 하면 다음과 같은 구조의 트리가 생성된다.

 

    1
   / \
  2   3
 / \
4   5

이 예에서 노드 1은 루트 노드이고 노드 2와 3은 자식이다. 그리고 노드 2에는 4와 5라는 두 개의 자식이 있다.

트리의 주요 특징 중 하나는 엄격한 계층 구조를 가지고 있다는 것이다. 맨 위에는 단일 루트 노드가 있고 그 아래에는 다른 모든 노드가 있다. 이를 통해 노드 간의 관계를 쉽게 이해하고 트리를 탐색할 수 있다.

 

그래프 (Graph)

그래프는 꼭짓점 집합(노드라고도 함)과 이 꼭짓점들을 연결하는 모서리 집합으로 구성된 비선형 데이터 구조이다. 모서리는 당면한 문제에 따라 방향을 지정하거나 방향을 지정하지 않을 수 있다. 트리와 달리 그래프는 단일 노드에 대해 다중 부모를 가질 수 있을 뿐만 아니라 루프(꼭짓점과 자신을 연결하는 모서리)도 가질 수 있다.

다음은 파이썬으로 작성한 그래프 구조의 예다.

class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_list = [[] for _ in range(num_vertices)]
    
    def add_edge(self, u, v):
        self.adj_list[u].append(v)

graph = Graph(5)
graph.add_edge(0, 1)
graph.add_edge(0, 4)
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(1, 4)
graph.add_edge(2, 3)
graph.add_edge(3, 4)

이 그래프 구조는 다음과 같다.

 

    0 ---- 1 ---- 4
          | \
          |  \
          2----3

이 그래프에는 5개의 꼭짓점(0, 1, 2, 3, 4)과 6개의 모서리가 연결되어 있다. 꼭짓점은 꼭짓점과 루프(꼭짓점과 자신을 연결하는 모서리) 사이에 여러 개의 연결이 있는 비선형 방식으로 연결된다. 이러한 유형의 구조는 네트워크 및 연결을 나타내는 데 유용하다.

 

요약

트리 구조와 그래프 구조의 주요 차이점은 트리는 각 노드에 대해 단일 부모를 갖는 계층적 데이터 구조인 반면, 그래프는 다중 부모와 루프를 가질 수 있는 비선형 데이터 구조라는 것이다. 트리는 종종 계층적 관계를 나타내는 데 사용되는 반면, 그래프는 여러 개의 점들이 선으로 이어져 있는 복잡한 네트워크 망과 같은 모습을 가지고 있어, 포털 사이트의 검색 엔진이나 SNS에서 사람들과의 관계, 내비게이션 (길 찾기) 등에 사용된다.