[CS 스터디] 5.3 비선형 자료구조(그래프, 트리, 힙, 우선순위 큐, 맵, 셋, 해시 테이블)

공부/면접을 위한 CS 전공지식 노트

[CS 스터디] 5.3 비선형 자료구조(그래프, 트리, 힙, 우선순위 큐, 맵, 셋, 해시 테이블)

규투리 2022. 10. 5. 20:28

[면접을 위한 CS 전공지식 노트] 는 C++ 기반의 자료구조를 다루고 있다.

자료구조는 크게 선형과 비선형의 구조로 나뉜다.

💡 비선형 자료 구조란?
: 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말한다.

대표적인 자료구조

선형구조 : 배열, 연결리스트, 스택, 큐, 데크
비선형구조 : 그래프, 트리, 힙, 우선순위 큐, 맵, 셋, 해시 테이블

1. 그래프(Graph)

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

정점(vertex) : 위치 (=node)
간선(edge) : 위치 간의 관계, 즉, 노드를 연결하는 선
outdgree : 해당 정점으로 나가는 간선
indgree : 해당 정점으로 들어오는 간선

정리하자면, 그래프는 정점과 간선으로 이루어진 집합이다.

1.1 무방향 그래프 vs 방향 그래프

무방향 그래프(Undirected Graph)

무방향 그래프의 간선은 간선을 통해서 양 방향으로 갈 수 있다.
정점 A와 정점 B를 연결하는 간선은 (A,B) 와 같이 정점의 쌍으로 표현한다.
(A,B) == (B,A)

방향 그래프(Directed Graph)

간선에 방향성이 존재하는 그래프
A → B 로만 갈 수 있는 간선은 <A,B> 로 표시한다.
<A,B> != <B,A>

1.2 가중치 그래프

가중치는 간선과 정점 사이에 드는 비용을 뜻한다.

간선에 비용이나 가중치가 할당된 그래프
'네트워크' 라고도 한다.
도시-도시의 연결, 도로의 길이, 회로 소자의 용량, 통신망의 사용료 등

1.3 그래프의 탐색

일반적으로 두 가지 방법이 존재한다.

깊이 우선 탐색(DFS)
: 모든 노드를 방문하고자 하는 경우에 사용
너비 우선 탐색(BFS)
: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용

2. 트리(Tree)

💡 트리
: 트리 구조로 배열된 일종의 계층적 데이터의 집합이다.

2.1 트리의 특징

그래프의 한 종류이다. '최소 연결 트리'라고도 불린다.
부모 - 자식 계층 구조를 가진다.
노드가 N개인 트리는 항상 N-1 개의 간선을 가진다.
루트에서 어떤 노드로 가는 경로는 유일하다.
루트 노드는 한 개로 유일하며, 모든 자식 노드는 한 개의 부모 노드만을 가진다.

2.2 트리와 관련된 용어

루트 노드(root node)
: 가장 위에 있는 노드를 뜻한다. 트리에서 루트 노드는 한 개로 유일하다.
내부 노드(internal node)
: 루트 노드와 내부 노드 사이에 있는 노드를 뜻한다.
리프 노드(leaf node)
: 리프 노드는 자식 노드가 없는 노드를 뜻한다.

2.3 트리의 높이와 레벨

깊이
: 루트 ↔ 특정 노드
루트 노드부터 특정 노드까지 최단 거리로 갔을 때의 거리를 말한다.
높이
: 루트 노드로부터 리프 노드까지 거리 중 가장 긴 거리를 의미한다.
레벨
: 트리의 특정 깊이를 가지는 노드의 집합
서브트리
: 트리 내의 하위 집합, 트리 내에 있는 부분집합이다.

2.4 이진 트리(Bibary Tree)

💡 이진트리
: 자식의 노드 수가 두 개 이하인 트리

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

2.5 이진 탐색 트리(Binary Search Tree)

다음과 같은 특징을 갖는 이진트리를 이진 탐색 트리라 한다.

1. 각 노드에 중복되지 않는 키(key)가 있다.
2. 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다.
3. 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다.
4. 좌우 서브 트리 모두 이진 탐색 트리여야 한다.

트리를 이렇게 구성하면 검색이 용이하다.

왼쪽에는 작은 값, 오른쪽에는 큰 값이 이미 정해져 있기 때문에 10을 찾으려고 하면 25의 왼쪽 노드들만 찾으면 된다.

그렇기 때문에 보통 O(logn)이 걸린다, 하지만 최악의 경우 O(n)이 걸린다.

2.6 AVL 트리(Adelson-Velsky and Landis tree)

💡 AVL 트리
: 선형 트리의 단점을 보완한 자료구조, 스스로 균형을 잡는 이진 탐색 트리이다.

AVL 트리는 다음과 같은 특징을 갖는다.

1. 이진 탐색 트리의 속성을 가진다.
2. 왼쪽 오른쪽 서브 트리의 높이 차이가 최대 1이다.
3. 높이 차이가 1보다 커지면 회전(Rotation)을 통해 균형을 맞춰 높이 차이를 줄인다.
4. 삽입, 검색, 삭제의 시간 복잡도가 O(log N)이다.

아래 사이트를 통해서 AVL 트리의 삽입과 삭제 과정을 눈으로 확인할 수 있다.

https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

AVL Tree Visualzation

www.cs.usfca.edu

2.7 레드 블랙 트리(Red-Black Tree)

💡 레드 블랙 트리
: 균형 이진 트리로 탐새그 삽이브 삭제 모두 시간 복잡도가 O(log N)dlek.

다음 조건을 만족하는 이진탐색트리를 레드블랙트리 라고 부른다.

1. 각 노드의 색은 red 또는 black이다.
2. 루트 노드는 black이다.
3. 모든 리프노드는 black이다.
4. red 노드의 자식노드들은 전부 black이다. (즉, red 노드는 연속되어 등장할 수 없다.)
5. 루트 노드에서 시작해서 자손인 리프노드에 이르는 모든 경로에는 동일한 개수의 black노드가 존재한다.

3. 힙(Heap)

💡 힙
: 완전 이진 트리 기반의 자료 구조이며, 최대힙과 최소힙 두 가지가 있고, 해당 힙에 따라 특정한 특징을 지닌 트리를 말한다.

최대 힙
→ 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 한다. 또한 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이뤄져햐 한다.
최소 힙
→ 최소힙에서 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야 한다. 또한, 각 노드의 자식 노드와 관계도 이와 같은 특징이 재귀적으로 이뤄져야 한다.