본 시리즈는 프로그래밍 자료구조의 개념을 정리하고 실습을 진행해보는 시리즈입니다.

• 실습은 다음과 같은 개발환경 및 버전에서 진행하였습니다.
  • IDE : IntelliJ IDEA (Ultimate Edition)
  • Java : JDK 21 (corretto-21)
  • Python : 3.9 (conda env)

트리(Tree) - Red-Black Tree (Part1)

• 일반적인 Tree에 대한 전반적인 내용들은 다음 포스팅에서 확인하실 수 있습니다.
  • [자료구조] Tree - 개요 (기본 개념과 구현)
• 이진트리에 대한 기본적인 내용들은 다음 포스팅에서 확인하실 수 있습니다.
  • [자료구조] Tree - Binary Tree (이진 트리) - 개념과 구현
• 이진탐색트리(BST)에 대한 전반적인 내용들은 다음 포스팅에서 확인하실 수 있습니다.
  • [자료구조] Tree - Binary Serach Tree (이진 탐색 트리) - 개념과 구현

1. Red-Black Tree란?

Red-Black Tree는 균형 이진 탐색 트리(Self-balancing Binary Search Tree)의 한 종류로, 삽입 및 삭제 연산이 발생할 때도 트리의 균형을 유지하여 탐색, 삽입, 삭제 등의 연산을 O(log n)의 시간 복잡도로 보장합니다.

• 레드-블랙 트리는 이진 탐색 트리에서 발생할 수 있는 최악의 경우 (한쪽으로 치우친 트리)를 방지하기 위해 고안된 트리입니다.

레드-블랙 트리는 AVL 트리와 마찬가지로 균형 유지를 목표로 하지만, AVL 트리보다 약간 덜 엄격한 방식으로 균형을 유지합니다.

• 이 덕분에 삽입과 삭제 시 연산량이 줄어들어, 실무에서는 AVL 트리보다 레드-블랙 트리가 더 많이 사용됩니다.

1.1 Red-Black Tree의 주요 특징

• 균형 유지: 레드-블랙 트리는 엄격한 균형이 아닌, 느슨한 균형을 유지합니다.

  • 트리의 높이가 어느 한쪽으로 지나치게 치우치지 않도록 설계되어 있으며, 최악의 경우에도 트리의 높이가 노드 수 n에 대해 2 * log(n+1)을 넘지 않습니다.

• 색상 규칙: 노드에 레드와 블랙 두 가지 색상 중 하나를 할당하여 트리의 균형을 관리합니다.

  • 노드의 색상에 따라 회전 또는 색상 변경을 수행하여 트리의 규칙을 만족시킵니다.

• 회전 연산: 레드-블랙 트리에서도 AVL 트리와 마찬가지로 LL 회전(Left-Left), RR 회전(Right-Right)과 같은 회전 연산을 통해 트리의 균형을 맞춥니다.

  • 삽입, 삭제 후 불균형이 발생할 때 회전과 색상 변화를 통해 균형을 유지합니다.

Red-Black Tree의 규칙:

레드-블랙 트리는 각 노드에 추가적인 색 정보(레드 또는 블랙)를 저장하며, 다음 규칙을 만족해야 합니다:

1. 노드 색상 규칙: 각 노드는 레드(Red) 또는 블랙(Black)입니다.
2. 루트 노드 규칙: 루트 노드는 항상 블랙입니다.
3. 리프 노드 규칙: 트리의 모든 리프 노드(NIL)는 블랙입니다.
   • NIL 노드는 실제 데이터가 없는 가상의 노드를 가리킵니다.
4. 레드-레드 규칙: 두 개의 연속된 레드 노드가 존재할 수 없습니다.
5. 경로 규칙: 각 노드에서 리프 노드(NIL)에 이르는 모든 경로는 같은 수의 블랙 노드를 포함해야 합니다.
   • 이를 블랙 높이(black-height)라고 합니다.

