0주차 이후 거의1달만에 프로잭트를 했다.
나름 수학공부도 오래했었고(고2~재수 동안 거의 수학만 팠었고 기계공학과 4학년 졸업이라 대학 내내 수학 계속함)
알고리즘도 남들 힘들어할때 오히려 재미가 붙어서 계속 했더니 나름 진도도 좀 빨랐었다.
하지만 처음보는 c언어 + git + docker + 포인터 + 스트럭쳐 사용 등등 그냥 처음보는게 수십개가 쏟아져 들어오니까 그냥 감당을 못했다.

진짜 딱 이느낌이었던거 같다.
팀원들은 '그래도 이사람 알고리즘 이해 좀 빠르니까 알아서 구현해 주겠지' 이러고 있고
나는 '새로 보는 프로그램 투성이인데 이거 하다보면 팀원들이 해주겠지' 이러고 있었다.
지금와서 보면 웃기는 소리이기도 한데...
팀원들이 하필 c언어 하시다 오신 분에 컴공 + 알고리즘 시험때 성적 좋으셨던분 이라서
서로가 서로를 믿고 다같이 지금 할거에만 집중하는(지금보면 참 속편한 소리다) 그런 상황이 벌어졌다.

키워드 공부 후 docker/ubuntu/git연결 이후 처음 rb 프로젝트 코드를 봤던게 일요일이었던가 그랬다.

그래도 나름 rb트리 구조는 이해가 빠르게 되어서 이거 그냥 코드만 치면 끝나겠구나 싶었는데
포인터 + 스트럭쳐만 쓰는 프로젝트라 c언어 공부한것도 그냥 쓸모도 없었고
이게 어떻게 쓰는것인가 한 1시간정도 코드만 계속 쳐다봤었다.

그러다가 진짜 답도없다 싶어서 '일단 클론코딩해!'를 했다.
일요일 오후는 그렇게 인터넷에 올라온 선배기수(인거같음)의 코드를 그냥 클론코딩했고...

시원하게 assert error를 받았다 ㅋㅋ

난 분명히 따라 쳤는데 중간에 뭐 하나 잘못쳤나보다...
지금 생각해보면 뭔가 erase쪽에서 방향 하나 잘못적었거나
parent 포인터 하나 지정 잘못해줬거나 기호 하나 잘못적었거나 그랬을 것이다.
복붙을 안하고 그냥 키보드로 쳤으니 오류가 발생했고, 대체로 맞으니까 대부분의 케이스는 통과한것 같다.

어쨌든 한 4시간의 클론 코딩 끝에 얻은것은
대충 structure의 구조가 어떻게 되는지 이해를 한 것과,
pointer의 사용 방법, 그리고 rbtree 코드 구조에 대해서 알게 되었다.
그렇게 틀린 코드를 보면서 월요일도 끝나버렸다.

이후 화요일, 이때까지 썼던 코드를 백업도 없이 싹다 지우고 처음부터 그냥 적기 시작했다.
물론 힘들다고 생각은 했지만, csrl의 의사코드를 보면서 그냥 쭈우우욱 따라 썼던거 같다.
처음 봤을때는 외계어 같던 의사코드였지만, 주말 + 월요일동안 포인터/스트럭쳐를 계속 봐왔기 때문에 코딩 하는게 가능해졌다!!

그래서 4일간 나를 계속 괴롭히던 코드따위 3시간 컷 했다.
물론 그 뒤에 이상하게 버그가 나서 4시간을 더 썼긴 했지만...
결국은 left -> right로 한번 고치고
빠트렸던 코드 한줄을 추가하였고...

결국 통과를 했다...!
선장님이 한 줄 찾아주신게 없었다면 1~2시간 더 추가됐을거 같은데 생각만 해도 아찔하다...

선배 기수 회고록을 보니까 책 대충 보고 바로 코드 적으셨다던 '천재'분 계신다던데
정말 진심으로 존경합니다
저는 의사코드 안보면 도저히 적지를 못하겠어요

이렇게 만들어진 코드이니까 일단 한번 정리는 해야될 것 같다.
회고록이기도 하고, 아직 git을 잘 쓰는것도 아니라서
지금 정리를 할 곳이 여기 밖에 없기 때문이다.

주 의!

이 밑으로는 rbtree 프로잭트 코드를 적은 코드 리뷰에 가깝습니다.
rbtree를 전혀 모르신다면 아래의 글로 들어가 rbtree에 대한 학습을 하고 읽으시는것이
글을 읽는데 도움이 됩니다.

