RB Tree를 C언어로 구현하던 중 맞이한 에러를 해결하는 과정을 담았기 때문에 이 글을 이해하기 위해서는 사전 지식이 필요할 것입니다.
저의 전체 코드는 아래 깃허브 링크를 참고해주시면 감사하겠습니다.
https://github.com/hyeona01/Data-Structures/blob/master/rbtree_lab/src/rbtree.c

"클론 코딩을 내 것으로 만드려면 한 줄 씩 부숴봐라"

CLRS 책을 참고하여 RB Tree를 구현하는 과제에 맞닥뜨렸다.
따라 쓰는 건 내 취향이 아니다.
이해하지 못한 코드를 옮겨쓰는 일은 정말 기분이 나쁘기 때문이다.

그래서 나는 내 취향대로, 내가 이해한대로 코드를 작성했다.
그러는 과정에서 마주한 에러, 그리고 정답 코드와 비교하면서 발견한 문제점을 기록하고자 한다.

❌ 내 논리에는 세 가지 문제가 있었다.

1️⃣ Rotation 에서 NIL 노드를 고려하지 않았다.

위의 그림이 right rotation의 방법을 그림으로 표현한 것이다.

노드간 이어진 간선을 수정해주면 rotation이 가능해진다.

이렇게 총 세 개의 간선이 변경된다.
이 때의 내 논리는 아래와 같다.

"이어진 노드가 존재하는 간선일 때만 바꿔주면 되겠다!"

• CLRS

void right_rotate(rbtree *T, node_t *x)
{
   node_t *y = x->left;
   // 1. 관련 자식 노드 재연결
   x->left = y->right;

   if (y->right != T->nil)
   {
	y->right->parent = x;
   }
.
.
.

}

• 내 추측

void right_rotate(rbtree *T, node_t *x)
{
   node_t *y = x->left;
   // 1. 관련 자식 노드 재연결
   if (y->right != T->nil)
   {
	x->left = y->right;
	y->right->parent = x;
   }

.
.
.

}

이 논리에는 문제가 있었다.

문제 발견

기존에 연결된 X의 left node 연결을 끊어주지 않게 된다.

다음과 같이 내가 의도하지 않았던 동작이 발생되면서 노드가 사이클을 그리게 된다.
코드로만 봤을 때는 납득되지 않았던 것이 시각화 하여 보니, 바로 문제를 발견하게 되었다.

문제 해결

그래서 나는 다음과 같이 직관적으로 코드를 정리하였다.

void right_rotate(rbtree *T, node_t *x)
{
   node_t *y = x->left;
   // 1. 관련 자식 노드 재연결
   if (y->right != T->nil)
   {
	x->left = y->right;
	y->right->parent = x;
   }

   else
   {
	x->left = T->nil; 
   }
.
.
.

}

NIL 노드인 경우에는 x의 새로운 left node를 NIL로 변경해주는 것이다.

2️⃣ insert fixup 함수에서 가독성을 높이고자 했다.

• CLRS