이러한 규칙들을 유지하면서 삽입과 삭제 시 트리의 불균형을 해결하기 위해 트리의 색상 변경과 회전 연산이 사용됩니다.

• 자세한 내용은 다음 섹션(Part 2)에서 정리합니다.

1.2 Red-Black Tree의 장단점과 주요 용도

장점:

• O(log n)의 성능 보장: 트리의 높이가 log n의 2배를 넘지 않으므로, 탐색, 삽입, 삭제 연산이 항상 O(log n)의 시간 복잡도를 보장합니다.
• 삽입/삭제 연산 효율성: 레드-블랙 트리는 균형을 맞추기 위한 회전 연산이 적게 발생합니다. 이는 삽입과 삭제가 빈번한 환경에서 AVL 트리보다 유리한 특징입니다.
• 데이터의 동적 관리: 레드-블랙 트리는 데이터 삽입과 삭제가 빈번한 상황에서도 트리의 높이가 지나치게 커지는 것을 방지하므로, 동적 데이터 관리에 적합합니다.

단점:

• 검색 성능: 레드-블랙 트리는 균형 유지가 덜 엄격하기 때문에, 검색 성능이 AVL 트리보다 약간 낮을 수 있습니다. 이는 AVL 트리가 더 정확하게 균형을 맞추기 때문입니다.
• 구현의 복잡성: 레드-블랙 트리의 색상 규칙과 회전 연산은 단순한 이진 탐색 트리보다 복잡하기 때문에, 구현에 시간이 더 소요됩니다.

주요 용도:

레드-블랙 트리는 삽입과 삭제가 빈번한 시스템에서 주로 사용됩니다. 다음과 같은 실무 환경에서 레드-블랙 트리가 자주 사용됩니다:

• Java의 TreeMap 및 TreeSet은 내부적으로 레드-블랙 트리를 사용하여 데이터 구조를 관리합니다.
• 데이터베이스 인덱싱에서 레드-블랙 트리는 데이터를 효율적으로 검색하고 삽입하는 데 도움을 줍니다.

2. Red-Black Tree의 규칙 및 삽입 연산

Red-Black Tree는 삽입과 삭제 시 균형을 유지하기 위해 색상 변경(Recoloring)과 회전(Rotation, Restructuring)을 사용합니다.

• 이 과정에서 트리는 특정 규칙들을 유지하며, 불균형 상태를 해결하기 위한 작업들이 수행됩니다.

2.1 Red-Black Tree의 규칙:

레드-블랙 트리는 각 노드에 추가적인 색 정보(레드 또는 블랙)를 저장하며, 다음 규칙을 만족해야 합니다:

1. 노드 색상 규칙:
   • 각 노드는 레드(Red) 또는 블랙(Black)입니다.
2. 루트 노드 규칙:
   • 루트 노드는 항상 블랙입니다.
3. 리프 노드 규칙:
   • 트리의 모든 리프 노드(NIL)는 블랙입니다.
   • NIL 노드는 실제 데이터가 없는 가상의 노드를 가리킵니다.
     (null과 유사한 의미라 생각하시면 됩니다)
4. 레드-레드 규칙:
   • 레드 노드의 자식은 항상 블랙입니다.
   • 즉, 두 개의 연속된 레드 노드가 존재할 수 없습니다.
5. 경로 규칙:
   • 각 노드에서 리프 노드(NIL)에 이르는 모든 경로는 같은 수의 블랙 노드를 포함해야 합니다.
   • 이를 블랙 높이(black-height)라고 합니다.

이 섹션에서는 삽입과 삭제 시 발생할 수 있는 상황과 트리의 균형을 맞추는 동작 원리를 설명합니다.

2.2 노드 삽입 시 동작

삽입 과정에서는 새로운 노드가 레드(Red)로 삽입되며, 이로 인해 트리의 레드-레드 규칙이 깨질 수 있습니다.

• 그래서 삽입 후에는 트리의 규칙을 유지하기 위해 색상 변경(Recoloring)과 회전 연산(Restructuring)이 필요할 수 있습니다.

