그래프
- 정점(vertax)과 간선(edge)으로 이루어진 자료 구조
- 가중치 : 간선과 정점 사이에 드는 비용
트리
- 정점과 간선으로 이뤄진, 트리 구조로 배열된 계층적 데이터의 집합
- 부모, 자식 계층 구조
- E = V - 1, 간선 수는 노드 수 - 1
- 루트 노드 : 가장 위에 있는 노드
- 내부 노드 : 루트 노드와 리프 노드 사이에 있는 노드
- 리프 노드 : 자식이 없는 노드
- 깊이 : 루트 노드로부터 특정 노드까지 최단 거리
- 높이 : 루트 노드로부터 리프 노드까지 거리 중 가장 긴 거리
- 서브 트리 : 트리 내의 하위 집합
이진 탐색 트리 (BST)
- 노드의 오른쪽 하위 트리에는 ‘노드 값보다 큰 값’ 이 있는 노드만 포함되고, 왼쪽 하위 트리에는 ‘노드 값보다 작은 값’이 들어 있는 트리
- 탐색 시간 복잡도는 O(logN), 최악의 경우 O(N)
AVL 트리
- 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리
- 두 자식 서브 트리의 높이는 항상 최대 1만큼 차이
- 탐색, 삽입, 삭제의 시간 복잡도 O(logN)
레드 블랙 트리
- 균형 이진 타맥 트리로 탐색, 삽입, 삭제 모두 시간 복잡도는 O(logN)
- 각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하며, 삽입 및 삭제 중 트리가 균형을 유지하는 사용
Heap
- 완전 이진 트리 기반의 자료 구조이며, 최소힙과 최대힙 두 가지가 있고 해당 힙에 따라 특정한 특징을 지킨 트리
- 최대힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중 최대값, 각 하위 트리도 같은 규칙
- 최소힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중 최솟값, 각 하위 트리도 같은 규칙
- 삽입은 가장 힙의 마지막 노드에 삽입해 부모노드와의 크기를 비교하며 교환해서 힙의 성질을 만족, 삭제는 루트노드가 삭제되고 자식노드가 루트노드를 대체
우선순위 큐
- 우선순위 대기열이라고도 하며, 대기열에서 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료 구조
- 힙을 기반으로 구현
Map
- 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료 구조
- 레드 블랙 트리 자료 구조를 기반으로 형성되고, 삽입하면 자동 정렬
- 정렬을 보장하지 않는 unordered_map 도 존재
Set
- 특정 순서에 따라 고유한 요소를 저장하는 컨테이너이며, 중복되는 요소는 없고 희소한 값만 저장하는 자료 구조
Hash Table
- 무한에 가까운 데이터를 유한한 개수의 해시 값으로 매핑한 테이블
- 삽입, 삭제, 탐색 시 평균 O(1)의 시간 복잡도
- unordered_map 으로 구현
728x90