[c언어] Red-Black Tree 구현하기

🔎 Red-Black Tree란?

• self-balancing binary search tree의 일종이다.

• 각 노드 당 한 비트의 추가 기억 공간을 가지는데, 이 비트는 노드의 색상 정보를 빨간색 또는 검은색으로 저장한다.

• 루트에서 리프까지의 경로에 나타나는 노드의 색깔을 제한함으로써 경로 중 어떠한 것도 다른 것보다 두 배 이상 길지 않음을 보장하게 되어 근사적으로 균형을 이룬 트리가 된다.

• 트리를 self-balancing 하게 만들어주어 검색, 삽입, 삭제 연산을 모두 O(log n)의 시간 복잡도를 보장하며, 이진 탐색 트리와 달리 최악의 경우에도 균형이 깨지지 않도록 보장한다.

🚨 Red-Black Tree의 규칙
1. 모든 노드는 빨강 또는 검정색이다.
2. 루트 노드는 검정색이다.
3. 모든 리프 노드는 검정색이다. (NIL 노드를 리프 노드로 취급한다.)
4. 빨강색 노드의 부모 노드와 자식 노드는 모두 검정색이다.
5. 어떤 노드에서 시작하여 해당 노드의 하위 트리에 속한 모든 경로는, 해당 노드에서부터 시작하여 리프 노드까지 이동하는 모든 경로와 같은 수의 검정색 노드를 가진다.
이를 RBT의 "균형" 조건이라고 한다.

1. Tree 생성

1) tree 구조체 동적 할당

• 여러 개의 tree를 생성할 수 있어야 하며 각각 다른 내용들을 저장할 수 있어야 한다.

2) nil 노드 생성 및 초기화

• RB tree에서 리프 노드는 nil 노드로 표시한다.

• nil 노드는 일종의 가상 노드로서, 트리에서 실제로 존재하지 않는 노드이다.

• 일반 노드와는 다르게 key, parent, left, right 등의 필드는 의미를 가지지 않으며, 색깔은 항상 BLACK이다.

• nil 노드를 트리의 리프 노드들에 대한 포인터로 간주하고, 키를 가지는 정상적인 노드들만을 트리의 내부 노드로 간주한다.

🙄 nil 노드를 활용하는 이유
(1) 효율적인 메모리 사용

• 보통의 BST에서는 NULL leaf를 사용하여 리프 노드를 표현한다. 그러나 모든 리프 노드가 하나의 NULL 값을 가지게 되면, 메모리 공간이 낭비된다.
  ex) 10,000개의 노드를 가지면, 약 5,000개의 NULL 값을 가지게 되어 메모리 공간이 크게 낭비된다.
• 반면에 nil 노드를 사용하여 리프 노드를 표현하면, 모든 리프 노드가 하나의 nil 노드를 가리키게 되어 메모리 공간을 절약할 수 있다.

(2) 노드 탐색 작업 단순화

• 리프 노드를 구별하는 데 활용할 수 있다.

• 💻 Tree 생성 CODE

/* 1️⃣ RB tree 구조체 생성 */

// tree를 구현하기 위한 구조체와 열거형을 정의
typedef enum { RBTREE_RED, RBTREE_BLACK } color_t;

typedef int key_t; // 각 노드에 저장되는 값의 데이터 형식 정의

typedef struct node_t { // tree의 각 노드를 표현하는 구조체
  color_t color;
  key_t key;
  struct node_t *parent, *left, *right;
} node_t;

typedef struct { // tree 자체를 나타내는 구조체
  node_t *root;
  node_t *nil;  // for sentinel
} rbtree;


// 새 트리를 생성하는 함수
rbtree *new_rbtree(void)
{
  // tree 구조체 동적 할당
  rbtree *t = (rbtree *)calloc(1, sizeof(rbtree));

  // nil 노드 생성 및 초기화
  node_t *nil = (node_t *)calloc(1, sizeof(node_t));
  nil->color = RBTREE_BLACK; // nil 노드는 항상 BLACK

  // tree의 nil과 root를 nil 노드로 설정 (tree가 빈 경우 root는 nil노드여야 한다.)
  t->nil = t->root = nil;

  return t;
}

2. Tree 삭제

