1. 운영체제에서의 활용
Linux 커널의 Completely Fair Scheduler (CFS)
- 프로세스 스케줄링에 레드-블랙 트리 사용
- 실행 대기 중인 프로세스들을 virtual runtime 기준으로 정렬
- O(log n) 시간 복잡도로 가장 적은 runtime을 가진 프로세스 선택 가능
- 실제 구현 코드:
struct rb_root { struct rb_node *rb_node; }; struct rb_node { unsigned long __rb_parent_color; struct rb_node *rb_right; struct rb_node *rb_left; } __attribute__((aligned(sizeof(long))));
메모리 관리
- 가상 메모리 영역(VMAs) 관리
- 메모리 할당자에서 사용 가능한 메모리 블록 추적
- 페이지 캐시 구현
2. 데이터베이스 시스템
MySQL InnoDB 스토리지 엔진
- B-tree의 변형된 형태로 레드-블랙 트리 특성 활용
- 인덱스 구현에 사용
- 트랜잭션 격리 수준 관리
PostgreSQL
- GiST (Generalized Search Tree) 인덱스 구현
- 동시성 제어 메커니즘
3. 프로그래밍 언어 표준 라이브러리
Java Collections Framework
TreeMap<Integer, String> map = new TreeMap<>();
TreeSet set = new TreeSet<>();
C++ STL
std::map<int, string> ordered_map;
std::set ordered_set;
Python의 정렬된 컨테이너
from sortedcontainers import SortedDict, SortedSet
sorted_dict = SortedDict({1: 'one', 2: 'two'})
sorted_set = SortedSet([1, 2, 3])
AVL 트리와 레드-블랙 트리 비교
AVL 트리란?
AVL 트리는 1962년 Adelson-Velsky와 Landis가 제안한 최초의 자가 균형 이진 탐색 트리입니다.
AVL 트리의 특성
- 모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1
- 더 엄격한 균형 조건으로 인해 더 빈번한 재조정 필요
- 완벽한 균형으로 인해 검색이 더 빠를 수 있음
Python으로 구현한 AVL 트리 노드
class AVLNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1 # 새 노드는 높이 1로 초기화
class AVLTree:
def get_height(self, node):
if not node:
return 0
return node.height
def get_balance(self, node):
if not node:
return 0
return self.get_height(node.left) - self.get_height(node.right)
def update_height(self, node):
if not node:
return
node.height = max(self.get_height(node.left),
self.get_height(node.right)) + 1
레드-블랙 트리 vs AVL 트리 비교
| 특성 | 레드-블랙 트리 | AVL 트리 |
|---|---|---|
| 균형 조건 | 느슨함 (검은 노드 수 동일) | 엄격함 (높이 차이 ≤ 1) |
| 높이 | 최대 2log(n+1) | 최대 1.44log(n+2) |
| 삽입 시 회전 | 최대 2회 | 최대 2회 |
| 삭제 시 회전 | 최대 3회 | 최대 log n회 |
| 메모리 | 노드당 1비트 추가(색상) | 노드당 정수 추가(높이) |
| 적합한 용도 | 삽입/삭제가 빈번한 경우 | 검색이 빈번한 경우 |
언제 어떤 트리를 사용해야 할까?
레드-블랙 트리 선택 시나리오:
- 데이터의 삽입과 삭제가 빈번한 경우
- 메모리 사용량이 중요한 경우
- 일반적인 용도의 정렬된 데이터 구조가 필요한 경우
AVL 트리 선택 시나리오:
- 검색 작업이 대부분인 경우
- 데이터베이스 인덱싱과 같이 검색 성능이 매우 중요한 경우
- 삽입/삭제가 드문 경우
더보기
레드-블랙 트리로 해결하는 알고리즘 문제 모음
1. [백준 7662] 이중 우선순위 큐
문제 개요
- 난이도: Gold IV
- 링크: https://www.acmicpc.net/problem/7662
- 핵심 개념: 이중 우선순위 큐, 정렬된 자료구조
문제 설명
- 이중 우선순위 큐는 최댓값과 최솟값을 모두 효율적으로 삭제할 수 있어야 함
- 연산:
- I n : 정수 n을 큐에 삽입
- D 1 : 최댓값 삭제
- D -1 : 최솟값 삭제
레드-블랙 트리를 이용한 해결 방법
from sortedcontainers import SortedDict
def solve():
T = int(input())
for _ in range(T):
k = int(input())
counter = SortedDict()
for _ in range(k):
cmd, n = input().split()
n = int(n)
if cmd == 'I':
counter[n] = counter.get(n, 0) + 1
else:
if not counter:
continue
key = counter.peekitem(-1 if n == 1 else 0)[0]
counter[key] -= 1
if counter[key] == 0:
del counter[key]
if counter:
print(counter.peekitem(-1)[0], counter.peekitem(0)[0])
else:
print("EMPTY")
2. [백준 1168] 요세푸스 문제 2
문제 개요
- 난이도: Platinum IV
- 링크: https://www.acmicpc.net/problem/1168
- 핵심 개념: 순서 통계량 트리 (Order Statistics Tree)
문제 설명
- N명의 사람이 원을 이루며 앉아있음
- K번째 사람을 순서대로 제거
- 제거되는 순서를 구해야 함
레드-블랙 트리를 이용한 해결 방법
from sortedcontainers import SortedList
def solve_josephus():
N, K = map(int, input().split())
sl = SortedList(range(1, N + 1))
result = []
index = K - 1
while sl:
index %= len(sl)
result.append(sl.pop(index))
if sl:
index += K - 1
print("<" + ", ".join(map(str, result)) + ">")
3. [백준 21944] 문제 추천 시스템 Version 2
문제 개요
- 난이도: Gold II
- 링크: https://www.acmicpc.net/problem/21944
- 핵심 개념: 다중 키 정렬, 범위 쿼리
문제 설명
- 알고리즘 문제들을 난이도와 알고리즘 분류별로 관리
- 다양한 추천 쿼리 처리 필요:
- 특정 알고리즘 분류에서 가장 어려운/쉬운 문제 찾기
- 특정 난이도 범위 내의 문제 찾기
- 전체 문제 중 가장 어려운/쉬운 문제 찾기
레드-블랙 트리를 이용한 해결 방법
from sortedcontainers import SortedSet
class ProblemRecommender:
def __init__(self):
self.problems = {} # 문제 정보 저장
self.by_level = SortedSet() # (난이도, 번호) 기준 정렬
self.by_algo = {} # 알고리즘 분류별로 (난이도, 번호) 정렬
def add_problem(self, P, L, G):
self.problems[P] = (L, G)
self.by_level.add((L, P))
if G not in self.by_algo:
self.by_algo[G] = SortedSet()
self.by_algo[G].add((L, P))
def remove_problem(self, P):
if P in self.problems:
L, G = self.problems[P]
self.by_level.remove((L, P))
self.by_algo[G].remove((L, P))
del self.problems[P]
def recommend(self, G, x):
if G in self.by_algo and self.by_algo[G]:
return self.by_algo[G][-1 if x == 1 else 0][1]
return -1
def recommend2(self, x):
if self.by_level:
return self.by_level[-1 if x == 1 else 0][1]
return -1
def recommend3(self, x, L):
if x == 1:
pos = self.by_level.bisect_left((L, 0))
if pos < len(self.by_level):
return self.by_level[pos][1]
else:
pos = self.by_level.bisect_left((L, 0)) - 1
if pos >= 0:
return self.by_level[pos][1]
return -1
4. [백준 1539] 이진 검색 트리
문제 개요
- 난이도: Platinum V
- 링크: https://www.acmicpc.net/problem/1539
- 핵심 개념: 이진 검색 트리의 높이 계산
문제 설명
- N개의 서로 다른 정수를 차례대로 이진 검색 트리에 삽입
- 완성된 이진 검색 트리의 모든 노드의 높이의 합을 구해야 함
레드-블랙 트리를 이용한 해결 방법
from sortedcontainers import SortedDict
def solve_bst_height():
N = int(input())
heights = SortedDict() # 키: 값, 값: 높이
total_height = 0
for _ in range(N):
num = int(input())
# 새 노드의 높이 계산
height = 1
# 왼쪽에서 가장 큰 값과 오른쪽에서 가장 작은 값 찾기
left = heights.bisect_left(num)
if left > 0:
height = max(height, heights.peekitem(left-1)[1] + 1)
if left < len(heights):
height = max(height, heights.peekitem(left)[1] + 1)
heights[num] = height
total_height += height
print(total_height)
실전 팁
1. Python에서의 레드-블랙 트리 구현체
sortedcontainers라이브러리 사용SortedDict: 정렬된 딕셔너리SortedSet: 정렬된 집합SortedList: 정렬된 리스트
2. 주요 활용 패턴
- 정렬된 상태 유지가 필요한 경우
from sortedcontainers import SortedSet numbers = SortedSet() numbers.add(5) # O(log n) numbers.remove(5) # O(log n)- 이중 우선순위 큐 구현
from sortedcontainers import SortedDict counter = SortedDict() counter[5] = counter.get(5, 0) + 1 # 삽입 min_val = counter.peekitem(0)[0] # 최솟값 max_val = counter.peekitem(-1)[0] # 최댓값- 범위 쿼리 처리
from sortedcontainers import SortedSet numbers = SortedSet([1, 3, 5, 7, 9]) # 4보다 큰 첫 번째 수 찾기 pos = numbers.bisect_left(4) if pos < len(numbers): next_num = numbers[pos]
3. 시간 복잡도
- 삽입: O(log n)
- 삭제: O(log n)
- 검색: O(log n)
- 최대/최소값 접근: O(1)
- 범위 쿼리: O(log n)
4. 주의사항
- 입력 크기가 큰 경우 PyPy3로 제출
- 삽입/삭제가 빈번한 경우
list대신SortedList사용 - 중복 원소 처리 시
SortedDict로 카운팅 - 메모리 제한이 빡빡한 경우 직접 구현 고려
