[CS] 비선형 자료 구조

• 일렬로 나열하지 않고, 자료 순서나 관계가 복잡한 구조 
• 일반적으로 트리, 그래프를 의미함
• 배열/리스트처럼 “앞뒤 순서”보다, “연결 관계·계층·우선순위”가 중요한 경우에 사용됨

 

1. 그래프

• 정점과 간선으로 이루어진 자료 구조
  💭 예: 보니가 회사까지 출근함 → 보니와 회사는 '정점', 회사까지 가는 길은 '간선'
• 노드 간 경로가 여러 개일 수 있음 → 정점으로 나가는 간선을 outdegree, 들어오는 간선을 indegree
• 가중치: 간선과 정점 사이에 드는 비용
• 그래프는 방향성 여부에 따라 나뉨
  1. 방향 그래프: 간선에 방향 있음 (A → B)
  2. 무방향 그래프: 방향 없음 (A — B)
• 가중치 그래프는 “비용/거리/시간” 같은 현실 문제 모델링에 적합
  💭 예: 최단 경로, 추천 시스템, 의존성 분석
• 사이클이 존재할 수 있음
• 트리보다 자유도가 높음

 

---

2. 트리

• 그래프 중 하나
• 정점과 간선으로 이루어져 있고, 트리 구조로 배열된 일종의 계층적 데이터의 집합
• 루트 노드, 내부 노드, 리프 노드 등으로 구성
  1. 루트 노드
     • 가장 위에 있는 노드
     • 트리를 탐색할 때 루트 노드 중심으로 탐색 시 쉽게 풀이 가능 
     • 트리는 항상 하나의 루트 노드만 존재
  2. 내부 노드
     • 루트 노드와 리프 노드 사이에 있는 노드
     • 자식 노드를 하나 이상 가지는 노드
     • 리프 노드는 내부 노드에 포함되지 않음
  3. 리프 노드
     • 자식 노드가 없는 노드
     • 트리의 끝 지점
• 부모-자식 계층 구조를 가짐
• 간선 수(E) = 노드 수(V) - 1
• 트리 내 노드 간 경로는 반드시 존재하며, 유일함 (두 개 이상 존재 불가)

1. 이진 트리

• 자식의 수가 2개 이하인 트리
• 정이진 트리
  • 자식 노드가 0 또는 두 개인 이진 트리
• 완전 이진 트리
  • 왼쪽부터 채워져 있는 이진 트리
  • 마지막 레벨 제외 모든 레벨은 완전히 채워져 있으나, 마지막 레벨의 경우 왼쪽부터 채워짐
• 변질 이진 트리
  • 자식 노드가 하나밖에 없는 이진 트리
• 포화 이진 트리
  • 모든 노드가 꽉 차 있는 이진 트리
• 균형 이진 트리
  • 왼쪽과 오른쪽 노드의 높이 차가 1 이하인 이진 트리 → 레드 블랙 트리가 여기에 해당

 

2. 이진 탐색 트리 (BST)

•  노드의 오른쪽 하위 트리에는 '노드 값보다 큰 값'이 있는 노드만 포함, 왼쪽 하위 트리에는 '노드 값보다 작은 값'이 들어 있는 트리
• 왼쪽 및 오른쪽 하위 트리도 해당 특성을 가져서 '검색'에 용이
• 평균 시간 복잡도는 O(logN), 최악의 경우에는 O(n)

 

3. AVL 트리

• 최악의 경우 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리
• 두 자식 서브트리의 높이는 항상 ≤ 1
• 탐색/삽입/삭제시 시간복잡도는 O(log N)
• 삽입/삭제 시 회전(rotation) 으로 균형 유지  

 

4. 레드 블랙 트리

• 균형 이진 탐색 트리
• 각 노드는 Red / Black 색상을 가짐
• AVL보다 균형 조건이 느슨
• 탐색, 삽입, 삭제 모두 시간복잡도가 O(log n)
• map, set의 내부 구현으로 사용됨

 

---

3. 힙