1) 각 노드의 메모리 반환

• 루트 노드부터 시작하여 각 노드의 자식 노드를 순회하면서 모든 노드의 메모리를 반환한다.

• 노드의 자식 노드가 nil 노드가 아니면, 해당 자식 노드를 루트로 하여 재귀적으로 함수를 호출한다.

2) nil 노드와 tree의 메모리 반환

• 모든 노드 삭제 후 nil 노드와 tree 구조체의 메모리를 반환한다.

• 💻 Tree 삭제 CODE

/* 2️⃣ RB tree 구조체가 차지했던 메모리 반환 */

// 트리를 순회하면서 각 노드의 메모리를 반환하는 함수
void delete_rbtree(rbtree *t)
{
  node_t *node = t->root;
  if (node != t->nil)
    traverse_and_delete_node(t, node);

  // nil 노드와 rbtree 구조체의 메모리를 반환
  free(t->nil);
  free(t);
}

// 각 노드와 그 자식 노드들의 메모리를 반환하는 함수
void traverse_and_delete_node(rbtree *t, node_t *node)
{
  if (node->left != t->nil)
    traverse_and_delete_node(t, node->left);
  if (node->right != t->nil)
    traverse_and_delete_node(t, node->right);

  // 현재 노드의 메모리를 반환
  free(node);
}

3. key 추가

1) 새 노드 생성

• 새 노드를 동적으로 생성한다.

• 노드의 key를 입력받고, color를 RED로, 자식 노드들은 nil 노드로 설정한다.

• 이미 같은 key의 값이 존재해도 하나 더 추가 한다. (multiset)

2) 새 노드를 삽입할 위치 탐색

• 루트 노드부터 탐색을 시작하여 탐색 중인 노드보다 key값이 작은 경우 왼쪽 자식으로, 큰 경우 오른쪽 자식으로 이동한다.

• 탐색 중인 노드의 자식 노드가 nil 노드인 경우, 새 노드를 해당 자식 노드로 추가하고, 반복문을 종료한다.

• 반복문 종료 후 새 노드의 부모를 지정한다.

• 💻 새 노드 생성, 위치 탐색 CODE
  

    /* 3️⃣ key 추가 */
    
    // 노드를 삽입하고 불균형을 복구하는 함수
    node_t *rbtree_insert(rbtree *t, const key_t key)
    {
      // 새 노드 생성
      node_t *new_node = (node_t *)calloc(1, sizeof(node_t));
      new_node->key = key;
      new_node->color = RBTREE_RED;              // 항상 레드로 추가
      new_node->left = new_node->right = t->nil; // 추가한 노드의 자식들을 nil 노드로 설정
    
      // 새 노드를 삽입할 위치 탐색
      node_t *current = t->root;
      while (current != t->nil)
      {
        if (key < current->key)
        {
          if (current->left == t->nil)
          {
            current->left = new_node; // 새 노드를 왼쪽 자식으로 추가
            break;
          }
          current = current->left;
        }
        else
        {
          if (current->right == t->nil)
          {
            current->right = new_node; // 새 노드를 오른쪽 자식으로 추가
            break;
          }
          current = current->right;
        }
      }
    
      new_node->parent = current; // 새 노드의 부모 지정
    
      // root가 nil이면(트리가 비어있으면) 새 노드를 트리의 루트로 지정
      if (current == t->nil)
        t->root = new_node;
    
      // 불균형 복구
      rbtree_insert_fixup(t, new_node);
    
      return new_node;
    }

3) 불균형 복구

• 노드 삽입 후, 삽입으로 인한 불균형을 해결한다.

• 새로 삽입된 노드는 항상 RED 색상으로 삽입되는데, 새로 삽입된 노드의 부모 노드가 RED인 경우, RB tree의 규칙을 위반하게 되어 불균형이 발생한다.

• 이 불균형을 해결하기 위해 총 3가지 CASE로 나누어 처리한다.
  

🔥 불균형 CASE 1 ~ 3

[CASE 1] 삼촌 노드가 RED인 경우

• 부모 노드와 삼촌 노드를 BLACK으로 변경한다.
• 조부모 노드를 RED로 변경한다.
• 조부모 노드 에서 불균형이 발생할 수 있으므로, 조부모 노드 를 추가된 노드로 설정하고 불균형 복구 함수를 재귀적으로 호출한다.

