[자료구조] AVL 트리란?

AVL 트리란 한 쪽으로 값이 치우치는 이진 균형트리의 한계점을 보완하기 위해 만들어진 균형 잡힌 이진트리.

AVL은 항상 좌/우로 데이터를 균형잡힌 상태로 유지하기 위해서 추가연산을 진행.

 

AVL 트리는 자가 균형 이진 탐색 트리(self-balancing binary search tree)의 한 종류입니다. 

모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1을 유지하도록 자동으로 균형을 잡습니다.

**핵심 개념**

1. 균형 인수(Balance Factor)
- BF = 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이
- 모든 노드의 BF는 -1, 0, 1 중 하나여야 함

2. 회전 연산
```python
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1

def right_rotate(y):
    x = y.left
    T2 = x.right
    
    x.right = y
    y.left = T2
    
    y.height = max(get_height(y.left), get_height(y.right)) + 1
    x.height = max(get_height(x.left), get_height(x.right)) + 1
    
    return x
```

3. 재균형 케이스:
- LL(Left-Left): 오른쪽 회전
- RR(Right-Right): 왼쪽 회전
- LR(Left-Right): 왼쪽-오른쪽 회전
- RL(Right-Left): 오른쪽-왼쪽 회전

**주요 연산**

1. 삽입
- 일반 BST처럼 삽입
- 조상 노드들의 균형 검사
- 필요시 회전으로 재균형

2. 삭제
- 일반 BST처럼 삭제
- 삭제 경로의 조상 노드들 균형 검사
- 필요시 회전으로 재균형

**특징**
- 탐색, 삽입, 삭제 모두 O(log n) 시간 복잡도
- 항상 균형을 유지하여 최악의 경우도 O(log n)
- Red-Black 트리보다 더 엄격한 균형 조건
- 조회가 빈번한 경우에 효율적

**사용 사례**
- 데이터베이스 인덱싱
- 인메모리 캐시
- 우선순위 큐 구현
- 파일 시스템 구현

AVL 트리는 빈번한 조회 작업이 필요하고 삽입/삭제가 상대적으로 적은 경우에 특히 유용합니다.