RB트리를 구현해보며 만났던 문제들

다시금 느끼는 포인터의 공포 😨

나같은 입문자에게 C의 포인터는 단순히 개념적으로도 충분히 높은 벽이었지만, 실제로 내 코드에서 포인터를 사용해보는 것은 그보다 한차원 너머의 어려움이었다. 산넘어 산이라고 해야할듯 😂

처음에는 포인터의 간편함에 놀랐다. 각각의 포인터는 메모리 주소들을 가리킬 뿐이지만, 포인터는 빡빡하게 돌아가는 C에 윤활유 같은 존재였다. 익히 알려진 포인터의 악명에 비해 생각보다 직관적으로, 또 쉽게 사용할 수 있다는 생각이 들었다. 버그들을 만나기 전까진 말이야 🤮

하라는거 다 해줬잖아! 😠

RB트리의 노드 삽입부를 완성하고, 간단한 테스트를 진행할 무렵이었다. 완벽히 로직을 구현했다는 자신감은 도통 이유를 알 수 없는 segment fault 에러를 만난 후 완전히 박살났다. 문제가 발생한 지점을 확실하게 찾아야겠다는 생각에 디버깅 툴 gdb 를 이용해서 코드의 흐름을 하나하나 따라가보았다. 하지만 내가 예상했던 곳과는 영 딴판인 곳에서 발생했다.

RB트리의 삽입은 대개 두 과정으로 이뤄진다.
1. RED색을 가진 노드를 이진 검색 트리의 경우와 동일하게 트리에 삽입한다.
2. RB트리의 속성 위반 여부를 검사한다. 위반했다면, 트리를 조정한다.

2번을 담당하는 함수에서 편의를 위해 위반 여부를 탐색할 노드의 부모 노드의 위치와 조부모 노드 위치를 포인터 변수에 담고 시작했는데, 아니나 다를까 속성 위반을 탐색할 노드가 트리의 루트 노드일 경우, 조부모 노드의 메모리 주소에 접근할 수 없어서 생기는 에러였다.

문제 해결 ✅

왼쪽이 기존에 구현했던 로직의 추상화, 오른쪽이 수정한 로직의 추상화이다. 기존에는 nil_node라는 별도의 node_t 구조체를 선언하고, rbtree의 nil포인터 변수가 이 nil_node의 주소를 담도록 했다. 이 경우 rbtree구조체의 nil멤버는 자연스레 parent속성을 가지지 못했고, 이를 참조하려고 할 때 segment fault에러를 뱉어내게 되었던 것.

이러한 문제를 해결하기 위해 오른쪽과 같이 nil노드의 처리를 바꿨다. 이미 rbtree구조체는 nil이라는 멤버를 가지고 있었기에, 여기에 node_t만큼의 메모리 주소만 할당해주는 것으로!
이렇게 처리함으로써 nil은 node_t의 크기만큼의 빈 메모리 공간을 할당받게 되고, parent 를 참조할 때 정상적으로 0을 받을 수 있게 되었다.

구조체와 포인터를 능숙하게 다루지 못해서 생긴 버그들은 당혹스러웠고, 디버깅하기 어려웠다. 이러한 작은 프로젝트에서도 디버깅하기 어려웠는데, 규모가 컸더라면? 상상도 하기 싫다 🥹 알고 있는 개념이라고 신나서 막 쓸게 아니라, 내가 어떠한 용도로 구조체를 선언할 것이고, 어떤 곳을 포인터로 가리킬 지 확실하게 알고 사용해야겠다는 생각이 뼈저리게 들었다.

의사 코드에서의 의문 ❓

위의 사진은 이번 구현에서 참조했던 명서인 CLRS의 RB트리 의사코드들의 일부이다.
line 12 ~ 13 이 왜 필요할까? y->right가 x라면, x의 부모는 어차피 y일텐데, 뭣하러 다시 한번 같은 부모를 정의해주는 걸까? 서칭을 통해 답을 얻을 수 있었다.

line 12 ~ 13은 바로 x가 sentinel nil node일 경우를 고려하기 위한 부분이다. nil노드를 sentinel노드로 사용한다는 건, nil노드를 하나로 묶어서 사용한다는 뜻이고, 이 경우에는 nil노드의 부모값을 따로 명시하지 않는다. 따라서 transplant 함수를 부르기 전에 nil노드의 부모를 정의해주는 것!