레드 블랙 트리 개념 및 노드 삽입

김민호·2025년 10월 16일

목록 보기

13/13

🧐 레드-블랙 트리란?

레드-블랙 트리는 다음 두 가지 핵심 특징을 가진 자가 균형 이진 탐색 트리(Self-Balancing BST)입니다.

이진 탐색 트리의 속성을 모두 가집니다. (왼쪽 서브트리는 부모보다 작고, 오른쪽 서브트리는 부모보다 큼)
스스로 균형을 맞추어 트리의 높이를 가능한 낮게 유지합니다.

        50
       /
     40             -> 20을 찾기 위해서는 n의 갯수만큼 반복해야한다.
    /
  20

일반적인 BST는 데이터가 정렬된 순서로 들어올 경우, 한쪽으로 치우쳐진 편향 트리(Skewed Tree)가 되어 탐색, 삽입, 삭제의 시간 복잡도가 최악의 경우 $O(n)$ 이 될 수 있습니다. 레드-블랙 트리는 특정 규칙에 따라 노드의 색(Red/Black)을 지정하고, 삽입/삭제 시 트리의 구조를 재조정하여 항상 $O(log n)$ 의 시간 복잡도를 보장합니다.

📜 레드-블랙 트리의 5가지 속성

레드-블랙 트리가 되기 위해서는 아래의 5가지 속성을 반드시 만족해야 합니다.

모든 노드는 RED 혹은 BLACK 색상을 가집니다.
루트(Root) 노드는 반드시 BLACK입니다.
모든 리프(Leaf) 노드는 BLACK입니다.

잠깐, 여기서 리프(Leaf) 노드란?
레드-블랙 트리에서는 자식 노드가 없는 경우, nil 노드라는 가상의 노드가 있다고 간주합니다. 이 nil 노드가 바로 리프 노드이며, 항상 BLACK 색상입니다. 데이터가 있는 실제 노드와 동등하게 취급하여 규칙을 적용하는 데 사용됩니다.
RED 노드의 자식은 반드시 BLACK입니다. (즉, RED 노드가 연속으로 두 개 나타날 수 없습니다.)
임의의 한 노드에서부터 그 노드의 자손인 모든 리프 노드까지 가는 경로에 있는 BLACK 노드의 수는 모두 동일합니다. (이때, 자기 자신은 카운트에서 제외합니다.)

새로운 개념: Black-Height
속성 5 덕분에 '노드 X의 Black-Height'라는 개념이 성립됩니다. 이는 노드 X에서부터 리프 노드까지의 경로에 있는 BLACK 노드의 수를 의미합니다. 어떤 경로로 가든 BLACK 노드의 수가 같기 때문에 유일한 값으로 정의될 수 있습니다.

✨ 삽입(Insertion) 연산의 원리

레드-블랙 트리는 어떻게 균형을 잡을까요? 바로 삽입/삭제 시 위반될 수 있는 속성 4번과 5번을 해결하는 과정에서 자연스럽게 균형이 맞춰집니다.

🧐 왜 새로운 노드는 항상 RED일까?

새로운 노드를 삽입할 때는 항상 RED 색상으로 삽입합니다. 그 이유는 가장 까다로운 속성 5번(Black-Height 동일)을 깨지 않기 위해서입니다.

기존에 속성 5를 만족하는 트리에서 어느 위치에 RED 노드를 추가하더라도, 특정 경로에 BLACK 노드의 수가 추가되는 것이 아니므로 Black-Height는 변하지 않습니다. 만약 BLACK으로 삽입한다면 해당 경로의 Black-Height가 1 증가하여 속성 5를 위반하게 되고, 이를 해결하는 과정은 훨씬 더 복잡해집니다.

🌳 초기 상태: 유효한 레드-블랙 트리

먼저, 모든 속성을 만족하는 간단한 레드-블랙 트리가 있다고 가정해 봅시다. 이 트리에서 루트(10)로부터 모든 리프(nil) 노드까지의 경로에 있는 블랙 노드의 수는 1개로 동일합니다 (Black-Height = 1).

      10(B)
     /     \
   5(B)     20(B)

10 -> 5 -> nil 경로: 블랙 노드는 5 + nil (2개)
10 -> 20 -> nil 경로: 블랙 노드는 20 + nil (2개)
결과: 속성 5를 만족합니다.

✅: 새로운 노드 '30'을 RED로 삽입

여기에 새로운 노드 30을 RED로 삽입해 보겠습니다. 30은 20의 오른쪽 자식으로 들어갑니다.

      10(B)
     /     \
   5(B)     20(B)
              \
              30(R)  <-- RED로 삽입

삽입 후 Black-Height를 다시 계산해 볼까요?

10 -> 5 -> nil 경로: 블랙 노드는 5, nil (2개)
10 -> 20 -> (left nil) 경로: 블랙 노드는 20, nil(2개)
10 -> 20 -> 30 -> nil 경로: 블랙 노드는 20, nil(2개)

결론: 새로운 RED 노드가 추가되었지만, 어떤 경로든 Black-Height는 여전히 2로 동일합니다. 가장 중요한 속성 5가 깨지지 않았습니다. (이 경우 다른 속성 위반도 없어서 바로 유효한 트리가 되었습니다.)

❌: 새로운 노드 '30'을 BLACK으로 삽입 (잘못된 방법)

만약 같은 위치에 30을 BLACK으로 삽입한다면 어떻게 될까요?

      10(B)
     /     \
   5(B)     20(B)
              \
              30(B)  <-- BLACK으로 삽입

