[RBTree] 초기화 및 전체 삭제 구현하기 (new_rbtree, delete_rbtree)

RB트리 초기화 및 전체 삭제 구현하기

라면을 끓일 때 "면부터 넣을까, 스프부터 넣을까?"라는 질문이 자주 나오는데요. 면일지 스프일지 고민이 되시겠지만 진짜 정답은 바로 냄비에 물부터 올리기입니다.

 

RB트리(Red-Black Tree)도 마찬가지입니다. 삽입과 삭제라는 핵심 로직에 집중하기 전에, 트리 자체를 초기화하고 전체를 삭제할 수 있는 기본 기능부터 먼저 마련해야 합니다.

 

이처럼 올바르게 준비된 RB트리 위에서 특정 노드에 대한 삽입, 삭제, 탐색 등 다양한 연산들이 제대로 동작하게 되는 것이죠. 이번 글에서는 RB트리를 초기화하는 함수와 RB트리 전체를 삭제하는 함수를 구현해봅니다.

 

 

RB트리 초기화 함수 (new_rbtree)

new_rbtree 함수는 RB트리를 사용하기 위한 준비 단계로, 트리 구조체를 동적으로 생성하고 초기 상태를 설정하는 역할을 하는데요. 특히 모든 리프 노드 자리에 공통으로 사용될 sentinel(nil) 노드를 만들어 트리의 외곽을 정의하고, 루트 노드를 이 sentinel로 초기화함으로써 빈 트리를 구성합니다.

 

sentinel 노드는 모든 말단 노드가 공통된 nil 노드를 가리키도록 하여, 이후 삽입/삭제/탐색 과정에서 NULL 체크 없이도 일관된 조건 처리가 가능하게 해 줍니다. 이렇게 생성된 트리를 기반으로 삽입, 삭제 등의 연산을 안정적으로 수행할 수 있습니다.

 

초기화 함수 구현하기

rbtree *new_rbtree(void) {
  // RB트리 구조체를 동적 할당하고, 모든 값을 0으로 초기화
  // root, nil 등이 자동으로 NULL로 초기화됨
  rbtree *p = (rbtree *)calloc(1, sizeof(rbtree));

  // nil 노드는 모든 노드의 '리프 노드 역할'을 하는 특별한 노드
  // 모든 말단 노드는 이 nil 노드를 가리키며, 트리 외부 경계를 표시하는 역할
  node_t *nil = malloc(sizeof(node_t));

  // RB트리 3번 규칙: nil 노드는 항상 black
  nil->color = RBTREE_BLACK;

  // key 값은 특별한 의미가 없으므로 -1로 초기화 (불필요한 값이 들어가는 것 방지)
  nil->key = -1;

  // nil 노드는 자기 자신을 가리키도록 설정 (자식/부모를 모두 nil로)
  // 이후 트리 연산에서 존재 여부를 NULL 대신 nil만으로 판별 가능
  nil->left = nil;
  nil->right = nil;
  nil->parent = nil;

  // 트리 구조체에 nil을 등록하고, 루트 노드도 처음엔 nil로 설정
  p->nil = nil;
  p->root = nil;

  // 초기화가 완료된 RB트리 포인터 반환
  return p;
}

다만, 실무에서는 malloc 등의 메모리 할당 함수가 정상적으로 동작하지 않을 경우를 대비해, malloc이 NULL을 반환했을 때의 처리 코드를 함께 작성해두는 것이 일반적입니다.

 

 

RB트리 전체 삭제 함수 (delete_rbtree 함수)

초기화 함수가 있다면, 당연히 그에 대응되는 전체 삭제 함수도 필요하겠죠. delete_rbtree 함수는 RB트리에서 사용된 모든 동적 메모리를 해제하는 역할을 하며, 트리 전체를 후위 순회 방식으로 탐색하면서 각 노드를 하나씩 삭제합니다. 루트부터 차례대로 제거하는 것이 아니라, 자식 노드를 먼저 삭제한 뒤 부모 노드를 정리하는 방식으로 진행되기 때문에 메모리 누수 없이 안전하게 전체 트리를 삭제할 수 있습니다.

 

이때 실질적인 노드 해제는 별도로 정의된 delete_node 함수에서 수행됩니다. 이 함수는 하나의 노드를 기준으로 재귀적으로 왼쪽, 오른쪽 자식 노드를 먼저 탐색하고, 모든 자식이 삭제된 이후에 자신을 해제하는 구조입니다. 최종적으로 모든 노드가 정리되면, 트리의 sentinel(nil) 노드와 트리 구조체 자체까지 메모리에서 해제하여 트리 전체를 깔끔하게 제거합니다.

 

전체 삭제 함수 구현하기

// RB트리의 개별 노드를 삭제하는 재귀 함수 (후위 순회 방식 사용)
void delete_node(node_t *node, node_t *nil) {
  // nil 노드에 도달한 경우 더 이상 삭제할 노드가 없으므로 return
  if (node == nil) return;

  // 왼쪽 서브트리부터 재귀적으로 삭제
  delete_node(node->left, nil);
  // 오른쪽 서브트리도 재귀적으로 삭제
  delete_node(node->right, nil);
  // 자식 노드를 모두 삭제한 뒤, 현재 노드를 해제
  free(node);
}

// RB트리 전체를 삭제하는 함수
// 트리 구조체 안의 모든 노드를 삭제하고, 메모리를 정리한다
void delete_rbtree(rbtree *t) {
  // NULL 포인터가 전달된 경우 return
  if (t == NULL) return;

  // 루트 노드부터 시작해서 트리 전체를 삭제
  delete_node(t->root, t->nil);
  // 동적으로 생성했던 sentinel(nil) 노드 해제
  free(t->nil);
  // 마지막으로 트리 구조체 자체 해제
  free(t);
}