레드-블랙 트리 (Red-Black Tree)

아쉽게도 이 Rbt.가 아닙니다.

0. 목차

1. 개념 정의

2. 레드-블랙 트리의 규칙 5개조

3. 레드-블랙 트리의 노드 삽입

4. 레드-블랙 트리의 노드 삭제

5. 레드-블랙 트리의 노드 검색

6. 기타 특징

7. 참고문헌

1. 개념 정의

레드-블랙 트리 (Red-Black Tree, RBT)는 이진 탐색 트리(BST)의 일종으로, 노드마다 적(赤)또는 흑(黒)색을 덧입혀 균형을 유지하는 자료구조입니다. 이를 통해 삽입, 삭제, 검색이 최악의 경우에도 O(log n)을 보장합니다.

레드-블랙 트리의 독특한 특징 중 하나로 NIL 노드가 있습니다. RBT에서 모든 리프 노드는 NIL 노드로 대체됩니다. 즉, 트리내 모든 리프는 NULL이 아니라 (즉, 그냥 비워놓는 게 아니라) NIL 노드가 되도록 합니다. 실제 구현 시 트리 전체에 하나뿐인 NIL 노드를 root에 배치하고, key가 있는 정상적인 노드가 자식이 없을 때 NULL 대신 이 NIL 노드를 가리키도록 하는 것이 일반적입니다. NIL 노드는 예외없이 흑색입니다.

참고로 여기서 NIL은 특별히 어떠한 약자는 아니며, 허무, 공허, nothing, zero, empty 등을 의미하는 라틴어 'nihil'에서 유래한 것으로 보입니다. 이 nihil은 흔히 말하는 '니힐리즘 (허무주의)' 같은 단어에서 그 용례를 찾아볼 수 있습니다.

---

2. 레드-블랙 트리의 규칙 5개조

RBT의 예시. Credit: https://www.happycoders.eu/algorithms/red-black-tree-java/

레드-블랙 트리는 아래 5개 규칙을 항상 만족시켜야만 합니다. 만족하도록 만드는 과정이 곧 균형을 잡는 과정과 같습니다.

1조. 모든 노드는 적색 또는 흑색.
2조. 루트는 반드시 흑색.
3조. 모든 리프 노드는 흑색 NIL이다.
4조. Red-red 금지. 적색 노드의 자식은 반드시 흑색이다. (즉, 연이은 적색 노드 불가)
5조. Black-height 동일의 원칙: 임의의 노드에서 자손인 NIL 노드까지의 모든 경로에서, 거치는 흑색 노드 수는 모두 동일해야 한다. 단, 자기 자신은 카운트에서 제외.

'Black-Height 동일의 원칙'의 경우 아래 예시를 봐주세요.

가령 노드 19를 기준으로 보면, NIL에 도달하기까지의 모든 경우의 수 (19-18-NIL, 19-75-24-NIL, 19-75-81-NIL)의 과정에서 거쳐가는 BLACK의 수는 2개로 동일합니다. 이는 루트 노드인 17을 기준으로 세어봐도 동일합니다 (상기했듯 자기 자신 카운트 x).

상기 규칙들을 만족하도록 조작하는 과정에서 레드-블랙 트리의 균형 유지가 보장됩니다.

---

3. 레드-블랙 트리의 삽입

새 노드의 삽입 과정 자체는 일반적인 BST와 같습니다. 그러나, RBT의 경우 삽입 후 '복구 과정'을 따로 거쳐야 합니다. 복구 과정에 대해서는, 구분하기 쉽도록 시작 처리 - 반복 케이스 I - 반복 케이스 II - 반복 케이스 III - 종료 처리로 칭합니다. 추가로, 반복 케이스 II와 III에서는 '회전'이라는 개념이 등장하는데 이에 대해서는 아래에서 다루겠습니다.

3.1. 시작 처리

복구 과정의 시작은, 새 노드의 삽입 위치의 부모가 RED인지 확인하는 것입니다. 부모가 RED일 때만 반복 케이스로 들어가도록 합니다. 아닐 경우 바로 종료 처리로 넘어갑니다.

