AVL 트리 시각화
AVL 트리 삽입·삭제·회전(LL/RR/LR/RL)을 단계별 애니메이션으로 배우는 자가 균형 BST 학습 도구
자료구조★★★
속도
1 / 1노드 수: 0트리 높이: 0
연산 선택
현재 노드회전 중삽입됨삭제됨균형 (BF)불균형 (BF)
AVL 트리가 어떻게 자가 균형을 유지하는지 관찰하세요.
비교
회전
균형 확인
삽입
높이 갱신
값을 입력하고 실행을 눌러 시작하세요.
AVL 트리란?
AVL 트리는 모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1인 자가 균형 이진탐색트리입니다. 1962년 Adelson-Velsky와 Landis가 발명했으며, 삽입·삭제 시 회전 연산으로 균형을 자동 유지하여 항상 O(log n) 성능을 보장합니다.
사용 방법
- 1값을 입력하고 삽입 또는 삭제 연산을 실행하세요
- 2각 노드 옆의 균형 인수(BF)를 관찰하세요 — |BF| > 1이면 불균형
- 3불균형 발생 시 LL/RR/LR/RL 회전 타입을 확인하세요
- 4랜덤 버튼으로 여러 트리를 생성해 회전 패턴을 학습하세요
- 5코드 탭에서 삽입 코드와 회전 코드를 전환하며 비교하세요
학습 팁
- •LL 회전: 왼쪽-왼쪽에 삽입 → 오른쪽으로 한 번 회전
- •RR 회전: 오른쪽-오른쪽에 삽입 → 왼쪽으로 한 번 회전
- •LR 회전: 왼쪽-오른쪽에 삽입 → 이중 회전 (왼쪽→오른쪽)
- •RL 회전: 오른쪽-왼쪽에 삽입 → 이중 회전 (오른쪽→왼쪽)
- •AVL은 검색이 빈번한 경우 Red-Black보다 빠르지만, 삽입/삭제가 빈번하면 회전 오버헤드가 큽니다
자주 묻는 질문
Q. AVL과 Red-Black 트리의 차이?
A. AVL은 높이 차이 ≤ 1로 더 엄격한 균형. Red-Black은 느슨한 균형. AVL은 탐색이 빠르고, Red-Black은 삽입/삭제가 빠릅니다.
Q. 회전의 시간 복잡도는?
A. 단일 회전(LL/RR)은 O(1), 이중 회전(LR/RL)도 O(1)입니다. 삽입 시 최대 2회, 삭제 시 최대 O(log n)회 회전이 발생합니다.
Q. 균형 인수(BF)란?
A. BF = 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이. AVL 조건: -1 ≤ BF ≤ 1. |BF| ≥ 2이면 회전이 필요합니다.