AVL 트리 (AVL Tree)

AVL 트리 (AVL Tree)

모든 노드의 왼쪽과 오른쪽 서브트리 높이 차이가 최대 1인 자가 균형(self-balancing) 이진 탐색 트리로, 삽입·삭제 시 회전 연산을 통해 균형을 자동으로 유지

목적: 균형 보장, 최악 O(log n), 예측 가능한 성능, 빠른 검색

특징: 균형 인수(Balance Factor), 자동 균형, 회전 연산, 엄격한 균형

균형 인수(BF): BF(node) = height(left) - height(right), |BF| ≤ 1 유지

회전(Rotation)

• •LL(Left-Left): 오른쪽 회전
• •RR(Right-Right): 왼쪽 회전
• •LR(Left-Right): 왼쪽 회전 후 오른쪽 회전
• •RL(Right-Left): 오른쪽 회전 후 왼쪽 회전

동작: 삽입·삭제 → 조상 노드 BF 갱신 → |BF| > 1이면 회전 → 균형 복구

시간 복잡도: 검색·삽입·삭제 모두 O(log n) 보장 (최악도)

공간 복잡도: O(n) + BF 저장

장점: 균형 보장, 최악 O(log n), 예측 가능, 빠른 검색

단점: 빈번한 회전(삽입·삭제 오버헤드), 구현 복잡도, 추가 메모리(BF)

적용사례: 읽기 많은 데이터베이스 인덱스, 메모리 관리, 심볼 테이블

비교: AVL(엄격균형/빠른검색/느린삽입) vs Red-Black(느슨균형/빠른삽입) vs BST(불균형가능)

연관: BST, Red-Black 트리, 균형 트리, 회전, 균형 인수