Red-Black Tree

Red-Black Tree는 자가 균형 이진 탐색 트리(Self-Balancing BST)의 대표적인 구현 중 하나입니다.
AVL 트리보다 균형 조건이 덜 엄격하여, 삽입과 삭제 시 더 빠르고 회전 횟수가 적다는 장점이 있습니다.
Java의 TreeMap, TreeSet, C++의 std::map, std::set 등이 내부적으로 Red-Black Tree를 사용합니다.

핵심 요약

항목	설명
정의	이진 탐색 트리이면서, 각 노드에 "검정/빨강" 색을 지정하고, 일정 규칙을 만족
목적	트리 높이를 제한하여 탐색, 삽입, 삭제를 O(log n) 시간에 수행
특징	불균형 허용 (균형 조건이 완화됨) → 회전 횟수가 적고 성능 안정적

Red-Black Tree의 5가지 규칙

1. 각 노드는 빨강 또는 검정
2. 루트는 항상 검정
3. 모든 리프(null)는 검정
4. 빨강 노드의 자식은 반드시 모두 검정
   → 즉, 빨강이 연속으로 두 번 나올 수 없음
5. 모든 노드에서 리프까지의 모든 단순 경로에는 같은 수의 검정 노드 존재

삽입 과정 요약

1. 일반 BST처럼 삽입 (새 노드는 빨강)
2. 삽입 후, 위반된 규칙을 회전/재색칠로 복구
3. 주요 케이스:
   • 부모와 삼촌이 모두 빨강이면 → 색 변경
   • 삼촌이 검정이면 → 회전 필요

루트에 도달하면 항상 검정으로 설정

삭제 과정 요약

1. 일반 BST처럼 삭제
2. 삭제된 노드가 검정일 경우 균형이 깨질 수 있음 → 복구 과정 필요
3. 복구 방법은 복잡하며 회전과 색 변경을 조합

Red-Black 트리에서 삭제는 삽입보다 구현이 더 복잡합니다.

회전 종류

이름	설명
Left Rotation	왼쪽으로 꺾는 회전
Right Rotation	오른쪽으로 꺾는 회전
Double Rotation	삽입/삭제 조건에 따라 두 번 회전

왼쪽 회전 예시:

     x                    y
      \       →          / \
       y       ←        x   γ
      / \               α   β
     β   γ

LeftRotate(x) 실행

Java에서 Red-Black Tree를 직접 쓰고 싶을 때

TreeMap<K,V> 또는 TreeSet<E> 사용

TreeMap<String, Integer> map = new TreeMap<>();
map.put("apple", 1);
map.put("banana", 2);

• 내부 구조는 RedBlackTree
• 자동 정렬, log(n) 성능 보장
• 탐색, 삽입, 삭제 모두 안정적