RedBlack Tree

devK08·2026년 1월 2일

RedBlack Tree란?

정의

Red-Black Tree는 자가 균형 이진 탐색 트리(Self-Balancing Binary Search Tree)의 한 종류입니다.

특징

느슨한 균형(최장 경로 <= 2 * 최단 경로)
메모리 효율성(색상정보 1bit)

시간 복잡도

연산	최선(Best)	평균(Average)	최악(Worst)
탐색 (Search)	O(log N)	O(log N)	O(log N)
삽입 (Insertion)	O(log N)	O(log N)	O(log N)
삭제 (Deletion)	O(log N)	O(log N)	O(log N)

RedBlack Tree 속성 5가지

모든 노드는 Red Or Black
Root는 항상 Black
Red의 자식은 항상 Black
모든 경로의 Black 노드 수는 동일
모든 Leaf노드는 Black

위 속성은 최장 경로 <= 2 최단 경로를 보장합니다.
이유는
최단 경로: 모두 Black 노드로만 구성 → 길이 = B
최장 경로: Black과 Red가 교대로 나타남 → 길이 = 2B
속성 4에 의해 모든 경로의 Black 노드 수가 동일하므로
최장 경로 <= 2 최단 경로입니다.

삽입 규칙

삽입(Insertion) 케이스별 해결 방법

기본 전제

새 노드는 항상 Red로 삽입
BST 규칙으로 위치를 찾아 삽입
Parent가 Black이면 → 문제 없음, 종료
Parent가 Red이면 → Red-Red 위반! Uncle 확인

N: 새로 추가된 노드
P: 추가된 노드의 부모 노드
U: 부모 노드의 형제 노드
G: 부모 노드의 부모 노드

Case 1: Uncle이 Red

Before

        (G, B)
       /      \
    (P, R)   (U, R)  ← Uncle이 Red
      /
    (N, R)  ← Red-Red 위반!

해결 과정

Step 1: Parent를 Black으로

        (G, B)
       /      \
    (P, B)   (U, R)
      /
    (N, R)

Step 2: Uncle을 Black으로

        (G, B)
       /      \
    (P, B)   (U, B)
      /
    (N, R)

Step 3: Grandparent를 Red로

        (G, R)  ← 위로 전파 가능
       /      \
    (P, B)   (U, B)
      /
    (N, R)

After

        (G, R)  ← 이제 G를 N으로 보고 위로 올라가서 다시 체크
       /      \
    (P, B)   (U, B)
      /
    (N, R)

결과: Recoloring만, 회전 없음, 위로 전파 계속

Case 2-1: Uncle이 Black + LL (Left-Left)

Before

        (G, B)
       /      \
    (P, R)   (U, B)  ← Uncle이 Black
      /
    (N, R)  ← Red-Red 위반!

해결 과정

Step 1: G를 기준으로 Right Rotation

       (P, R)
      /      \
   (N, R)   (G, B)
               \
              (U, B)

Step 2: Recoloring (P를 Black, G를 Red)

       (P, B)  ← 새로운 루트
      /      \
   (N, R)   (G, R)
               \
              (U, B)

After

       (P, B)
      /      \
   (N, R)   (G, R)
               \
              (U, B)

결과: 1번 회전 + Recoloring, 완료

Case 2-2: Uncle이 Black + RR (Right-Right)

Before

        (G, B)
       /      \
    (U, B)   (P, R)  ← Uncle이 Black
                \
               (N, R)  ← Red-Red 위반!

해결 과정

Step 1: G를 기준으로 Left Rotation

       (P, R)
      /      \
   (G, B)   (N, R)
   /
(U, B)

Step 2: Recoloring (P를 Black, G를 Red)

       (P, B)  ← 새로운 루트
      /      \
   (G, R)   (N, R)
   /
(U, B)

After

       (P, B)
      /      \
   (G, R)   (N, R)
   /
(U, B)

결과: 1번 회전 + Recoloring, 완료

Case 3-1: Uncle이 Black + LR (Left-Right)

Before

        (G, B)
       /      \
    (P, R)   (U, B)  ← Uncle이 Black
        \
       (N, R)  ← Red-Red 위반!

해결 과정

Step 1: P를 기준으로 Left Rotation

        (G, B)
       /      \
    (N, R)   (U, B)  ← LL 케이스로 변환!
      /
   (P, R)

Step 2: G를 기준으로 Right Rotation

       (N, R)
      /      \
   (P, R)   (G, B)
               \
              (U, B)

Step 3: Recoloring (N을 Black, G를 Red)

       (N, B)  ← 새로운 루트
      /      \
   (P, R)   (G, R)
               \
              (U, B)

After

       (N, B)
      /      \
   (P, R)   (G, R)
               \
              (U, B)

결과: 2번 회전 + Recoloring, 완료

