[TIL][Krafton Jungle] 4주차 - (3) : RB Tree 공부 및 실제 구현

 

오늘은 RB 트리의 삭제 연산과 구현을 실제로 진행해보겠다.

그전에 make 파일에서 발생한 오류부터 해결해 보자.

 

---

 

Segmentation fault

세그멘테이션 폴트(Segmentation fault)는 프로그램이 잘못된 메모리 주소에 접근하려고 할 때 발생하는 오류이다.

이는 일반적으로 배열의 범위를 초과하거나 널 포인터를 참조하는 등의 상황에서 발생할 수 있다.

 

현재 RB 트리의 선언, 단일 노드의 삽입과 탐색, 삭제까지 구현을 마치고 올바르게 작동 된다는 것을 확인했다.

 

근데 test_find_erase() 함수에서 for문으로 arr[i]의 값들을 각각 insert하는 상황에서 Segmentation fault가 발생한 상황이다.

 

 

문제는 이 함수를 진입하지도 못하고 있는 상황이라는 것이다.

 

아마 Segmentation fault가 발생하면, 해당 함수 실행했던 것을 모두 백업하고 return 하는 것 같은데, printf() 문으로 로깅 디버깅을 했으나 함수 시작부분의 printf도 반응하지 않는 걸 보니 뭐가 잘못된지 예측하기 굉장이 어렵다.

 

++

 

현재 아직 탐색중이지만 결론을 찾지 못했지만, 예상 가능한 문제점을 찾았다.

 

delete_tree()함수에서 node도 모두 동적으로 할당한 것을 해제하는 로직을 작성해서 추가해줬는데,

erase() 함수에서 지운 노드의 동적 할당 해제를 수행하지 않았다.

 

그 부분을 수정하기 위해서 delete 문에 지워지는 노드의 동적 할당을 해제 해주어야 한다.

 

 

++

해당 문제점이 맞는지 확인하기 위해 erase() 함수가 쓰이는 부분을 주석처리 했더니,

정상으로 작동되는 걸 확인할 수 있었다.

 

erase() 함수가 3번까지는 작동되는데 그 이후부터 문제가 발생한 것을 보니,

 

1. 삭제 연산 로직 구현의 실수

2. 삭제 연산 시 노드의 동적할당 해제 관련 문제

 

2번일 가능성이 높으므로 내일 바로 그 연산을 추가하도록 하겠다.

 

 

일단 밑에다가 트리를 삭제할 때, 동적할당을 해제하는 코드를 작성해보았다.

 

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

int delete_node(rbtree *t, node_t *node){
  if(node == t->nil){
    return 0;
  }

  delete_node(t,node->left);
  delete_node(t,node->right);

  free(node);
  return 0;
}

 

위 코드는 트리를 삭제하기 위해서 이전 노드들을 전부 free()로 동적 할당을 해제해 준 뒤, 트리를 해제하는 방식의 코드이다.

 

해당 방식을 재귀로 진행했는데, 재귀 오류가 발생할 지는 아직 예상하지 못하겠다.

 

해당 알고리즘이 어떤 오류를 가져올 것인지에 대한 예측이 어려운 상황에서 그냥 일단 임시방편으로 구현해 둔 상황이다.