[CASE 2] 삼촌 노드가 BLACK & 부모 노드와 새 노드가 Left/Right 자식인 경우

• 부모 노드를 기준으로 Right/Left 회전을 수행한다.
• 부모 노드와 형제 노드의 색상을 바꾼다.

[CASE 3] 삼촌 노드가 BLACK & 부모 노드가 Left/Right 자식 & 새 노드가 Right/Left 자식인 경우

• 새 노드를 기준으로 Left/Right 회전을 수행한 후 Right/Left 회전을 수행한다.
• 새 노드와 자식 노드의 색상을 바꾼다. (자식 노드는 회전 수행 후 생긴 자식이다.)

• 💻 불균형 복구 CODE

// 노드 삽입 후 불균형을 복구하는 함수
void rbtree_insert_fixup(rbtree *t, node_t *node)
{
  node_t *parent = node->parent;
  node_t *grand_parent = parent->parent;
  node_t *uncle;
  int is_left = node == parent->left; // 현재 노드가 왼쪽 자식인지 여부
  int is_parent_is_left;              // 부모가 왼쪽 자식인지 여부

  // 추가된 노드가 root 노드인 경우: 색만 변경
  if (node == t->root)
  {
    node->color = RBTREE_BLACK;
    return;
  }

  // 부모가 BLACK인 경우: 변경 없음
  if (parent->color == RBTREE_BLACK)
    return;

  is_parent_is_left = grand_parent->left == parent;
  uncle = (is_parent_is_left) ? grand_parent->right : grand_parent->left;

  // [CASE 1]: 부모와 부모의 형제가 모두 RED인 경우
  if (uncle->color == RBTREE_RED)
  {
    parent->color = RBTREE_BLACK;
    uncle->color = RBTREE_BLACK;
    grand_parent->color = RBTREE_RED;
    rbtree_insert_fixup(t, grand_parent);
    return;
  }

  if (is_parent_is_left)
  {
    if (is_left)
    // [CASE 2]: 부모의 형제가 BLACK & 부모가 왼쪽 자식 & 현재 노드가 왼쪽 자식인 경우
    {
      right_rotate(t, parent);
      exchange_color(parent, parent->right);
      return;
    }

    // [CASE 3]: 부모의 형제가 BLACK & 부모가 왼쪽 자식 & 현재 노드가 오른쪽 자식인 경우
    left_rotate(t, node);
    right_rotate(t, node);
    exchange_color(node, node->right);
    return;
  }

  if (is_left)
  {
    // [CASE 3]: 부모의 형제가 BLACK & 부모가 오른쪽 자식 & 현재 노드가 왼쪽 자식인 경우
    right_rotate(t, node);
    left_rotate(t, node);
    exchange_color(node, node->left);
    return;
  }

  // [CASE 2]: 부모의 형제가 BLACK & 부모가 오른쪽 자식 & 현재 노드가 오른쪽 자식인 경우
  left_rotate(t, parent);
  exchange_color(parent, parent->left);
}

4) Right 회전, Left 회전

• 매개변수로 들어온 기준 노드를 기준으로 오른쪽/왼쪽으로 회전시킨다.

• 기준 노드: 회전 후 부모 노드의 자리를 대체하게 되는 노드

🔁 오른쪽으로 회전하기
1. 부모 변경 node의 부모를 grand_parent로 변경한다.
자식 변경 node를 grand_parent의 자식으로 변경한다. (양방향 연결)
2. 부모 변경 parent의 부모를 node로 변경한다.
자식 변경 parent를 node의 자식으로 변경한다. (양방향 연결)
3. 부모 변경 node_right_child의 부모를 parent로 변경한다.
자식 변경 node_right_child를 parent의 자식으로 변경한다. (양방향 연결)
(node_left_child는 그대로 node의 왼쪽 자식으로 남는다.)
💡왼쪽 회전인 경우는 3에서 node_left_child의 부모를 변경한다는 점만 다르다.

