늦어도 다시 한번 : RBTree

많이 늦어버린 WIL 작성이다.

지금까지 너무 많은 일이 있었다. 사실 게을러서 안 쓴 거지만..

하지만 핀토스 들어가면 절대 못 쓸 것 같고, 머릿속이 전부 GC당해버릴 것 같아서 희미한 기억을 되짚어 써보려고 한다.

첫날은 아마 RBTree 개념 파악 및 삽입, 삭제 로직 이해에 집중했던 것 같다. 팀원들과 함께 코어타임 동안 4시간 정도 이야기를 나눴다.

전 주차와 다르게 이번 주는 작성해야 하는 코드의 양이 많아 보였고, 함수들은 전부 빈칸이었으며, RBTree 개념 자체도 어렵고 — 익숙하지도 않은 C로 그걸 구현해야 했다.

그래서 코어타임 때 엄청 많은 이야기를 했고, 관련 영상을 6번 정도 반복해서 보면서 RBTree가 정확히 어떤 구조인지 이해하려고 노력했다.

그 과정에서 위키피디아를 통해 알게 된 건, 이 구조를 만든 두 명의 개발자가 같은 교수님 밑 대학원생이었다는 것. 같은 랩실 출신이라니 — 역시 대학원생을 갈구면 좋은 게 나온다.

둘째 날부터는 CSAPP 책 7~9장을 병행하면서 RBTree 삽입 구현에 본격적으로 들어갔던 것 같다. 다음 주 월요일부터 책 내용을 깊게 이야기하기로 했고, 그날 코어타임에서는 구현 내용을 공유하는 선에서 마무리했다.

처음으로 상연님, 태성님과 같은 팀이 되었는데, 꽤 잘 맞았다. 상연님이랑은 아침 7시가 넘도록 인간에 대한 철학적인 이야기를 주고받았던 기억이 있다.

나 스스로 생각해도 수면 부족으로 머리가 이상하게 돌아가 있었는데, 그 와중에 진중하게 들어주시고, 의견도 주셔서 대화가 진짜 재밌었다.

아침의 푸른빛이 깃든 정글 캠퍼스를 바라보며 대화하던 장면은 정글 수료 후에도 오래 기억날 것 같다.

월요일부터는 본격적으로 책 이야기를 시작했다.

저녁 먹을 때까지 당일 읽을 분량을 잘못 알고 있어서 7장을 열심히 읽고 있었는데, 식사 도중 팀원분이 “엥? 우리 오늘 8장인데요?” 하셔서 그 순간 머릿속에서 사이렌이 울렸다.

예전에 읽었던 위기주도 학습법이라는 책이 떠올랐다. 밥 먹고 와서 3시간 동안 물 한 잔도 안 마시고 8장만 파고들었다. 그래도 집중해서 읽으니 어느 정도 따라잡을 수 있었고, 이해한 내용을 바탕으로 질문도 던지며 흐름을 따라갈 수 있었다.

다음 날과 그다음 날도 CSAPP는 만만치 않았다. 하루 종일 9장을 붙잡고 GPT와 씨름했다. 한 번만 더 이상하게 대답하면 구독 해지한다고 협박했을 정도다.

9장은 가상 메모리와 메모리 매핑, 페이지 테이블, 캐시 지역성 등을 다루는데, 읽다 보니 내가 정말 모르는 게 너무 많았다. “컴퓨터는 이렇게 복잡하게 굴러가는구나…” 그 와중에도 공부 자체가 재밌었다. 끝이 없는 세상이라서, 더 파고들고 싶은 욕심이 난다.

다시 RBTree 이야기로 돌아오면, 결국 삽입은 화이트보드에 손으로 직접 그리면서 구현에 성공했다.

RBTree 삽입 핵심 로직

삽입 노드는 항상 빨강(Red) 으로 시작

연속된 빨강(red-red violation)이 생기면 회전(Rotation)과 색 변환으로 해결

루트는 항상 검정(Black)

삭제 부분에서는 한동안 헤맸다. 특히 더블 블랙(double-black) 케이스를 어떻게 처리해야 하는지 정리가 안 됐다. 마지막 날 AI의 도움을 받아 흐름을 완성했고, “완벽한 구현은 아니어도 이해라도 하자”는 마음으로 마무리했다.

이때 깨달은 게 많았다. AI의 도움으로 답을 단번에 얻는 것도 좋지만, 화이트보드에 손으로 직접 트리 그리며 추적하는 과정이 진짜 실력이 되는 구간이었다는 걸 느꼈다.

정민 코치님과 커피챗을 했던 기억이 난다. 코치님은 정글 수료 후에 같은 커리큘럼을 혼자 한 번 더 돌려보셨다고 하셨다.

그 말을 듣고 “나도 비슷하게 해봐야겠다”는 생각이 들었다. 정글 커리큘럼은 단순히 취업 준비용이 아니라, 좋은 개발자가 되는 방향성 자체를 잡아주는 과정이라는 걸 체감했다.

결론적으로, RBTree 주차는 C를 이용한 구현 능력과, **‘설명하면서 배우는 공부법’**의 효능감을 동시에 느꼈던 시간이었다.

잘하냐고 하면 잘 모르겠지만, 적어도 RBTree 전의 나보다는 코드를 읽고 쓰는 감각이 훨씬 늘었다.

정글 과정중에 들었던 말중에서

“어제의 나와 경쟁해라.” 이 말이 생각났다. 그 말 그대로, 저번주의 나보단 조금은 성장하지 않았을까 싶다.

이렇게 RBTree 주차를 마무리했다. 리마인드해보니 참 즐겁게 보낸 한 주였다. …아닌 것 같기도 하고. 두 번 하긴 싫다.

쓰고 나니까 사진을 안 남긴 게 너무 아쉽다. 화이트보드 좀 찍어둘걸. 너무 허전한 글이다. 밥 먹은 거라도 맨날 찍어서 올려야겠다.

그리고 공부한 티가 하나도 안 나는 게 아쉽다. 진짜 열심히 했는데.

RBTree
- Red-Black Tree는 이진 탐색 트리의 균형을 유지하는 자료구조
- 삽입, 삭제 시 균형이 깨지면 회전(Rotation) 과 색 변환(Color Flip) 으로 복원
- 삽입은 항상 빨강으로, 루트는 항상 검정으로 유지
- 시간 복잡도는 삽입, 삭제, 탐색 모두 O(log n)
삽입/삭제 구현 시 주의점
- Sentinel(더미 노드)을 사용하면 NULL 체크를 줄일 수 있다.
- 삭제는 두 자식이 있을 때 successor 노드로 교체 → fixup으로 복원