Case 3-2: Uncle이 Black + RL (Right-Left)

Before

        (G, B)
       /      \
    (U, B)   (P, R)  ← Uncle이 Black
              /
           (N, R)  ← Red-Red 위반!

해결 과정

Step 1: P를 기준으로 Right Rotation

        (G, B)
       /      \
    (U, B)   (N, R)  ← RR 케이스로 변환!
                \
               (P, R)

Step 2: G를 기준으로 Left Rotation

       (N, R)
      /      \
   (G, B)   (P, R)
   /
(U, B)

Step 3: Recoloring (N을 Black, G를 Red)

       (N, B)  ← 새로운 루트
      /      \
   (G, R)   (P, R)
   /
(U, B)

After

       (N, B)
      /      \
   (G, R)   (P, R)
   /
(U, B)

결과: 2번 회전 + Recoloring, 완료

삽입 케이스 비교표

Case	초기 상태	Rotation	최종 상태	종료
1	Red-Red	없음	Recolor 후 전파	❌ 계속
2-1 (LL)	Red-Red (왼-왼)	Right 1회	균형 잡힘	✅ 완료
2-2 (RR)	Red-Red (오-오)	Left 1회	균형 잡힘	✅ 완료
3-1 (LR)	Red-Red (왼-오)	Left→Right	균형 잡힘	✅ 완료
3-2 (RL)	Red-Red (오-왼)	Right→Left	균형 잡힘	✅ 완료

핵심 패턴:

Uncle Red → Recoloring만 (전파)
Uncle Black + 일자 (LL/RR) → 1번 회전
Uncle Black + 꺾임 (LR/RL) → 2번 회전

삭제

삭제 기본 개념

Double Black이란?

Black 노드를 삭제하면 발생하는 문제:

Before:
      (B)
     /   \
   (B)   (B)  ← 이 Black 노드를 삭제
   / \   / \
  N  N  N  N

After:
      (B)
     /   \
   (B)  (DB)  ← Double Black! (Black 카운트가 2개)
   / \
  N  N

문제: 왼쪽 경로는 Black 2개, 오른쪽 경로는 Black 1개 → Property 4 위반!

목표: Double Black을 Single Black으로 만들기

X: 제거해야할 노드

S: 제거해야할 노드의 형제 노드

P: 제거해야할 노드의 부모 노드

Case 1: Sibling이 Red

Before

      (P, B)
     /      \
  (X, DB)  (S, R)  ← Sibling이 Red!
           /    \
        (C1,B) (C2,B)

해결 과정

Step 1: P를 기준으로 Left Rotation

        (S, R)
       /      \
    (P, B)   (C2,B)
     /  \
  (X,DB)(C1,B)

Step 2: Recoloring (S를 Black, P를 Red)

        (S, B)
       /      \
    (P, R)   (C2,B)
     /  \
  (X,DB)(C1,B)  ← 새로운 Sibling!

After

        (S, B)
       /      \
    (P, R)   (C2,B)
     /  \
  (X,DB)(C1,B)  ← 이제 C1이 Black Sibling → Case 2,3,4로 계속

결과: 1번 회전 + Recoloring, Black Sibling 만들기 → 다른 케이스로 이동

Case 2: Sibling이 Black, Sibling의 자식들이 모두 Black

이 케이스는 Parent의 색깔에 따라 두 가지로 나뉩니다.

Case 2.1: Parent가 Red인 경우

Before

      ...
       |
    (P, R)  ← Parent가 Red
     /   \
  (X,DB) (S,B)  ← Sibling이 Black
          / \
        (B) (B)  ← Sibling의 자식들이 모두 Black
        / \ / \
       N N N N

해결 과정

Step 1: S를 Red로 변경

      ...
       |
    (P, R)
     /   \
  (X, B)  (S, R)  ← Sibling을 Red로
          / \
        (B) (B)
        / \ / \
       N N N N

Step 2: P를 Black으로

      ...
       |
    (P, B)  ← 완료!
     /   \
  (X, B)  (S, R)
          / \
        (B) (B)
        / \ / \
       N N N N

After

      ...
       |
    (P, B)
     /   \
  (X, B)  (S, R)
          / \
        (B) (B)
        / \ / \
       N N N N

결과: Recoloring만, 완료

Case 2.2: Parent가 Black인 경우

Before

      ...  ← P 위에 다른 노드 존재
       |
    (P, B)  ← Parent가 Black
     /   \
  (X,DB) (S,B)  ← Sibling이 Black
          / \
        (B) (B)  ← Sibling의 자식들이 모두 Black
        / \ / \
       N N N N

해결

Step 1: S를 Red로 변경하고, P를 Doubly Black으로 간주

      ...
       |
    (P, DB)  ← P를 새로운 문제 노드로 봄
     /   \
  (X, B)  (S, R)  ← S를 Red로 바꿈
          / \
        (B) (B)
        / \ / \
       N N N N

