비선형 자료 구조

그래프

• 정점(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 으로 구현