[RBTree] 삭제 구현하기 (erase_fixup, rbtree_erase)

RB트리 삭제 구현하기

지금까지 RB트리를 생성하고, 삽입 기능과 탐색 기능까지 구현을 마쳤다면 이제 마지막으로 남은 것은 대망의 삭제 연산입니다. 삭제는 일반적인 이진 탐색 트리에서도 가장 어려운 연산 중 하나입니다. 자식의 유무에 따라 세 가지로 분기 처리해야 하기 때문이죠. RB트리의 삭제 또한 기본적으로는 이진 탐색 트리의 삭제 로직을 따릅니다. 다만 여기에 추가적으로 RB트리의 균형 규칙을 검사하고, 필요 시 재조정하는 단계가 포함됩니다.

 

하지만 너무 겁먹을 필요는 없습니다. 우리는 이미 RB트리의 삭제 개념을 충분히 이해하고 있고, 삭제 구현에서 가장 까다로운 연산인 회전과 색상 교환도 유틸리티 함수로 미리 준비해두었기 때문입니다. 이번 글에서는 RB트리에서 가장 어렵다고 평가받는 연산이지만, 동시에 가장 보람 있는 핵심 기능인 RB트리 삭제 연산을 직접 구현해보겠습니다.

 

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

 

 

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

RB트리에서 노드를 삭제한 뒤에는, 트리가 여전히 RB트리의 규칙을 만족하는지 검사하게 됩니다. 만약 삭제로 인해 규칙을 위반한 경우, 별도로 준비된 재조정 함수인 erase_fixup을 통해 트리의 균형을 다시 맞추는 과정이 진행됩니다.

 

보다 구체적으로 설명하자면, 삭제된 노드의 색이 Black이고, 그 색상을 물려받은 노드가 루트가 아닌 Black 노드일 때 본격적인 재조정에 들어가게 됩니다. 이 재조정은 총 4가지 Case로 나뉘며, 각 상황에 따라 회전이나 색상 교환을 통해 트리의 균형을 복구합니다. 그리고 이 과정을 완료함으로써, 비로소 하나의 RB트리 삭제 연산이 완전히 끝나게 됩니다.

 

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

// 삭제 후 RB트리의 규칙을 복구하는 함수
// p는 삭제된 노드 자리를 대신하게 된 fix_target 노드
void erase_fixup(rbtree *t, node_t *p) {
  node_t *cur = p;

  // 현재 노드가 루트가 아니고, BLACK일 경우 재조정
  while (cur != t->root && cur->color == RBTREE_BLACK) {
    node_t *sibling;

    // 현재 노드가 왼쪽 자식인지 오른쪽 자식인지에 따라 형제 위치 결정
    if (cur == cur->parent->left) {
      sibling = cur->parent->right;
    } else {
      sibling = cur->parent->left;
    }

    // Case 1: 형제가 RED인 경우
    // → 부모-형제 색상 교환 후 회전하여 Case 2~4로 변환
    if (sibling->color == RBTREE_RED) {
      color_swap(t, sibling);  // 형제와 부모 색상 교환
      if (cur == cur->parent->left) {
        left_rotate(t, cur->parent);  // 왼쪽 자식이면 좌회전
      } else {
        right_rotate(t, cur->parent); // 오른쪽 자식이면 우회전
      }
      continue;  // 회전 후 형제가 BLACK이 되어 Case 2~4로 넘어감
    }

    // Case 2: 형제와 형제의 두 자식이 모두 BLACK인 경우
    // → 형제를 RED로 바꾸고, 부모로 올라가 다시 검사
    if ((sibling->left->color == RBTREE_BLACK) && (sibling->right->color == RBTREE_BLACK)) {
      sibling->color = RBTREE_RED;
      if (cur->parent->color == RBTREE_RED) {
        cur->parent->color = RBTREE_BLACK;  // 부모가 RED였다면 BLACK으로 바꾸고 종료
        break;
      } else {
        cur = cur->parent;  // 부모가 BLACK이면 다시 재조정
        continue;
      }
    }

    // Case 3: 형제가 BLACK이고, 형제의 자식 RED가 할아버지까지 꺾인 상태
    // → 형제와 자식 RED 색상 교환 후 회전 → Case 4로 변환
    if ((cur == cur->parent->left) && (sibling->left->color == RBTREE_RED)) {
      color_swap(t, sibling->left);
      right_rotate(t, sibling);
      sibling = cur->parent->right;  // 회전 후 형제가 바뀔 수 있으므로 갱신
    } else if ((cur == cur->parent->right) && (sibling->right->color == RBTREE_RED)) {
      color_swap(t, sibling->right);
      left_rotate(t, sibling);
      sibling = cur->parent->left;
    }

    // Case 4: 형제가 BLACK이고, 형제의 자식 RED가 할아버지까지 일자인 상태
    // → 형제의 색을 할아버지의 색으로 덮고, 할아버지와 형제 자식 Red는 BLACK으로
    // → 할아버지를 축으로 회전하면 fixup 종료
    sibling->color = cur->parent->color;
    if ((cur == cur->parent->left) && (sibling->right->color == RBTREE_RED)) {
      cur->parent->color = sibling->right->color = RBTREE_BLACK;
      left_rotate(t, cur->parent);
    } else if ((cur == cur->parent->right) && (sibling->left->color == RBTREE_RED)) {
      cur->parent->color = sibling->left->color = RBTREE_BLACK;
      right_rotate(t, cur->parent);
    }
    break;  // fixup 완료
  }

  // 루트 노드는 항상 BLACK으로 보장
  t->root->color = RBTREE_BLACK;
}

 

 