3.2. 반복 케이스 3개

새 노드가 루트가 아닐 경우, 무조건 적색으로 하여 추가합니다. 이 과정에서 상기 5개 조항을 위반할 수 있습니다. 그렇기에 아래 케이스들을 차례로 검사 및 처리하여 위반 사항을 해결합니다. 만약 부모가 RED가 아닐 경우 반복 케이스들을 무시합니다.

케이스	조건 설명	처리 방법
I	부모 RED, 삼촌 RED	재채색(부모, 삼촌을 BLACK로, 조부모는 RED로)
II	부모 RED, 삼촌 BLACK, 삼각형 형태	부모를 축으로 좌회전/우회전하여 일자형으로 만듦
III	부모 RED, 삼촌 BLACK, 일자 형태	조부모를 축으로 좌회전/우회전 후 색 교환

실제로는 좌우 대칭으로 존재하니 구현 시 총 6개 케이스에 대하여 작성하게 됩니다. 이 케이스들에 대하여 아래에서 더 자세히 살펴보시겠습니다.

아, 앞으로 나올 등장인물의 이니셜을 소개합니다. G, P, U, N. 순서대로 조부모, 부모, 삼촌, 새 노드입니다.

3.2.1. 반복 케이스 I: 부모와 숙부가 둘 다 R인 경우 (재채색)

