Red-black tree

정의

• 자기 균형을 유지하는 이진 탐색 트리(BST)의 일종
• 각 노드에 “빨강(Red)” 또는 “검정(Black)” 색을 부여하여 균형 유지를 보장
• STL에서는 set, map 등에 활용됨

시간복잡도

• 삽입(insert), 삭제(erase), 탐색(find)의 시간 복잡도는 O(log N)

조건

1. 루트(Root) 노드는 항상 검정
2. 모든 리프(Leaf, NIL) 노드는 검정 NIL: null leaf, 트리의 끝을 나타내는 노드 (자료는 갖지 않음)
3. 빨강 노드의 자식은 반드시 검정 (연속해서 존재할 수 없음)
4. 루트에서 모든 리프(NIL)까지의 검정 노드 개수(depth)는 동일 (균형 유지)

재조정(fix-up)

레드-블랙 트리에서는 트리의 균형과 색상 규칙을 회복하기 위해 두 가지 주요 기법을 사용

Recoloring

노드의 색만 바꾸어 규칙위반을 수정하는 방법

Rotation

트리의 모양을 변경하기 위해 회전을 수행하는 방법

조정 과정

조정 과정은 경우의 수가 많기에 주요한 경우에 대해서 정리함

경우	부모 색	삼촌 색	삽입된 노드 위치	해결 방법
Case 1	🔴 (빨강)	🔴 (빨강)	상관없음	부모와 삼촌을 ⚫ (검정)으로, 조부모를 🔴 (빨강)으로 변경
Case 2	🔴 (빨강)	⚫ (검정)	부모의 반대쪽 자식	새 노드를 부모 방향으로 회전하여 Case 3으로 변환
Case 3	🔴 (빨강)	⚫ (검정)	부모의 같은쪽 자식	조부모를 기준으로 회전 후, 부모를 ⚫ (검정), 조부모를 🔴 (빨강)으로 변경

Case 1. Recoloring

부모와 삼촌이 모두 빨강인 경우

Case 1 예시

       (⚫ 20)
       /    \
   (🔴10)  (🔴30)   <- 부모(🔴), 삼촌(🔴)
   /
(🔴5) <- 새로 삽입된 노드

• 해결 방법: 부모와 삼촌을 검정으로 바꾸고, 조부모를 빨강으로 변경
• 추가 조정 필요: 조부모에 대하여 double-red 문제가 발생할 수 있으므로 재귀적으로 검토 필요

Case 1 조정 결과

       (🔴 20)   <- 조부모(⚫ → 🔴)
       /    \
   (⚫10)  (⚫30)  <- 부모(🔴 → ⚫), 삼촌(🔴 → ⚫)
   /
(🔴5)

Case 2. Rotation 준비 단계

부모는 빨강, 삼촌은 검정이고, 새 노드가 부모의 반대쪽 자식

Case 2 예시

       (⚫ 50)
       /     \
   (🔴30)    (⚫70)
      \
     (🔴40)  <- 새로 삽입된 노드

• 해결 방법: 새 노드를 부모 방향으로 회전하여 Case 3로 변환
• 추가 조정 필요: Case 3로 변환 후 추가 조정 진행

Case 2 조정 결과

       (⚫ 50)
       /     \
   (🔴40)    (⚫70)  <- (회전: 30 ↔ 40)
  /
(🔴30)

Case 3. Rotation 및 Recoloring

부모는 빨강, 삼촌은 검정이고, 새 노드가 부모의 같은쪽 자식

Case 3 예시

       (⚫ 50)
       /     \
   (🔴40)    (⚫70)  <- (회전: 30 ↔ 40)
   /
(🔴30)

• 해결 방법: 조부모를 기준으로 회전, 부모와 조부모의 색을 교환
• 추가 조정 필요: 최종적으로 균형이 맞추어짐

3-1 Rotation

• 조부모 기준으로 rotation 진행

       (🔴 40)   <- 조부모(50 → 40)
       /    \
   (🔴30)  (⚫50)
             \
            (⚫70)

3-2 Recoloring

Case 3 조정 결과

       (⚫ 40)   <- 조부모(🔴 → ⚫)
       /    \
   (🔴30)  (🔴50)   <- 부모(⚫ → 🔴)
             \
            (⚫70)

Red-black tree simulator

아래 사이트에서 red-black tree의 시뮬레이션을 할 수 있음

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html