자료구조Hard#29
이진 탐색 트리(BST)의 특성과 편향 트리 문제를 어떻게 해결하나요?
#자료구조#트리#BST#알고리즘
힌트
AVL 트리, Red-Black 트리 등 자가 균형 트리를 생각해보세요.
정답 및 해설
이진 탐색 트리(BST)의 특성과 편향 트리 문제를 어떻게 해결하나요?
이진 탐색 트리(Binary Search Tree, BST)는 각 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값, 오른쪽 서브트리에는 큰 값이 위치하는 자료구조입니다. 이 특성 덕분에 평균 O(log n)의 탐색, 삽입, 삭제가 가능하지만, 삽입 순서에 따라 편향 트리가 되면 최악 O(n)으로 성능이 저하됩니다. 이를 해결하기 위해 자가 균형 트리(Self-Balancing BST)가 사용됩니다.
이진 탐색 트리 (BST)의 기본 특성
핵심 규칙
모든 노드 N에 대해:
- N의 왼쪽 서브트리의 모든 값 < N의 값
- N의 오른쪽 서브트리의 모든 값 > N의 값
- 왼쪽/오른쪽 서브트리도 각각 BST
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
BST 구현
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, val):
if not self.root:
self.root = Node(val)
else:
self._insert(self.root, val)
def _insert(self, node, val):
if val < node.val:
if node.left is None:
node.left = Node(val)
else:
self._insert(node.left, val)
else:
if node.right is None:
node.right = Node(val)
else:
self._insert(node.right, val)
def search(self, val):
return self._search(self.root, val)
def _search(self, node, val):
if node is None:
return False
if node.val == val:
return True
elif val < node.val:
return self._search(node.left, val) # 왼쪽으로
else:
return self._search(node.right, val) # 오른쪽으로
BST 탐색의 원리
8을 찾을 때 (루트가 8인 트리에서):
값 6 탐색:
root(8) → 6 < 8 → 왼쪽 이동
node(3) → 6 > 3 → 오른쪽 이동
node(6) → 6 == 6 → 찾음! (3번 비교)
이진 탐색처럼 매 단계에서 탐색 범위가 절반으로 줄어듦
중위 순회로 정렬된 출력
BST의 중요한 특성 중 하나는 중위 순회(In-order Traversal) 시 정렬된 순서로 출력됩니다.
def inorder(node):
if node:
inorder(node.left)
print(node.val, end=" ")
inorder(node.right)
# 트리: 8
# / \
# 3 10
# / \ \
# 1 6 14
inorder(root) # 1 3 6 8 10 14 (정렬된 순서!)
BST의 시간 복잡도
| 연산 | 평균 | 최악 |
|---|---|---|
| 탐색 | O(log n) | O(n) |
| 삽입 | O(log n) | O(n) |
| 삭제 | O(log n) | O(n) |
| 최솟값 | O(log n) | O(n) |
| 최댓값 | O(log n) | O(n) |
편향 트리 (Skewed Tree) 문제
편향 트리 발생
정렬된 순서나 역순으로 데이터를 삽입하면 트리가 한쪽으로 치우칩니다.
bst = BST()
for val in [1, 2, 3, 4, 5]: # 정렬된 순서로 삽입
bst.insert(val)
# 결과: 선형 구조 (연결 리스트와 동일)
# 1
# \
# 2
# \
# 3
# \
# 4
# \
# 5
# 탐색 시 O(n) - 완전히 BST의 장점 소멸
높이가 n에 가까워져 모든 연산이 O(n)이 됩니다.
자가 균형 이진 탐색 트리 (Self-Balancing BST)
AVL 트리
균형 인수(Balance Factor) = 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이
모든 노드의 균형 인수가 -1, 0, 1 중 하나여야 합니다. 삽입/삭제 후 균형이 깨지면 회전(Rotation) 으로 복원합니다.
균형 잡힌 AVL 트리:
8 (BF=0)
/ \
3(BF=0) 10(BF=-1)
/ \ \
1(0) 6(0) 14(0)
AVL 회전 종류
LL 회전 (우측 회전):
삽입 전 (불균형): 우측 회전 후:
C (BF=2) B
/ / \
B (BF=1) A C
/
A
RR 회전 (좌측 회전):
삽입 전 (불균형): 좌측 회전 후:
A (BF=-2) B
\ / \
B (BF=-1) A C
\
C
LR 회전 (좌-우 회전):
삽입 전: 좌측 회전: 우측 회전:
C C B
/ / / \
A B A C
\ /
B A
RL 회전 (우-좌 회전):
삽입 전: 우측 회전: 좌측 회전:
A A B
\ \ / \
C B A C
/ \
B C
class AVLNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.height = 1 # 높이 정보 유지
class AVLTree:
def height(self, node):
return node.height if node else 0
def balance_factor(self, node):
return self.height(node.left) - self.height(node.right) if node else 0
def update_height(self, node):
node.height = 1 + max(self.height(node.left), self.height(node.right))
def right_rotate(self, z):
y = z.left
T3 = y.right
y.right = z
z.left = T3
self.update_height(z)
self.update_height(y)
return y # 새 루트 반환
def left_rotate(self, z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
self.update_height(z)
self.update_height(y)
return y
def insert(self, node, val):
# 일반 BST 삽입
if not node:
return AVLNode(val)
if val < node.val:
node.left = self.insert(node.left, val)
elif val > node.val:
node.right = self.insert(node.right, val)
else:
return node # 중복 불허
# 높이 업데이트
self.update_height(node)
# 균형 인수 계산
bf = self.balance_factor(node)
# LL 케이스
if bf > 1 and val < node.left.val:
return self.right_rotate(node)
# RR 케이스
if bf < -1 and val > node.right.val:
return self.left_rotate(node)
# LR 케이스
if bf > 1 and val > node.left.val:
node.left = self.left_rotate(node.left)
return self.right_rotate(node)
# RL 케이스
if bf < -1 and val < node.right.val:
node.right = self.right_rotate(node.right)
return self.left_rotate(node)
return node
Red-Black 트리
각 노드에 빨강(Red) 또는 검정(Black) 색을 부여하여 균형을 유지합니다.
Red-Black 트리의 규칙
- 모든 노드는 빨강 또는 검정
- 루트는 항상 검정
- 리프(NIL) 노드는 검정
- 빨간 노드의 자식은 반드시 검정 (빨강 노드 연속 불가)
- 어떤 노드에서 리프까지의 모든 경로에는 같은 수의 검정 노드 존재
7(B)
/ \
3(R) 18(R)
/ \ / \
2(B) 4(B) 11(B) 19(B)
\
14(R)
Red-Black 트리 vs AVL 트리
Red-Black 트리: 높이 ≤ 2 × log₂(n+1)
AVL 트리: 높이 ≤ 1.44 × log₂(n)
AVL 트리가 더 엄격하게 균형 유지 → 탐색은 AVL이 빠름
Red-Black 트리는 삽입/삭제 재균형 비용이 낮음 → 쓰기 빈번 시 유리
실제 언어에서의 활용
// Java TreeMap - Red-Black 트리 기반
import java.util.TreeMap;
TreeMap<String, Integer> map = new TreeMap<>();
map.put("banana", 2);
map.put("apple", 1);
map.put("cherry", 3);
// 항상 정렬된 순서로 반환
for (String key : map.keySet()) {
System.out.println(key); // apple, banana, cherry (정렬됨)
}
map.firstKey(); // "apple" - O(log n)
map.lastKey(); // "cherry" - O(log n)
map.floorKey("blueberry"); // "banana" - O(log n)
// C++ std::map - Red-Black 트리 기반
#include <map>
std::map<std::string, int> m;
m["banana"] = 2;
m["apple"] = 1;
// 자동으로 정렬 유지, 모든 연산 O(log n) 보장
자가 균형 트리 비교
| 항목 | AVL 트리 | Red-Black 트리 |
|---|---|---|
| 균형 기준 | 좌우 높이 차 ≤ 1 | 색상 규칙 (엄격도 낮음) |
| 높이 | 더 낮음 (엄격한 균형) | 약간 높음 |
| 탐색 성능 | 약간 빠름 | 약간 느림 |
| 삽입/삭제 오버헤드 | 높음 (더 많은 회전) | 낮음 |
| 구현 복잡도 | 중간 | 높음 |
| 메모리 | 높이 정보 저장 | 색상 비트 저장 |
| 주요 사용처 | 읽기 빈번한 경우 | Java TreeMap, C++ map |
| 시간 복잡도 | O(log n) 보장 | O(log n) 보장 |