After

      ...
       |
    (P, DB)  ← P를 X로 보고 위로 올라가서 다시 해결
     /   \
  (X, B)  (S, R)
          / \
        (B) (B)
        / \ / \
       N N N N

결과: S를 Red로 바꾸고, P를 Double Black으로 간주.
P를 새로운 X로 보고 위로 전파 ⬆️ (계속)

Case 3: Sibling이 Black, Near Child가 Red

Before

      (P, ?)
     /      \
  (X, DB)  (S, B)
           /    \
        (C1,R) (C2,B)  ← Near Child만 Red!
        / \    / \
       N  N   N  N

해결 과정

Step 1: S를 기준으로 Right Rotation

      (P, ?)
     /      \
  (X, DB)  (C1,R)
              \
             (S,B)
               \
              (C2,B)
              / \
             N  N

Step 2: Recoloring (C1을 Black, S를 Red)

      (P, ?)
     /      \
  (X, DB)  (C1,B)  ← Case 4로 변환!
              \
             (S,R)
               \
              (C2,B)
              / \
             N  N

After

      (P, ?)
     /      \
  (X, DB)  (C1,B)
              \
             (S,R)  ← 이제 Far Child가 Red → Case 4로!
               \
              (C2,B)
              / \
             N  N

결과: 1번 회전 + Recoloring, Case 4로 변환

Case 4: Sibling이 Black, Far Child가 Red

Before

      (P, ?)  ← P는 Red 또는 Black
     /      \
  (X, DB)  (S, B)
           /    \
        (C1,?) (C2,R)  ← Far Child가 Red!
        / \    / \
       N  N   N  N

해결 과정

Step 1: P를 기준으로 Left Rotation

        (S, ?)
       /      \
    (P, ?)   (C2,R)
     /  \     / \
  (X,DB)(C1,?) N  N
        / \
       N  N

Step 2: Recoloring

S가 P의 색을 가져감
P를 Black으로
C2를 Black으로

        (S, P의 색)  ← S가 P의 원래 색 가져감
       /      \
    (P, B)   (C2,B)
     /  \     / \
  (X,B)(C1,?) N  N
     / \  / \
    N  N N  N

After

        (S, P의 원래 색)
       /      \
    (P, B)   (C2,B)
     /  \     / \
  (X,B)(C1,?) N  N
     / \  / \
    N  N N  N

결과: 1번 회전 + Recoloring, Double Black 해결

삭제 케이스 비교표

Case	Sibling	자식 상태	Parent 색	Rotation	결과	종료
1	Red	-	-	Left/Right 1회	Black Sibling 생성	❌ 계속
2.1	Black	모두 Black	Red	없음	Recolor만	✅ 완료
2.2	Black	모두 Black	Black	없음	위로 전파	❌ 계속
3	Black	Near=Red	-	Right/Left 1회	Case 4로 변환	❌ 계속
4	Black	Far=Red	-	Left/Right 1회	DB 해결	✅ 완료

핵심 패턴:

Sibling Red → Rotation으로 Black Sibling 만들기 (Case 1)
자식 모두 Black + P가 Red → Recoloring으로 완료 (Case 2.1)
자식 모두 Black + P가 Black → Recoloring 후 위로 전파 (Case 2.2)
Near Child만 Red → Rotation으로 Case 4 변환 (Case 3)
Far Child가 Red → Rotation으로 완전 해결 (Case 4)

devK08

안녕하세요. 개발자 지망 고등학생입니다.

이전 포스트

Java Reflection

다음 포스트

RedBlack Tree

RedBlack Tree란?

정의

특징

RedBlack Tree 속성 5가지

삽입 규칙

삽입(Insertion) 케이스별 해결 방법

기본 전제

Case 1: Uncle이 Red

Before

해결 과정

After

Case 2-1: Uncle이 Black + LL (Left-Left)

Before

해결 과정

After

Case 2-2: Uncle이 Black + RR (Right-Right)

Before

해결 과정

After

Case 3-1: Uncle이 Black + LR (Left-Right)

Before

해결 과정

After

Case 3-2: Uncle이 Black + RL (Right-Left)

Before

해결 과정

After

삽입 케이스 비교표

삭제

삭제 기본 개념

Double Black이란?

Case 1: Sibling이 Red

Before

해결 과정

After

Case 2: Sibling이 Black, Sibling의 자식들이 모두 Black

Case 2.1: Parent가 Red인 경우

Before

해결 과정

After

Case 2.2: Parent가 Black인 경우

Before

해결

After

Case 3: Sibling이 Black, Near Child가 Red

Before

해결 과정

After

Case 4: Sibling이 Black, Far Child가 Red

Before

해결 과정

After

삭제 케이스 비교표

Java Reflection

Proxy in Java

0개의 댓글