2025-08-30 00:10
Tags: 자료구조
AVL트리
- 자가 균형 이진트리. 항상 O(log n)의 시간 복잡도 로 검색 보장
- 모든 노드 의 왼쪽과 오른쪽 서브트리 높이 차이 1이하, 차이 나면 회전으로 균형 맞춤
- 검색은 매우 중요하지만, 삽입 삭제 별로 안나는 경우, 정렬된 순서, 범위 검색 필요한 경우
- 일반 이진트리는 높이가 최악에는 일자로 쭉 늘어날 수 있는데 이를 회전으로 방어
| 자료구조 | 검색 시간 | 삽입/삭제 시간 | 특징 |
|---|---|---|---|
| AVL 트리 | O(log n) | O(log n) | - 엄격한 균형 유지 (높이 차이 1 이하) - 검색 성능이 매우 뛰어남 - 삽입/삭제 시 회전이 비교적 빈번할 수 있음 |
| 레드 블랙 트리 | O(log n) | O(log n) | - AVL보다 덜 엄격한 균형 유지 - 삽입/삭제 시 회전이 덜 발생하여 삽입/삭제가 잦은 경우 유리 - 검색 성능은 AVL보다 미세하게 느릴 수 있음 |
| 이진 탐색 트리 | 최선: O(log n) 최악: O(n) | 최선: O(log n) 최악: O(n) | - 구현이 간단함 - 데이터 입력 순서에 따라 성능이 극단적으로 저하될 수 있음 |
| 해시 테이블 | 평균: O(1) 최악: O(n) | 평균: O(1) 최악: O(n) | - 키-값 쌍으로 데이터를 저장 - 평균적인 속도는 가장 빠름 - 데이터 정렬 및 범위 검색이 불가능함 |