Table of contents
저번 시간에는 자료구조의 선형 자료구조(linear data structure)에 대해 알아봤습니다.
자료구조(Data Structure) - 1: Linear Data Structure
이번 시간에는 non-linear 한 자료구조에 대해 알아보겠습니다.
1. 그래프(Graph)
그래프는 노드(vertices)와 간선(edge)들로 이루어져 있는 자료구조이다.
간선들은 노드를 연결하는 데 사용된다.
그래프의 종류에는 두가지가 있다. (directed, undirected)
1-1. 무방향 그래프(undirected graph)
말 그대로 방향성이 없는 그래프 구조를 말한다. 두 정점을 연결하는 간선에 방향이 존재하지 않는다. 간선의 개수는 N*(N - 1) / 2
1-2. 방향 그래프(directed graph)
간선에 방향이 있는 그래프 구조를 말한다. 간선의 개수는 N*(N - 1)
1-3. 가중 그래프(Weighted graph)
각각의 간선이 어떠한 값(value)를 갖는다.
2. 그래프 구현 방법
2-1. Adjacency Matrix
배열을 활용하여 1차원 배열과 2차원 배열을 하나씩 만든다. 1차원 배열은 노드를 저장하는 데 사용하고, 2차원 배열은 간선을 저장하는 데 사용한다.
- 장점
두 노드간 연결성을 빠르게 확인할 수 있다.
간선이 많은 밀집도가 높은 그래프에 활용하기 좋다. (ex. complete graph)
- 단점
비어있는 간선에도 메모리를 할당해야 하므로 낭비되는 메모리가 많다.
2-2. Adjacency List
linked list 기반으로 구현한다.
첫번째 값은 노드를 나타내고, 이에 이어지는 Linked list에는 간선과 가중치(weighted value)가 들어간다.
- 장점
간선이 얼마 없는 희소 그래프에 좋다.
메모리 필요할 때 필요한 만큼만 할당할 수 있어 메모리 사용량이 많지 않다.
특정 꼭짓점에 인접한 노드를 찾기 쉽다.
3. 트리(Tree)
그래프의 일종으로, 노드들이 나무처럼 연결된 비선형 계층적 자료구조이다.
트리 내에 하위 트리가 존재하고, 그 하위 트리 안에는 또다른 하위 트리가 존재하는 재귀적 자료구조이기도 하다.
3-1. 트리 관련 용어
Root: 맨 상위의 노드, beginning node라고도 한다. 트리는 하나의 루트 노드만 가진다.
Parent Node: 부모 노드. 한 노드의 바로 상단에 연결되어 있는 노드
Child Node: 자식 노드. 한 노드의 바로 하단에 연결되어 있는 노드
Leaf Node: 자식 노드를 갖지 않는 노드
Sub-tree: 하위 트리. 트리 내부에서 트리 구조를 갖는 또 다른 트리를 말한다.
Depth: 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
3-2. 이진 트리(Binary Tree)
최대 2개의 자녀 노드만을 가지는 트리. 루트 노드로부터 특정 노드까지의 unique한 경로가 존재한다.
이진 트리 예시
3-3. 이진 트리 종류
(1) 정 이진 트리(Full Binary Tree)
모든 노드가 0 또는 2개의 자녀 노드를 가진다.
(2) 완전 이진 트리(Complete Binary Tree)
높이가 h일 때, h -1 까지는 정 이진 트리이고, 레벨 h는 왼쪽부터 노드가 채워진 트리이다.
노드의 개수는 2^(h -1) -1 <= n <= 2^h - 1
(3) 포화 이진 트리(Perfect Binary Tree)
모든 leaf node가 같은 높이에 있고 leaf node가 아닌 노드는 모두 2개의 자녀 노드를 갖는 트리이다.
3-4. 트리 순회
트리에 존재하는 노드들을 방문하는 방법에는 3가지가 있다. 정말 많이 사용하는 개념으로 중요하다!!
(1) 중위 순회: InOrder Traversal
왼쪽 하위 트리 -> root -> 오른쪽 하위 트리 순서로 순회한다.
알파벳 순서대로 print할 때 주로 사용한다.
void InOrder(TreeNode* tree, QueType& inQue){
if (tree != NULL) {
InOrder(tree->left, inQue);
inQue.Enqueue(tree);
InOrder(tree->right, inQue);
}
}
(2) 후위 순회: PostOrder Traversal
왼쪽 하위 트리 -> 오른쪽 하위 트리 -> root
노드들을 delete할 때 사용하기 좋다.
void PostOrder(TreeNode* tree, QueType& postQue) {
if (tree != NULL) {
PostOrder(tree->left, postQue);
PostOrder(tree->right, postQue);
postQue.Enqueue(tree);
}
}
(3) 전위 순회: PreOrder Traversal
root -> 왼쪽 하위 트리 -> 오른쪽 하위 트리
tree copy할 때 사용하기 좋다.
DFS(Depth-first Search) 의 원리
void PreOrder(TreeNode* tree, QueType& preQue) {
if (tree != NULL) {
preQue.Enqueue(tree);
PreOrder(tree->left, preQue);
PreOrder(tree->right, preQue);
}
}