2.2.1 삽입 시 기본 원칙

1. 새로운 노드는 항상 레드로 삽입됩니다.

   • 이렇게 하는 이유는 삽입 후 트리의 균형을 맞추기 위한 회전이나 색상 변경이 더 쉬워지기 때문입니다.

2. 삽입된 노드의 부모가 블랙인 경우:

   • 규칙 위반이 없으므로 더 이상의 작업이 필요하지 않습니다.
   • 트리의 규칙을 그대로 유지한 채 삽입이 완료됩니다.

3. 삽입된 노드의 부모가 레드인 경우:

   • 레드-레드 위반이 발생하며, 이를 해결하기 위해 색상 변경, 회전 연산 또는 두 가지를 모두 사용해야 합니다.

2.2.2 삽입 후 레드-레드 위반인 경우 발생할 수 있는 주요 케이스

1. 케이스 1: 부모의 형제가 레드인 경우 (색상 변경):
   • 삽입된 노드의 부모와 그 형제(삼촌 노드)가 모두 레드일 경우, 색상 변경이 필요합니다.
   • 해결 방법:
     • 부모 노드와 그 형제를 블랙으로 변경합니다.
     • 할아버지 노드를 레드로 변경하고, 해당 노드가 루트가 아니면 트리 위쪽으로 다시 균형을 맞춥니다.
     • 만약 루트가 레드로 바뀌면 마지막으로 다시 블랙으로 바꾸어 주면 됩니다.

2. 케이스 2: 부모의 형제가 블랙인 경우 (회전 필요):
   • 삽입된 노드의 부모는 레드이지만, 그 형제(삼촌 노드)는 블랙(혹은 NIL)일 경우 회전이 필요합니다.
     • LR 회전 또는 RL 회전과 같은 이중 회전이 발생할 수도 있으며, 회전 후에도 색상 변경으로 균형을 맞춥니다.
   • 회전 방식으로 설명드려도 되지만, 설명이 다소 직관적이진 않을 수 있어서 중간값을 올리는 방식으로 설명드리겠습니다. (이를 Restructuring이라 하는데, 어차피 같은 메커니즘입니다.)
     • 실제론 단일회전(LL,RR) 혹은 이중회전(LR, RL) 메커니즘이 적용되는데, 이와 관련해선 코드 구현 부분에서 다시 다룹니다.
   • 해결 방법 (중간값을 올리는 방식) :
     1. 단일 회전 (LL 또는 RR 회전):
        • 삽입된 노드와 부모 노드가 조부모 노드와 같은 방향에 있는 경우입니다.
        • 이때 부모 노드가 중간값이 되어 조부모의 자리에 올라가면서 블랙 노드가 되고, 삽입 노드와 조부모 노드는 올라간 부모 노드의 자식 노드로 다시 배치가 되며 레드 노드가 됩니다.
        • 재배치 후, 트리의 상위로 계속 올라가면서 루트까지 규칙을 확인하고, 필요하다면 추가적으로 색상 변경이나 회전이 이루어집니다.
          
     2. 이중 회전 (LR 회전 또는 RL 회전):
        • 삽입된 노드와 부모 노드가 조부모 노드와 반대 방향에 있는 경우입니다.
        • 이때는 삽입 노드가 중간값이 되어 조부모의 자리에 올라가면서 블랙 노드가 되고, 부모 노드와 조부모 노드는 올라간 삽입 노드의 자식 노드로 다시 배치가 되며 레드 노드가 됩니다.
        • 재배치 후, 트리의 상위로 계속 올라가면서 루트까지 규칙을 확인하고, 필요하다면 추가적으로 색상 변경이나 회전이 이루어집니다.
          

2.3 Red-Black Tree 삽입 연산 정리

• 공통적으로 삽입시 레드(RED) 노드를 적절한 위치에 삽입합니다.
  • 이때 레드(RED)-레드(RED) 규칙을 위반한 경우 다음 표에 정리된 방법으로 해결합니다.

