토픽 73 / 76·비교표
## Part 6: 트리 기반 특수 자료구조
트라이 vs 해시 vs BST
| 항목 | 트라이 | 해시 테이블 | BST |
|---|
| 검색 | O(m) - 키 길이 | O(m) 평균 | O(m log n) |
| 접두사 검색 | 가능 (최적) | 불가 | 비효율 |
| 공간 | 큼 (노드 많음) | 중간 | 중간 |
| 적용 | 자동완성, 사전 | 정확 매칭 | 정렬 데이터 |
Union-Find vs BFS/DFS (연결성)
| 항목 | Union-Find | BFS/DFS |
|---|
| 복잡도 | O(alpha(n)) - 거의 상수 | O(V+E) |
| 동적 연결 | 효율적 (Union 연산) | 비효율 (재탐색) |
| 적용 | Kruskal MST, 동적 연결성 | 정적 연결성, 경로 탐색 |
세그먼트 트리 vs Fenwick 트리 vs 누적합
| 항목 | 세그먼트 트리 | Fenwick (BIT) | 누적합 |
|---|
| 구간 쿼리 | O(log n) | O(log n) | O(1) |
| 갱신 | O(log n) | O(log n) | O(n) |
| 공간 | 4n | n | n |
| 연산 | 합/최대/최소 등 다양 | 합만 | 합만 |
| 적용 | 범용 구간 쿼리 | 구간합 (간단) | 정적 데이터 |
Lazy Propagation vs 단순 세그먼트 트리
| 항목 | Lazy Propagation | 단순 세그먼트 트리 |
|---|
| 구간 갱신 | O(log n) | O(n log n) |
| 단일 갱신 | O(log n) | O(log n) |
| 복잡도 | 높음 (지연 전파) | 낮음 |
| 적용 | 구간 갱신이 빈번한 경우 | 단일 갱신만 필요 시 |
LRU vs LFU vs FIFO (캐시 교체)
| 항목 | LRU | LFU | FIFO |
|---|
| 기준 | 최근 사용 시간 | 사용 빈도 | 삽입 순서 |
| 장점 | 시간 지역성 활용 | 빈도 반영 | 단순 구현 |
| 단점 | 스캔 취약 | 과거 핫 데이터 잔류 | 지역성 무시 |
| 적용 | 범용 캐시 | CDN | 단순 캐시 |