• 새로 삽입하는 노드를 N이라 가정. 위에서 언급 드렸듯 새 노드는 R색입니다.
• 이때 부모 P가 R색이면, 부모도 R색 자식도 R색. 즉, Red‑Red (규칙 #4) 위반이 발생합니다.

Case 1:
         (G,B)                     ← 조부모 G
       ／       ＼
  (P,R)         (U,R)              ← 부모 P, 숙부 U
    ／
 (N,R)                             ← 새로 삽입된 노드 N

해결하기 위해 아래와 같이 수행합니다. 이를 통해 Red-Red 위반을 해결할 수 있습니다.

1. P와 U를 BLACK으로 변경
2. G를 RED로 변경
3. 현재 탐색 중인 노드를 그의 조부모로 바꾼 뒤, 반복문의 처음으로

3.2.2. 반복 케이스 II: 삼각형 (triangle) 모양일 시 회전

• 부모 P는 R색, 숙부 U는 B색(또는 NIL)입니다.
• N이 P의 오른쪽 (또는 왼쪽 자식)인 삼각형 모양입니다.

Case 2 (왼쪽-삼각형 예시):

       (G,B)                       ← 조부모 G
      ／    ＼
  (P,R)     (U,B)                  ← 부모 P(회전축), 숙부 U
       ＼
       (N,R)                       ← 새로 삽입된 노드 N

해결하기 위해, 이 삼각형 구조를 일자 형태로 폅니다. 전체 과정은 아래와 같습니다.

1. 회전: '왼쪽-삼각형 (G → P 왼쪽 → N 오른쪽)'이면, 부모 P를 기준으로 왼쪽 회전(leftRotate(P)). '오른쪽-삼각형 (G → P 오른쪽 → N 왼쪽)'이면, 부모 P를 기준으로 오른쪽 회전(rightRotate(P)).
2. 새로운 N 지정 (회전 후 N ← P로 재지정)
3. 다음 단계로 이동 (일자 형태가 되었으므로, 일자 형태를 처리하는 케이스 III로 넘김)

위 '왼쪽-삼각형' 예시의 경우 부모(P)를 축으로 왼쪽 회전이 필요하며, 회전 결과는 아래와 같습니다.

P를 기준으로 왼쪽 회전 결과:

      (G,B)                        ← 조부모 G
     /     \
  (N,R)   (U,B)                    ← 새 노드 N, 숙부 U
   /
(P,R)                              ← 부모 P (회전축)

3.2.3. 반복 케이스 III: 일자 (line) 모양일 때 회전 및 색상 스왑

• 위와 마찬가지로 부모 P는 R색, 숙부 U는 B색(또는 NIL)입니다.
• "왼쪽–왼쪽(Left‑Left)" 모양, 즉, N이 P의 왼쪽 자식이면서 P가 G의 왼쪽 자식인 "왼쪽–왼쪽(Left‑Left)" 모양이라고 가정합니다. (또는 대칭으로 "오른쪽–오른쪽" 모양)

Case 3 (Left‑Left 예시):

        (G,B)                      ← 조부모 G(회전축)
     ／      ＼
  (P,R)     (U,B)                  ← 부모 P, 숙부 U
   ／           
(N,R)                              ← 새로 삽입된 노드 N

해결하기 위해 G와 P의 색을 서로 교환하여 균형을 복구합니다. 그리고 조부모 G를 축으로 단일 회전합니다. 회전과 색 교환만으로 트리의 모든 경로에서 black-height를 유지 및 red-red 위반을 해결할 수 있습니다. 그러나 조상으로 전파된 것이 있을 수 있으므로 반복해야 합니다.

1. G와 P의 색을 맞바꿈
2. Left-left 구조일 시 G를 기준으로 오른쪽 회전(rightRotate(G)). 단, right-right 구조라면 G를 기준으로 왼쪽 회전
3. P가 RED일 경우 반복문의 처음으로

위 '왼쪽-왼쪽 라인' 예시의 경우 조부모(G)를 축으로 오른쪽 회전이 필요하며, 회전 결과는 아래와 같습니다.

G를 축으로 오른쪽 회전 결과:

        (P,R)                        ← 부모 P
     ／        ＼
  (N,R)       (G,B)                  ← 새 노드 N, 조부모 G(회전축)    
                   ＼
                  (U,B)              ← 숙부 U

3.2.4. 반복 3개 케이스를 보니 드는 의문점.

'부모 BLACK, 삼촌 RED' 같은 경우는 따로 대응하지 않나요? 네, 대응할 필요가 없습니다. 새로 삽입되는 노드는 무조건 RED이므로, 부모 BLACK, 자식 RED. 상기 규칙 5개조에 어긋나는 바가 없습니다.

3.3. 종료 처리

반복을 탈출했는데 루트가 적색이라면, 이를 흑색으로 재채색하고 종료합니다.

3.4. 잠깐, 왼쪽/오른쪽 회전이란?

Credit: https://simpletechtalks.com/

트리 회전은 이진 탐색 트리(BST)의 구조를 재조정하면서 BST의 특징(왼쪽 자식 ≤ 부모 ≤ 오른쪽 자식) 을 유지하는 연산입니다. 레드-블랙 트리뿐만 아니라 AVL 트리 등 self-balancing BST (균형을 스스로 되찾는 BST)에서 높이 균형을 맞추기 위해 사용됩니다.

일반적인 BST에서는, 삽입/삭제 후, BST 속성에 어긋나게 될 경우 회전을 시킵니다 (부모 > 오른쪽 자식, 부모 < 왼쪽 자식 등). 한편 레드-블랙 트리의 삽입의 경우 상기 반복 케이스 I, II, III를 처리하는 과정에서 자연스럽게 수행시키게 됩니다.

3.4.1. 왼쪽 회전

오른쪽 서브트리가 무거울 때, 균형을 맞추기 위해 왼쪽으로 꺾습니다.

Credit: https://www.happycoders.eu/algorithms/red-black-tree-java/

안내: 애플 구형기기에서는 정상적으로 동작하지 않을 수 있습니다.

1. R ← N.right
2. N.right ← R.left
3. R.parent ← N.parent (R가 루트가 되거나, 부모의 자식 포인터를 수정)
4. R.left ← N
5. N.parent ← R

왼쪽 회전 수도코드는 아래와 같습니다.

function leftRotate(T, x):
    y = x.right
    x.right = y.left
    if y.left ≠ nil:
        y.left.parent = x

    y.parent = x.parent
    if x.parent == nil:
        T.root = y
    else if x == x.parent.left:
        x.parent.left = y
    else:
        x.parent.right = y

    y.left = x
    x.parent = y

3.4.2. 오른쪽 회전 (Right Rotate)

왼쪽 서브트리가 무거울 때, 균형을 맞추기 위해 오른쪽으로 꺾습니다.

Credit: https://www.happycoders.eu/algorithms/red-black-tree-java/

안내: 애플 구형기기에서는 정상적으로 동작하지 않을 수 있습니다.

1. L ← N.left
2. N.left ← L.right
3. L.parent ← N.parent (L가 루트가 되거나, 부모의 자식 포인터를 수정)
4. L.right ← N
5. N.parent ← L

오른쪽 회전 수도코드는 아래와 같습니다.

function rightRotate(T, y):
    x = y.left
    y.left = x.right
    if x.right ≠ nil:
        x.right.parent = y

    x.parent = y.parent
    if y.parent == nil:
        T.root = x
    else if y == y.parent.left:
        y.parent.left = x
    else:
        y.parent.right = x

    x.right = y
    y.parent = x

3.4.3. 회전의 기타 특징

• 레드‑블랙 트리뿐만 아니라 AVL 트리 등 BST 전반적으로 서브트리의 균형을 맞추기 위해 사용됩니다. 노드를 “꺾어서” 트리의 모양을 바꿔줍니다.
• 회전 자체로는 색이 바뀌지 않습니다 (black-height를 유지).
• O(1) 연산으로 수행됩니다.

3.5. 복구 과정 수도코드

 

---

4. 레드-블랙 트리의 삭제

※ BST의 삭제 과정 자체만으로도 복잡하므로, 먼저 BST의 삭제 과정을 꼭 읽고 와주시면 감사하겠습니다.

삽입을 했으니 이제 삭제를 해야겠지요? 삭제 역시 일반적인 BST의 과정을 그대로 따릅니다만, 그 후 삭제 복구 과정을 통해 RBT의 상기 규칙 5개을 지키도록 해야 합니다. 삭제 복구 과정은 먼저 속성 위반 여부의 확인에서부터 시작합니다.

4.1. 개요 — 왜 ‘삭제’가 까다로운가?

이미 BST 삭제 자체도 충분히 복잡한데, 여기에 더해 RBT는 색까지 봐야 하기 때문입니다. 더 자세하게는, 일반 BST의 삭제와 마찬가지로, 1) 삭제 요청받은 노드 z 선택 → 2) z가 자식 ≤ 1개면 바로 제거, 자식 2개면 후계자 y와 교환 후 y를 제거까지는 동일합니다. 그러나 차이가 생기는 지점은 “트리에서 실제로 삭제되는 노드의 색”입니다. 

