[자료구조] 트리와 그래프의 차이점

그래프

위키백과에 따르면 그래프의 정의는 아래와 같다.

• 그래프는 vertex(정점)와 edge(간선)로 구성된 한정된 자료구조를 말한다.
• 컴퓨터 시스템에 그래프를 저장하는 방법은 여러가지가 있다. 이론적으로 그래프는 리스트와 행렬 구조 중의 하나로 구별 가능하다. 하지만 실제 적용에 있어서 최적의 자료 구조는 이 두구조의 조합된 형태를 띤다.

단순히 말해 노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 자료구조를 그래프라고 말하는데, 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조이다.

그래프의 예시

• 지하철 노선도
• 도로

그래프의 특징

• 노드들 사이에 무방향/방향 양방향 경로를 가질 수 있다.
• 무방향 그래프의 경우 간선을 통해서 양 방향으로 갈 수 있으며 정점 A와 정점 B를 연결하는 간선은 정점의 쌍으로 표현한다.(ex. (A, B)) 특히 (A, B)와 (B, A)가 동일하다는 것을 알아두면 좋다.
• 방향 그래프는 간선에 방향성이 존재하는 그래프인데 아래에서 설명할 트리가 이에 해당된다.
• 루트 노드라는 개념이 없다. 따라서 부모, 자식 관계라는 개념이 없다.

그래프의 구현 방법 2가지

1. 인접 리스트
2. 인접 행렬

트리

트리는 특정 조건을 만족하는 그래프이다. 즉, 모든 트리는 그래프가 되지만 모든 그래프가 트리가 될 수 있는 것은 아니다. 벤 다이어그램으로 표현했을 때, 그래프가 트리를 포함하는 관계를 떠올리면 좋겠다.

그래프가 앞서 말했듯 개체 간의 '관계'를 표현한다면, 트리는 개체를 '계층' 구조로 표현하는 것이 핵심이다.

트리의 예시

• 회사의 전체 조직도
• 족보

트리의 특징

• 루트 노드가 존재하고, 루트노드를 시작으로 부모와 자식관계가 형성된다.
• 자식노드는 반드시 한개의 부모노드만을 가진다. 즉 두 정점 사이에 반드시 한개의 경로를 가진다.
• 트리는 사이클이 없는 연결 그래프이다.
• 정점의 개수가 A개라면, 간선의 개수가 A-1개이며 모든 정점이 연결된 그래프이다.

트리의 종류

• 이진트리(완전이진트리, 불완전이진트리)
• 이진탐색트리
• 힙트리 등

이진트리

자식을 최대 2개만 가지고 있는 트리이다.

완전이진트리

노드를 새로 추가할 때, 왼쪽부터 차례대로 넣어주는 트리이다. 예를 들어 왼쪽이 비어있고 오른쪽부터 들어간 트리가 있다면 그건 완전이진트리라고 할 수 없다. 그래서 좀더 생각해보면 완전 이진트리는 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있음을 머릿속에 그려볼 수 있다.

이진탐색트리

이진탐색트리는 우선 이진트리의 한 종류이다. 어떤 특징을 가지고 있냐면, 부모의 키가 왼쪽 자식 노드의 키보다 크고 오른쪽 자식 노드의 키보다는 작다. 왼쪽과 오른쪽 서브트리도 모두 이진 탐색트리로 구성되어 있다. 이름에서도 알 수 있듯이 탐색을 효율적으로 하기위해 고안되었다.