자료구조 정리 - AVL 트리와 Red-Black 트리

AVL 트리란?

핵심: 자동으로 균형 맞춰주는 BST

 

균형 (Balance)이란?

 

 

균형 잡힌 트리:
      5
     / \
    3   8
   / \   \
  2   4   9

높이 차이: 왼쪽(2) - 오른쪽(2) = 0

 

 

불균형 트리:
      5
     / \
    3   8
   /     \
  2       9
 /
1

높이 차이: 왼쪽(3) - 오른쪽(2) = 1 (괜찮음)

 

 

심각한 불균형:
1
 \
  2
   \
    3
     \
      4

높이 차이: 왼쪽(0) - 오른쪽(4) = -4 (문제!)

 

AVL의 균형 규칙

모든 노드에서:

• |왼쪽 높이 - 오른쪽 높이| ≤ 1

이 숫자를 **Balance Factor (BF)**라고 함

 

 

BF = 왼쪽 높이 - 오른쪽 높이

BF = -1, 0, 1 → OK
BF = -2 이상, 2 이상 → 불균형! 회전 필요!

 

예시

균형 잡힌 경우:

 

 

      5 (BF=0)
     / \
    3   8
   / \   \
  2   4   9

노드 5: 왼쪽 높이(2) - 오른쪽 높이(2) = 0 ✓
노드 3: 왼쪽 높이(1) - 오른쪽 높이(1) = 0 ✓
노드 8: 왼쪽 높이(0) - 오른쪽 높이(1) = -1 ✓

 

불균형 발생:

 

 

1, 2, 3을 순서대로 삽입:

1 삽입
1 (BF=0)

2 삽입
1 (BF=-1)
 \
  2 (BF=0)

3 삽입
1 (BF=-2) ← 불균형!
 \
  2 (BF=-1)
   \
    3 (BF=0)

BF = -2 발생! → 회전 필요!

 

회전 (Rotation)

4가지 경우:

1. LL (Left-Left) - 우회전

 

 

불균형:
    3 (BF=2)
   /
  2 (BF=1)
 /
1

우회전:
  2
 / \
1   3

균형 잡힘!

언제?

• 왼쪽-왼쪽으로 치우침
• BF = 2, 왼쪽 자식 BF = 1

 

2. RR (Right-Right) - 좌회전

 

 

불균형:
1 (BF=-2)
 \
  2 (BF=-1)
   \
    3

좌회전:
  2
 / \
1   3

균형 잡힘!

언제?

• 오른쪽-오른쪽으로 치우침
• BF = -2, 오른쪽 자식 BF = -1

 

3. LR (Left-Right) - 좌회전 후 우회전

 

 

불균형:
    3 (BF=2)
   /
  1 (BF=-1)
   \
    2

1단계: 1 기준 좌회전
    3
   /
  2
 /
1

2단계: 3 기준 우회전
  2
 / \
1   3

균형 잡힘!

언제?

• 왼쪽-오른쪽으로 꺾임
• BF = 2, 왼쪽 자식 BF = -1

 

4. RL (Right-Left) - 우회전 후 좌회전

 

 

불균형:
1 (BF=-2)
 \
  3 (BF=1)
 /
2

1단계: 3 기준 우회전
1
 \
  2
   \
    3

2단계: 1 기준 좌회전
  2
 / \
1   3

균형 잡힘!

언제?

• 오른쪽-왼쪽으로 꺾임
• BF = -2, 오른쪽 자식 BF = 1

 

회전 정리

패턴BF자식 BF회전

LL	2	1	우회전
RR	-2	-1	좌회전
LR	2	-1	좌→우
RL	-2	1	우→좌

 

AVL 삽입 과정

 

 

1, 2, 3을 순서대로 삽입:

1. 1 삽입
   1

2. 2 삽입 (BST 규칙대로)
   1
    \
     2

3. 3 삽입 (BST 규칙대로)
   1 (BF=-2) ← 불균형 발견!
    \
     2 (BF=-1)
      \
       3

4. RR 패턴 → 좌회전
     2
    / \
   1   3

균형 잡힘!

 

