[자료구조] 5.3. 비선형 자료 구조

본 포스팅은 [면접을 위한 CS 전공지식 노트]의 내용을 참고하여 작성하였습니다.

---

 

5.3. 비선형 자료 구조

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

 

 

1) 그래프

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

 

정점과 간선

' 어떠한 곳에서 어떠한 곳으로 무언가를 통해 간다. '

위에서 '어떠한 곳'은 정점(vertex)이고, '무언가'는 간선(edge)이 된다.

이와 같이 정점과 간선으로 이루어진 집합을 '그래프(graph)'라고 한다.

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

또한, 간선과 정점 사이에 드는 비용을 '가중치'라고 한다.

 

 

 

2) 트리

트리는 그래프 중 하나로 정점과 간선으로 이루어져 있고, 트리 구조로 배열된 계층적 데이터의 집합이다.

 

트리의 특징

1. 부모, 자식 계층 구조를 가진다. 같은 경로 상에서 어떤 노드보다 위에 있으면 부모, 아래에 있으면 자식 노드가 된다.
2. 간선의 수는 노드의 수 - 1이다.
3. 임의의 두 노드 사이의 경로는 항상 '유일'하게 '존재'한다.

 

트리의 구성

트리는 루트 노드, 내부 노드, 리프 노드로 이루어져 있다.

• 루트 노드: 가장 위에 있는 노드.
• 내부 노드: 루트 노드와 리프 노드 사이에 있는 노드.
• 리프 노드: 자식 노드가 없는 노드.

 

트리의 높이와 레벨

• 깊이(depth): 루트 노드부터 특정 노드까지의 최단거리.
• 높이(height): 루트 노드부터 리프 노드까지 거리 중 최장거리.
• 레벨(level): 문제마다 의미가 조금씩 다르지만, 보통 깊이와 같은 의미를 지닌다.
• 서브트리: 트리 내의 하위 집합(부분집합).

 

이진 트리

• 정이진 트리(full binary tree): 자식 노드가 0 또는 두 개인 이진 트리
• 완전 이진 트리(complete binary tree): 왼쪽에서부터 완전히 채워져 있는 이진 트리
• 변질 이진 트리(degenerate binary tree): 자식 노드가 하나뿐인 이진 트리
• 포화 이진 트리(perfect binary tree): 모든 노드가 꽉 차 있는 이진 트리
• 균형 이진 트리(balanced binary tree): 왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 트리.(ex. 레드 블랙 트리)

 

이진 탐색 트리

노드의 왼쪽 하위 트리에는 '노드 값보다 작은 값', 오른쪽 하위 트리에는 '노드 값보다 큰 값'만 들어 있는 트리이다.

이렇게 구성하는 이유는 값을 검색하기 용이하기 때문이다. 보통 요소를 찾을 때 O(logn)이 걸린다.

 

하지만 최악의 경우 O(n)이 걸리는데, 이진 탐색 트리는 요소의 삽입 순서에 따라 선형적일 수 있기 때문이다.

 

 

AVL 트리

앞서 설명한 최악의 경우가 되는 것을 방지하기 위해 사용하는 이진 탐색 트리이다.

두 자식 서브트리의 높이는 항상 최대 1만큼만 차이가 난다는 특징이 있다.

삽입과 삭제, 탐색 모두 시간 복잡도가 O(logn)이며, 삽입과 삭제를 할 때마다 균형을 맞추기 위해 트리 일부를 왼쪽 혹은 오른쪽으로 회전시키며 균형을 잡는다.

 

 

레드 블랙 트리

 

균형 이진 탐색 트리이며 삽입과 삭제, 탐색 모두 시간 복잡도가 O(logn)이다.

각 노드는 빨간색 혹은 검은색의 색상을 나타내는 추가 비트를 저장하는데, 이는 삽입 / 삭제를 할 때 트리의 균형을 유지하는 데 사용한다.

1. 모든 리프 노드와 루트 노드는 블랙이다.
2. 어떤 노드가 레드이면 그 노드의 자식은 반드시 블랙이다.

등의 규칙을 기반으로 균형을 잡는 트리이다.

 

 

 

3) 힙

힙은 완전 이진 트리 기반의 자료구조이며, 최소힙 / 최대힙 두 가지가 있고 해당 힙에 따른 특징이 있는 트리를 말한다.

• 최소힙: 특정 노드에 있는 키가 모든 자식의 키보다 작아야 한다. 즉 루트 노드는 전체 키의 최솟값이다.
• 최대힙: 특정 노드에 있는 키가 모든 자식의 키보다 커야 한다. 즉 루트 노드는 전체 키의 최댓값이다.

 

최소힙 / 최대힙의 삽입, 삭제

최소힙 / 최대힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.

이 새로운 노드를 부모 노드의 크기와 비교하며 교환해서, 힙의 성질을 만족시키게 된다.

삭제 시 루트 노드를 삭제하며, 최솟값 혹은 최댓값을 반환한다. 그 이후 마지막 노드와 루트 노드를 스왑하고 재정렬한다.

 

 

 

4) 우선순위 큐

우선순위 큐는 대기열이라고도 하며, 대기열에서 우선순위가 높은 요소가 먼저 제공되는 자료구조이다.

 

우선순위 큐는 힙을 기반으로 구현되고, 다양한 자료구조를 넣어서 사용할 수 있다.

오름차순과 내림차순 뿐만 아니라 우선순위를 직접 정의하여 사용할 수도 있다.

 

 

 

5) 맵

맵은 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료구조이다.

레드 블랙 트리 자료 구조를 기반으로 형성되고, 삽입하면 자동으로 정렬된다.

 

맵을 사용할 때는 Map<String, int> 형태로 구현한다. 배열과 비슷하게 clear(), size(), erase()와 같은 기능을 지원한다.

맵은 해시 테이블을 구현할 때 쓰며, 정렬을 보장하지 않는 unordered_map과 정렬을 보장하는 map 두 가지가 있다.

 

 

 

6) 셋

셋은 특정 순서에 따라 고유한 요소를 저장하는 컨테이너이며, 중복되는 요소 없이 유니크한 값만 저장하는 자료 구조이다.

 

 

 

7) 해시 테이블

해시 테이블은 무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블이다.

삽입과 삭제, 탐색에 O(1)이 걸리며 undordered_map으로 구현한다.