[RBTree] set 기반 RBTree를 multiset 기반으로 전환하기

set 기반 RBTree를 multiset 기반으로 전환하기

알고리즘의 동작 과정을 충분히 정리했다 하더라도, 구현에 들어가기 전 반드시 확인해야 할 것이 있습니다. 바로 README 파일이나 테스트 파일을 살펴보는 것인데요. 이 파일들을 통해 내가 만들어야 할 최종 결과물의 정확한 조건과 기대되는 동작을 파악할 수 있기 때문입니다.

 

하지만 저는 이번 주에 책 정리와 RB트리 구현을 병행하다 마음이 조급해져서 테스트 조건을 충분히 확인하지 않고 제가 이해하고 있는 로직만으로 구현을 시작해버리고 말았습니다. 그 결과, 문제에서 요구한 RBTree는 중복 키를 허용하는 multiset 기반이었음에도 불구하고, 중복 키의 삽입을 막는 set 기반 RBTree를 만들어 버렸죠. 열심히 구현했지만, 요구사항을 만족하지 못한 채 테스트에서도 실패하게 되었습니다.

 

이 경험을 통해, 다음부터는 반드시 요구사항부터 확실히 확인하겠다는 다짐을 했고, 늦었지만 '이제라도 바꿔보자', '포기하지 말자'는 마음으로 물고 늘어져서, 현재는 RBTree를 multiset 기반으로 전환하는 작업을 완료한 상태입니다. 이번 글에서는 multiset 기반으로 변경된 insert, delete 함수에 대해 정리해 보려고 합니다.

 

 

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

insert_fixup() 함수는 삽입된 노드로 인해 깨진 Red-Black Tree의 균형을 복구하는 역할을 하기 때문에, multiset 기반으로 전환하더라도 별다른 수정 없이 그대로 사용할 수 있습니다. 중복 키의 허용 여부는 삽입 위치를 결정하는 rbtree_insert() 함수에서 처리되고, insert_fixup()은 그 결과에 따라 트리의 구조와 색상을 조정할 뿐이죠. 다만 이번에 rbtree_insert() 기능을 변경하는 과정에서 함께 구조적인 개선도 진행하여, 조건 분기를 명확히 하고 회전 흐름을 직관적으로 만들었습니다.

 

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

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

  // 부모가 nil이 아니고, 빨강일 때만 재조정
  while (cur->parent != t->nil && cur->parent->color == RBTREE_RED) {
    // 부모의 부모가 없다면 종료
    if (cur->parent->parent == t->nil) break;

    node_t *grandparent = cur->parent->parent; // 할아버지 노드

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

      // Case 1: Red가 포화된 상태
      if (uncle->color == RBTREE_RED) {
        cur->parent->color = RBTREE_BLACK;
        uncle->color = RBTREE_BLACK;
        grandparent->color = RBTREE_RED;
        cur = grandparent; // 조정 대상 노드를 할아버지로 올림
        continue;
      }

      // Case 2: Red가 꺾이면서 쏠린 상태
      if (cur == cur->parent->right) {
        cur = cur->parent;
        left_rotate(t, cur); // 부모를 기준으로 좌회전
      }

      // Case 3: Red가 일자로 쏠린 상태
      cur->parent->color = RBTREE_BLACK;
      grandparent->color = RBTREE_RED;
      right_rotate(t, grandparent);
    }

    // 부모가 할아버지의 오른쪽 자식일 경우 (대칭)
    else {
      node_t *uncle = grandparent->left; // 삼촌 노드는 왼쪽 자식

      // Case 1: Red가 포화된 상태
      if (uncle->color == RBTREE_RED) {
        cur->parent->color = RBTREE_BLACK;
        uncle->color = RBTREE_BLACK;
        grandparent->color = RBTREE_RED;
        cur = grandparent;
        continue;
      }

      // Case 2: Red가 꺾이면서 쏠린 상태
      if (cur == cur->parent->left) {
        cur = cur->parent;
        right_rotate(t, cur); // 부모를 기준으로 우회전
      }

      // Case 3: Red가 일자로 쏠린 상태
      cur->parent->color = RBTREE_BLACK;
      grandparent->color = RBTREE_RED;
      left_rotate(t, grandparent);
    }
  }

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

 

 

multiset 기반 RB트리 삽입 함수 (rbtree_insert)