그냥 코드의 구조만을 보고 싶으시다면 상관없습니다.

https://velog.io/@kts5927/%ED%81%AC%EB%9E%98%ED%94%84%ED%86%A4%EC%A0%95%EA%B8%80-4%EC%A3%BC%EC%B0%A8-RB%ED%8A%B8%EB%A6%AC

new_rbtree

#include "rbtree.h"

#include <stdlib.h>

rbtree *new_rbtree(void) {
  rbtree *p = (rbtree *)calloc(1, sizeof(rbtree));
  // TODO: initialize struct if needed
  node_t *nil = (node_t *)calloc(1, sizeof(node_t));
  nil->color = RBTREE_BLACK;

  p->root = p->nil = nil;

  return p;
}

새로운 rbtree를 만드는 곳이다.
새로운 rbtree를 만드는 것이니 callocd으로 초기화 + 새로운 힙 메모리를 배정 해 주었고,
nil 노드를 추가해준다.

여기서 2가지 방법이 있는데,

• 그냥 만드는 방법
• nil 노드를 가지고 경계값을 만들어 주는 방법

이 있다.
경계값을 만들어 준다는 소리는
리프 노드의 자식을 nil로 연결 해 주고, root 노드의 부모를 nil 로 연결한다는 것이다.
이렇게 되면 그래프에서 벗어나면 nil로 들어가게 되니

그래프의 안과 밖을 nil로 구분지을 수 있는 것이다!

이렇게 하고 안하고는 makefile의 주석처리된 코드를 지우고/추가하고를 통해 채점 기준을 다르게 만들 수 있으니 편한 방식대로 만들면 된다.

이거 말고는 뭐 특별한게 없다.

• nil 노드를 만들고

• nil -> color = black 지정 해 주고

• rbtree root , nil = nil 지정 해 준다.
  이렇게 되면 nil 노드 하나만 가진 비어있는 rbtree 하나가 완성된다!

rbtree_delete

void delete_rbtree(rbtree *t) {
  // TODO: reclaim the tree nodes's memory
  node_t *node = t->root;
  if(node != t->nil)
    search_delete(t,node);
  
  free(t->nil);
  free(t);
}

void search_delete(rbtree *t , node_t *node){

  if(node->left != t->nil)
    search_delete(t,node->left);
  if(node->right != t->nil)
    search_delete(t,node->right);
>key);
  free(node);

}

rbtree를 삭제하는 함수들이다.
주의 해야 할 것이, c언어는 위에서 아래로 읽기 때문에 먼저 선언되지 않은 함수가 보이면 에러를 띄운다. 그러니까 따로 search_delete를 선언해 주지 않았다면 delete_rbtree보다 먼저 적어줘야 에러가 안난다.

일단 tree의 root 노드를 함수를 돌린다.
그 노드는 자식이 nil이 아닐경우 재귀적으로 함수를 돌리게 되는데,
재귀를 돌린 후에는 free()를 통해서 메모리 할당을 해제한다.

이후 재귀가 모두 돌고 난 후, nil의 메모리를 free() 하고,
nil 조차 남지않은 껍데기 rbtree도 free()를 통해 메모리를 해제한다.

밑에 나오는 노드 삭제 함수와는 다르니까 주의하자!

rotate

void left_rotate(rbtree *t , node_t *x){
 node_t *y ;
  y = x->right;
  x->right = y->left;
  if(y->left != t->nil){y->left->parent = x;}
  y->parent = x->parent;
  if(x->parent == t->nil){t->root = y;}
  else if (x == x->parent->left){x->parent->left = y;}
  else{x->parent->right = y;}
  y->left = x;
  x->parent = y;}
  
void right_rotate(rbtree *t , node_t *x){
 node_t *y ;
  y = x->left;
  x->left = y->right;
  if(y->right != t->nil){y->right->parent = x;}
  y->parent = x->parent;
  if(x->parent == t->nil){t->root = y;}
  else if (x == x->parent->right){x->parent->right = y;}
  else{x->parent->left = y;}
  y->right = x;
  x->parent = y;}