(전위)선행자 / (중위)후계자란?

BST에서 어떤 노드 z를 기준으로 중위 순회(in-order traversal) 시,

선행자(in-order predecessor)란, z의 좌측 서브트리의 가장 우측 노드. 다시 말하여, z보다 작은 값 중 가장 최대값인 노드이자, 중위 순회 시 z 이전에 출력될 노드. 예를 들어 위 트리의 4의 선행자는 3입니다.

후계자(in-order successor)란, z의 우측 서브트리의 가장 좌측 노드. 다시 말하여, z보다 큰 값 중 최솟값인 노드이자, 중위 순회 시 z 다음으로 출력될 노드. 예를 들어 위 트리의 4의 후계자는 5입니다.

이 개념은 특히, 삭제할 노드의 자식이 둘일 때, 해당 노드를 직접 삭제하지 않고 값을 교환한 뒤, 후계자(또는 선행자)를 실제로 삭제하는 방식으로 사용됩니다.

아래는 선행자/후계자 탐색에 필요한 Tree-Minimum 및 Tree-Maximum을 찾는 간단한 수도코드입니다.

function TREE-MAXIMUM(t, x):
    while x.right != t.nil:
        x ← x.right
    return x

function TREE-MINIMUM(t, x):
    while x.left != t.nil:
        x ← x.left
    return x

노드의 색	문제 여부	상세
RED	문제 없음	규칙 #4 (연속 RED 금지), #5 (black-height 보존)의 일관성 유지 가능
BLACK	문제 발생	삭제로 인해 해당 경로의 black‑height가 1 줄어들어 규칙 #5가 깨짐

