4주차 키워드

동적 메모리 할당, 포인터, 메모리 누수, 균형 이진 탐색 트리

RBtree

rbtree의 작동원리를 이해하고, c언어로 직접 구현해보는 과제이다.
삽입을 포함한 다른 기능들은 어렵지 않았지만, 삭제가 쉽지 않았다.

1. 삭제 - fixup의 시작점?

int rbtree_erase(rbtree *t, node_t *z) {
  node_t *y = z;
  color_t delete_color = y->color;
  node_t *x;
  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 { // 자식이 두명 -> successor의 컬러를 지워야함
    y = find_successor(t,z->right);
    delete_color = 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 (delete_color == RBTREE_BLACK) rb_delete_fixup(t,x); // x matters!
  print_tree(t,t->root);
  free(z);
  return 0; 
}

위 함수에서 헷갈렸던 점은 삭제한 뒤 어느 노드에서 fixup을 진행해야 하는가 였다.
다시 말해, rb_delete_fixup(t,x)함수에서 x가 무엇인지가 핵심이었고, 여기서 x는 successor의 자식임을 알 수 있다.
이 때, successor의 자식이 t->nil이라면, t->nil의 부모를 successor로 바꾼 뒤 fixup과정을 진행하게 된다.
t->nil은 트리에 하나 뿐이므로 모든 리프노드의 자식 역할을 하는 t->nil의 부모를 바꿔가며 fixup을 진행한다는 것이 논리적으로 불가능할 것이라고 생각했다. 그래서 temp라는 노드를 successor의 자식으로 선언한 뒤 fixup을 진행하려고 했지만 뜻대로 되지 않았다.😢

하지만, 결국 fixup을 진행하는 과정에서 한번에 노드 하나씩 검사하며 부모를 바꿔주므로, 충분히 이 논리가 가능하다는 것을 알게 되었다.

void rb_delete_fixup(rbtree *t, node_t *x){
  node_t *w;
  while( x != t->root && x->color == RBTREE_BLACK){
    if( x == x->parent->left){
      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{ // x == x->parent->right
       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;
}

2. memory leak

valgrind로 메모리 누수를 테스트한다.
제대로 free를 했다고 생각했는데 누수가 존재했고, 1시간의 사투 끝에 찾아냈다.

모든 노드를 탐색하며 노드를 먼저 free하고 마지막으로 트리를 free하기 전에 t->nil을 free해야만 했다.
트리의 필드로 존재하지만, 엄연히 malloc을 통해 메모리를 할당했기 때문에 반드시 따로 free를 호출해야만 한다!

3. rbtree_to_array 함수 구현

int rbtree_to_array(const rbtree *t, key_t *arr, const size_t n) {
  int *visited = (int *)calloc(1,n * sizeof(int*));

  inorder(t,t->root,arr,0,n,visited);
  free(visited);
  return 0;
}

void inorder(const rbtree *t,node_t *cur, key_t *arr,int num, const size_t n,int *visited){ //need test..!

  if(cur == t->nil) return;

  inorder(t,cur->left,arr,num,n,visited);

  if(cur != t->nil && num < n){
    for(int i=0;i<n;i++){
      if( visited[i] == 0){
        arr[i] = cur->key;
        visited[i] = 1;
        break;
      }
    }
  }
  inorder(t,cur->right,arr,num,n,visited);
  
}

rbtree의 노드들을 크기 순으로 array에 저장해야 한다. 만약 array의 크기보다 더 많은 노드가 존재할 경우, array를 다 채우면 종료된다.

나는 visited라는 배열을 선언하여 순차적으로 접근하도록 하였다.