왼쪽으로 돌리고 오른쪽으로 돌린다.
가독성이 박살났는데, 이건 미리 미안하다고 말하고 넘어가겠다.
이번에 쓴 코드는 책의 '의사코드'를 보고 쓴 코드들이 많은데,
며칠째 거의 30시간 넘게 같은코드드 + 같은 개념 붙잡고 있으니까 정신 나갈거 같아서
내가 편한 방식으로 그냥 밀고 지나갔다.
근데 회고록이니까 상관없지않나? 싶다.

이제 이 코드 가래떡을 해석 해 보자.

rotate 노드는 돌리는 두 노드 중 위쪽의 노드를 기준을 한다.
left_rotate의 2번째 줄에 y = x->right; 가 있는것을 확인 할 수가 있다.

이후의 과정을 left_rotate를 기준으로 적자면

• x->right 를 y->left로 바꿈
• 만약 y->left가 nil이 아니라면 y->left의 부모를 x로 바꾼다.
• y->parent를 x->parent로 바꿈(y가 x의 위로 올라가기 때문에)
• 만약 x->parent가 nil이라면(x가 트리의 root라면) y를 tree의 root로 바꿈
• 그게 아니라면 x의 부모를 y의 부모로 바꾼다
• y의 왼쪽에 x를 할당한다
• x의 부모를 y로 바꾼다

(right는 left의 방향(left,right)를 반대로 적으면 됨.

과정을 통해 rotate 코드가 완성되었다!
코드로 적으니까 어려워 보이지 그냥 rbtree rotation 한거다.

insert , insert_fixup

드디어 나왔다 양심없는 insert와 insert_fix이다.

근데 이건 진짜 쉬운거다. 사실 rbtree에서 어려운거는
c 포인터/스트럭쳐 코딩 처음 할 때랑, erase 구문이다.
그러니까 일단 그냥 한번 봐 보자.

insert를 먼저 보자.

while(x != t->nil)
  {y = x;
  if(z->key < x->key){x = x->left;}
  else{x = x->right;}}
  z->parent = y;
  if(y == t->nil){t->root = z;}
  else if (z->key < y->key){y->left = z;}
  else {y->right = z;}
  z->left = t->nil;
  z->right = t->nil;
  z->color = RBTREE_RED;
  rbtree_insert_fixup(t,z);
  return z;
}

어차피 위의 node_t * 이쪽은 그냥 노드 배정한다는 소리고 이 while 구문 하나면 끝난다.
한줄로 요약하면 key 값을 기준으로 이진탐색을 하면서 자기 자리 찾아간다는 소리다.

while 구문 이후 조건 따져가면서 자기자리에 배정받는게 다이다.
그런 코드를 좀 보자면,

• if(y == t->nil){t->root = z;} => 그냥 rbtree에 처음넣을때 root로 지정하라는 소리다.

이런식으로 그냥 조건따져서 넣으면된다.
모르겠다고? 그러면 이 글 말고 rbtree공부를 하러 가면 된다.

void rbtree_insert_fixup(rbtree *t , node_t *z){
  node_t *y;
  while(z->parent->color == RBTREE_RED){
    if(z->parent == z->parent->parent->left){
      y = z->parent->parent->right;
      if(y->color == RBTREE_RED){
        z->parent->color = RBTREE_BLACK;
        y->color = RBTREE_BLACK;
        z->parent->parent->color = RBTREE_RED;
        z = z->parent->parent;}
      else {if(z == z->parent->right){
        z = z->parent;
        left_rotate(t,z);}
        z->parent->color = RBTREE_BLACK;
        z->parent->parent->color = RBTREE_RED;
        right_rotate(t,z->parent->parent);}}
    else{
      y = z->parent->parent->left;
      if(y->color == RBTREE_RED){
        z->parent->color = RBTREE_BLACK;
        y->color = RBTREE_BLACK;
        z->parent->parent->color = RBTREE_RED;
        z = z->parent->parent;}
      else {if(z == z->parent->left){
        z = z->parent;
        right_rotate(t,z);}
        z->parent->color = RBTREE_BLACK;
        z->parent->parent->color = RBTREE_RED;
        left_rotate(t,z->parent->parent);}}
  }
  t->root->color = RBTREE_BLACK;  
}

다음으로는 insert_fix이다.
여기서 중요한 포인트가 2개 있다.

