트리와 그래프

컴퓨터공학 전공 중이시라면 당연히 두 자료구조의 이름은 들어보셨을 겁니다.

하지만 뭐.. 저는 학교 다니면서 그 차이점에 대해 전혀 알지 못했었는데요.
그렇게 여러 문제를 접하며 박살이 난 후에야 그 중요성을 알게 되었습니다.. 하하;

그래서 이 글에선 문제를 제대로 이해하기 위해선 반드시 정의와 그 차이를 알아야 하는 두 자료구조에 대해 알아보겠습니다.

(가볍게 어떤 것이고 이런 차이가 있다 정도로만 짚고 넘어가보겠습니다. ㅎㅎ)

 

---

Tree?

트리 구조란 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다.

(참고: wiki)

 

 

---

Graph?

그래프는 일부 객체들의 쌍들이 서로 연관된 객체의 집합을 이루는 구조이다. 일련의 꼭짓점들과 그 사이를 잇는 변들로 구성된 조합론적 구조로 볼 수 있다. 그래프를 연구하는 수학의 분야를 그래프 이론이라고 한다. 

(참고: wiki)

---

 

그래프는 수학 쪽 정의가 그나마 자주 접하는 그래프에 대한 정의를 써둔 것 같네요.

글로만 쓰면 역시 이해가 어렵기 때문에 그림으로 한번 나타내 보겠습니다.

 

그림 1. 트리

해당 그림은 트리 중에서도 자주 보실 수 있는 이진 트리입니다.

우선 트리는 노드가 N개라면 간선은 N-1개라는 특징을 갖습니다.

 

게다가 이진트리는 보시다시피 추가적인 특징을 갖고있습니다.

 

각 레벨 k에 존재하는 노드의 갯수는 2^k개 입니다.

또한 위와 같은 포화 이진 트리라면 전체 노드의 갯수는 최대 레벨이 K라고 가정했을 때, 2^(K+1) - 1개 입니다.

이걸 또 외워야하나 하실 수 있는데, 2진수의 특징을 생각해 보시면 굳이 외우지 않아도 익혀지실 것 같습니다.

level 0: 1

level 1: 11

level 2: 111

level N - 1: 11 ..... 1 (N 개)

level N : 11 ..... 1 ( N + 1 개)

이렇게 이진수 각 자리의 합은 2^N - 1로 정의 되니까 매칭해서 생각해보시면 트리 사이즈 당 전체 노드의 갯수는 쉽게 알아 낼 수 있습니다.

 

참고로, 포화 이진 트리란 각 레벨에 해당하는 노드가 모두 채워진 트리를 말합니다.

(이와 함께 완전 이진트리, 두가지에 대한 것은 어려운 개념은 아니니 찾아보시면 될 것 같습니다.)

 

또한, 그림에서 1번에 해당하는 노드를 루트노드라고 합니다.

루트노드: 트리의 가장 위에 있는 부모노드

부모노드: 한 노드의 상위 레벨에 인접한 노드

자식노드: 한 노드의 하위 레벨에 인접한 노드

 

즉, 1번이 루트노드이며 1번의 자식노드는 2, 3이 될 것이고 2, 3의 부모는 1번이 됩니다.

마찬가지로 2번은 4, 5의 부모 4, 5는 2번의 자식노드 이런식으로 연관됩니다.

 

보기편하시도록 일부러 익숙한 이진트리로 보여드렸는데요. 아래와 같은 것들도 트리에 속합니다.

특히, 세번째 트리는 한쪽에 치우쳐져 있다해 편향 트리라고 불립니다.

그림 2. 여러가지 트리

 

 

다음은 그래프입니다.

그림 3. 그래프

 

트리와는 사뭇 다른 모습을 보입니다.

우선 루트나 부모 자식노드라는게 존재하지 않습니다.

 

또한, 각 노드 사이에 Cycle을 형성 할 수 있습니다.

즉, 위 그림에서 1-3-4, 10-7-9-13-11 등의 사이클을 확인 하실 수 있는데요.

이는 그래프와 트리의 차이를 결정짓는 가장 중요한 특징입니다.

 

맨위에 찾아봤던 정의에 따르면, 트리와 그래프 사이의 관계는 이와 같습니다.

그림 4. 트리와 그래프 포함 관계

 

즉, 트리도 그래프라 볼 수 있지만, 그래프는 트리라고 볼 수 없습니다.

 

정리해보면, 트리는 DAG (Directed Acyclic Graph) 한 종류 입니다.

이는 사이클이 존재하지 않는 방향 그래프를 뜻합니다.

일반적으론 단방향이지만, LCA 같은 알고리즘에선 트리 내에서 양방향으로 연결 후, 단방향처럼 유도해서 처리하는 모습도 볼 수 있습니다.

 

그래프는 단방향(One direction), 양방향(Bidirection) 등 모두 가질 수 있습니다.

또한 사이클 뿐만 아니라 self loop도 가질 수 있습니다.

 

 

어떤 입력값에 사이클이 존재하느냐 안하느냐 또는 트리냐, 그래프냐의 차이는 해당 문제에 어떤 알고리즘을 적용할지에 대해 많은 도움을 주곤합니다.

예를 들어 사이클이 존재한다면, 위상정렬 등 트리를 이용한 알고리즘은 적용 할 수 없겠죠.

(물론 사이클 처럼 주어졌는데 해당 그래프를 리모델링하면 non cycle이 될 수도 있겠지만요.)

 

 

이외에도 많은 특징을 가지고 있는 자료구조지만, 우선적으로 사용 할 개념들만 정리해 보았습니다.

추가적으로 생각나는대로 수정해보겠습니다. 감사합니다.