[RBTree] 유틸리티 함수 구현하기 (rotate, color flip, color swap)

RB트리 유틸리티 함수 구현하기 (rotate, color flip, color swap)

RB트리의 삽입과 삭제를 공부하면서 눈에 띄는 공통된 작동 방식들이 있었는데요. 바로 회전(Rotation), 색상 반전(Color Flip), 색상 교환(Color Exchange)과 같은 연산들이었습니다. 이러한 연산은 RB트리의 균형을 유지하는 핵심 요소로, 삽입과 삭제 과정에서 반복적으로 등장하는 친구들입니다.

 

그래서 본격적인 RB트리 구현에 앞서, 이들 연산을 별도의 유틸리티 함수로 분리해 구현해 보았습니다. 이렇게 미리 구성해두면, 이후 삽입과 삭제 알고리즘을 작성할 때 핵심 로직에 집중할 수 있고, 코드도 훨씬 더 깔끔하게 유지할 수 있습니다.

 

이번 포스팅에서는 제가 직접 구현한 회전, 색상 반전, 색상 교환 함수들을 소개하고, 각 연산이 어떤 상황에서 사용되는지도 함께 정리해보겠습니다.

 

 

회전 연산 함수 (left_rotate, right_rotate)

RB트리의 균형 유지를 위해 가장 핵심적인 역할을 하는 연산을 하나 꼽자면, 단연 회전(Rotation)이라 할 수 있는데요. 삽입과 삭제 과정 모두에서 등장하며, 거의 모든 불균형 상황에서 충돌을 해결하는 데 직접적으로 관여하는 핵심 연산입니다.

 

회전 연산은 회전 방향에 따라 노드들의 위치 변화 방식에 차이가 생깁니다. 회전 축 노드는 같은 방향의 자식과 자리를 바꾸며 한 계층 내려가고, 반대 방향의 자식은 한 계층 올라오게 되죠. 이러한 과정은 C 언어에서는 주로 포인터 재배치로 구현되며, 각 노드의 부모 포인터까지 올바르게 갱신하는 작업이 반드시 함께 이루어져야 합니다.

 

회전 연산 함수 구현

[RB트리의 삽입과 회전]에서 다뤘던 RB트리의 우측 회전을 C 언어로 구현한 코드는 다음과 같습니다.

// RB트리 우측 회전 함수 (축 노드를 기준으로 오른쪽으로 회전)
void right_rotate(rbtree *t, node_t *axis) {
  // 왼쪽 자식을 새 부모로 올릴 준비
  node_t *new_parent = axis->left;
  // 회전 과정에서 축 노드가 잃게 되는 서브트리 (new_parent의 오른쪽 자식)
  node_t *remain_child = axis->left->right;

  // 1단계: 회전 축의 부모에 따라 부모의 자식 포인터를 새 부모로 연결
  if (axis->parent == t->nil) {
    // 축이 루트인 경우, 트리의 루트를 new_parent로 갱신
    t->root = new_parent;
  } else if (axis->parent->left == axis) {
    // 축이 부모의 왼쪽 자식이면, 부모의 왼쪽 자식을 new_parent로 바꿈
    axis->parent->left = new_parent;
  } else {
    // 축이 부모의 오른쪽 자식이면, 부모의 오른쪽 자식을 new_parent로 바꿈
    axis->parent->right = new_parent;
  }

  // 2단계: new_parent와 축 노드의 관계를 재정립 (축을 new_parent의 오른쪽 자식으로)
  new_parent->right = axis;
  new_parent->parent = axis->parent; // new_parent의 부모는 축의 원래 부모
  axis->parent = new_parent;         // 축의 부모는 이제 new_parent

  // 3단계: 축의 왼쪽 자식을 new_parent의 오른쪽 자식으로 교체 (단절된 서브트리 연결 복원)
  axis->left = remain_child;
  if (remain_child != t->nil) {
    // 잃었던 서브트리가 존재하면, 그 부모를 축으로 설정
    remain_child->parent = axis;
  }
}

그리고 좌측 회전은 위의 우측 회전과 동일한 로직을 기반으로, 회전 방향만 반대인 형태로 구현됩니다. 아래는 이를 C 언어로 작성한 코드이며, 우측 회전과 마찬가지로 포인터 재배치와 부모 포인터 갱신 과정을 포함하고 있습니다.

