[RBTree] 삽입 구현하기 (insert_fixup, rbtree_insert)

RB트리 삽입 구현하기

이제까지 RB트리의 개념과 규칙, 그리고 파생 개념들을 배우고, 삽입과 삭제 과정의 작동 원리를 충분히 이해해보는 시간을 가졌는데요. 또한 회전, 색상 교환 등 자주 사용되는 연산에 대한 유틸리티 함수 구현까지 마쳤다면, 본격적으로 C언어를 활용해 RB트리의 핵심 로직을 직접 구현할 준비가 끝났다고 볼 수 있습니다.

 

본격적인 구현 내용에 들어가기 전에, 만약 위의 이론들이 아직 완전히 숙지되지 않았다면 아래 포스트들을 먼저 참고하시기 바랍니다.

• [CS] RB트리의 개념과 규칙, 파생 개념
• [CS] RB트리의 삽입과 회전
• [CS] RB트리의 삭제
• [C언어] RB트리 유틸리티 함수 구현하기

※ 주의: 해당 RB트리 구현은 set 자료구조를 기반으로 하고 있습니다.

 

RB트리 삽입 후 재조정 함수 (insert_fixup)

RB트리의 삽입 기능을 구현하기 전, 가장 먼저 해야 할 일은 무엇일까요? 바로 삽입 후 RB트리의 규칙을 만족하지 않았을 때 이를 해결해 주는 재조정 기능을 먼저 구현하는 것입니다.

 

RB트리는 본래 이진 탐색 트리(BST)이기 때문에, 새로운 노드의 삽입 자체는 BST의 삽입 과정을 그대로 따릅니다. 하지만 삽입 이후 RB트리의 규칙을 만족하는지를 검사하고, 필요한 경우 이를 재조정한다는 게 BST와의 차별점이죠. 이러한 재조정 과정을 통해 삽입 후에도 트리의 균형이 자동으로 유지됩니다.

 

이를 위해서는 새 노드를 삽입한 뒤, 그 부모 노드가 Red일 때 발생할 수 있는 세 가지 경우(Case 1~3)를 확인하고, 각 상황에 맞는 해결 방식을 적용하여 트리를 재조정해야 합니다. 이 과정을 거쳐 RB트리의 모든 규칙을 만족하는 상태로 만든 뒤, 비로소 하나의 삽입 연산이 완성됩니다.

 

삽입 후 재조정 함수 구현하기

// 삽입 후 재조정 함수
void insert_fixup(rbtree *t, node_t *node) {
  node_t *cur = node;

  // 부모 노드가 빨강일 경우에만 RB트리 규칙 위반 가능성이 있음
  while (cur->parent->color == RBTREE_RED) {
    node_t *uncle;

    // 부모가 할아버지의 왼쪽 자식일 경우
    if (cur->parent == cur->parent->parent->left) {
      uncle = cur->parent->parent->right; // 삼촌 노드는 오른쪽 자식
    } else {
      // 부모가 할아버지의 오른쪽 자식일 경우
      uncle = cur->parent->parent->left; // 삼촌 노드는 왼쪽 자식
    }

    // Case 1: Red가 포화된 상태
    if (uncle->color == RBTREE_RED) {
      // 할아버지와 두 자식 간 색상 반전
      color_flip(t, cur->parent->parent);
      // 검사 대상을 할아버지로 바꾼 뒤 다시 검사
      cur = cur->parent->parent;
      continue;
    }

    // Case 2: Red가 꺾이면서 쏠린 상태
    // 부모가 왼쪽 자식 + 현재 노드가 오른쪽 자식 OR
    // 부모가 오른쪽 자식 + 현재 노드가 왼쪽 자식
    if ((uncle == cur->parent->right) && (cur == cur->parent->right)) {
      cur = cur->parent;
      left_rotate(t, cur->parent); // 꺾임 → 부모 기준으로 회전
    } else if ((uncle == cur->parent->left) && (cur == cur->parent->left)) {
      cur = cur->parent;
      right_rotate(t, cur->parent); // 꺾임 → 부모 기준으로 회전
    }

    // Case 3: Red가 일자로 쏠린 상태
    color_swap(t, cur->parent); // 부모와 할아버지 색상 교환

    if (cur == cur->parent->left) {
      // 현재 노드가 왼쪽 자식인 경우 → 우회전 (부모를 중심으로 올라감)
      right_rotate(t, cur->parent->parent);
    } else {
      // 현재 노드가 오른쪽 자식인 경우 → 좌회전
      left_rotate(t, cur->parent->parent);
    }
  }

  // 회전으로 Red가 루트가 됐을 경우 고려
  t->root->color = RBTREE_BLACK;
}

 

 

RB트리 삽입 함수 (rbtree_insert)

사실, 회전 연산과 색상 교환, 그리고 삽입 후 재조정 함수까지 이미 모두 구현해 놓았다면, 삽입 함수 자체는 오히려 가장 간단하게 구현할 수 있습니다. 기존 BST처럼 새 노드를 알맞은 위치에 삽입한 뒤, 재조정 함수만 호출해주면 되기 때문이죠.

 

모든 복잡한 과정들은 이미 별도의 함수로 분리해두었기 때문에, 이 단계에서는 삽입 로직을 어렵게 생각할 필요가 없습니다. 직접 구현해보면 생각보다 단순하다는 걸 금방 느끼실 수 있을 것이라 생각합니다. 그리고 나서 다시 이 포스트의 삽입 함수 구현 코드를 살펴보며, 미리 구성해둔 유틸리티 함수들의 역할과 구조적 설계의 이점을 자연스럽게 체감해 보시면 좋겠습니다.

 

삽입 함수 구현하기

node_t *rbtree_insert(rbtree *t, const key_t key) {
  // 트리 포인터가 NULL이면 삽입할 수 없으므로 NULL 반환
  if (t == NULL) return NULL;
  
  // 삽입할 새 노드 동적 생성 및 초기화
  node_t *new_node = malloc(sizeof(node_t));
  new_node->color = RBTREE_RED;         // 새 노드는 항상 RED로 삽입
  new_node->key = key;                  // 키 설정
  new_node->parent = t->nil;            // 초기 부모는 nil
  new_node->left = t->nil;              // 왼쪽 자식은 nil
  new_node->right = t->nil;             // 오른쪽 자식은 nil

  // 트리가 비어 있다면(루트가 nil), 새 노드를 루트로 설정
  if (t->root == t->nil) {
    new_node->color = RBTREE_BLACK;     // 루트는 항상 BLACK이어야 함
    t->root = new_node;
  } else {
    // 트리가 비어 있지 않다면 BST 삽입을 통해 위치 탐색
    node_t *parent, *cur;
    cur = t->root;
    while (cur != t->nil) {
      // 중복 키는 삽입하지 않고 기존 루트 반환 (메모리 해제)
      if (key == cur->key) {
        free(new_node);
        return cur;
      } else if (key < cur->key) {
        parent = cur;
        cur = cur->left;
      } else {
        parent = cur;
        cur = cur->right;
      }
    }

    // 위치를 찾은 후, 부모의 왼쪽 또는 오른쪽에 새 노드 연결
    if (new_node->key < parent->key) {
      parent->left = new_node;
    } else {
      parent->right = new_node;
    }
    // 새 노드의 부모 설정
    new_node->parent = parent;
  }

  // 삽입 후 RB트리의 규칙을 만족시키도록 재조정 함수 호출
  insert_fixup(t, new_node);

  // 삽입 후 새로 삽입한 노드의 주소 반환
  return new_node;
}