트리·힙·그래프

---

0) 한눈에 보기

구조	핵심 개념	강점	약점	대표 쓰임
트리(Tree)	계층 구조(부모→자식)	계층 표현·검색 용이	구현/회전(균형) 복잡	폴더/카테고리, BST, DB 인덱스(B-트리)
힙(Heap)	완전이진트리 + 부모-자식 우선순위	최솟값/최댓값 O(1) 조회	중간 접근 부적합	우선순위 큐, 스케줄링, 힙 정렬
그래프(Graph)	노드+간선(방향/가중치 가능)	복잡 관계·경로 표현	구현·메모리 관리 난이도	네트워크, 최단경로, 소셜그래프

---

1) 트리 (Tree)

계층형 자료구조 — 노드가 부모-자식 관계를 이룸

1-1. 구현/종류

• 이진 트리: 각 노드 최대 2자식

• BST(이진 탐색 트리): 왼쪽 < 루트 < 오른쪽

• 레드-블랙 트리: 색(RED/BLACK)로 균형 유지

  • 규칙 요약: 루트=BLACK, RED의 자식은 모두 BLACK, 모든 경로의 블랙 높이 동일, null 리프는 BLACK
  • 시각화: Red/Black Tree

• AVL 트리: 각 노드 높이차 ∈ {-1,0,1} 유지(단/이중 회전)

  • 시각화: AVL Tree

• B-트리: 다진 트리, 리프 동일 깊이, 디스크 I/O 최적화

  • 시각화: B-Tree

선택 가이드

• 일반 목적: 레드-블랙 (삽·삭제 성능/구현 난이도 균형)
• 검색 성능 중시: AVL (더 촘촘한 균형)
• DB·파일시스템: B-트리 (블록 I/O 효율)

1-2. 연산 & 순회

• insert(x), delete(x), search(x)
• 순회: preOrder(전위), inOrder(중위), postOrder(후위) (+ BFS도 가능)

1-3. 복잡도

• 일반 BST: 평균 O(log n) / 최악 편향 시 O(n)
• 균형 트리(AVL, RB, B): 접근/삽입/삭제 모두 O(log n)
• 공간: O(n)

---

2) 힙 (Heap)

완전 이진 트리 기반 우선순위 구조 (Min/Max Heap)

2-1. 구현

• 배열 기반이 일반적(캐시 친화/공간 효율)

  • 부모/자식 인덱스: parent=i/2, left=2i, right=2i+1

• 링크드 힙도 가능하지만 잘 쓰지 않음

2-2. 연산

• insert(x) → heapify-up
• extractMin()/extractMax() → 루트 제거 후 heapify-down
• peek() / heapify(array) / isEmpty() / size() / clear()

2-3. 사용

• 우선순위 큐(스케줄러/이벤트), 힙 정렬, K개 중 상위/하위 유지

2-4. 복잡도

• 조회(루트): O(1)
• 삽입/삭제: O(log n)
• 공간: O(n)

---

3) 그래프 (Graph)

노드(V) + 간선(E), 방향/가중치/사이클 가능

3-1. 표현

• 인접 행렬(V×V 배열)

  • 간선 존재 확인 O(1), 공간 O(V²) (밀집 그래프 유리)

• 인접 리스트(노드별 연결 리스트)

  • 공간 O(V+E) (희소 그래프 유리), 간선 확인은 탐색 필요

3-2. 연산

• addNode, addEdge(u,v), removeNode/Edge
• findPath(u,v), traverse()(DFS/BFS)

3-3. 그래프 종류·예시

• 유향: 웹 링크, 의존 그래프
• 무향: 친구 관계
• 가중치: 도로망(거리/비용)

3-4. 인접 행렬 vs 리스트 (요약)

항목	행렬	리스트
간선 확인	O(1)	O(deg(u)) ≈ O(E)
간선 추가	O(1)	O(1)
간선 삭제	O(1)	O(deg(u))
공간	O(V²)	O(V+E)
적합	밀집 그래프	희소 그래프

---

4) 트리 vs 그래프

구분	트리	그래프
방향성	보통 단방향(부모→자식)	유향/무향 모두 가능
사이클	없음	있을 수 있음
루트	1개	없음
부모-자식	명확 (부모 1개, 루트 제외)	개념 없음(간선으로만 표현)
간선 수	V-1	제한 없음
경로	루트→노드 유일 경로	다수 경로 가능(최단경로 탐색 필요)
순회	전위/중위/후위/BFS	DFS/BFS

---

5) 핵심 요약

• 트리: 검색은 O(log n)이 표준 → 균형 트리 채택으로 최악 방지
• 힙: 루트 최솟값/최댓값 즉시 접근, 삽/삭제는 O(log n)
• 그래프: 희소 → 리스트, 밀집 → 행렬 선택
• 용도에 맞는 구조를 고르면 코드는 단순·빠르고 메모리도 절약