// RB트리 좌측 회전 함수 (축 노드를 기준으로 왼쪽으로 회전)
void left_rotate(rbtree *t, node_t *axis){
  node_t *new_parent = axis->right;
  node_t *remain_child = axis->right->left;

  // 축 부모 노드의 자식 포인터 변경
  if (axis->parent == t->nil) {
    t->root = new_parent;
  } else if (axis->parent->left == axis) {
    axis->parent->left = new_parent;
  } else {
    axis->parent->right = new_parent;
  }

  // 자식 재배치
  new_parent->left = axis;
  new_parent->parent = axis->parent;
  axis->parent = new_parent;

  // 축의 오른쪽 자식 포인터 재설정
  axis->right = remain_child;
  if (remain_child != t->nil) {
    remain_child->parent = axis;
  }
}

 

 

색상 반전 함수 (color_flip)

색상 반전은 RB트리에서 회전만큼 자주 등장하는 유용한 연산 중 하나입니다. 부모 노드와 두 자식 노드의 색상을 동시에 바꾸더라도, RB트리의 핵심 규칙(특히 black-height)을 그대로 유지할 수 있기 때문이죠. 특히 삽입 과정에서 삼촌 노드가 Red일 때 발생하는 Case 1을 처리할 때, 이 연산이 핵심 역할을 합니다.

 

색상 반전 함수 구현

회전 연산에 비해 색상 반전은 C 언어로 구현할 때 구조가 훨씬 단순합니다. 부모가 Red일 경우 Black으로, 두 자식이 Black이면 Red로 바꾸면 되고, 반대로 부모가 Black이면 Red로, 자식이 Red면 Black으로 바꿔주면 됩니다.

 

이처럼 조건에 따라 부모-자식 간 색상만 맞바꾸는 방식으로 간단하게 구현이 가능한데, 이를 구현한 코드는 다음과 같습니다.

// 색상 반전 함수 (부모-두 자식 간 색상 교환)
void color_flip(rbtree *t, node_t *node) {
  // 노드나 자식이 nil 노드(유효한 노드)가 아닌 경우 return
  if (node == t->nil || node->left == t->nil || node->right == t->nil) return;

  // 부모 노드가 Black인 경우
  if (node->color == RBTREE_BLACK) {
    // 부모를 Red로 바꾸고, 두 자식을 Black으로 바꾼다
    node->color = RBTREE_RED;
    node->left->color = RBTREE_BLACK;
    node->right->color = RBTREE_BLACK;
  } else {
  	// 부모 노드가 Red면 반대로 부모를 Black으로, 자식들을 Red로 바꾼다
    node->color = RBTREE_BLACK;
    node->left->color = RBTREE_RED;
    node->right->color = RBTREE_RED;
  }
}

 

 

색상 교환 함수 (color_swap)

색상 교환은 말 그대로 해당 노드와 그 부모의 색상을 맞바꾸는 연산입니다. 보통 회전을 수행하기 직전, 트리의 균형과 규칙을 유지하기 위해 자주 사용됩니다. 제가 구현하면서 느낀 바로는, 이 연산이 함수로 따로 분리해 두었을 때 가장 유용하게 활용될 수 있는 기능이 아닐까 싶은데요. 직관적이고 단순한 동작이지만, RB트리의 균형 유지 흐름을 코드로 깔끔하게 표현하기 위해 꼭 필요한 요소라고 할 수 있습니다.

 

색상 교환 함수 구현

C 언어에서 두 값을 교환하는 함수를 작성해본 분들이라면 익숙할 텐데요. 색상 교환도 이와 동일한 방식으로, 값이 아니라 노드의 색상만 맞바꾸는 방식으로 동작합니다. 구조는 단순하지만, 회전 전후의 트리 구조에서 색상 규칙을 유지하는 데 핵심적인 역할을 담당합니다.

 

이를 코드로 구현하면 다음과 같습니다.

// 색상 교환 함수 (해당 노드와 부모 노드의 색상 스왑)
void color_swap(rbtree *t, node_t *node) {
  // 노드가 nil이거나 부모가 nil이면 (즉, 루트 노드거나 잘못된 입력이라면) return
  if (node == t->nil || node->parent == t->nil) return;

  // 현재 노드와 부모 노드의 색을 서로 스왑
  // 일반적인 값 교환 방식과 동일하게 임시 변수(tmp)를 활용
  int tmp = node->color;               // 현재 노드의 색을 임시로 저장
  node->color = node->parent->color;  // 부모의 색을 현재 노드에 대입
  node->parent->color = tmp;          // 임시로 저장해둔 원래 색을 부모에 대입
}