10 -> 5 -> nil 경로: 블랙 노드는 5,nil(2개)
10 -> 20 -> (left nil) 경로: 블랙 노드는 20, nil (2개)
10 -> 20 -> 30 -> nil 경로: 블랙 노드는 20, 30, nil (3개)

삽입 과정

일반적인 BST처럼 노드를 삽입할 위치를 찾습니다.
해당 위치에 RED 색상으로 새로운 노드를 삽입합니다.
삽입 후 레드-블랙 트리의 속성을 위반하는지 확인합니다. (주로 속성 2 또는 4)
속성을 위반했다면, 재조정(Restructuring)과 색상 변경(Recoloring)을 통해 해결합니다.

🛠️ 삽입 후 재조정: 3가지 케이스

새로운 RED 노드(N)를 삽입했을 때, 부모 노드(P)가 RED라면 속성 4(RED는 연속될 수 없다)를 위반하게 됩니다. 이 "Double Red" 문제를 해결하는 방법은 삼촌 노드(U, 부모의 형제 노드)의 색상에 따라 3가지 케이스로 나뉩니다.

(N: 새로 삽입된 노드, P: 부모, G: 조부모, U: 삼촌)

CASE 1: 삼촌(U)이 RED인 경우

가장 간단한 케이스입니다. Double Red가 발생했지만, 넘겨줄 반대편(삼촌)도 RED인 상황입니다. 이때는 색상 변경(Recoloring)으로 해결합니다.

해결 방법:
1. 부모(P)와 삼촌(U)을 BLACK으로 변경합니다.
2. 조부모(G)를 RED로 변경합니다.
3. 조부모(G)를 새로운 노드(N)로 간주하고, 위반 사항이 있는지 다시 확인합니다. (만약 조부모(G)의 부모도 RED라면 또다시 Double Red 문제가 발생하므로 재귀적으로 해결)
예시: 아래와 같은 트리에 30을 삽입해 봅시다.
```
        20(B)
       /     \
     10(R)   50(R)
```
50의 왼쪽에 30(R)을 삽입하면 P(50)와 N(30)이 모두 RED가 됩니다. 이때 U(10)도 RED입니다.
```
        20(B)
       /     \
     10(R)   50(R)  <-- P
             /
           30(R)    <-- N
```
1. P(50)와 U(10)를 BLACK으로, G(20)를 RED로 변경합니다.
2. G(20)가 RED가 되었지만 루트이므로 속성 2(루트는 BLACK)를 위반합니다.
3. 따라서 20을 다시 BLACK으로 변경하여 모든 속성을 만족시킵니다.
```
        20(B)
       /     \
     10(B)   50(B)
             /
           30(R)
```

CASE 2: 삼촌(U)이 BLACK이고, 경로가 직선 형태(Line)인 경우

삽입된 노드(N) - 부모(P) - 조부모(G)의 경로가 // 또는 \\ 모양의 직선입니다. 색상 변경과 회전을 통해 균형을 맞춥니다.

해결 방법:
1. 부모(P)를 BLACK으로, 조부모(G)를 RED로 변경합니다.
2. 조부모(G)를 기준으로 회전합니다. (P가 G의 왼쪽 자식이면 우회전, 오른쪽 자식이면 좌회전)

예시: CASE 2에서 변환된 트리로 계속 진행해 봅시다.

        50(B) <-- G
       /
     40(R) <-- P
    /
  20(R) <-- N (역할이 바뀜)

P(40)를 BLACK으로, G(50)를 RED로 변경합니다.

        50(R)
       /
     40(B)
    /
  20(R)

G(50)를 기준으로 우회전합니다.

        40(B)
       /     \
     20(R)   50(R)

CASE 3: 삼촌(U)이 BLACK이고, 경로가 꺾인 형태(Triangle)인 경우

삽입된 노드(N) - 부모(P) - 조부모(G)의 경로가 꺾여있는 < 또는 > 모양입니다. 이 경우는 회전(Rotation)을 통해 경로를 직선 형태로 만들어 CASE 3으로 전환하여 해결합니다.

해결 방법:
1. 부모(P)를 기준으로 회전하여 경로를 직선 형태로 만듭니다. (P가 G의 왼쪽 자식이면 좌회전, 오른쪽 자식이면 우회전)
2. 이제 CASE 3의 상황이 되었으므로, CASE 3의 방법으로 해결합니다.
예시: 아래 트리에 40을 삽입해 봅시다.
```
        50(B)
       /
     20(R)      <-- G
    /   \
        40(R)   <-- N
```
N(40)-P(20)-G(50)의 경로가 꺾여있고, U는 nil 노드이므로 BLACK입니다.
1. P(20)를 기준으로 좌회전합니다.
```
        50(B)
       /
     40(R)      <-- 이제 N이 됨 (CASE 3 형태로 변환)
    /
  20(R)
```
1. 이제 CASE 3의 형태로 바뀌었으므로 아래 방법으로 해결합니다.

결론

레드-블랙 트리의 삽입 과정은 다소 복잡해 보일 수 있지만, '삼촌 노드의 색상'을 기준으로 케이스를 나누고, 색상 변경(Recoloring)과 회전(Rotation)이라는 두 가지 도구를 적절히 사용하여 트리의 균형을 맞춘다는 핵심 원리를 이해하면 충분히 정복할 수 있습니다.

김민호

개발자를 꿈꾸고 있어요

이전 포스트