[자료구조] 레드블랙 트리

레드블랙 트리는 모든 노드를 빨간색 또는 검은색으로 색칠합니다.

그리고 연결된 노드들은 색이 중복되지 않도록 관리됩니다.

 

레드블랙 트리는 자가 균형 이진 탐색 트리의 한 종류로, 각 노드에 색상(빨간색 또는 검은색)을 부여하여 균형을 유지합니다.

**기본 규칙**

1. 모든 노드는 빨간색 또는 검은색
2. 루트는 항상 검은색
3. 모든 리프(NIL)는 검은색
4. 빨간 노드의 자식은 모두 검은색
5. 임의의 노드에서 그 노드의 자손인 리프까지 가는 경로들은 모두 같은 수의 검은 노드를 포함

**구현 예시**

```python
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.parent = None
        self.color = "RED"  # 새 노드는 항상 빨간색으로 삽입
        
class RedBlackTree:
    def __init__(self):
        self.nil = Node(None)
        self.nil.color = "BLACK"
        self.root = self.nil
```

**주요 연산**

1. 삽입
- BST처럼 노드 삽입
- 새 노드를 빨간색으로 설정
- 규칙이 위반되면 재조정:
  - 색상 변경
  - 회전 연산

2. 삭제
- BST처럼 노드 삭제
- 규칙이 위반되면 재조정
- 이중 흑색 노드 처리

**재조정 연산**

1. 색상 변경

```python
def color_flip(self, node):
    node.color = "RED"
    node.left.color = "BLACK"
    node.right.color = "BLACK"
```

2. 회전
- 왼쪽 회전
- 오른쪽 회전

**특징과 장점**
- 삽입, 삭제, 검색 모두 O(log n) 시간 복잡도
- AVL 트리보다 덜 엄격한 균형 조건
- 삽입/삭제 시 재조정 횟수가 적음
- 실제 구현에서 널리 사용됨

**사용 사례**
- Java의 TreeMap, TreeSet
- Linux 커널의 완전 공정 스케줄러
- 데이터베이스 인덱싱
- C++ STL의 map, set

**AVL 트리와의 비교**
- AVL: 더 엄격한 균형, 빠른 검색
- 레드블랙: 더 빠른 삽입/삭제
- 레드블랙은 실제 구현에서 더 많이 사용됨

레드블랙 트리는 실제 시스템에서 많이 사용되는 자료구조이며, 특히 삽입과 삭제가 빈번한 경우에 효율적입니다.