• 💻 Right 회전, Left 회전 CODE
  

    // 오른쪽으로 회전하는 함수
    void right_rotate(rbtree *t, node_t *node)
    {
      node_t *parent = node->parent;
      node_t *grand_parent = parent->parent;
      node_t *node_right = node->right;
    
      // 부모가 루트인 경우: 현재 노드를 루트로 지정 (노드를 삭제한 경우만 해당)
      if (parent == t->root)
        t->root = node;
      else
      { // 1-1) 노드의 부모를 grand_parent로 변경
        if (grand_parent->left == parent)
          grand_parent->left = node;
        else
          grand_parent->right = node;
      }
      node->parent = grand_parent; // 1-2) 노드를 grand_parent의 자식으로 변경 (양방향 연결)
      parent->parent = node;       // 2-1) parent의 부모를 노드로 변경
      node->right = parent;        // 2-2) parent를 노드의 자식으로 변경 (양방향 연결)
      node_right->parent = parent; // 3-1) 노드의 자식의 부모를 parent로 변경
      parent->left = node_right;   // 3-2) 노드의 자식을 부모의 자식으로 변경 (양방향 연결)
    }
    ```
    
    ```c
    // 왼쪽으로 회전하는 함수
    void left_rotate(rbtree *t, node_t *node)
    {
      node_t *parent = node->parent;
      node_t *grand_parent = parent->parent;
      node_t *node_left = node->left;
    
      // 부모가 루트인 경우: 현재 노드를 루트로 지정 (노드를 삭제한 경우만 해당)
      if (parent == t->root)
        t->root = node;
      else
      { // 1-1) 노드의 부모를 grand_parent로 변경
        if (grand_parent->left == parent)
          grand_parent->left = node;
        else
          grand_parent->right = node;
      }
      node->parent = grand_parent; // 1-2) 노드를 grand_parent의 자식으로 변경 (양방향 연결)
      parent->parent = node;       // 2-1) parent의 부모를 노드로 변경
      node->left = parent;         // 2-2) parent를 노드의 자식으로 변경 (양방향 연결)
      parent->right = node_left;   // 3-1) 노드의 자식의 부모를 parent로 변경
      node_left->parent = parent;  // 3-2) 노드의 자식을 부모의 자식으로 변경 (양방향 연결)
    }

4. 탐색

1) key 탐색

• tree내에 해당 key가 있는지 탐색하여 해당 노드의 포인터를 반환한다.

• 해당하는 node가 없으면 NULL을 반환한다.

• 루트 노드를 시작으로 current 포인터를 설정한다.

• current의 key값과 찾으려는 key값을 비교하며 노드를 이동시키면서 key값과 같은 노드를 찾는다.

• 시간 복잡도: 탐색 시 자식 노드의 수가 항상 2개로 제한되기 때문에, 한 단계씩 이동할 때마다 검색 대상 노드의 수가 절반으로 줄어들게 되어 시간 복잡도는 $O(log n)$이 된다.

• 💻 key 탐색 CODE
  

/* 4️⃣ 탐색 1 - key 탐색 */

// key에 해당하는 노드를 반환하는 함수
node_t *rbtree_find(const rbtree *t, const key_t key)
{
  node_t *current = t->root;
  while (current != t->nil)
  {
    if (key == current->key)
      return current;
    else
      current = (key < current->key) ? current->left : current->right;
  }
  return NULL; // 해당 key값을 가진 노드가 없을 경우 NULL 반환
}

2) 최소값/최대값 탐색

• 루트 노드를 시작으로 current 포인터를 설정한다.

• current 노드의 왼쪽/오른쪽 자식 노드가 nil 노드가 아닐 때까지 반복하여, current 노드를 왼쪽/오른쪽 자식 노드로 업데이트한다.

• current 노드는 tree에서 가장 작은/큰 key 값을 가진 노드가 되므로 current 노드를 반환한다.

• 시간 복잡도: 트리의 높이만큼 반복되므로 시간 복잡도는 $O(log n)$이 된다.

• 💻 최소값/최대값 탐색 CODE
  

/* 4️⃣ 탐색 2 - 최소값을 가진 node 탐색 */

// key가 최소값에 해당하는 노드를 반환하는 함수
node_t *rbtree_min(const rbtree *t)
{
  node_t *current = t->root;
  while (current->left != t->nil)
    current = current->left;
  return current;
}

