토픽 74 / 76·비교표
## Part 7: 확률적 자료구조
블룸 필터 vs 해시 테이블
| 항목 | 블룸 필터 | 해시 테이블 |
|---|
| 정확도 | 확률적 (FP 존재, FN 없음) | 정확 |
| 공간 | 매우 작음 (비트 배열) | 큼 |
| 삭제 | 불가 (Counting BF 제외) | 가능 |
| 검색 | O(k) - 해시 함수 수 | O(1) 평균 |
| 적용 | 스팸 필터, DB 캐시 | 딕셔너리, 인덱스 |
스킵 리스트 vs AVL vs Red-Black
| 항목 | 스킵 리스트 | AVL | Red-Black |
|---|
| 균형 | 확률적 | 결정적 (엄격) | 결정적 (느슨) |
| 구현 | 단순 (다층 연결리스트) | 복잡 (회전) | 복잡 (회전+색상) |
| 검색 | O(log n) 기대 | O(log n) 보장 | O(log n) 보장 |
| 병렬성 | 높음 (부분 잠금) | 낮음 | 낮음 |
| 적용 | Redis SortedSet | 검색 최적 | STL, 커널 |
Suffix Tree vs Suffix Array vs 트라이
| 항목 | Suffix Tree | Suffix Array | 트라이 |
|---|
| 공간 | O(n) - 상수 큼 | O(n) - 상수 작음 | O(n) - 상수 큼 |
| 패턴 검색 | O(m) | O(m log n) | O(m) |
| 메모리 | 많음 | 적음 | 많음 |
| 적용 | 생물정보학 | 공간 제약 시 | 사전, 자동완성 |
영속 자료구조 vs 일시 자료구조
| 항목 | 영속 (Persistent) | 일시 (Ephemeral) |
|---|
| 불변성 | 불변 (이전 버전 보존) | 가변 (단일 버전) |
| 메모리 | 많음 (경로 복사) | 적음 |
| 적용 | Git, 함수형 언어, 에디터 Undo | 일반 프로그래밍 |
공간 자료구조: Quadtree vs Octree vs KD-Tree
| 항목 | Quadtree | Octree | KD-Tree |
|---|
| 차원 | 2D | 3D | k차원 |
| 분할 | 4분할 | 8분할 | 2분할 (축 교대) |
| 적용 | 2D 게임, 지도 | 3D 렌더링, 볼륨 | 최근접 이웃, ML |
KD-Tree vs Ball Tree vs R-Tree
| 항목 | KD-Tree | Ball Tree | R-Tree |
|---|
| 적합 차원 | 저차원 | 고차원 | 공간 객체 |
| 분할 | 축 기반 분할 | 구(Ball) 기반 | MBR (최소 경계 사각형) |
| 적용 | 점 쿼리 | ML (고차원 NN) | GIS, 공간 DB |
Count-Min Sketch vs 해시 테이블
| 항목 | Count-Min Sketch | 해시 테이블 |
|---|
| 정확도 | 근사 (과대추정) | 정확 |
| 공간 | 매우 작음 | 큼 |
| 삭제 | 불가 | 가능 |
| 적용 | 스트리밍 빈도 추정 | 정확 카운트 |
HyperLogLog vs 해시 셋
| 항목 | HyperLogLog | 해시 셋 |
|---|
| 정확도 | 근사 (오차 ~2%) | 정확 |
| 공간 | KB | GB |
| 적용 | 고유 방문자 수 | 정확 카운트 필요 시 |
Cuckoo Filter vs Bloom Filter
| 항목 | Cuckoo Filter | Bloom Filter |
|---|
| 삭제 | 지원 | 불가 |
| 공간 | 더 작음 | 큼 |
| False Positive | 유사 | 유사 |
| 적용 | 삭제 필요 시 | 삽입 전용 |