• if(z->parent == z->parent->parent->left){
  else{
  }
  구문으로 이루어 져 있다는 것. 위 아래가 똑같은데 방향만 바꾼 것 이다.

• 마지막에 루트 노드를 black 으로 바꾸는것.

이 두가지만 잘 기억한다면, 나머지는 그냥 recoloring과 rotation을 이용한 균형 맞추기가 전부이다.

find/min/max

node_t *rbtree_find(const rbtree *t, const key_t key) {
 // printf("Find Key: %d\n", key);
 // TODO: implement find
 node_t *current = t->root;
   while (current != t->nil){
     // printf("cur key: %d\n", current->key);
     if(key == current->key)
       return current;
     else
       current = (key < current->key) ? current->left : current->right;
   }
   return NULL;
}

node_t *rbtree_min(const rbtree *t) {
 // TODO: implement find
 node_t *finder = t->root;
 while(finder->left != t->nil){finder = finder->left;}
 return finder;
}
node_t *rbtree_min_search(const rbtree *t , node_t *node) {
 // TODO: implement find
 node_t *finder = node;
 while(finder->left != t->nil){finder = finder->left;}
 return finder;
}

node_t *rbtree_max(const rbtree *t) {
 // TODO: implement find
 node_t *finder = t->root;
 while(finder->right != t->nil){finder = finder->right;}
 return finder;
}

void rb_transplant(rbtree *t,node_t *u , node_t *v){
 if(u->parent == t->nil){t->root = v;}
 else if(u == u->parent->left){u->parent->left = v;}
 else{u->parent->right = v;}
 v->parent = u->parent;
}

함수들을 동작시킬 때 필요한 min/max/find 함수들이다.
의사코드에 없는 애들이 많고 직관적으로 이해 할 수 있다.

min/max/find는 이진탐색에서 찾듯이 하면 되고,
transplant는 두 노드를 바꾸는 것인데, insert의 노드 바꾸기랑 비슷하다.

erase , erase_fixup

드디어 나왔다.. rbtree에서 많은 사람들을 좌절시킨 그 '삭제'파트이다.

하지만 너굴맨이 처치해 버렸기 때문에 걱정 할 필요는 없다.

먼저 erase부터 보자.

int rbtree_erase(rbtree *t, node_t *z) {
  // TODO: implement erase
  node_t *y = z;
  node_t *x;
  color_t y_oricol = y->color;
  if(z->left == t->nil){
    x = z->right;
    rb_transplant(t,z,z->right);
  }else if(z->right == t->nil){
    x = z->left;
    rb_transplant(t,z,z->left);
  }else{y = rbtree_min_search(t,z->right);
  y_oricol = y->color;
  x = y->right;
  if(y->parent == z){x->parent = y;}
  else{rb_transplant(t,y,y->right);
  y->right = z->right;
  y->right->parent = y;}
  rb_transplant(t,z,y);
  y->left = z->left;
  y->left->parent = y;
  y->color = z->color;
  }
if(y_oricol == RBTREE_BLACK){
  rbtree_delete_fixup(t,x);
} 
free(z);
return 0;
}

내가 봐도 참 굵고 튼튼한 코드들이다.

하지만 하나하나 살펴본다면 erase는 간단한 코드이다.
왜냐? 이진트리 삭제를 그대로 한 것이기 때문이다.
이 코드는 크게 3등분을 할 수가 있는데,

• 처음 if~elseif~else 구문
• y_oricol = y->color; , 즉 색깔 저장 구문
• if~else 구문

이후 fixup을 한 후 사라진 node의 메모리를 free() 해 주는것으로 끝이 난다.

처음 if 문은 이진트리 삭제를 통해 바꿀 노드를 찾는 것이고,
두번째 색깔 저장 구문은 삭제 후 사용할 색깔을 찾는 것이고,
세번째 if~else 구문은 찾은 노드를 연결 연결 하는 것이다.

생각보다 정말 간단한 구문이다. 처음봐서 당황했다고 보는게 맞는 말 일 것이다.

다음은 erase_fix이다.

void rbtree_delete_fixup(rbtree *t , node_t *x){

while(x != t->root && x->color == RBTREE_BLACK){
if(x == x->parent->left){
node_t *w = x->parent->right;
if(w->color == RBTREE_RED){
  w->color = RBTREE_BLACK;
  x->parent->color = RBTREE_RED;
  left_rotate(t,x->parent);
  w = x->parent->right;}
if(w->left->color == RBTREE_BLACK && w->right->color == RBTREE_BLACK){
  w->color = RBTREE_RED;
  x = x->parent;}
else {if (w->right->color == RBTREE_BLACK){
  w->left->color = RBTREE_BLACK;
  w->color = RBTREE_RED;
  right_rotate(t,w);
  w = x->parent->right;}

  w->color = x->parent->color;
  x->parent->color = RBTREE_BLACK;
  w->right->color = RBTREE_BLACK;
  left_rotate(t,x->parent);
  x = t->root;}}
else{
  node_t *w = x->parent->left;
if(w->color == RBTREE_RED){
  w->color = RBTREE_BLACK;
  x->parent->color = RBTREE_RED;
  right_rotate(t,x->parent);
  w = x->parent->left;}
if(w->right->color == RBTREE_BLACK && w->left->color == RBTREE_BLACK){
  w->color = RBTREE_RED;
  x = x->parent;}
else {if (w->left->color == RBTREE_BLACK){
  w->right->color = RBTREE_BLACK;
  w->color = RBTREE_RED;
  left_rotate(t,w);
  w = x->parent->left;}

  w->color = x->parent->color;
  x->parent->color = RBTREE_BLACK;
  w->left->color = RBTREE_BLACK;
  right_rotate(t,x->parent);
  x = t->root;}}
}


x -> color = RBTREE_BLACK;
}

진짜 길다. 장난아니게 길다
하지만 이 코드에도 함정이 있는게,
전체 구문을 줄이고 줄인다면

while
if~
else~

이걸로 줄일수 있다!
그러니까 우리가 볼 부분은

node_t *w = x->parent->right;
if(w->color == RBTREE_RED){
  w->color = RBTREE_BLACK;
  x->parent->color = RBTREE_RED;
  left_rotate(t,x->parent);
  w = x->parent->right;}
if(w->left->color == RBTREE_BLACK && w->right->color == RBTREE_BLACK){
  w->color = RBTREE_RED;
  x = x->parent;}
else {if (w->right->color == RBTREE_BLACK){
  w->left->color = RBTREE_BLACK;
  w->color = RBTREE_RED;
  right_rotate(t,w);
  w = x->parent->right;}

  w->color = x->parent->color;
  x->parent->color = RBTREE_BLACK;
  w->right->color = RBTREE_BLACK;
  left_rotate(t,x->parent);
  x = t->root;}

이게 끝이다! 이 밑의 else 구문은 위의 코드의 방향을 바꾼 것 뿐이다.

해석을 해 보자.

• 만약에 삼촌의 색깔이 red라면 ~ case1번 실행해라(자식은 당연히 검은색)
• 만약에 삼촌 자식들이 모두 검은색이라면 ~ case2번 실행해라(삼촌은 red가 아니니까 black)
• else(자식중에 red가 있다면) if(왼쪽 자식이 빨간색이라면) case3를 하고
• 이후 case4를 해라

왜?
case3를 하면 무조건 4번을 해야되지만
case3을 안해도 4는 해야되기 때문에
case3은 하던 안하던 삼촌 자식 색깔이 모두 black이 아니라면 무조건 case4를 해야하기 때문이다.

이거 반복이다 ㅋㅋㅋ
fix_up 코드는 복잡한 것이 아니라

• case를 잘 나누고
• 그 case를 상황에 따라 재귀를 잘 돌게 만들면

Rbtree 로직이 깔끔하게 만들어진다는 것이다.

inorder traversal

void inorder(const rbtree *t, node_t *node, key_t *arr, const size_t n, size_t *cnt)
{
  if (*cnt == n || node == t->nil)
    return;
  inorder(t, node->left, arr, n, cnt);
  arr[*cnt] = node->key;
  *cnt += 1;
  inorder(t, node->right, arr, n, cnt);
}
// 트리를 중위 순회하며 n개의 키를 배열 arr에 저장
int rbtree_to_array(const rbtree *t, key_t *arr, const size_t n)
{
  size_t cnt = 0;
  size_t *pcnt = &cnt;

  inorder(t, t->root, arr, n, pcnt);

  return 0;
}

이후 중위순회 하면서 코드를 return 하면 끝!

다들 이쯤 왔으면 전위/중위/후위 순회 문제를 풀었을꺼니까

나도 힘들다

대충 이런식으로 포인터 + 스트럭쳐를 이용한 rbtree 구현을 했다.

복습 - malloc/calloc/realloc
-inorder/preorder/postorder
배열과 포인터는 비슷하다
포인터는 실제로는 그냥 값일 뿐이다

brk/메모리 할당 전략/