1) 각 노드의 메모리 반환

• 루트 노드부터 시작하여 각 노드의 자식 노드를 순회하면서 모든 노드의 메모리를 반환한다.
• 노드의 자식 노드가 nil 노드가 아니면, 해당 자식 노드를 루트로 하여 재귀적으로 함수를 호출한다.

2) nil 노드와 tree의 메모리 반환

• 모든 노드 삭제 후 nil 노드와 tree 구조체의 메모리를 반환한다.

/* 2. RB tree 구조체가 차지했던 메모리 반환 */
// 트리와 노드의 메모리를 해제하는 함수
void delete_node(rbtree *t, node_t *node){
  // 노드의 왼쪽 자식이 nil이 아닌 경우
  if(node->left != t->nil)
    delete_node(t, node->left); // 왼쪽 자식 노드부터 재귀적으로 메모리 해제 수행
  // 노드의 오른쪽 자식이 nil이 아닌 경우
  if(node->right != t->nil)
    delete_node(t, node->right); // 오른쪽 자식 노드부터 재귀적으로 메모리 해제 수행
  // 현재 노드의 메모리 해제
  free(node);
}

// 트리를 삭제 시 순회하면서 각 노드의 메모리를 반환하는 함수
void delete_rbtree(rbtree *t) {
  // 트리의 루트 노드를 시작으로 순회
  node_t *node = t->root;
  // 루트 노드가 nil이 아닌 경우에만 순회하고 메모리 해제 수행
  if(node != t->nil)
    delete_node(t,node);
  free(t->nil); // nil 노드의 메모리 해제
  free(t); // 트리 자체의 메모리 해제
}