경우	부모 노드 색상	형제(삼촌) 노드 색상	해결 방법
Case 1	레드 (Red)	레드 (Red)	색상 변경: 부모와 형제를 블랙으로, 조부모를 레드로 변경. 조부모가 루트가 아닐 경우 상위 노드로 색상 위반 문제 전파
Case 2-1 (단일 회전)	레드 (Red)	블랙 (Black) 혹은 NIL	단일 회전: 부모와 삽입된 노드가 조부모와 같은 방향에 있을 경우 단일 회전(LL 또는 RR)으로 재구조화 실시
Case 2-2 (이중 회전)	레드 (Red)	블랙 (Black) 혹은 NIL	이중 회전: 부모와 삽입된 노드가 조부모와 반대 방향에 있을 경우 이중 회전(LR 또는 RL)으로 재구조화 실시

3. 노드 삭제 시 동작 원리

Red-Black Tree의 삭제 과정은 삽입보다 복잡하며, 블랙 높이(Black Height)를 유지해야 하는 규칙 때문에 다양한 연산이 필요할 수 있습니다.

• 삭제 후에는 이중 블랙 문제(Double Black)가 발생할 수 있으며, 이러한 문제가 발생하면 이를 해결하기 위해 색상 변경(Recoloring)과 회전(Restructuring)이 필요합니다.

3.1 이중 블랙(Double Black) 문제란?

이중 블랙 문제는 주로 블랙 노드 삭제로 인해 발생하는 문제로, 트리의 균형을 유지하기 위한 규칙을 위반하는 상태입니다.

• Red-Black Tree에서 Root에서 NIL노드까지의 각 경로는 동일한 수의 블랙 노드를 가져야 합니다. 블랙 노드를 삭제하면 경로의 블랙 높이(Black Height)가 달라지며 트리의 균형이 깨질 수 있습니다.

이때 트리의 규칙을 유지하기 위해, 삭제된 블랙 노드의 자리에서 이중 블랙(Double Black)이 발생한 상태를 적용하는데, 이중 블랙은 다음과 같은 의미를 가집니다:

• 이중 블랙 상태는 노드를 삭제한 자리에서 블랙 높이 규칙을 맞추기 위해, 그 자리 또는 해당 노드를 추가적인 블랙 속성이 있는 것처럼 처리하는 상황을 말합니다.
  • 즉, 삭제된 블랙 노드의 자리가 블랙 높이를 맞추기 위해 추가적으로 블랙을 가져야 하는 상황입니다. (논리적으로 그 자리에 두 개의 블랙이 존재하는 것처럼 처리하는 것이지, 실제로 한 노드가 두 개의 블랙 속성을 가지는 것은 아닙니다.)

이중 블랙 상태에서는 추가적인 블랙 속성을 가질 수 있는 상태로 처리하며, 이를 해결하기 위해서는 색상 변경(Recoloring)과 회전(Rotation)과 같은 연산이 필요합니다.

3.2 노드 삭제 시 기본 원칙

노드를 삭제할 때는 실제로 삭제되는 노드의 색상에 따라 트리의 균형을 맞추는 방식이 달라집니다.

• 여기서는 실제로 삭제되는 노드의 색상이 중요한 역할을 합니다.

3.2.1 삭제할 노드가 두 자식을 가지는 경우

• 두 자식 노드를 가진 경우에서는 후계자 노드의 값을 삭제할 노드의 위치로 복사합니다.
  • 이때 후계자의 색상은 복사되지 않고, 후계자 값(혹은 Entry의 Key와 Value)만 복사됩니다.
  • 이후 실제 삭제 대상의 위치는 후계자 자리가 됩니다.

• 후계자가 Red든 Black이든 후계자 자리에서 삭제가 이루어지며, 후계자가 Black이면 이중 블랙 문제가 발생할 수 있습니다.
  • 후계자가 Red면, 단순히 지우기만 하면 됩니다. (아래 3.2.2 파트의 경우에 해당합니다)

