비선형 자료구조

본 포스팅은 '면접을 위한 CS 전공지식 노트'를 기반으로 작성되었습니다.

 

비선형 자료구조

• 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조
• 일반적으로 트리나 그래프를 말함

그래프(Graph)

• 정점과 간선으로 이루어진 자료구조

https://ltsgod.tistory.com/147

그래프 이론

트리

• 그래프의 특징처럼 정점과 간선으로 이루어져 있고, 트리 구조로 배열된 일종의 계층적 데이터 집합

https://ltsgod.tistory.com/125

트리(Tree), 이진 탐색 트리(BST)

힙(Heap)

• 완전 이진트리 기반의 자료 구조
• 최대 힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 함. 각 노드의 자식 노드들도 이러한 관계가 재귀적으로 이루어짐.
• 최소 힙 : 최대힙과 반대

최대힙의 삽입

• 일단 리프 노드에 이어서 삽입 후 부모 노드와 비교하며 재귀적으로 바꾼다.

최대힙의 삭제

• 루트 노드 삭제 후 마지막 노드와 루트 노드를 스왑하여 재귀적으로 재구성

https://johoonday.tistory.com/129

힙[Heap], 삽입 및 삭제

우선 순위 큐(Priority Queue)

• 우선순위가 높은 요소가 우선 순위가 낮은 요소보다 먼저 제공되는 자료구조
• 힙 기반으로 구현 됨.

맵(Map)

• 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료구조
• 레드블랙 트리 자료구조 기반 형성, 삽입되면 자동으로 정렬됨.
• 정렬이 되는 map 과 정렬을 보장하지 않는 unordered_map으로 나뉨.

셋(Set)

• 특정 순서에 따라 고유한 요소를 저장하는 컨테이너
• 중복되는 요소가 존재하지 않고 unique한 값만 저장한는 자료구조

해시 테이블(Hash Table)

• 무한에 가까운 데이터들을 유한한 개수의 해시값으로 매핑한 테이블
• 삽입, 삭제, 탐색 평균 O(1)
• unordered_map으로 구현