기존 rbtree_insert() 함수는 set 기반으로 중복 키를 허용하지 않고 있었지만, multiset 기반으로 전환하면서 중복 키도 오른쪽 서브트리에 삽입되도록 로직을 변경했는데요. 동시에 루트 설정 조건을 간결하게 정리하고, 삽입 위치 탐색 과정에서 불필요한 중복 검사와 메모리 해제 코드를 제거함으로써 구조를 단순화했습니다. 특히, parent와 cur의 역할을 명확히 분리해 기존 삽입 로직이 보다 직관적이고 깔끔해졌고, 중복 키도 안정적으로 삽입 가능한 multiset 형태로 개선했습니다.

 

RB트리 삽입 함수 구현하기

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

  // BST 삽입을 위한 위치 탐색
  node_t *parent = t->nil;
  node_t *cur = t->root;
  while (cur != t->nil) {
    parent = cur;
    if (key < cur->key) {
      cur = cur->left;
    } else {
      // 중복 키도 오른쪽으로 삽입(multiset 기반)
      cur = cur->right;
    }
  }

  // 새 노드의 부모 설정
  new_node->parent = parent;

  // 트리가 비어 있는 경우 → 새 노드를 루트로 설정
  if (parent == t->nil) {
    t->root = new_node;
  }
  // 부모의 왼쪽 또는 오른쪽에 새 노드 연결
  else if (new_node->key < parent->key) {
    parent->left = new_node;
  } else {
    parent->right = new_node;
  }

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

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

 

 

multiset 기반 RB트리 삭제 후 재조정 함수 (erase_fixup)

기존 erase_fixup() 함수는 Case 1~4의 상황을 하나의 흐름에 통합하여 처리했지만, 조건 중첩이 많고 흐름이 복잡해 가독성이 떨어졌는데요. 이를 개선하기 위해 왼쪽 자식인 경우와 오른쪽 자식인 경우를 완전히 분리하고, 각 Case를 명확히 나눠 순서대로 처리함으로써 로직의 직관성을 높였습니다.

 

특히 Case 3과 Case 4의 전환 과정에서 회전과 색상 변경을 각각의 상황에 맞게 명확하게 구분하여 구성했고, 전체적으로 균형 트리 복구의 흐름을 보다 직관적이고 간결하게 정리해 보았습니다.

 

RB트리 삭제 후 재조정 함수 구현하기

// 삭제 후 RB트리의 규칙을 복구하는 함수
void erase_fixup(rbtree *t, node_t *p) {
  // 현재 노드가 루트가 아니고, BLACK일 경우 재조정
  while (p != t->root && p->color == RBTREE_BLACK) {
    node_t *sibling;
    
	// p가 왼쪽 자식인 경우
    if (p == p->parent->left) {
      sibling = p->parent->right;

      // Case 1: 형제가 RED인 경우
      if (sibling->color == RBTREE_RED) {
        sibling->color = RBTREE_BLACK;
        p->parent->color = RBTREE_RED;
        left_rotate(t, p->parent);
        sibling = p->parent->right;
      }

      // Case 2: 형제와 형제의 두 자식이 모두 BLACK인 경우
      if (sibling->left->color == RBTREE_BLACK && sibling->right->color == RBTREE_BLACK) {
        sibling->color = RBTREE_RED;
        p = p->parent;
      } else {
        // Case 3: 형제가 BLACK이고, 형제의 자식 RED가 할아버지까지 꺾인 상태
        if (sibling->right->color == RBTREE_BLACK) {
          sibling->left->color = RBTREE_BLACK;
          sibling->color = RBTREE_RED;
          right_rotate(t, sibling);
          sibling = p->parent->right;
        }
        // Case 4: 형제가 BLACK이고, 형제의 자식 RED가 할아버지까지 일자인 상태
        sibling->color = p->parent->color;
        p->parent->color = RBTREE_BLACK;
        sibling->right->color = RBTREE_BLACK;
        left_rotate(t, p->parent);
        p = t->root;
      }
    } else {
      // 좌우 대칭: p가 오른쪽 자식인 경우
      sibling = p->parent->left;

	  // Case 1: 형제가 RED인 경우
      if (sibling->color == RBTREE_RED) {
        sibling->color = RBTREE_BLACK;
        p->parent->color = RBTREE_RED;
        right_rotate(t, p->parent);
        sibling = p->parent->left;
      }

	  // Case 2: 형제와 형제의 두 자식이 모두 BLACK인 경우
      if (sibling->left->color == RBTREE_BLACK && sibling->right->color == RBTREE_BLACK) {
        sibling->color = RBTREE_RED;
        p = p->parent;
      } else {
        // Case 3: 형제가 BLACK이고, 형제의 자식 RED가 할아버지까지 꺾인 상태
        if (sibling->left->color == RBTREE_BLACK) {
          sibling->right->color = RBTREE_BLACK;
          sibling->color = RBTREE_RED;
          left_rotate(t, sibling);
          sibling = p->parent->left;
        }
		// Case 4: 형제가 BLACK이고, 형제의 자식 RED가 할아버지까지 일자인 상태
        sibling->color = p->parent->color;
        p->parent->color = RBTREE_BLACK;
        sibling->left->color = RBTREE_BLACK;
        right_rotate(t, p->parent);
        p = t->root;
      }
    }
  }
  
  // 루트 노드는 항상 BLACK으로 보장
  t->root->color = RBTREE_BLACK;
}

 

 

