Ch.6 트리 기초
트리 높이와 균형 — AVL 개념
트리가 기울면 성능이 무너진다
BST의 아킬레스건은 편향입니다. 최악의 경우 O(n)으로 퇴화하죠. AVL 트리는 자동 균형으로 이 문제를 해결합니다.
균형을 유지하면서도 삽입/삭제가 빨라야 한다 — 어떻게?
회전(Rotation)이라는 간단한 연산 하나로 항상 O(log n)을 보장합니다.
핵심 개념
균형 이진 트리
모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하인 트리
균형 인수(Balance Factor)
왼쪽 서브트리 높이 - 오른쪽 서브트리 높이
핵심 내용
같은 7개의 데이터. 트리 모양에 따라 성능이 7배 차이납니다
균형 트리 (높이 2) • 탐색: 최대 3번 비교 • 시간: O(log 7) ≈ O(3) 편향 트리 (높이 6) • 탐색: 최대 7번 비교 • 시간: O(7) = O(n)
n = 100만이면? 균형: 20번 비교 vs 편향: 100만 번 비교. 5만 배 차이입니다
AVL 트리의 규칙은 단순합니다. 모든 노드에서 | 왼쪽 높이 - 오른쪽 높이 | ≤ 1
삽입이나 삭제 후 균형 인수가 ±2가 되면 회전을 통해 다시 ±1 이내로 복구합니다
균형이 깨지는 패턴은 4가지. 각각에 맞는 회전이 있습니다
LL (Left-Left) — 왼쪽의 왼쪽에 삽입 → 오른쪽 회전 1회 RR (Right-Right) — 오른쪽의 오른쪽에 삽입 → 왼쪽 회전 1회 LR (Left-Right) — 왼쪽의 오른쪽에 삽입 → 왼쪽 회전 + 오른쪽 회전 RL (Right-Left) — 오른쪽의 왼쪽에 삽입 → 오른쪽 회전 + 왼쪽 회전
# 오른쪽 회전 (LL 케이스)
def rotate_right(z):
y = z.left
T3 = y.right
# 회전 수행
y.right = z
z.left = T3
return y # 새로운 루트
# 왼쪽 회전 (RR 케이스)
def rotate_left(z):
y = z.right
T2 = y.left
# 회전 수행
y.left = z
z.right = T2
return y # 새로운 루트면접에서 AVL 회전 코드를 처음부터 쓸 일은 드뭅니다. 개념과 왜 O(log n)이 보장되는지를 설명할 수 있으면 충분합니다
AVL 외에도 다양한 균형 트리가 있습니다
AVL 트리 • 엄격한 균형 (높이 차 ≤ 1) • 탐색 빠름, 삽입/삭제 시 회전 잦음 Red-Black 트리 • 느슨한 균형 (높이 차 ≤ 2배) • Java TreeMap, C++ std::map에서 사용 B-Tree • 다진 트리, 디스크 접근 최적화 • 데이터베이스 인덱스의 핵심
Python의 내장 dict는 해시테이블, Java의 TreeMap은 Red-Black 트리. 언어마다 기본 자료구조가 다릅니다
면접관이 좋아하는 균형 트리 관련 질문들
자주 나오는 질문 Q: BST의 최악 시간 복잡도는? A: O(n) — 편향 트리일 때 Q: 어떻게 O(log n)을 보장하나? A: AVL/Red-Black 등 자가 균형 트리 사용 Q: 이진 트리가 균형인지 확인하는 코드는? A: 아래 isBalanced 함수!
# LeetCode #110: Balanced Binary Tree
def isBalanced(root):
def check(node):
if not node:
return 0 # 높이 0
left_h = check(node.left)
if left_h == -1:
return -1 # 이미 불균형
right_h = check(node.right)
if right_h == -1:
return -1
if abs(left_h - right_h) > 1:
return -1 # 불균형 발견!
return max(left_h, right_h) + 1
return check(root) != -1
# 시간: O(n), 공간: O(h)-1을 신호로 사용하는 테크닉. 불균형을 발견하면 즉시 -1을 올려보내 조기 종료합니다
면접 마무리 한마디: '균형 트리를 직접 구현하는 것보다 왜 필요한지 설명하는 것이 더 중요합니다'
AVL 트리에서 허용하는 균형 인수의 범위는?
LL(Left-Left) 케이스에서는 어떤 회전을 수행하는가?
Red-Black 트리는 AVL보다 더 엄격하게 균형을 유지한다
핵심 용어
균형 인수
height(left) - height(right), -1/0/1만 허용
회전
균형이 깨지면 회전으로 복구
성능 보장
탐색/삽입/삭제 모두 O(log n)
정리 노트
트리 높이와 균형 — AVL
균형의 필요성
- 편향 BST
- O(n) — 연결 리스트와 동일
- 균형 BST
- O(log n) 보장
AVL 트리
- 균형 인수
- -1, 0, 1만 허용
- 회전
- LL/RR(단일), LR/RL(이중)
- isBalanced
- -1 신호 + O(n) 순회
시각 자료
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작