[스터디3] 자료구조 - 08. 비선형 자료 구조

목차

 

 

이번에는 5.3 섹션인 비선형 자료 구조 위주로 정리하려고 합니다. 내용은 적지만 중요한 내용이므로 잘 기억해야 할 것 같네요.

5장 자료 구조

5.3 비선형 자료 구조

• 비선형 자료 구조: 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조

5.3.1 그래프

• 그래프(graph): 정점과 간선으로 이루어진 집합
• 정점(vertex): 위치를 나타내는 점 / 간선(edge): 두 정점을 연결하는 선으로, 두 위치 간의 관계나 경로를 표현함.
• 정점으로 나가는 간선은 해당 정점의 outdegree, 들어오는 간선은 해당 정점의 indegree라고 함.
• 가중치: 간선과 정점 사이에 드는 비용

▲ 간선의 종류

5.3.2 트리

• 트리: 그래프의 특징처럼 정점과 간선으로 이루어져 있고, 트리 구조로 배열된 일종의 계층적 데이터의 집합
• 숲: 트리로 이루어진 집합
• 트리의 특징
  1. 부모, 자식 계층 구조를 가짐.
  2. V(노드 수) - 1 = E(간선 수)
  3. 임의의 두 노드 사이의 경로는 유일무이하게 존재함.
• 트리의 구성
  1. 루트 노드: 가장 위에 있는 노드
  2. 내부 노드: 루트 노드와 리프 노드 사이에 있는 노드
  3. 리프 노드: 자식 노드가 없는 노드
• 트리의 구조
  • 깊이: 루트 노드부터 특정 노드까지 최단 거리로 갔을 때의 거리 (=레벨)
  • 높이: 루트 노드부터 리프 노드까지 거리 중 가장 긴 거리
  • 서브트리: 트리 내의 하위 집합
• 트리의 종류
  • 이진 트리: 자식의 노드 수가 두 개 이하인 트리
  • 이진 탐색 트리: 노드의 오른쪽 하위 트리에는 노드 값보다 큰 값이 있는 노드만 포함되고, 왼쪽 하위 트리에는 노드 값보다 작은 값이 들어 있는 트리

트리의 종류		설명
이진 트리	정이진 트리(full binary tree)	자식 노드가 0 또는 두 개인 이진 트리
	완전 이진 트리(complete binary tree)	왼쪽에서부터 채워져 있는 이진 트리
	변질 이진 트리(degenerate binary tree)	자식 노드가 하나밖에 없는 이진 트리
	포화 이진 트리(perfect binary tree)	모든 노드가 꽉 차 있는 이진 트리
	균형 이진 트리(balanced binart tree)	왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진 트리 (예: 레드 블랙 트리)
이진 탐색 트리(BST)	AVL 트리(Adelson-Velsky and Landis tree)	최악의 경우 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리
	레드 블랙 트리	탐색, 삽입, 삭제 모두 시간 복잡도가 O(log n)인 균형 이진 탐색 트리

▲ AVL 트리

▲ 레드 블랙 트리

5.3.3 힙

• 힙: 완전 이진 트리 기반의 자료 구조이고, 최소힙과 최대힙을 가지고 있음.
  • 최대힙: 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 함.
  • 최소힙: 최소힙에서 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야 함.

5.3.4 우선순위 큐

• 우선순위 큐(우선순위 대기열): 대기열에서 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료 구조
• 힙을 기반으로 구현됨.

▲ 우선순위 큐

5.3.5 맵

• 맵(map): 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료 구조
• 레드 블랙 트리를 기반으로 형성되고, 삽입하면 자동으로 정렬됨.
• 해시 테이블을 구현할 때 사용함.

5.3.6 셋

• 셋(set): 특정 순서에 따라 고유한 요소를 저장하는 컨테이너이며, 중복되는 요소는 없고 희소한 값만 저장하는 자료 구조

5.3.7 해시 테이블

• 해시 테이블: 무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블
• 정렬을 보장하지 않는 unordered_map으로 구현함.

이 글은 『 면접을 위한 CS 전공지식 노트 』 책을 학습한 내용을 정리한 것입니다.