void insert_fixup(rbtree *t, node_t *x)
{
   node_t *u; // 삼촌 노드
   while (x->parent->color == RBTREE_RED)
   {
	if (x->parent == x->parent->parent->left) // 부모가 left child
	{
	   u = x->parent->parent->right; // 삼촌 노드
	   if (u->color == RBTREE_RED) // case 4 : 부모, 삼촌이 red
	   {
	     x->parent->color = RBTREE_BLACK;
	     u->color = RBTREE_BLACK;
	     x->parent->parent->color = RBTREE_RED;
	     x = x->parent->parent; // --- 추가 검사 ---
.
.
.

}

위 코드는 x-<parent가 무수히 반복된다.
코드를 읽는 입장에서 정말 가독성이 떨어진다.

• 내 추측

void insert_fixup(rbtree *t, node_t *x)
{
   node_t *u; // 삼촌 노드
   node_t *p; // 부모 노드
   while (x->parent->color == RBTREE_RED)
   {
	p = x->parent;
	if (p == p->parent->left) // 부모가 left child
	{
	   u = p->parent->right; // 삼촌 노드
	   if (u->color == RBTREE_RED) // case 4 : 부모, 삼촌이 red
	   {
	     p->color = RBTREE_BLACK;
	     u->color = RBTREE_BLACK;
	     p->parent->color = RBTREE_RED;
	     x = p->parent; // --- 추가 검사 ---
.
.
.

}

왜 안 되지.. 정말 의아했다.
이건 간단한 내 실수였다.

문제 발견

Loop 안에서 원본 값인 x가 업데이트 되고있으며, p는 x값을 따라간다. Loop 내에서 p를 재사용하는 경우가 생기면 이 때를 위해서 x가 업데이트 되는 시점에 p 또한 업데이트를 해주어야 한다.

문제 해결

바로 해결 되었다.

3️⃣ rbtree_erase 함수에서 NIL 노드를 고려하지 않았다.

[ 현재 상황 ]

1. 삭제할 노드의 자식이 하나 이상일 때, successor가 대체된다.
2. 이 때, successor가 삭제할 노드의 바로 아래 자식 노드이다.

이러한 상황에서 CLRS 책에서의 코드는 x의 parent를 y로 재설정해준다.

• 내 추측
  이미 x의 parent는 y이지 않나?
  나는 그냥 삭제하기로 한다.

이번엔 될줄 알았는데 안 된다 ㅎㅎ

문제 발견

혼자 힘으로 논리의 오류를 발견하기 어려워서 동료에게 조언을 구했다. 흑흑 최고
나는 또 NIL 노드일 때를 고려하지 못했던 것이다.

자, 살펴보자.

삭제할 노드를 대체하는 노드는 successor(오른쪽 서브트리에서 가장 작은 값)이다. 그리고 extra black을 부여받는 노드는 successor의 자식이다.
이 경우에 자식 노드가 NIL node라면 나중에 발생되는 일을 전혀 예상하지 못했다.

extra black을 부여받은 노드는 loop문 안에서 또다시 fixup 과정을 거친다.
그러면 부모 노드와 삼촌 노드를 찾아가서 비교해야한다.
그러면! NIL 노드일 경우, 그 NIL 노드의 부모와 삼촌에 접근하려 할 때 존재하지 않는 주소였기 때문에 segmentation fault 를 맞이하게 된다.

아 이 사실을 깨달았을 때 정말정말 상쾌 통쾌했다ㅜㅜ!

결국, CLRS 책대로 해주어야 함을 깨달았다!

문제 해결

int rbtree_erase(rbtree *t, node_t *p)
{
   /* 생략 */
   else
   {
	x->parent = y;
   }
   /* 생략 */
}

문제 해결 후의 쫑알쫑알

C 언어에 미숙해서 발생한 에러는 생각보다 적었다.
아, 자잘자잘한 에러들은 즉시 수정해서였을지 모른다.

전체 에러를 잡는 데만 오롯이 5시간이 걸렸다. 빠르다면 빠른걸까? 그치만 5시간 내내 모니터를 뚫어지게 쳐다보고 있던 시간이 내게는 길게 느껴졌다.

앞으로는 좀 더 촘촘한 논리로 코드를 접해야겠다는 생각을 하게 되었다. 그리고 동료들에게 도움을 요청해보는 것도 좋겠다고 생각했다. 나는 동료들의 귀한 시간을 내 디버깅으로 뺏는 게 미안해서 혼자 해결하려다보니 정말 눈물나게 힘들었다.. 다음부터는 나도 돕고, 도움을 받고 상부상조 ㅎ 하며 공부하자!

그리고 C 언어에 익숙하지 않다보니 디버깅을 하기 어려워서 너무너무너무너무 힘들었다!!!!
이번 학습을 계기로 더 성장하는 내가 되길!