rbtree *new_rbtree(void) {
rbtree *p = (rbtree *)calloc(1, sizeof(rbtree)); // 트리 생성
node_t *NIL = (node_t *)calloc(1, sizeof(node_t)); // nil노드 생성
NIL->color = RBTREE_BLACK; // nil 노드 색깔 블랙으로
p->root = NIL; // p의 루트를 nil 노드로
p->nil = NIL; // p의 nil을 nil노드로
return p;
}
void delete_node(rbtree *t, node_t *node) {
if (node == t->nil) { // 현재 노드가 트리 nil노드와 같으면 그냥 return
return;
}
delete_node(t, node->left); // 왼쪽 재귀 호출
delete_node(t, node->right); // 오른쪽 재귀 호출
free(node); // 현재 노드가 가리키는 공간 할당 해제
node = NULL; // 노드값 NULL로 초기화
return;
}
void delete_rbtree(rbtree *t) {
// TODO: reclaim the tree nodes's memory
if (t == NULL) {
return; // 트리 없다면 return
}
delete_node(t, t->root); // 생성된 노드가 가리키는 공간 할당 해제
free(t->nil); // 트리의 nil노드가 가리키는 공간 할당 해제
t->nil = NULL; // 트리의 nil노드 값 NULL로 초기화
free(t); // 트리가 가리키는 공간 할당 해제
t = NULL; // 트리 값 NULL로 초기화
return;
}
void left_rotate(rbtree *t, node_t *x){
node_t *y = x->right; // y에 x의 오른쪽 자녀를 넣음
x->right = y->left; // y 왼쪽 자녀를 x의 오른쪽으로 옮김
if(y->left != t->nil){ // y 왼쪽 자녀 있다면
y->left->parent = x; // 그 왼쪽 자녀의 부모값을 x로 지정
}
y->parent = x->parent; // y의 부모를 x의 부모로 변경
if (x->parent == t->nil){ // x가 root인 경우 (부모가 nil)
t->root = y; // 트리의 루트를 y로 변경
}else if (x == x->parent->left){ // x가 x부모의 왼쪽 자식인 경우
x->parent->left = y; // x부모의 왼쪽 자식을 y로 변경
}else{ // x가 x 부모의 오른쪽 자식인 경우
x->parent->right = y; // x부모의 오른쪽 자식을 y로 변경
}
y->left = x; // y의 왼쪽자식을 x로
x->parent = y; // x의 부모를 y로
return;
}
void right_rotate(rbtree *t, node_t *x){ // left rotate 반대로
node_t *y = x->left;
x->left = y->right;
if(y->right != t->nil){
y->right->parent = x;
}
y->parent = x->parent;
if (x->parent == t->nil){
t->root = y;
}else if (x == x->parent->right){
x->parent->right = y;
}else{
x->parent->left = y;
}
y->right = x;
x->parent = y;
return;
}