/* 4️⃣ 탐색 3 - 최대값을 가진 node 탐색 */

// key가 최대값에 해당하는 노드를 반환하는 함수
node_t *rbtree_max(const rbtree *t)
{
  node_t *current = t->root;
  while (current->right != t->nil)
    current = current->right;
  return current;
}

5. array로 변환

• RB tree의 내용을 key 순서대로 주어진 array로 변환한다.

• array의 크기는 n으로 주어지며 tree의 크기가 n 보다 큰 경우에는 순서대로 n개 까지만 변환한다.

• rbtree_min() 함수를 호출하여 가장 작은 값을 가진 노드를 시작으로 current 포인터를 설정한다.

• 루프를 돌면서 current 노드를 **get_next_node** 함수를 활용해 inorder traversal 하면서 다음 노드를 가져와서 key 값을 arr에 저장한다.

• 루프를 n번 반복하거나 current가 더 이상 존재하지 않을 때까지 반복한다.

• 💻 array로 변환 CODE
  

/* 5️⃣ array로 변환 */

// `t`를 inorder로 `n`번 순회한 결과를 `arr`에 담는 함수
int rbtree_to_array(const rbtree *t, key_t *arr, const size_t n)
{
  node_t *current = rbtree_min(t);
  arr[0] = current->key;
  for (int i = 1; i < n; i++)
  {
    if (current == t->nil)
      break;                             // 노드가 끝까지 탐색된 경우 loop 탈출
    current = get_next_node(t, current); // 다음 노드로 이동
    if (current == t->nil)
      break;               // 노드가 끝까지 탐색된 경우 loop 탈출
    arr[i] = current->key; // 현재 노드의 key 값을 배열에 저장
  }
  return 0;
}

1) inorder traversal

• **get_next_node** 함수를 활용해 다음 노드를 찾아서 inorder traversal을 수행한다.

get_next_node

• p 노드의 오른쪽 자식 노드를 시작으로 current 포인터를 설정한다.

• p 노드의 오른쪽 자식 노드가 없다면 current 변수를 p 노드로 초기화하고, while
  루프를 통해 다음과 같이 작업한다.

  • current 노드가 부모 노드의 오른쪽 자식 노드인 경우, 부모 노드로 이동한다.
  • current 노드가 부모 노드의 왼쪽 자식 노드인 경우, 부모 노드를 반환한다.

• current 노드의 왼쪽 자식 노드가 없을 때까지 current 노드를 왼쪽 자식 노드로 업데이트한다.

• 최종적으로 current 노드를 반환한다.

• 💻 get_next_node CODE
  

// 키 값을 기준으로 다음 노드를 반환하는 함수
node_t *get_next_node(const rbtree *t, node_t *p)
{
  node_t *current = p->right;
  if (current == t->nil) // 오른쪽 자식이 없으면
  {
    current = p;
    while (1)
    {
      if (current->parent->right == current) // current가 오른쪽 자식인 경우
        current = current->parent;           // 부모 노드로 이동 후 이어서 탐색
      else
        return current->parent; // current가 왼쪽 자식인 경우 부모 리턴
    }
  }
  while (current->left != t->nil) // 왼쪽 자식이 있으면
    current = current->left;      // 왼쪽 끝으로 이동
  return current;
}

6. Node 삭제

1) 삭제할 노드를 대체할 노드 찾기

• 삭제할 키를 가진 노드인 delete를 삭제하면 해당 노드가 삭제되고, 삭제된 자리에 다른 노드가 채워지게 된다.

• delete를 대체하면서 사라지는 노드를 remove, remove의 자식이던 노드를 replace_node로 정한다.

• replace_node가 remove의 자리를 대체하게 된다.

• 삭제할 노드 delete의 양쪽 자식 노드가 모두 존재하는 경우

  • remove : 삭제할 노드의 오른쪽 서브트리에서 가장 작은 노드인 후계자(successor) 노드가 제거된다.
  • replace_node : 후계자 노드의 자식 노드가 remove의 기존 자리를 대체한다. (후계자 노드는 항상 왼쪽 자식이 없으므로 오른쪽 자식 노드 하나만 존재한다.)

