자료구조
AVL TreeAVL 트리
AVL 트리는 1962년 Adelson-Velsky와 Landis가 고안한 최초의 자기 균형 이진 탐색 트리다. 모든 노드에서 왼쪽·오른쪽 서브트리의 높이 차이(균형 인수)가 최대 1임을 보장해 O(log n) 연산을 보장한다.
균형 인수 (Balance Factor)
회전 유형
AVL vs 레드-블랙 트리
| 항목 | AVL | 레드-블랙 |
|---|---|---|
| 균형 엄격도 | 더 엄격 | 덜 엄격 |
| 검색 | 빠름 | 약간 느림 |
| 삽입/삭제 | 더 많은 회전 | 적은 회전 |
관련 개념
- •이진 트리 — AVL의 기반 구조
- •레드-블랙 트리 — AVL의 대안
- •이진 탐색 — BST 내 탐색
참고문헌
- •Knuth. The Art of Computer Programming, Vol. 3