RB트리 삭제 함수 (rbtree_erase)

삭제되는 노드의 색과 그 후속 처리

RB트리에서 노드를 삭제하는 과정은 기본적으로 이진 탐색 트리(BST)의 삭제 방식과 동일하게 시작되는데요. 하지만 삭제되는 노드의 색과, 삭제 이후 그 자리에 남는 노드의 상태에 따라 RB트리의 규칙이 깨질 수 있으며, 이 경우 반드시 추가적인 재조정(fixup) 작업이 필요하게 됩니다.

 

첫번째 조건: 삭제되는 노드의 색이 Black인지 확인

삭제할 노드의 자식 개수에 따라 실제로 삭제되는 노드가 달라질 수 있고, 따라서 삭제되는 색도 달라집니다.

• 자식이 없거나 1개인 경우: 삭제 대상이 자기 자신이므로, 삭제되는 색은 해당 노드의 색
• 자식이 2개인 경우: 삭제 대상이 후임자(또는 전임자)이므로, 삭제되는 색은 후임자(전임자)의 색

이렇게 삭제 색이 정해지고 나면, 그 색이 Red인지 Black인지에 따라 처리 방식이 달라집니다.

• 삭제되는 노드의 색이 Red인 경우: 트리의 Black height에 영향을 주지 않으므로, 재조정 없이 삭제 종료
• 삭제되는 노드의 색이 Black인 경우: 트리의 균형이 깨졌을 가능성이 있으므로 두번째 조건을 추가로 확인해야 함

 

두번째 조건: 삭제되는 노드의 색을 물려받은 노드가 Black인지 확인

삭제 후, 삭제된 노드의 자리에 남는 노드(삭제된 노드의 자식 또는 NIL 노드)는 삭제된 색을 물려받게 되는데, 이 노드의 기존 색상에 따라 재조정 여부가 결정됩니다.

• 물려받은 노드의 기존 색이 Red인 경우: 해당 노드는 Red and Black이 되고 이를 Black으로 바꾼 뒤 재조정 없이 삭제 종료
• 물려받은 노드의 기존 색이 Black인 경우: 해당 노드가 Doubly Black이 되므로 이를 해결하기 위한 재조정에 들어감

이처럼 삭제되는 색이 Black이고, 이를 물려받는 노드가 Black일 때만 재조정이 필요하며, 그 외의 경우는 비교적 간단하게 처리됩니다. 이 두 가지 조건만 명확히 이해하고 있다면, fixup 함수 내부의 회전과 색상 반전은 이미 구현된 상태이므로, 삭제 로직은 무리 없이 완성할 수 있습니다.

 

