[알고리즘, 자료구조] 트리와 그래프

그래프

그래프는 정점과 간선으로 이루어진 자료구조 이다.

 

정점과 간선

어떤 곳에서 다른 어떤곳으로 무언가를 통해 간다고 할때, 어떤곳은 정점(vertex)이고 무언가는 간선(edge)이 된다.

 

B는 1개의 outdegree, A는 1개의 outdegree, 1개의 indegree, C는 1개의 indegree를 가지고 있다.

정점으로 나가는 간선을 해당 정점의 outdegree라고 하며 들어오는 간선을 해당 정점의 indegree라고 한다.

보통 정점은 약자로 V또는 U라고 하며 일반적으로 어떤 정점으로부터 시작해서 어떤 정점으로까지 간다를 U에서부터 V로 간다 라고 표현한다. 이렇게 정점과 간선으로 이루어진 집합을 그래프 라고 한다.

---

트리

트리는 그래프 중 하나로 그래프의 특징처럼 정점과 간선으로 이루어져 있고, 트리구조로 배열된 일종의 계층적 데이터 집합이다. 루트 노드, 내부 노드, 리프 노드 등으로 구성되고 트리로 이루어진 집합을 숲이라고 한다.

 

트리의 특징

1. 부모, 자식의 계층 구조를 가진다.

2. V - 1 = E  라는 특징이 있다.  (간선수는 노드수의 -1 이다.)

3. 임의의 두 노드 사이의 경로는 유일무이하게 존재한다. 즉 트리 내의 어떤 노드와 어떤 노드까지의 경로는 무조건 존재한다.

 

트리의 구성

• 루트 노드 
  • 부모가 없는 노드로, 가장 위에 있는 노드를 뜻한다. 보통 트리 문제가 나오고 트리를 탐색할 때 루트 노드를 중심으로 탐색하면 문제가 쉽게 풀리는 경우가 많다.
• 내부 노드
  • 리프 노드를 제외한 모든 노드로 자식이 있는 노드이다.
• 리프 노드
  • 리프 노드는 자식 노드가 없는 노드를 뜻한다.

 

트리의 높이와 레벨

• 깊이 : 트리에서 깊이는 각 노드마다 다르며 루트 노드로 부터 특정 노드까지 최단거리로 갔을때의 거리를 말한다.
• 높이 : 트리의 높이는 루트 노드로부터 리프 노드까지 거리 중 가장 긴 거리를 의미한다.
• 레벨 : 트리의 레벨은 주어지는 문제마다 조금씩 다르지만, 보통 깊이와 같은 의미를 지닌다. 
• 서브트리 : 트리 내의 하위 집합을 서브트리라고 한다. 트리 내에 있는 부분집합과 같다.

 

이진트리

이진트리는 자식의 노드 수가 두 개 이하인 트리를 의미하며, 이를 다음과 같이 분류한다.

• 정이진 트리(full binary tree) : 자식 노드가 0 또는 두 개인 이진 트리를 의미한다.
• 완전 이진 트리 (complete binary tree) : 왼쪽에서부터 채워져 있는 이진 트리를 의미한다. 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 경우 왼쪽부터 채워져 있다.
• 변질 이진 트리 (degenerate binary tree) : 자식 노드가 하나밖에 없는 이진 트리를 의미한다.
• 포화 이진 트리 (perfect binary tree) : 모든 노드가 꽉 차 있는 이진 트리를 의미한다.
• 균형 이진 트리 (balanced binary tree) : 왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진 트리를 의미한다. map, set을 구성하는 레드 블랙 트리는 균형 이진 트리중 하나입니다.

이진탐색트리(Binary serch tree)

이진탐색트리는 노드의 오른쪽 하위 트리에는 노드값보다 큰 값이 있는 노드만 포함하고 왼쪽 트리에는 노드값보다 작은 값이 포함된 트리를 말한다. 이때 왼쪽트리의 하위 트리 또한 해당 특성을 갖는다.

이진 탐색 트리

이렇게 하는 경우 검색하기가 용이하다. 보통 이진 탐색 트리의 경우 O(log n)이 걸린다. 하지만 최악의 경우 O(n)이 걸릴수도 있다.

그 이유는 이진탐색트리는 아래 그림처럼 삽입 순서에 따라 선형적일수 있기 때문이다.

이진 탐색 트리의 삽입 순서에 따른 선형적인 모습

---

트리와 그래프의 차이점 (간단설명)

그래프

• 그래프는 네트워크 모델이다
• 노드간에 2개이상의 경로도 가능하다
• 부모-자식 관계 개념이 없다.
• 그래프는 순환 혹은 비순환 구조를 가진다.
• 그래프는 방향성이 있는 그래프와 없는 그래프가 있다.

 

트리

• 그래프의 한 종류이다.
• 방향성이 있으며 사이클이 존재하지 않는다.(비순환 그래프)
• 부모-자식 관계 개념이 있으며 최상위에 루트노드가 있다.