그래프(Graph) - Tree, Binary Tree, Binary Search Tree

그래프이론은 오일러경로, SCC, 단절점 등 어려운 개념과 넓은 범위를 다루는 이론이지만,

해당 포스트에서는 그래프의 기초에 대해 다뤄보도록 하겠습니다.

 

우선 그래프의 기초 요소에 대해 알아봅시다.

Graph, Vertex, Edge, Weight

• Vertex (정점) : 하나의 지점
• Edge (간선) : 정점을 잇는 선 - 즉 경로
• Weight (가중치) : 간선에 부여된 값 (일종의 비용)

정점과 간선의 대표적 예시는 지하철 노선도를 들 수 있겠네요.

 

지하철 역 = Vertex,

역 사이의 경로 = Edge,

경로를 지날 때 걸리는 시간(or 경로 교통비) = Weight

 

간선은 단방향 간선, 양방향 간선으로 분류되기도 합니다.

또한 그래프 자체는 Undirected Graph 와 Directed Graph 로 분리됩니다. 

Undirected Graph의 경우에는 간선의 방향성이 없기 때문에, 양방향 간선으로 취급되곤 합니다.

 

 

Degree

degree는 Vertex에 이어진 간선의 개수를 의미합니다. 

그리고 방향 그래프에서, degree는 2가지로 나눌 수 있습니다.

indegree	Vertex에 들어오는 간선의 개수
outdegree	Vetex에서 나가는 간선의 개수

 

 

u(from), v(to) 는 자주 사용하는 네이밍이니까 기억하세요!

u노드의 경우 outdegree : 2, indegree: 3

v노드의 경우 outdegree: 3, indegree: 2

 

이렇듯 노드들이 간선으로 이어진 집합들을 모아둔 걸 "그래프(Graph)" 라고 합니다.

 

---

Tip!  문제에서 root node 가 주어지면 그 root node부터 탐색하면 된다.

Tree

Tree도 결국 그래프의 한 종류입니다.

다만 가장 자주 쓰이는 자료구조이기도 하고, 나무 모양을 닮아서 Tree 이름을 붙인겁니다.

 

다음의 조건을 만족하는 Graph는, Tree가 됩니다.

• Undirect Graph (무방향 그래프)  ➡️ 따라서 단순한 degree 개념만 존재한다 (연결된 간선의 개수)
• Cycle이 존재하지 않는다. ➡️ A노드에서 B노드로 향하는 경로는 오직 1개 뿐이다.
• 부모, 자식 계층 구조를 갖는다.  ➡️ 상위 노드, 하위 노드를 구분할 수 있다. 
• V - 1 = E 이다. ➡️ 즉, 간선의 수는 노드의 수 - 1 이다.

 

 

그 이외에, Tree에서 자주 쓰이는 단어들이 있습니다.

 

depth (0부터 시작, root 노드로부터 거리 - 혹은 Level이라고 하기도 함),

internal node,

leaf node,

subtree,

자식 노드, 부모 노드, 루트 노드

 

자세한 설명은 생략하도록 하겠습니다. (필요하면 검색 고!)

 

 

 

Binary Tree (이진 트리)

Tree 중에서도 자식 노드를 최대 2개까지만 가지는 트리를 이진 트리라고 합니다.

 

(https://towardsdatascience.com/5-types-of-binary-tree-with-cool-illustrations-9b335c430254)

 

이진 트리의 종류는 크게 5가지로 분류할 수 있습니다. 

 

1. 정이진 트리(full binary tree)

2. 완전 이진 트리(complete binary tree)

3. 변질 이진 트리(degenerate binary tree)

4. 포화 이진 트리(perfect binary tree)

5. 균형 이진 트리(balanced binary tree)

 

그 중에서, 균형이진트리에 대한 이야기를 좀 더 해보고자 합니다. 

 

 

위 그림의 왼쪽의 경우 균형이진트리이고, 오른쪽은 아닙니다. 

균형 이진 트리는 다음의 조건을 만족해야 합니다.

트리의 모든 노드에 대해, 그 노드의 왼쪽 하위 트리와 오른쪽 하위 트리의 높이 차이가 1 이하여야 한다.

 

여기서 높이 차이는, depth를 의미한다고 보면 됩니다. 

 

 

 

Binary Search Tree (이진 탐색 트리)

이진트리의 일종으로, 특정 노드(A노드) 의 왼쪽 하위 트리에는 A 노드의 값보다 큰 값이, 오른쪽 하위 트리에는 A 노드의 값보다 작은 값이 들어있는 트리를 의미합니다. BST를 통해 빠른 속도로 값을 찾아낼 수 있습니다. (전체 탐색 X)

(https://www.geeksforgeeks.org/applications-of-bst/)

 

 

따라서 만약 BST가 균형잡히게 노드가 분포되어 있다면, 

탐색, 삽입, 수정 모두 O(logN)의 시간복잡도를 가지게 됩니다.

 

하지만 BST의 형성은 노드의 삽입 순서에 따라 영향을 받습니다.

(1) 만약 2 → 1 → 3 순서로 삽입될 경우 : 왼쪽 그림과 같이 형성

(2) 만약 3 → 2 → 1 순서로 삽입될 경우 : 오른쪽 그림과 같이 형성 (선형적)

 

 

 

그래서 삽입 순서가 어떻게 되는 트리의 노드들을 회전시키는 등의 방법을 통해서

"균형 잡힌" 이진 탐색 트리를 형성하는 방식이 있는데, 그게 AVL 트리와 레드블랙트리입니다.

 

참고로, map이라는 자료구조는 삽입, 탐색, 삭제, 수정의 시간복잡도가 모두 O(logN)임을 보장받는데

이는 map이 균형잡힌트리(Balanced Binary Tree)인 레드블랙트리를 기반으로 구현되었기 떄문입니다.

아래는 레드 블랙트리의 기본적인 모습입니다. (지금 당장 자세한 설명은 생략하겠습니다.)

 

 

 

아래는 AVL트리가 노드를 회전시켜 BBT를 만드는 예시 그림입니다.