삭제 함수 구현하기

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

  node_t *cur = p;           // 현재 삭제 대상 노드
  node_t *fix_target;        // 삭제 후 색을 물려받아 fixup 대상이 되는 노드
  color_t del_color;         // 실제 삭제된 노드의 색을 저장

  // Case 1: 자식이 없는 노드를 삭제하는 경우
  if ((cur->left == t->nil) && (cur->right == t->nil)) {
    del_color = cur->color;

    // 부모와의 연결을 끊고, 삭제 노드를 nil로 대체
    if (cur == cur->parent->left) {
      cur->parent->left = t->nil;
    } else {
      cur->parent->right = t->nil;
    }

    // 삭제할 노드가 루트인 경우 nil이 새 루트가 됨
    if (cur == t->root) {
      t->root = t->nil;
    }

    fix_target = t->nil; 			// fixup 대상은 nil 노드
    t->nil->parent = cur->parent; 	// fixup을 위해 nil 노드에 임시로 부모 설정

    free(cur); // 삭제 대상 메모리 해제
  }

  // Case 2: 자식이 1개인 노드를 삭제하는 경우
  else if ((cur->left == t->nil) || (cur->right == t->nil)) {
    // 삭제 노드의 유일한 자식이 fixup 대상이 됨
    if (cur->left != t->nil) {
      fix_target = cur->left;
    } else {
      fix_target = cur->right;
    }

    del_color = cur->color;

    // 부모가 삭제 노드 대신 그 자식을 가리키도록 연결
    if (cur == cur->parent->left) {
      cur->parent->left = fix_target;
    } else {
      cur->parent->right = fix_target;
    }

    // 삭제 노드의 자식 노드 부모 포인터도 갱신
    fix_target->parent = cur->parent;

    // 루트 노드를 삭제하는 경우 자식 노드를 새 루트로 설정
    if (cur == t->root) {
      t->root = fix_target;
    }

    free(cur); // 삭제 노드 메모리 해제
  }

  // Case 3: 자식이 2개인 노드를 삭제하는 경우
  else {
    // 오른쪽 서브트리에서 최소값(후임자)을 찾아 삭제
    node_t *del_target = cur->right;
    while (del_target->left != t->nil) {
      del_target = del_target->left;
    }

    del_color = del_target->color; 	// 실제로 삭제되는 후임자의 색 저장
    cur->key = del_target->key; 	// 삭제할 노드의 key를 후임자의 key로 교체

    // Case 3-1: 후임자의 자식이 없는 경우
    if ((del_target->left == t->nil) && (del_target->right == t->nil)) {
      fix_target = t->nil;						// fixup 대상은 nil 노드
      t->nil->parent = del_target->parent;		// fixup을 위해 nil 노드에 임시로 부모 설정

      // 부모와의 방향을 확인하여 nil로 교체
      if (del_target == del_target->parent->left) {
        del_target->parent->left = t->nil;
      } else {
        del_target->parent->right = t->nil;
      }

      free(del_target);	// 후임자 메모리 해제
    }

    // Case 3-2: 후임자가 오른쪽 자식을 가진 경우
    else {
      fix_target = del_target->right;

      if (del_target == del_target->parent->left) {
        del_target->parent->left = fix_target;
      } else {
        del_target->parent->right = fix_target;
      }

      fix_target->parent = del_target->parent;

      free(del_target);	// 후임자 메모리 해제
    }
  }

  // === 색상에 따라 fixup 여부 판단 ===

  // 삭제된 노드가 Black이고, 자식이 Red였다면 Red and Black 상태가 됨
  // 색만 Black으로 바꿔주고 재조정 생략
  if ((fix_target->color == RBTREE_RED) && (del_color == RBTREE_BLACK)) {
    fix_target->color = RBTREE_BLACK;
  }

  // 삭제된 노드가 Black이고, fix_target도 Black이면 Doubly Black 상태가 됨
  // Doubly Black을 해결하기 위해 재조정 시작
  else if ((fix_target->color == RBTREE_BLACK) && (del_color == RBTREE_BLACK)) {
    erase_fixup(t, fix_target);
  }

  return 0; // 정상적으로 삭제 완료
}