그래프(graph)와 트리(tree)

그래프(graph)

 여러 개의 점들이 서로 연결되어 있는 관계를 표현한 자료구조

그래프에서 하나의 점을 정점(vertex), 하나의 선을 간선(edge)라고 한다.

 

인접 행렬

[1] = [0, 0, 1, 0, 1] // 간선이 있으면 1, 없으면 0
[2] = [0, 0, 0, 1, 0] // 무방향 그래프
[3] = [1, 0, 0, 0, 0]
[4] = [0, 1, 0, 0, 0] // ex) 4 -> 5처럼 한 방향만 있으면 방향 그래프
[5] = [1, 0, 0, 0, 0]

 두 정점을 이어주는 간선이 있을 때, 이 두 정점을 인접하다고 한다. 예를 들어 A, B, C라는 서로 다른 정점이 있고 A와 B가 서로  이어져 있다면 1(true), 이어져 있지 않다면 0(false)을 표시한다. 한 개의 큰 표와 같은 모습이기 때문에 두 정점 사이의 관계를 확인하기 용이하다. 가장 빠른 경로를 찾을 때 주로 사용한다.

 

트리(tree)

트리의 구성요소는 노드(node)와 가지(edge)이다.

 

트리 용어

루트 노드 : 트리의 가장 윗 부분의 노드
리프 : 트리의 가장 아래에 있는 노드
레벨 : 루트로부터 얼마나 떨어져 있는지를 나타낸 값으로 루트 노드는 레벨 0이다.
차수(degree) : 노드가 갖는 자식의 수를 차수라고 한다.
높이 : 루트에서 가장 멀리 떨어진 리프까지의 거리 루트 노드의 레벨이 0이므로 총 4칸으로 구성된 트리의 높이는 3이다.

 

 

너비 우선 탐색(breadth-first search)

 낮은 레벨에서 시작해 왼쪽에서 오른쪽으로 가다가 한 레벨의 탐색이 끝나면 다음 레벨(아래)로 가 다시 왼쪽부터 오른쪽으로 탐색을 한다.

 

깊이 우선 탐색(depth-first search)

 리프(leaf)에 이를때까지 아래로 내려가 탐색하고 리프에 도달하면 부모에게 돌아간 후 다시 다른 자식 노드로 내려간다. 깊이 우선 탐색에는 세 종류가 있다.

 

전위 순회(preorder)

부모 노드 - 왼쪽 자식 노드 - 오른쪽 자식 노드

중위 순회(inorder)

왼쪽 자식 노드 - 부모 노드 - 오른쪽 자식 노드

후위 순회(postorder)

왼쪽 자식노드 - 오른쪽 자식 노드 - 부모 노드

 

이진트리(binary tree)

 이진트리는 각 노드가 왼쪽 자식과 오른쪽 자식 둘을 갖는 트리를 말한다. 이때 두 자식 가운데 한쪽이 없거나 둘 다 없는 경우도 있다. 즉, 최대 두 개의 자식 노드를 가질 수 있는 트리를 말한다.

 

완전 이진트리(complete binary tree)

 이진트리에서  마지막 레벨을 제외한 레벨은 노드를 빠짐없이 채운다. 높이가 k인 완전 이진트리가 가질 수 있는 노드의 최댓값은 2^(k+1) - 1개이다.

 

이진 검색 트리(binary search tree)

 이진트리에서 왼쪽 자식 노드는 부모 노드보다 작은 값이 들어가고, 오른쪽 자식 노드는 부모 노드보다 큰 값이 들어간다.

 

균형 검색 트리(self-balancing search tree)

 높이를 O(log n)으로 억제하여 빠른 속도로 검색할 수 있게 한다. 균형 검색 트리는 이진 균형 검색 트리와 이진이 아닌 균형 검색 트리로 나뉘는데 이진 균형 검색 트리에는 AVL 트리와 레드-블랙트리가 있으며, 이진이 아닌 균형 검색 트리에는 B 트리, 2-3 트리가 있다.