✔️ RBTree 이론 보고 오기 => 클릭
✔️ RBTree 구현 정리 노션 => 클릭
✔️ RBTree 구현 전체 코드 => 클릭
🎄 트리 생성
- tree = new_tree(): RB tree 구조체 생성
=> 여러 개의 tree를 생성할 수 있어야 하며 각각 다른 내용들을 저장할 수 있어야 합니다.
tree 구조체 동적 할당
- 여러 개의 tree를 생성할 수 있어야 하며 각각 다른 내용들을 저장할 수 있어야 한다.
nil 노드 생성 및 초기화
- RB tree에서 리프 노드는
nil 노드로 표시한다. nil 노드는 일종의 가상 노드로서, 트리에서 실제로 존재하지 않는 노드이다.- 일반 노드와는 다르게 key, parent, left, right 등의 필드는 의미를 가지지 않으며, 색깔은 항상 BLACK이다.
nil 노드를 트리의 리프 노드들에 대한 포인터로 간주하고, 키를 가지는 정상적인 노드들만을 트리의 내부 노드로 간주한다.- 💡 nil node를 사용하여 구현하기 위해
test/Makefile에서CFLAGS변수에-DSENTINEL이 추가되도록 comment를 제거한다!
트리 생성 code
/* 1. RB tree 구조체 생성 */
// 트리를 생성하는 함수
rbtree *new_rbtree(void) {
// rbtree 구조체에 대한 동적 할당
rbtree *t = (rbtree *)calloc(1, sizeof(rbtree));
// nil 노드 생성 및 초기화
node_t *nil_node = (node_t *)calloc(1,sizeof(node_t)); // nil 노드 동적 할당
// nil 노드는 언제나 검정
nil_node->color = RBTREE_BLACK;
t->nil = nil_node; // rbtree 구조체의 nil 포인터에 nil 노드 할당
t->root = nil_node; // rbtree 구조체의 root 포인터에 nil 할당
return t;
}🎄 트리 삭제
- delete_tree(tree): RB tree 구조체가 차지했던 메모리 반환
=> 해당 tree가 사용했던 메모리를 전부 반환해야 합니다. (valgrind로 나타나지 않아야 함)
각 노드의 메모리 반환
- 루트 노드부터 시작하여 각 노드의 자식 노드를 순회하면서 모든 노드의 메모리를 반환한다.
- 노드의 자식 노드가 nil 노드가 아니면, 해당 자식 노드를 루트로 하여 재귀적으로 함수를 호출한다.
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); // 트리 자체의 메모리 해제
}
Sunny Day!