토픽 70 / 76·비교표
## Part 3: 트리 자료구조
트리 vs 그래프
| 항목 | 트리 | 그래프 |
|---|---|---|
| 구조 | 계층적, 사이클 없음 | 일반적, 사이클 가능 |
| 루트 | 존재 | 없음 |
| 간선 수 | V-1 (정점 수-1) | 제한 없음 |
| 적용 | 파일 시스템, DOM | 소셜 네트워크, 경로 탐색 |
이진 트리 vs 일반 트리
| 항목 | 이진 트리 | 일반 트리 |
|---|---|---|
| 자식 수 | 최대 2개 | 제한 없음 |
| 순회 | 전위/중위/후위/레벨 | 전위/후위/레벨 |
| 적용 | BST, 힙, 허프만 | 파일 시스템, XML |
트리 순회: 전위 vs 중위 vs 후위 vs 레벨
| 항목 | 전위 (Preorder) | 중위 (Inorder) | 후위 (Postorder) | 레벨 (Level) |
|---|---|---|---|---|
| 순서 | 루트→좌→우 | 좌→루트→우 | 좌→우→루트 | 층별 좌→우 |
| 적용 | 복사, 직렬화 | 정렬 순서 출력 | 삭제, 후위식 | BFS |
| 구현 | 재귀/스택 | 재귀/스택 | 재귀/스택 | 큐 |
BST vs AVL vs Red-Black
| 항목 | BST | AVL | Red-Black |
|---|---|---|---|
| 균형 | 보장 안 함 | 엄격 (높이 차 ≤1) | 느슨 (높이 2배 이내) |
| 검색 | 평균 O(log n), 최악 O(n) | O(log n) 보장 | O(log n) 보장 |
| 삽입/삭제 | 빠름 (불균형 가능) | 느림 (회전 빈번) | 빠름 (회전 적음) |
| 회전 | 없음 | 삽입 시 많음 | 삽입 시 적음 |
| 적용 | 교육 | 검색 빈번 환경 | Java TreeMap, Linux RB-tree |
B-트리 vs B+트리
| 항목 | B-트리 | B+트리 |
|---|---|---|
| 데이터 위치 | 모든 노드에 데이터 | 리프 노드에만 데이터 |
| 리프 연결 | 없음 | 연결 리스트 (범위 쿼리) |
| 검색 | 중간 노드에서 종료 가능 | 항상 리프까지 탐색 |
| 범위 쿼리 | 비효율 (트리 재탐색) | 효율적 (리프 순회) |
| 적용 | 일반 인덱스 | DB 인덱스 (MySQL InnoDB) |
해시 vs BST
| 항목 | 해시 테이블 | BST |
|---|---|---|
| 검색 | 평균 O(1) | O(log n) |
| 정렬 | 불가 | 가능 (중위 순회) |
| 범위 쿼리 | 불가 | 가능 |
| 최악 | O(n) (충돌) | O(n) (편향) |
| 적용 | 캐시, 딕셔너리 | 정렬 데이터, 범위 검색 |
힙 vs BST
| 항목 | 힙 | BST |
|---|---|---|
| 정렬 수준 | 부분 정렬 (부모≥자식) | 완전 정렬 (좌<부모<우) |
| 최대/최소 | O(1) 접근 | O(log n) 접근 |
| 삽입/삭제 | O(log n) | 평균 O(log n) |
| 구조 | 완전 이진 트리 (배열) | 이진 탐색 트리 |
| 적용 | 우선순위 큐, 힙 정렬 | 사전, 정렬 데이터 |
피보나치 힙 vs 이진 힙 vs 이항 힙
| 항목 | 피보나치 힙 | 이진 힙 | 이항 힙 |
|---|---|---|---|
| decrease-key | O(1) 상각 | O(log n) | O(log n) |
| 삽입 | O(1) | O(log n) | O(1) 상각 |
| 병합 | O(1) | O(n) | O(log n) |
| 적용 | Dijkstra 최적화 | 범용 우선순위 큐 | 병합 필요 시 |
Splay vs AVL vs Red-Black
| 항목 | Splay Tree | AVL | Red-Black |
|---|---|---|---|
| 균형 | 자가 조정 (접근 시 루트 이동) | 엄격 균형 | 느슨 균형 |
| 검색 | O(log n) 상각 | O(log n) 보장 | O(log n) 보장 |
| 특징 | 자주 접근 데이터 빠름 | 검색 최적 | 삽입/삭제 최적 |
| 적용 | 캐시, 자주 접근 패턴 | 읽기 많은 DB | STL map, 커널 |