즉, BLACK 노드의 제거로 인한 black‑height 불균형을 복구하는 과정이 필요합니다.

 

4.2. 등장인물 소개

노드 삭제의 경우 등장인물이 막장드라마를 방불케 할 정도로 복잡합니다. 아래와 같이 표로 정리해드립니다.

기호	역할	설명
z	삭제 요청 노드	사용자가 삭제하려고 한 노드. 자식이 둘이면 실제로는 삭제되지 않음.
y	실제로 제거되는 노드	트리에서 물리적으로 제거되는 노드. z 또는 z의 중위 후계자. y.color가 BLACK이면 복구(delete-fix-up)가 필요.
x	y의 자리를 대신할 노드	y의 자식 (또는 NIL). delete-fix-up()의 시작 지점. 불균형이 발생한 위치로, 루프를 통해 black-height를 복구한다.
p	x의 부모	루프 중 상위 노드. x가 root가 아니라면 항상 존재. 반복문에서 기준이 됨.
w (또는 s)	x의 형제	핵심 판단 대상. 색과 자식의 색에 따라 케이스 I-IV를 결정한다.
w.left w.right	형제의 자식들	이들의 RED/BLACK 여부로 회전 방향 및 색상 조정 여부가 결정됨.
T.root	트리의 루트	복구 과정의 종료 조건 중 하나. x == T.root이면 루프 종료.

 

4.3. 삭제 절차의 흐름

1. 일반적인 BST 삭제 과정과 비슷하게 수행
   • 삭제 요청받은 노드 z 선택
   • 실제로 제거될 노드 y 결정
     • 만약 z의 자식이 0개면, y=z.
     • 1개면, y=z; x=(y의 자식).
     • 2개면, y=(y의 중위후계자); x=y->right.
   • y.color를 y_original_color로 보관
   • TRANSPLANT(T, y, x) 호출: 트리로부터 y를 떼어내고, 그 자리에 x를 붙임 (BST의 이식 관련 개념 참조)
   • 삭제된 노드의 색깔(y_original_color)이 RED면 여기서 종료
2. y_original_color == BLACK이면 delete‑fix‑up(T, x)
   • x는 “black‑height 불균형이 전파된 지점”
   • 이후 fixup 과정은 아래 4.4. 참조
   • (C/C++ 등 메모리 조작 필요 시) 메모리 해제

아래는 이식 함수의 간단한 RBT 버전 수도코드입니다.

function RB-TRANSPLANT(T,u,v):
    if u.p == T.nil:
        T.root ← v
    else if u == u.p.left:
        u.p.left ← v
    else u.p.right ← v
    v.p ← u.p

 

4.4. 삭제 복구의 케이스 4가지

※ 아래 표는 “P가 부모, x는 왼쪽 자식”으로 가정한 좌측 기준 설명입니다.