AVL의 장점

항상 균형 유지:

• 최악의 경우도 O(log n) 보장
• 편향 트리 방지

단점:

• 삽입/삭제 시 회전 필요 (복잡함)
• 구현 어려움

 

시간복잡도

연산시간복잡도

탐색	O(log n)
삽입	O(log n)
삭제	O(log n)

항상 보장!

 

정리

AVL 트리:

• BST + 자동 균형
• BF = 왼쪽 높이 - 오른쪽 높이
• |BF| ≤ 1 유지
• 불균형 시 회전으로 해결
• 4가지 회전: LL, RR, LR, RL

왜 어려운가:

• 회전 알고리즘 구현이 복잡
• BF 계산과 갱신
• 여러 경우의 수

Red-Black 트리란?

핵심: AVL보다 덜 엄격한 균형 트리

 

AVL vs Red-Black

AVL:

• 완벽한 균형 (|BF| ≤ 1)
• 탐색 빠름
• 삽입/삭제 시 회전 많음

Red-Black:

• 느슨한 균형
• 탐색 약간 느림 (그래도 O(log n))
• 삽입/삭제 시 회전 적음

실무에서는 Red-Black이 더 많이 쓰임!

• Java의 TreeMap
• C++의 map
• Linux 커널

 

Red-Black 규칙 (5가지)

1. 모든 노드는 빨강 or 검정

 

 

    10(B)
   /    \
 5(R)   15(B)

 

2. 루트는 항상 검정

 

 

    10(B)  ← 루트는 검정
   /    \
 5(R)   15(R)

 

3. 모든 리프(NIL)는 검정

 

 

    10(B)
   /    \
 5(R)   15(R)
 / \    / \
NIL NIL NIL NIL  ← 모두 검정

NIL = NULL = 빈 노드

 

4. 빨강 노드의 자식은 모두 검정

즉, 빨강이 연속으로 나올 수 없음!

 

 

올바른 예:
    10(B)
   /    \
 5(R)   15(R)
 / \    / \
3(B) 7(B) 12(B) 20(B)

잘못된 예:
    10(B)
   /    \
 5(R)   15(B)
 /
3(R)  ← 빨강-빨강 연속! 규칙 위반!

 

5. 모든 경로의 검정 노드 개수 동일

루트에서 리프까지 가는 모든 경로에 검정 노드가 같은 개수

 

 

    10(B)          경로별 검정 노드:
   /    \
 5(R)   15(R)      10→5→NIL: 검정 2개 (10, NIL)
 / \    / \        10→15→NIL: 검정 2개 (10, NIL)
NIL NIL NIL NIL    

모두 2개 → OK!

이걸 Black Height라고 함

 

왜 이 규칙들이 균형을 만드나?

규칙 4 + 5의 효과:

 

 

최단 경로: 검정-검정-검정 (검정만)
최장 경로: 검정-빨강-검정-빨강-검정 (검정-빨강 교대)

Black Height = 3이면:
- 최단 경로 길이: 3
- 최장 경로 길이: 5 (검정3 + 빨강2)

최장 / 최단 = 5 / 3 ≈ 1.67배

즉, 한쪽이 다른 쪽의 2배 이상 길 수 없음! → 어느 정도 균형 유지 → O(log n) 보장

 

삽입 과정

기본 전략:

1. BST처럼 삽입
2. 새 노드는 빨강으로 삽입
3. 규칙 위반 체크
4. 위반 시 수정 (Recoloring or Rotation)

 

왜 빨강으로 삽입?

 

 

검정으로 삽입하면:
→ Black Height 변경
→ 모든 경로 재계산 필요
→ 복잡!

빨강으로 삽입하면:
→ Black Height 유지
→ 규칙 4만 체크 (빨강-빨강 연속)
→ 간단!

 

 

AVL vs Red-Black 정리

 

특징	AVL	Red-Black
균형	엄격 (완벽)	느슨
높이	더 낮음	약간 높음
탐색	약간 빠름	약간 느림
삽입/삭제	회전 많음	회전 적음
구현	복잡	더 복잡
실무 사용	적음	많음