레드 블랙 트리 핸드북

핵심 요약 레드 블랙 트리는 삽입·삭제 시에도 높이 균형을 $O(\log n)$로 유지하여 검색, 삽입, 삭제 연산을 모두 최악의 경우 $O(\log n)$에 보장하는 자가 균형 이진 탐색 트리이다. 색 속성을 이용한 단순한 규칙으로 구현이 용이하면서도 회전(rotation)과 색 재배치(recoloring)를 통해 효율적으로 균형을 유지한다.

1. 개요

레드 블랙 트리는 각 노드가 추가로 빨강(Red) 또는 검정(Black) 색을 가지는 자가 균형 이진 탐색 트리이다. 이진 탐색 트리의 최악의 경우 $O(n)$ 높이를 방지하여, 모든 기본 연산을 $O(\log n)$에 수행할 수 있다¹.

2. 주요 속성

1. 색 속성: 각 노드는 빨강 또는 검정이다.
2. 루트 속성: 루트 노드는 항상 검정이다.
3. 레드 속성: 빨강 노드는 자식이 빨강일 수 없다(붉은 노드 연속 금지).
4. 깊이 속성: 모든 루트→NIL(리프) 경로에 존재하는 검정 노드 개수(black-height)가 같다.
5. NIL 속성: 트리의 리프 역할을 하는 NIL 노드들은 모두 검정이다.

이들 속성으로 인해 루트에서 가장 먼 리프까지의 경로 길이가 가장 짧은 경로의 최대 2배를 넘지 않으며, 높이가 $O(\log n)$임이 보장된다².

3. 구조 및 노드 정의

struct RBNode {
    int key;
    enum { RED, BLACK } color;
    struct RBNode *left, *right, *parent;
};
// NIL 노드(리프)는 color=BLACK, left=right=parent=NULL

4. 회전(Rotation)

균형을 맞추기 위해 수행되는 기본 연산으로, 서브트리 구조만 변경하고 이진 탐색 트리 속성은 유지한다.

4.1 왼쪽 회전

노드 $x$를 기준으로 오른쪽 자식 $y$가 올려오며, $y$의 왼쪽 서브트리를 $x$의 오른쪽에 부착한다¹.

4.2 오른쪽 회전

왼쪽 회전의 거울 연산으로, 노드 $y$를 기준으로 왼쪽 자식 $x$를 올려온다.

5. 삽입 연산

1. BST 삽입: 새 노드를 빨강으로 삽입.
2. 속성 복구: 부모·삼촌의 색, 회전 등을 통해 위 5가지 속성 위반을 수정한다.
   • Case 1: 삼촌이 빨강 → 부모·삼촌을 검정, 조부모를 빨강으로 재색칠 후 조부모로 이동
   • Case 2: 삼촌이 검정 + 삽입 노드가 삼촌 반대쪽 자식 → 회전 후 Case 3로 전환
   • Case 3: 삼촌이 검정 + 삽입 노드가 같은 쪽 자식 → 조부모 회전 및 부모·조부모 색 교환
3. 최종적으로 루트는 검정으로 설정¹.

6. 삭제 연산

1. BST 삭제: 표준 이진 탐색 트리 삭제 수행.
2. 더블 블랙 해결: 삭제로 인해 블랙 높이 차이가 발생한 경우, 다음과 같이 수정한다:
   • Case 1: 형제가 빨강 → 회전 및 색 교환
   • Case 2: 형제가 검정 + 형제 자식 둘 다 검정 → 형제를 빨강으로, 문제 노드를 부모로 끌어올림
   • Case 3: 형제가 검정 + 형제의 적어도 한 자식이 빨강 → 적절한 회전 및 색 교환으로 더블 블랙 해소
3. 루트 노드 색은 검정으로 유지¹.

7. 시간·공간 복잡도

연산	평균 / 최악
검색(Search)	$O(\log n)$2
삽입(Insert)	$O(\log n)$2
삭제(Delete)	$O(\log n)$2
공간(Space)	$O(n)$3

8. AVL 트리와 비교

특징	레드 블랙 트리	AVL 트리
균형 정도	조금 덜 균형, 높이 최대 $2{\log }_2(n+1)$2	더 엄격히 균형, 높이 $\approx 1.44{\log }_2(n)$
회전 횟수	삽입·삭제 시 회전 적음 → 동적 변동 많은 경우 유리	검색 위주, 회전 많음 → 삽입·삭제 적고 검색 많을 때 유리
구현 복잡도	중간	높음

9. 주요 활용 사례

• 표준 라이브러리: C++ STL map/set, Java TreeMap/TreeSet 등 내부 구현⁴.
• 운영체제: Linux 커널 스케줄링, 메모리 매니저⁵.
• 데이터베이스 인덱싱: MySQL, PostgreSQL 등 B-tree 대안으로 사용 가능⁵⁴.
• 네트워크 라우팅, 컴파일러 심볼 테이블, 그래프 알고리즘 등 다양한 분야에서 활용된다⁵⁶.

10. 장단점

장점

• 삽입·삭제 시 회전 횟수가 비교적 적어 동적 변화에 강함⁷.
• 구현이 AVL보다 간단하고, 균형 보장이 충분히 높음.
• 색 정보 1비트만 추가해 메모리 부담이 거의 없음².

단점

• AVL 트리보다 검색 시 최악 높이가 다소 큼 → 검색 성능이 약간 느림.
• 삽입·삭제 로직이 복잡하여 이해 난이도가 중간 수준.

11. 결론 및 추천

레드 블랙 트리는 삽입·삭제가 빈번하면서도 검색 성능이 중요한 애플리케이션에 적합하다. 운영체제, 데이터베이스, 표준 라이브러리처럼 동적 변화와 안정적 성능 보장이 필요한 시스템에서 폭넓게 채택된다. 만약 검색 위주의 정적 데이터셋이라면, 더 엄격한 균형을 제공하는 AVL 트리를 고려할 수 있다. Nevertheless, 전반적인 활용성과 구현 편의성 측면에서 레드 블랙 트리는 균형 잡힌 대안이다.

⁂

Footnotes

1. https://www.geeksforgeeks.org/dsa/introduction-to-red-black-tree/ ↩ ↩² ↩³ ↩⁴

2. https://en.wikipedia.org/wiki/Red–black_tree ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

3. https://iq.opengenus.org/time-and-space-complexity-of-red-black-tree/ ↩

4. https://bmsce.ac.in/Content/CS/Unit-2-ADA-NM.pdf ↩ ↩²

5. https://www.geeksforgeeks.org/dsa/applications-advantages-and-disadvantages-of-red-black-tree/ ↩ ↩² ↩³

6. https://stackoverflow.com/questions/3901182/applications-of-red-black-trees ↩

7. https://www.programiz.com/dsa/red-black-tree ↩