3.2.2 실제로 삭제되는 노드가 Red인 경우

• Red 노드를 삭제하는 경우, 트리의 균형에 큰 영향을 미치지 않으므로 추가적인 조치가 필요하지 않습니다.

• Red 노드는 자식이 없는 리프 노드이거나, Red 노드를 후계자로 설정한 경우에도 특별한 조치 없이 바로 삭제가 가능합니다.

3.2.3 실제로 삭제되는 노드가 Black인 경우

• Black 노드를 삭제하면 이중 블랙 문제가 발생할 수 있습니다. 이 문제는 블랙 높이를 맞추기 위해 추가적인 블랙이 필요하게 되는 상황입니다.

• 이중 블랙 상태는 해당 노드나 자리에서 추가적인 블랙 속성이 적용된 상태를 말하며, 이를 해결하기 위해 색상 변경과 회전 연산을 사용하여 트리의 균형을 맞춰야 합니다.

중요한 점:

• 삭제할 노드가 리프 노드가 아닌 경우, 후계자의 값을 복사한 후 후계자 자리에서의 색상을 확인해야 합니다.
• 후계자의 색상이 Black일 경우, 이중 블랙 문제가 발생할 수 있으며, 이를 해결하기 위한 추가적인 연산이 필요합니다.

3.3 블랙 노드 삭제시 이중 블랙 문제 해결

블랙 노드를 삭제할 때 발생하는 이중 블랙 문제는 트리의 균형을 유지하기 위해 반드시 해결해야 하는 문제입니다.

• 이 문제는 트리의 블랙 높이 규칙을 위반하는 상태를 나타내며, 색상 변경과 회전을 통해 해결됩니다.

해결 방법은 형제 노드와 그 자식(조카 노드)들의 색상에 따라 달라지며, 크게 세 가지 경우로 나뉩니다.
1. 형제 노드가 레드(Red)일 경우
2. 형제 노드가 블랙(Black)이고, 형제의 자식(조카)들이 모두 블랙(Black)일 경우
3. 형제 노드가 블랙(Black)이고, 형제의 자식(조카)들 중 하나 이상이 레드(Red)일 경우

참고로 형제 노드는 Sibling Node라 부르고, 조카 노드는 Nephew Node라 부르며, 이 용어는 Red-Black Tree의 균형 복구 알고리즘에서 공식적으로 사용되는 용어입니다.

Case 1. 형제 노드가 레드(Red)인 경우

형제 노드가 레드인 경우, 이중 블랙 문제를 해결하기 위한 첫 번째 단계는 형제 노드를 블랙으로, 부모 노드를 레드로 색상 변경한 후, 회전을 통해 트리 구조를 재정렬하는 것입니다.

• 하지만 이 과정이 끝난 뒤에도 트리가 완전히 정상 상태로 돌아오지 않을 수 있으며, 추가적인 처리가 필요할 수 있습니다.

해결 과정:

1. 형제 노드를 블랙으로, 부모 노드를 레드로 변경

   • 형제 노드가 레드라면 부모 노드는 블랙이어야 합니다. 이때 형제 노드를 블랙으로 바꾸고, 부모 노드를 레드로 변경하여 트리의 균형을 맞추는 첫 번째 단계가 진행됩니다.

   • 예시: 주어진 트리에서 형제 노드 35가 레드이고, 부모 노드 25는 블랙입니다.

     • 먼저 형제 노드 35를 블랙으로, 부모 노드 25를 레드로 색상 변경합니다.