multiset 기반 RB트리 삭제 함수 (rbtree_erase)

기존 rbtree_erase()는 삭제 케이스별 분기를 세세하게 나누고 직접 부모 자식 연결을 관리했지만, 코드가 장황하고 중복이 많아 가독성이 떨어졌는데요. 이를 개선하기 위해 공통 동작인 노드 대체(transplant)를 transplant() 유틸리티 함수로 분리하여 중복 코드를 제거하고, 전체 흐름을 BST 삭제의 일반적 구조에 따라 간결하게 재정비했습니다.

 

특히 삭제되는 노드의 색을 별도로 저장하여 재조정이 필요 여부를 명확히 판단할 수 있게 되었고, 자식이 없는 후임자나 자식이 있는 후임자에 대한 처리 역시 일관된 방식으로 단순화했습니다.

 

RB트리 삭제 함수 구현하기

// 두 노드의 위치를 트리 상에서 교체하는 유틸리티 함수
void transplant(rbtree *t, node_t *u, node_t *v) {
  if (u->parent == t->nil) {
    t->root = v;               // u가 루트였던 경우 v가 새 루트가 됨
  } else if (u == u->parent->left) {
    u->parent->left = v;       // u가 왼쪽 자식이면 v를 왼쪽에 연결
  } else {
    u->parent->right = v;      // u가 오른쪽 자식이면 v를 오른쪽에 연결
  }

  t->nil->parent = u->parent;
  if (v != t->nil) {
    v->parent = u->parent;     // v의 부모도 갱신
  }
}

int rbtree_erase(rbtree *t, node_t *p) {
  // 트리 또는 삭제할 노드가 NULL인 경우 -1을 return
  if (!t || !p || p == t->nil) return -1;

  node_t *y = p;                      	// 현재 삭제 대상 노드
  node_t *x;                          	// 삭제 후 색을 물려받아 fixup 대상이 되는 노드
  color_t y_original_color = y->color;  // 실제 삭제된 노드의 색을 저장

  // Case 1, 2: 자식이 하나 이하인 경우
  if (p->left == t->nil) {
    x = p->right;
    transplant(t, p, p->right);
  } else if (p->right == t->nil) {
    x = p->left;
    transplant(t, p, p->left);
  }

  // Case 3: 자식이 둘 다 있는 경우
  else {
    y = p->right;
    while (y->left != t->nil) {
      y = y->left;  // 오른쪽 서브트리에서 최솟값 찾기
    }

    y_original_color = y->color;
    x = y->right;

    // 후임자가 바로 삭제 대상의 오른쪽 자식이 아니라면
    if (y->parent != p) {
      transplant(t, y, y->right);
      y->right = p->right;
      y->right->parent = y;
    }

    transplant(t, p, y);  // 삭제 대상 p를 후임자 y로 대체
    y->left = p->left;
    y->left->parent = y;
    y->color = p->color;  // 색도 복사하여 RB 속성 유지
  }

  // 삭제된 노드가 BLACK인 경우 → fixup 필요 여부 판단
  if (y_original_color == RBTREE_BLACK) {
    erase_fixup(t, x);
  }

  // 삭제 대상 노드 메모리 해제
  free(p);
  return 0;
}