3. RBTree key 추가

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] 새 노드가 부모 노드의 Right 자식 & Red인 부모노드가 할아버지 노드의 Left 자식 & 삼촌 노드는 Black인 경우 ⇒ 꺾인 경우
- 부모 노드를 기준으로 Left 회전을 수행한다. → CASE 3으로 만들어서 수행한다.

[CASE 3] `부모 노드`가 Right 자식 & `새 노드`가 Right자식인 경우 & `삼촌 노드`가 BLACK인 경우 ⇒ 펴진경우
- `부모 노드`를 BLACK로 변경한다
- `할아버지 노드`를 RED로 변경한다
- `할아버지 노드`를 기준으로 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) 노드의 자식을 부모의 자식으로 변경 (양방향 연결)
}