RBTree 조금 더 심화

목적

RBTree를 어떻게 코드로 구현해야 할지 고안해보자

살짝 생각

일단 각 노드를 통해
left, right, value, color, parent를 알아야 할 것이다

black height도 기록해야 할지랑 color로 doubly black을 나타낼지 새로 변수를 도입해 extra black을 넣을지 고민이다

가능한 변수 많이 안넣는게 좋을테니
black height은 그냥 다른 함수나 그런걸로 필요할 경우 만들고
extra black은 개념으로만 쓰며 color 로 red-and-black과 doubly black을 나타내보자

new tree

주어지는 코드를 보면 new tree라고 주는데

기본 껍데기로 필드 초기화나 메모리 지정등을 위해서라고 한다

뭘 해야 할지는 잘 모르겠지만 해봐야겠다

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

일단은 이렇게 만들었다

원래 있던 ` rbtree p = (rbtree *)calloc(1, sizeof(rbtree));에서 rbtree *캐스팅은 사실 없어도 알아서 void`반환 후 자동변환되기에 그냥 빼고 포인터로 사용했다

그리고 nil값을 만들어 센티넬로 사용할 준비를 했다

delete rbtree

주석의 말로는 메모리 할당 해제인데 흐음…

뭘 말하나 고민했는데 걍 트리 하나 날리는거다

뭐 함수 하나로 구현하려니까 쉽지 않아서 재귀로 트리 순회하는거 만들어 끝냈다

재귀하는거

static void free_subtree(rbtree *t, node_t *x) {
  if (x == t->nil) return;
    free_subtree(t, x->left);
    free_subtree(t, x->right);
    free(x);
}

그거 써서 지우는거

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