2. 회전을 수행하여 트리 재구조화

   • 색상 변경 후, 트리의 균형을 맞추기 위해 회전 연산을 수행합니다.

   • 형제 노드가 부모 노드의 오른쪽 자식일 경우 왼쪽 회전(Left Rotation)을, 왼쪽 자식일 경우 오른쪽 회전(Right Rotation)을 수행하여 트리를 재구성합니다.

     • 쉽게 말해서 형제 -> 부모 방향으로 회전한다는 것입니다.

   • 예시: 이 트리에서 형제 노드 35는 부모 노드 25의 오른쪽 자식입니다. 따라서 왼쪽 회전(Left Rotation)을 수행하여 트리의 구조를 재정렬합니다.

     • 회전 후, 형제 노드였던 35가 부모 노드 25의 자리를 차지하고, 부모였던 25는 35의 왼쪽 자식으로 이동하게 됩니다.

3. 회전 후 남은 이중 블랙 상태 처리

   • 회전이 완료된 후에도 이중 블랙 상태는 해결되지 않았습니다. 이 시점에서 새로운 형제 노드와 이중 블랙이 적용된 노드의 관계에 따라 추가적인 처리가 필요합니다.

   • 예시: 회전 후, 이중 블랙 상태가 적용된 자리(10의 자리)는 NIL 노드가 되어있고, 그 새로운 형제는 이제 노드 30입니다. 이때 NIL 노드와 형제 노드(30)의 관계를 분석해야 합니다.

     • 형제 노드 30의 색상과 자식 노드들의 상태를 기반으로 추가적인 색상 변경 또는 회전이 필요합니다.

   • 새로운 형제가 블랙이고, 자식들이 모두 블랙이라면 형제 노드를 레드로 바꾸고 상위로 이중 블랙을 전파해야 할 수 있습니다. (Case 2에 해당하는 경우 입니다.)

   • 반면, 새로운 형제가 블랙이고 자식 중 하나가 레드라면 추가 회전으로 이중 블랙을 해결할 수 있습니다. (Case 3에 해당하는 경우입니다.)

Case 2. 형제 노드가 블랙(Black)이고, 형제의 자식(조카)들이 모두 블랙(Black)일 경우

형제 노드와 자식들(조카 노드들)이 모두 블랙인 경우, 이중 블랙 문제를 해결하기 위한 첫 단계는 형제 노드를 레드로 변경하는 것입니다.

• 그 이후엔 부모 쪽으로 이중 블랙 문제를 전파하여 부모의 형제(삼촌 노드)와의 관계에 따라 Case를 반복하게 됩니다.

해결 과정:

1. 형제 노드를 레드로 변경

   • 형제 노드가 블랙이고, 자식(조카 노드)들이 모두 블랙이라면, 이 상황에서 형제 노드를 레드로 변경하고 이중 블랙 상태를 상위로 전파하는 것이 필요합니다.
   • 예시: 주어진 트리에서 형제 노드 30과 그 자식(NIL 노드들)이 모두 블랙입니다. 이 상황에서 형제 노드 30을 레드로 변경하여 블랙 높이를 맞춥니다.

2. 상위로 이중 블랙 문제 전파

   • 형제 노드를 레드로 바꾼 후에도, 부모 노드에서 여전히 이중 블랙 문제가 남아있을 수 있습니다. 이 경우, 이중 블랙 문제는 상위로 전파되며 부모 노드 25가 이를 처리해야 합니다.
   • 예시: 부모 노드 25가 레드 상태로 남아 있습니다. 부모 노드와 삼촌 노드(40)와의 관계를 따져 Case에 따라 이중 블랙 문제가 해결을 반복하게 됩니다.

3. 트리 상태 확인

   • 전파 후 부모 노드가 레드라면, 추가 작업 없이 블랙으로 색상을 변경하면 높이가 맞춰져서 트리는 정상 상태로 돌아옵니다. 더 이상 추가적인 연산은 필요하지 않으며, 이 시점에서 트리의 균형이 만족된 상태가 됩니다.
   • 예시: 부모 노드 25는 레드 상태이고, 이 상태에서 블랙으로 색상을 변경하게 되면 트리의 블랙 높이 규칙이 맞춰집니다.

Case 3. 형제 노드가 블랙(Black)이고, 형제의 자식(조카)들 중 하나 이상이 레드(Red)일 경우