• 완전 이진 트리 기반의 자료 구조
• 최댓값 또는 최솟값을 빠르게 관리하기 위한 자료 구조
• 힙의 종류는 최소힙과 최대힙 두 가지가 존재
  
  1. 최대힙: 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 함.
  2. 최소힙: 최소힙에서 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야 함.

      해당 힙에 따라, 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 함.

• 최대힙
  1. 삽입
     • 힙에 새로운 요소가 들어오면, 새로운 노드를 힙의 마지막 노드에 이어서 삽입.
     • 그 후 새로운 노드를 부모 노드들과 크기를 비교하며 교환(트리 높이만큼 이동)하여 힙의 성질을 만족
  2. 삭제
     • 최대힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제 > 마지막 노드를 루트로 올린 후 > 자식 노드 중 더 큰 값과 비교하며 내려감

 

---

4. 우선순위 큐

• 일반 큐(FIFO)와 달리 들어온 순서가 아니라, 우선순위가 높은 요소가 먼저 제공되는 자료 구조
• 힙을 기반으로 구현됨
• CPU 스케줄링, 작업 스케줄러, 이벤트 처리 시스템 등에서 사용

 

---

5. 맵 (Map)

• 특정 순서에 따라 키(Key)와 매핑된 값(Value)의 조합으로 형성된 자료 구조
• 키는 중복 불가하지만, 값은 중복 가능
• 레드 블랙 트리 자료 구조를 기반으로 형성 → "항상 균형 잡힌 이진 탐색 트리"
• 삽입 시 키 기준으로 항상 정렬 상태 유지
• 삽입 / 삭제 / 탐색 모두 O(log N)
• map의 종류: map vs unordered_map

  항목	map	unordered_map
  내부 구조	레드-블랙 트리	해시 테이블
  정렬	O	X
  탐색	O(log N)	평균 O(1)
  범위 탐색	가능	불가능
  순회 순서	정렬 순	랜덤

• 주요 메소드들
  1. clear(): 모든 요소 삭제
  2. size(): 요소 개수 반환
  3. erase(): 특정 키와 키에 매핑된 값 삭제
• 해시 테이블을 구현할 때 map 사용
• ✅ map이 적합한 경우
  1. 키 기준으로 정렬된 데이터가 필요할 때 (값에 바로 접근 가능)
  2. 범위 기반 탐색
  3. 순서가 논리적으로 의미 있을 때
  4. 데이터 개수가 많아도 최악 성능 보장이 필요할 때
• ❌ map이 부적합한 경우: 정렬 필요 없음 + 속도 최우선 → unordered_map이 더 적절

---

6. 셋 (Set)

• 특정 순서에 따라 중복되지 않는 값만 저장하는 컨테이너
• 값 자체가 곧 키 역할
• Set의 종류: set vs unordered_set

  항목	set	unordered_set
  내부 구조	레드-블랙 트리	해시 테이블
  정렬	O	X
  탐색	O(log N)	평균 O(1)

• 중복 불가
  1. 동일한 값을 여러 번 넣어도 1개만 저장
  2. 삽입 시 이미 존재하면 무시

     set = {1, 3, 5}
     insert(3) → 변화 없음

     
     

• 자동 정렬
  1. 기본적으로 오름차순
  2. 내부적으로 트리가 정렬을 유지

     insert 순서: 5 → 1 → 3
     결과: {1, 3, 5}

• 값의 존재 여부 탐색에 특화
• ✅ set이 적합한 경우
  1. 중복 제거가 핵심
  2. 데이터가 정렬된 상태로 필요
  3. 범위 탐색 (lower_bound, upper_bound) 필요
  4. 최악 성능도 예측 가능해야 할 때

 

---

7. 해시 테이블

• 무한에 가까운 데이터(키)들을 유한한 개수의 해시 값으로 매핑한 테이블
• 삽입, 삭제, 탐색 시 평균적으로 O(1)의 시간 복잡도를 가짐
• unordered_map으로 구현
• 작은 크기의 캐시 메모리로도 프로세스를 관리하도록 할 수 있음