케이스	조건	처리 요약	결과
I	S.color == RED	1. S → BLACK 2. P → RED 3. 좌회전(P)	형제를 BLACK으로 만든 뒤 케이스 II–IV로 진행
II	S.color == BLACK S.left.color == BLACK S.right.color == BLACK	1. S → RED 2. x ← P	문제를 위로 올림 (x=x.p) x가 루트가 아니면서 x가 BLACK일 경우 처음으로
III	S.color == BLACK S.left.color == RED S.right.color == BLACK	1. S.left → BLACK 2. S → RED 3. 우회전(S)	수행 후 케이스 IV로 진행
IV	S.color == BLACK S.right.color == RED	1. S.color ← P.color 2. P → BLACK 3. S.right → BLACK 4. 좌회전(P) 5. x ← root	black-height (규칙 #5) 복구 && 속성을 모두 만족 x가 루트가 아니면서 x가 BLACK일 경우 처음으로

대칭으로 x가 오른쪽 자식이면 LEFT/RIGHT, INNER/OUTER 방향만 바꾸면 됩니다.

4.5. 노드 삭제 수도코드

삭제는 상당히 복잡하여 fixup뿐만 아니라 노드 삭제 전체 알고리즘도 같이 올려드립니다.

function RB-DELETE-FIXUP(T, x):
    while x ≠ T.root and x.color == BLACK
        if x == x.parent.left
            w ← x.parent.right
            if w.color == RED
                w.color ← BLACK
                x.parent.color ← RED
                LEFT-ROTATE(T, x.parent)
                w ← x.parent.right
            if w.left.color == BLACK and w.right.color == BLACK
                w.color ← RED
                x ← x.parent
            else
                if w.right.color == BLACK
                    w.left.color ← BLACK
                    w.color ← RED
                    RIGHT-ROTATE(T, w)
                    w ← x.parent.right
                w.color ← x.parent.color
                x.parent.color ← BLACK
                w.right.color ← BLACK
                LEFT-ROTATE(T, x.parent)
                x ← T.root
        else
            ... (상기 과정의 좌우 대칭) ...
    x.color ← BLACK

function RB-DELETE(T, z):
    y ← z
    y_original_color ← y.color
    if z.left == T.nil
        x ← z.right
        RB-TRANSPLANT(T, z, z.right)
    else if z.right == T.nil
        x ← z.left
        RB-TRANSPLANT(T, z, z.left)
    else
        y ← TREE-MINIMUM(z.right)
        y_original_color ← y.color
        x ← y.right
        if y.parent == z
            x.parent ← y
        else
            RB-TRANSPLANT(T, y, y.right)
            y.right ← z.right
            y.right.parent ← y
        RB-TRANSPLANT(T, z, y)
        y.left ← z.left
        y.left.parent ← y
        y.color ← z.color

    if y_original_color == BLACK
        RB-DELETE-FIXUP(T, x)

 

---

5. 레드-블랙 트리의 검색

검색은 일반적인 BST와 동일합니다. 트리 순회가 으레 그렇듯 반복 버전과 재귀 버전이 있습니다. 아래 수도코드를 참고해주세요.

// 반복
function RB-TREE-FIND-ITER(T, k):
    x ← T.root
    while x ≠ T.nil and k ≠ x.key:
        if k < x.key:
            x ← x.left
        else:
            x ← x.right
            
    if x = T.nil:
        return T.nil
    else
        return x

// 재귀
function RB-TREE-FIND-RECUR(x, k):
    if x = T.nil or k = x.key:
        return x
    if k < x.key:
        return RB-TREE-FIND-RECUR(x.left, k)
    else:
        return RB-TREE-FIND-RECUR(x.right, k)

// 사용 예시
function RB-TREE-FIND(T, k):
    // return RB-TREE-FIND-ITER(T.root, k) // 반복
    return RB-TREE-FIND-RECUR(T.root, k) // 재귀

 

---

6. 레드-블랙 트리의 기타 특징

• 삽입, 삭제, 검색 모두 최악의 경우에도 O(log n)입니다.
• 트리의 최대 높이(h)는 항상 2 * log₂(n+1) 이하로 제한됩니다.
• RBT는 2-3-4 트리의 이진 트리 구현으로 볼 수 있으며, B-Tree의 특수한 경우로 이해될 수도 있습니다.
• AVL 트리에 비해 균형 복구에 필요한 회전 횟수가 적고, 더 빠른 연산 수행이 가능합니다.
• 실제로 널리 쓰이며, 특히 C++의 std::map과 std::set, 자바의 TreeMap이 대표적인 예입니다.
• 리눅스 커널의 rbtree.c: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/lib/rbtree.c 

---

7. 참고문헌

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms (4th ed., p. 343-345). The MIT Press.

Woltmann, S. (n.d.). Red-Black Tree (Fully Explained + with Java Code). HappyCoders.eu. Retrieved April 19, 2025, from https://www.happycoders.eu/algorithms/red-black-tree-java/

김두루. (n.d.). Red-Black Tree (4) 삽입(insert, insert_fix_up). Velog. Retrieved April 19, 2025, from https://velog.io/@stthunderl/Red-Black-Tree-4-%EC%82%BD%EC%9E%85insert