• 삭제할 노드 delete의 자식 노드가 없거나 하나만 있는 경우

  • remove : 삭제할 노드 delete가 제거된다.
  • replace_node : delete의 자식 노드가 remove( = delete )의 기존 자리를 대체한다. (자식이 존재하지 않으면 nil 노드가 대체한다.)

2) remove 노드 제거하기

• remove의 부모와 replace_node를 이어준다.

• 💻 node 삭제 CODE
  

/* 6️⃣ node 삭제 */

// 노드를 삭제하는 함수
int rbtree_erase(rbtree *t, node_t *delete)
{
  node_t *remove; // 트리에서 없어질 노드
  node_t *remove_parent, *replace_node;
  int is_remove_black, is_remove_left;

  // Step 1) delete 삭제 후 대체할 replace_node 찾기
  // Step 1-1) delete 노드의 자식이 둘인 경우: delete의 키를 후계자 노드의 키값으로 대체, 노드의 색은 delete의 색 유지
  if (delete->left != t->nil && delete->right != t->nil)
  {
    remove = get_next_node(t, delete); // 후계자 노드 (오른쪽 서브트리에서 가장 작은 노드)
    replace_node = remove->right;      // 대체할 노드: 지워질 노드인 후계자는 항상 왼쪽 자식이 없기 때문에, 자식이 있다면 오른쪽 자식 하나뿐임
    delete->key = remove->key;         // delete의 키를 후계자 노드의 키값으로 대체 (색은 변경 X)
  }
  else
  { // Step 1-2) delete 노드의 자식이 없거나 하나인 경우: delete 노드를 자식으로 대체, 노드의 색도 대체되는 노드의 색으로 변경
    remove = delete;
    // 대체할 노드: 자식이 있으면 자식노드로, 없으면 nil 노드로 대체
    replace_node = (remove->right != t->nil) ? remove->right : remove->left;
  }
  remove_parent = remove->parent;

  // Step 2) remove 노드 제거하기
  /* [CASE D1]: remove 노드가 루트인 경우 */
  if (remove == t->root)
  {
    t->root = replace_node;        // 대체할 노드를 트리의 루트로 지정
    t->root->color = RBTREE_BLACK; // 루트 노드는 항상 BLACK
    free(remove);
    return 0; // 불균형 복구 함수 호출 불필요 (제거 전 트리에 노드가 하나 혹은 두개이므로 불균형이 발생하지 않음)
  }

  // Step 2-1) 'remove의 부모'와 'remove의 자식' 이어주기
  is_remove_black = remove->color; // remove 노드 제거 전에 지워진 노드의 색 저장
  is_remove_left = remove_parent->left == remove;

  // Step 2-1-1) 자식 연결
  if (is_remove_left) // remove가 왼쪽 자식이었을 경우: remove 부모의 왼쪽에 이어주기
    remove_parent->left = replace_node;
  else // remove가 오른쪽 자식이었을 경우: remove 부모의 오른쪽에 이어주기
    remove_parent->right = replace_node;

  // Step 2-1-2) 부모도 연결 (양방향 연결)
  replace_node->parent = remove_parent;
  free(remove);

  /* [CASE D2~D6]: remove 노드가 검정 노드인 경우 */
  // Step 3) 불균형 복구 함수 호출
  if (is_remove_black)
    rbtree_erase_fixup(t, remove_parent, is_remove_left);
  return 0;
}

3) 불균형 복구

• 제거된 노드인 remove가 root 노드거나 BLACK인 경우, RB tree의 규칙을 위반하게 되어 불균형이 발생한다.
• 이 불균형을 해결하기 위해 총 6가지 CASE로 나누어 처리한다.
  

🔥 불균형 CASE 1 ~ 6
[CASE 1] remove가 루트인 경우

• replace_node를 루트로 지정하고 BLACK으로 변경한다.

[CASE 2] 형제 노드와 형제의 자식 노드가 왼쪽과 오른쪽 자식 전부 다 BLACK

• 형제 노드를 RED로 변경한다.
• 부모 노드 에서 불균형이 발생할 수 있으므로, 부모 노드 를 삭제된 노드로 설정하고 불균형 복구 함수를 재귀적으로 호출한다.
  