형제 노드가 Black이고 조카 노드 중 하나 이상이 Red인 경우에는 트리의 균형을 맞추기 위해 색상 변경과 회전이 필요합니다.

• 이때, 형제와 조카의 위치에 따라 추가 회전이 필요한지 여부가 결정됩니다.

Case 3-1. 형제와 반대 방향에 있는 조카만 Red인 경우

부모 노드 기준 형제 노드의 방향과 반대 방향에 Red 조카 노드가 있는 경우, 중간에 추가 회전이 필요합니다.

• 쉽게 말해서 부모를 기준으로 부모 노드->형제 노드->조카 Red 노드가 LR 혹은 RL인 경우입니다.

• 형제 노드가 두개의 자식 Red를 가지거나, LL, RR과 같은 형태라면 추가 회전 없이 바로 최종 회전 단계로 넘어갑니다. (이러한 Case를 3-2 케이스로 이어서 설명합니다)

해결 과정:

1. 조카와 형제의 색상 변경

   • RED 조카 → BLACK, BLACK 형제 → RED로 색상을 변경합니다.

   • 예시: 형제 노드 60을 RED로, 조카 노드 65를 BLACK으로 변경합니다.

2. 추가 회전 (형제 방향으로 회전)

   • 형제 노드가 부모의 왼쪽(L)에 있으면 좌회전(Left Rotation), 오른쪽(R)에 있으면 우회전(Right Rotation)을 형제 노드 중심으로 수행합니다.

   • 예시: 형제 노드 60를 중심으로 왼쪽 회전을 수행합니다.

3. (Case 3 공통) 형제, 부모, 조카의 색상 변경

   • 형제의 색상을 부모의 색상으로 교체합니다.

     • 최종 회전 이후 형제 노드가 부모 자리로 오기 때문에, 이를 맞춰주기 위해 형제 노드의 색상을 부모의 색상으로 미리 바꾸어 주는 것입니다.

   • 이후 부모 노드와 부모 기준 같은 방향의 조카(LL, RR)를 BLACK으로 변경합니다.

   • 예시 :

     • 새로운 형제 노드 65를 부모 노드 75의 색상 BLACK으로 변경합니다.
     • 이후에 부모 노드 75와 조카 노드 60의 색상을 BLACK으로 변경합니다.

4. 최종 회전 (반대 방향으로 회전)

   • 마지막으로, 형제 노드가 부모의 왼쪽(L)에 있으면 우회전(Right Rotation), 오른쪽(R)에 있으면 좌회전(Left Rotation)을 부모 노드 중심으로 수행합니다.
     • 즉, 부모기준 형제노드의 방향과 반대쪽으로 최종 회전을 수행합니다.
   • 예제에서는 오른쪽 회전(Right Rotation)을 수행하여 마무리합니다.

Case 3-2. 형제와 같은 방향에 Red인 조카가 있는 경우

부모 노드 기준 형제와 같은 방향에 레드 조카가 있는 경우, 추가 회전이 필요하지 않으며, 색상 변경과 최종 회전만 수행됩니다.

해결 과정:

3. (Case 3 공통) 형제, 부모, 조카의 색상 변경

   • 형제의 색상을 부모의 색상으로 교체합니다.

     • 최종 회전 이후 형제 노드가 부모 자리로 오기 때문에, 이를 맞춰주기 위해 형제 노드의 색상을 부모의 색상으로 미리 바꾸어 주는 것입니다.

   • 이후 부모 노드와 부모 기준 같은 방향의 조카(LL, RR)를 BLACK으로 변경합니다.

   • 예시 :

     • 형제 노드 60를 부모 노드 75의 색상 BLACK으로 변경합니다.
     • 이후에 부모 노드 75와 조카 노드 55의 색상을 BLACK으로 변경합니다.

