[자료구조] RBTree

1. 레드 - 블랙 트리 개요

1.1 기원과 정의

레드‑블랙 트리는 Leonidas J. Guibas와 Robert Sedgewick이 1978년에 제안한 self‑balancing 이진 탐색 트리 자료구조입니다.
각 노드는 추가로 한 비트(“색상(color)”) 정보를 가지며, 이 색상은 red 또는 black 중 하나입니다.
이 색상 비트는 삽입/삭제 시 균형을 유지하기 위한 제약 조건을 정의하는 데 사용됩니다.
이론적으로 RBT는 삽입·삭제·탐색 모든 연산에서 최악 O(log n)의 시간 복잡도를 보장합니다.
또한 2‑3‑4 트리(B‑트리의 특수형)와 구조적으로 대응 관계가 있어, 2‑3‑4 트리의 각 노드를 하나의 black 노드와 그에 연결된 red 자식 그룹으로 매핑할 수 있습니다.

---

1.2 주요 제약조건(Invariant)

RBT가 유효 트리로 간주되기 위해 반드시 만족해야 할 다섯 가지 속성은 다음과 같습니다.

 

• 모든 노드는 red 또는 black.
• 모든 리프(NULL) 노드는 black.
• red 노드는 red 자식을 가질 수 없음.
• 루트에서 모든 리프까지 경로상의 black 노드 수(black-height)는 동일.
• (선택) 루트는 black.

이 속성들로 인해, 루트에서 가장 먼 리프와 가장 가까운 리프 간 높이 차가 최대 2배로 제한되며, 트리 높이가 O(log n)을 유지합니다.

---

 

2. 노드 구조 및 성능 보장

2.1 노드 구조 예시 (C언어)

struct rb_node {
    enum { red, black } color;     // 색상 정보 (1비트)
    KeyType key;                    // 키 값
    struct rb_node *left, *right;   // 자식 포인터
    struct rb_node *parent;         // 부모 포인터
};

추가되는 색상 비트는 메모리 오버헤드가 거의 1비트 수준으로 매우 작습니다.

---

2.2 높이 및 시간 복잡도

RBT는 n개의 내부 노드에 대해 트리 높이가 최대 2 log₂(n + 1) 로 제한됨이 증명되어 있습니다.

• 삽입/삭제 후에도 회전 및 색상 변경 과정을 통해 O(log n) 단계 이내에 균형을 복구합니다.
• 따라서 탐색·삽입·삭제 연산 모두 최악 O(log n)을 보장합니다.

---

3. 주요 응용

• Linux 커널: Completely Fair Scheduler(CFS)와 epoll의 이벤트 관리에 활용
• Java 8 이상: HashMap에서 충돌이 많아지면 링크드 리스트 대신 RBT로 버킷을 전환하여 탐색을 O(m)→O(log m)으로 개선
• C++ STL: std::map/std::set의 내부 구현.

이 외에도 데이터베이스 인덱스, 윈도우 레지스트리 등 다양한 시스템과 라이브러리에서 활용됩니다.

---

4. BST, AVL ,RBT 비교

특성	BST	AVL 트리	레드-블랙 트리(RBT)
정의	왼쪽 서브트리 키 < 노드 키 < 오른쪽 서브트리 키	모든 노드의 왼쪽, 오른쪽 서브 트리 높이 차 <= 1	각 노드에 red/black 색상 추가하여 느슨하게 균형 유지
최악 높이(h)	O(n) – 정렬된 순서 삽입 시 퇴화 가능	≤ 1.44 log₂(n + 2)	≤ 2 log₂(n + 1)
검색 성능	평균 O(log n), 최악 O(n)	O(log n), 경로 짧음	O(log n)
삽입, 삭제, 회전 수	없음 (회전 연산 미사용)	최대 2회 회전 (엄격 균형 유지)	최대 2회 회전, AVL보다 회전 횟수 적음
메모리 오버헤드	없음	각 노드에 균형 인수(정수) 저장 (약 2 비트)	색상 비트 1개만 추가 (거의 1 비트)
구현 난이도	쉬움 (기본 BST 구현)	중간 (4가지 회전 케이스 처리 필요)	높음 (색상 판단·회전·재색칠 로직 복잡)

 

• BST는 구현이 간단하지만, 균형 보장이 없어 최악 성능(O(n))에 취약합니다.
• AVL 트리는 검색 경로가 가장 짧아 읽기 성능이 우수하나, 업데이트 시 회전이 자주 발생하고 메모리 오버헤드가 있습니다.
• RBT는 삽입·삭제 시 회전이 AVL보다 적고 메모리 오버헤드가 극소인 반면, 균형이 느슨해 검색 경로가 다소 길어지고 구현이 복잡합니다.
• 사용 패턴(읽기 vs 쓰기 비율), 메모리 제약, 구현 난이도를 고려하여 적절한 자료구조를 선택하세요