[CASE 3] 형제 노드가 RED

• 삭제된 노드가 왼쪽/오른쪽 자식이라면 형제 노드를 기준으로 Left/Right 회전을 수행한다.
• 형제 노드와 부모 노드의 색상을 바꾼다.
• 불균형 복구 함수를 재귀적으로 호출한다.
  

[CASE D4] 형제 노드가 BLACK, 형제의 가까운 자식이 RED, 형제의 더 먼 자식이 BLACK

• 형제의 가까운 자식을 기준으로 Right 회전을 수행한다.
• 형제 노드와 형제의 가까운 자식의 색상을 바꾼다.
• 불균형 복구 함수를 재귀적으로 호출한다.
  

[CASE D5] 형제 노드가 BLACK, 형제의 더 먼 자식이 RED

• remove가 왼쪽/오른쪽 자식이라면 형제 노드를 기준으로 Left/Right 회전을 수행한다.
• 형제 노드와 부모 노드의 색상을 바꾼다.
• 형제의 더 먼 자식의 색상을 BLACK으로 바꾼다.

• 💻 불균형 복구 CODE
  

// 노드 삭제 후 불균형을 복구하는 함수
// `parent`: extra_black이 부여된 노드의 부모
// `is_left`: extra_black이 부여된 노드가 왼쪽 자식인지 여부
void rbtree_erase_fixup(rbtree *t, node_t *parent, int is_left)
{
  // 삭제 후 대체한 노드가 RED (Red & Black): BLACK으로 변경
  node_t *extra_black = is_left ? parent->left : parent->right;
  if (extra_black->color == RBTREE_RED)
  {
    extra_black->color = RBTREE_BLACK;
    return;
  }

  node_t *sibling = is_left ? parent->right : parent->left;
  node_t *sibling_left = sibling->left;
  node_t *sibling_right = sibling->right;

  if (sibling->color == RBTREE_RED)
  { // [CASE D3] 형제가 RED
    if (is_left)
      left_rotate(t, sibling);
    else
      right_rotate(t, sibling);
    exchange_color(sibling, parent);
    rbtree_erase_fixup(t, parent, is_left);
    return;
  }

  node_t *near = is_left ? sibling_left : sibling_right;    // 형제의 자식 중 extra_black으로부터 가까운 노드
  node_t *distant = is_left ? sibling_right : sibling_left; // 형제의 자식 중 extra_black으로부터 먼 노드

  if (is_left && near->color == RBTREE_RED && distant->color == RBTREE_BLACK)
  { // [CASE D4] 형제가 BLACK, 형제의 가까운 자식이 RED, 형제의 더 먼 자식이 BLACK
    right_rotate(t, near);
    exchange_color(sibling, near);
    rbtree_erase_fixup(t, parent, is_left);
    return;
  }

  if (is_left && distant->color == RBTREE_RED)
  { // [CASE D5] 형제가 BLACK, 형제의 더 먼 자식이 RED
    left_rotate(t, sibling);
    exchange_color(sibling, parent);
    distant->color = RBTREE_BLACK;
    return;
  }

  if (near->color == RBTREE_RED && distant->color == RBTREE_BLACK)
  { // [CASE D4] 형제가 BLACK, 형제의 가까운 자식이 RED, 형제의 더 먼 자식이 BLACK
    left_rotate(t, near);
    exchange_color(sibling, near);
    rbtree_erase_fixup(t, parent, is_left);
    return;
  }

  if (distant->color == RBTREE_RED)
  { // [CASE D5] 형제가 BLACK, 형제의 더 먼 자식이 RED
    right_rotate(t, sibling);
    exchange_color(sibling, parent);
    distant->color = RBTREE_BLACK;
    return;
  }

  // [CASE D2] 형제가 BLACK, 형제의 자식이 둘 다 BLACK
  sibling->color = RBTREE_RED;

  if (parent != t->root)
    rbtree_erase_fixup(t, parent->parent, parent->parent->left == parent);
}

void exchange_color(node_t *a, node_t *b)
{
  int tmp = a->color;
  a->color = b->color;
  b->color = (tmp == RBTREE_BLACK) ? RBTREE_BLACK : RBTREE_RED;
}