4. 최종 회전 (반대 방향으로 회전)

   • 마지막으로, 형제 노드가 부모의 왼쪽(L)에 있으면 우회전(Right Rotation), 오른쪽(R)에 있으면 좌회전(Left Rotation)을 부모 노드 중심으로 수행합니다.
     • 즉, 부모기준 형제노드의 방향과 반대쪽으로 최종 회전을 수행합니다.
   • 예제에서는 오른쪽 회전(Right Rotation)을 수행하여 마무리합니다.

3.4 Red-Black Tree 삭제 연산 정리

Red-Black Tree에서 노드를 삭제하는 과정은 트리의 균형을 유지하기 위해 몇 가지 규칙을 따라야 하며, 특히 블랙 높이(Black Height)가 중요한 역할을 합니다.

1. 삭제할 노드가 두 자식을 가지는 경우에는 후계자의 값을 삭제할 노드 위치로 복사하고, 후계자 자리를 삭제합니다. 이때 후계자가 블랙 노드라면 이중 블랙 문제가 발생할 수 있습니다.

2. Red 노드를 삭제할 때는 트리의 균형에 영향을 미치지 않으므로 추가적인 조치가 필요하지 않습니다.

3. Black 노드를 삭제할 때는 이중 블랙 문제가 발생할 수 있으며, 이는 블랙 높이 규칙을 위반한 상태입니다. 이를 해결하기 위해서는 형제 노드와 그 자식들의 색상을 고려해 색상 변경과 회전을 통해 트리의 균형을 맞춰야 합니다.

이중 블랙 문제 해결 (3.3)

경우	형제 노드 색상	조카 노드 상태	해결 방법
Case 1	레드 (Red)	상관없음	형제를 블랙으로, 부모를 레드로 색상 변경 후 부모 기준 회전
Case 2	블랙 (Black)	모두 블랙 (Black)	형제를 레드로 변경 후 이중 블랙을 부모로 전파
Case 3-1	블랙 (Black)	반대 방향의 조카가 레드	조카를 블랙으로, 형제를 레드로 색상 변경 후 형제 기준 회전 및 Case 3-2 수행
Case 3-2	블랙 (Black)	같은 방향의 조카가 레드	형제, 부모, 조카의 색상 변경 후 부모 기준 회전

이러한 규칙과 과정을 통해 트리의 균형을 유지하며, 삭제 후에도 O(log n)의 성능을 보장할 수 있습니다.

마무리

이번 포스팅에서는 Red-Black Tree의 개념과 주요 특징, 그리고 삽입 및 삭제 시 발생할 수 있는 다양한 문제와 그 해결 방법을 다루었습니다.

• 레드-블랙 트리는 실무에서도 자주 쓰이는 균형 잡힌 이진 탐색 트리로, 특히 삽입과 삭제가 빈번하게 발생하는 시스템에서 효율적으로 사용됩니다.

  • Java의 TreeMap, TreeSet과 같은 컬렉션 프레임워크에서 레드-블랙 트리가 사용되고 있으며, 그 성능과 안정성을 보장합니다.

• 삽입 연산에서는 레드-레드 위반을 해결하기 위해 색상 변경과 회전 연산을 활용하여 트리의 규칙을 유지하는 과정을 살펴보았습니다.

• 삭제 연산에서는 이중 블랙 문제가 발생할 때, 형제와 조카 노드의 색상에 따라 트리의 균형을 맞추는 방법을 Case 1, 2, 3로 나누어 분석하였습니다.

  1. 형제 노드가 레드(Red)일 경우
  2. 형제 노드가 블랙(Black)이고, 형제의 자식(조카)들이 모두 블랙(Black)일 경우
  3. 형제 노드가 블랙(Black)이고, 형제의 자식(조카)들 중 하나 이상이 레드(Red)일 경우
     • 특히 Case 3에서 형제와 조카의 위치에 따라 추가 회전이 필요한 경우와 그렇지 않은 경우를 구체적으로 다루어 보았습니다.

다음 포스팅에서는 Red-Black Tree의 실제 구현을 살펴보며, Java와 Python에서 레드-블랙 트리를 직접 코드로 구현해보는 실습을 진행할 예정입니다.