RB_Tree
1. RB_Tree 초기화
rbtree *new_rbtree(void)
{
rbtree *p = (rbtree *)malloc(sizeof(rbtree));
if (p == NULL)
{
perror("Failed to allocate memory for RB tree");
exit(EXIT_FAILURE);
}
// TODO: initialize struct if needed
p->nil = (node_t *)malloc(sizeof(rbtree));
if (p->nil == NULL)
{
perror("Failed to allocate memory for sentinel node");
exit(EXIT_FAILURE);
}
p->nil->color = RBTREE_BLACK;
p->root = p->nil;
return p;
}
난 RB_Tree의 NIL 노드를 하나만 선언해서 모두가 같은 NIL노드를 가르키게 되는 방법인 센티넬 노드를 사용했는데, 이 방범의 장점은 NIL 노드를 선언할때마다 추가적인 메모리 선언이 필요 없으며, root의 부모 또한 NIL 노드를 가르키게끔 해서 이중포인터 없이 root 노드에 대한변경작업을 가능하게 해준다.
위 코드를 보면 RB트리를 초기화 한 후 nil노드에 대한 메모리를 할당해주는 모습을 볼 수 있다.
이후 root에 값이 들어오면 root의 부모포인터는 nil 노드를 가르키게 될 것이다.
2. RB_Tree 삽입
RB트리의 삽입을 구현하려면 우선 RB트리의 특징에 따라 해당 노드를 rotate하는 코드를 구현해야 하는데 이는 다음과 같다.
// 왼쪽 회전
void left_rotate(rbtree *T, node_t *cur_node)
{
node_t *target_node = cur_node->right;
cur_node->right = target_node->left;
if (target_node->left != T->nil)
{
target_node->left->parent = cur_node;
}
target_node->parent = cur_node->parent;
// 만약 현재 노드가 root였다면
if (cur_node->parent == T->nil)
{
T->root = target_node;
// 만약 cur 노드가 parant 기준 왼쪽에 존재하면
}
else if (cur_node == cur_node->parent->left)
{
cur_node->parent->left = target_node;
// 만약 cur 노드가 parant 기준 오른쪽에 존재하면
}
else
{
cur_node->parent->right = target_node;
}
target_node->left = cur_node;
cur_node->parent = target_node;
}
void right_rotate(rbtree *T, node_t *cur_node)
{
node_t *target_node = cur_node->left;
cur_node->left = target_node->right;
if (target_node->right != T->nil)
{
target_node->right->parent = cur_node;
}
target_node->parent = cur_node->parent;
// 만약 현재 노드가 root였다면
if (cur_node->parent == T->nil)
{
T->root = target_node;
// 만약 cur 노드가 parant 기준 왼쪽에 존재하면
}
else if (cur_node == cur_node->parent->left)
{
cur_node->parent->left = target_node;
// 만약 cur 노드가 parant 기준 오른쪽에 존재하면
}
else
{
cur_node->parent->right = target_node;
}
target_node->right = cur_node;
cur_node->parent = target_node;
}
각 노드를 회전시키고 서브트리의 방향을 돌아간 방향으로 바꿔주는 코드를 먼저 짜준다.
이 후 삽입이 이뤄지고 노드를 회전시키며 삽입된 값을 재정렬해주면 된다.
참고로 RB트리는 이분탐색트리라서 노드를 삽입하는 과정은 같다.
void rbtree_insert_fixup(rbtree *t, node_t *new_node)
{
while (new_node->parent->color == RBTREE_RED)
{
// 만약 부모 노드가 할아버지 노드 기준 왼쪽에 있을때
if (new_node->parent == new_node->parent->parent->left)
{
node_t *uncle_node = new_node->parent->parent->right;
// 만약 RB트리 부모와 삼촌 노드가 모두 RED일때 쭈왑
if (uncle_node->color == RBTREE_RED)
{
new_node->parent->color = RBTREE_BLACK;
new_node->parent->parent->color = RBTREE_RED;
uncle_node->color = RBTREE_BLACK;
new_node = new_node->parent->parent;
// 바꿨으면 다시 반복문 초기화
continue;
// 만약 다른색이고 할아버지 노드와 부모 노드가 꺾여있다면
} if (new_node == new_node->parent->right)
{
new_node = new_node->parent;
// 펴주기
left_rotate(t, new_node);
}
new_node->parent->color = RBTREE_BLACK;
new_node->parent->parent->color = RBTREE_RED;
right_rotate(t, new_node->parent->parent);
}
else
{
node_t *uncle_node = new_node->parent->parent->left;
if (uncle_node->color == RBTREE_RED)
{
new_node->parent->color = RBTREE_BLACK;
new_node->parent->parent->color = RBTREE_RED;
uncle_node->color = RBTREE_BLACK;
new_node = new_node->parent->parent;
continue;
}
else if (new_node == new_node->parent->left)
{
new_node = new_node->parent;
right_rotate(t, new_node);
}
new_node->parent->color = RBTREE_BLACK;
new_node->parent->parent->color = RBTREE_RED;
left_rotate(t, new_node->parent->parent);
}
}
t->root->color = RBTREE_BLACK;
}
node_t *rbtree_insert(rbtree *t, const key_t key)
{
node_t *new_node = (node_t *)malloc(sizeof(node_t));
new_node->color = RBTREE_RED;
new_node->key = key;
new_node->left = new_node->right = t->nil;
node_t *cur_node = t->root;
node_t *prev_node = t->nil;
while (cur_node != t->nil)
{
prev_node = cur_node;
if (new_node->key < cur_node->key)
{
cur_node = cur_node->left;
}
else
{
cur_node = cur_node->right;
}
}
new_node->parent = prev_node;
// 만약 바로 반복문에 탈출했다면 루트라는 뜻
if (prev_node == t->nil)
{
t->root = new_node;
}
else if (new_node->key < prev_node->key)
{
prev_node->left = new_node;
}
else
{
prev_node->right = new_node;
}
// 노드 삽입 후 트리 재정렬
rbtree_insert_fixup(t, new_node);
// TODO: implement insert
return t->root;
}
우선 rbtree_insert함수는 기존 이분 탐색트리의 값을 추가하는 방법과 완전 유사하다. 하지만 이어서 실행되는 rbtree_insert_fixup 함수에 RB트리만의 정렬법이 수행되는데, 이 절차는 다음과 같다.
- 만약 삽입된 노드의 부모 노드의 색상이 빨간색이라면, RB 트리의 특성을 유지하기 위해 회전과 색상 조정을 수행.
- Case 1: 삽입된 노드의 부모 노드와 그 부모 노드의 형제 노드가 모두 빨간색인 경우
- 부모 노드와 형제 노드의 색상을 검은색으로 변경.
- 부모의 부모 노드(즉, 삽입된 노드의 조부모)의 색상을 빨간색으로 변경.
- 삽입된 노드를 부모의 부모 노드로 옮긴다.
- Case 2: 삽입된 노드의 부모 노드가 빨간색이지만, 그 부모 노드의 형제 노드는 검은색인 경우
- 삽입된 노드가 부모 노드의 오른쪽 자식이고, 부모 노드가 부모의 왼쪽 자식인 경우
- 삽입된 노드를 부모 노드로 옮긴다.
- 왼쪽 회전(Left Rotate)을 수행.
- 부모 노드의 색상을 검은색으로 변경.
- 부모의 부모 노드의 색상을 빨간색으로 변경.
- 오른쪽 회전(Right Rotate)을 수행.
- 삽입된 노드가 부모 노드의 오른쪽 자식이고, 부모 노드가 부모의 왼쪽 자식인 경우
- Case 1: 삽입된 노드의 부모 노드와 그 부모 노드의 형제 노드가 모두 빨간색인 경우
- 루트 노드의 색상 변경:
- 마지막으로, 루트 노드의 색상을 검은색으로 변경하여 RB 트리의 루트 노드가 항상 검은색이 되도록 한다.
해당 방법을 숙지하고 위의 코드를 읽어보면 좀 더 이해가 쉽다.
3. RB_Tree 탐색
node_t *rbtree_find(const rbtree *t, const key_t key)
{
// TODO: implement find
node_t *cur = t->root;
while (cur != t->nil)
{
if (cur->key == key)
{
return cur;
}
else if (cur->key < key)
{
cur = cur->right;
}
else
{
cur = cur->left;
}
}
return NULL;
}
이 코드는 이진 탐색트리의 탐색 방식과 완전 동일하다고 봐도 괜찮음
4. RB_Tree 삭제
삭제를 하는데 사용되는 함수는 총 4개.
1. target node를 부모로부터 때어내고 대체할 노드를 붙히는 transplant 함수.
2. 삭제하려는 노드의 successor를 찾아내는 find_successor 함수.
3. transplant함수를 사용해 실질적으로 node를 삭제하는 rbtree_erase 함수.
4. 노드를 삭제하고 난 뒤, 트리를 재정렬하는 rbtree_erase_fixup 함수.
1. transplant
void rb_transplant(rbtree *t, node_t *u, node_t *v){
// 만약 삭제 노드가 root면
if (u->parent == t->nil) {
t->root = v;
// 부모기준 왼쪽이면
} else if (u == u->parent->left) {
u->parent->left = v;
// 부모기준 오른쪽이면
} else {
u->parent->right = v;
}
// 양방향 매핑
v->parent = u->parent;
// 최종 삭제는 밖에서
}
target 노드인 u를 부모노드로부터 때어내고, 대체할 노드인 v를 붙여놓는 코드다.
2. find_successor
node_t * find_successor(node_t *cur_node, node_t *nil) {
cur_node = cur_node->right;
while (cur_node->left != nil) {
cur_node = cur_node->left;
}
return cur_node;
}
재귀적으로 successor를 탐색하고 해당 노드를 return하는 코드.
3. rbtree_erase
int rbtree_erase(rbtree *t, node_t *z)
{
node_t *y = z;
// 최초 target node 색깔 저장
color_t y_original_color = y->color;
// 대체 노드 초기화
node_t *x;
// 자식이 하나만 있는 경우
if (z->left == t->nil) {
x = z->right;
rb_transplant(t, z, z->right);
} else if (z->right == t->nil) {
x = z->left;
rb_transplant(t, z, z->left);
} else {
// 후임자 탐색
y = find_successor(z, t->nil);
y_original_color = y->color;
// 한번밖에 안들어가면 대체할 노드는 그대로
x = y->right;
// 만약 edge가 내려갔으면
if (y->parent == z) {
x->parent = y;
} else {
// 후임자의 오른쪽을 기존 후임자 노드 위치로 이동
rb_transplant(t, y, y->right);
// 후임자와 target node의 위치를 swap할 준비
y->right = z->right;
y->right->parent = y;
}
// target node와 후임자의 노드를 swap
rb_transplant(t, z, y);
// target의 속성을 물려받음
y->left = z->left;
y->left->parent = y;
y->color = z->color;
}
// 자유
free(z);
// 대참사 발생
if (y_original_color == RBTREE_BLACK) {
// 대체 노드부터 fixup
rbtree_erase_fixup(t, x);
}
return 0;
}
조건을 만족하는 노드를 찾고 삭제하는 함수.
4. rbtree_erase_fixup
void rbtree_erase_fixup(rbtree *t, node_t *x) {
while (x != t->root && x->color == RBTREE_BLACK) {
// 대체 노드가 왼쪽에 있을때
if (x == x->parent->left) {
node_t *w = x->parent->right;
// 삼촌 노드의 색이 빨강일 경우 부모와 삼촌 노드의 색을 바꾸고 왼쪽으로 rotate
if (w->color == RBTREE_RED) {
w->color = RBTREE_BLACK;
x->parent->color = RBTREE_RED;
left_rotate(t, x->parent);
// 회전 후 삼촌 노드의 위치를 재조정
w = x->parent->right;
}
if (w->left->color == RBTREE_BLACK && w->right->color == RBTREE_BLACK) {
w->color = RBTREE_RED;
x = x->parent;
// 만약 왼쪽 red 오른쪽 black이면
} else {
if (w->right->color == RBTREE_BLACK) {
// 색 변경
w->left->color = RBTREE_BLACK;
w->color = RBTREE_RED;
// 돌리고 오른 자식이 red가 되게끔 만든다.
right_rotate(t, w);
w = x->parent->right;
}
// 최종적으로 오른쪽 자식이 red일때 작업을 수행 "깜부깜"
w->color = x->parent->color;
x->parent->color = RBTREE_BLACK;
w->right->color = RBTREE_BLACK;
left_rotate(t, x->parent);
// 깜깜부가 수행되면 사실상 노드의 정렬이 끝났다고 봐도 무방함
x = t->root;
}
// 대체 노드가 오른쪽에 있을때 -> 정반대
} else {
node_t *w = x->parent->left;
// 삼촌 노드의 색이 빨강일 경우 부모와 삼촌 노드의 색을 바꾸고 왼쪽으로 rotate
if (w->color == RBTREE_RED) {
w->color = RBTREE_BLACK;
x->parent->color = RBTREE_RED;
right_rotate(t, x->parent);
// 회전 후 삼촌 노드의 위치를 재조정
w = x->parent->left;
}
if (w->left->color == RBTREE_BLACK && w->right->color == RBTREE_BLACK) {
w->color = RBTREE_RED;
x = x->parent;
// 만약 왼쪽 red 오른쪽 black이면
} else {
if (w->left->color == RBTREE_BLACK) {
// 색 변경
w->right->color = RBTREE_BLACK;
w->color = RBTREE_RED;
// 돌리고 오른 자식이 red가 되게끔 만든다.
left_rotate(t, w);
w = x->parent->left;
}
// 최종적으로 오른쪽 자식이 red일때 작업을 수행 "깜부깜"
w->color = x->parent->color;
x->parent->color = RBTREE_BLACK;
w->left->color = RBTREE_BLACK;
right_rotate(t, x->parent);
// 깜깜부가 수행되면 사실상 노드의 정렬이 끝났다고 봐도 무방함
x = t->root;
}
}
}
// 트리는 무조건 black
x->color = RBTREE_BLACK;
}
마지막으로 노드가 삭제된 코드를 RB트리의 5원칙에 위배되지 않도록 재정렬하는 함수.
노드를 재정렬하는 순서는 다음과 같다.
- 초기 설정:
- 삭제된 노드의 대체 노드와 삭제된 노드의 색상을 기반으로 고려해야 할 여러 상황을 검사.
- 대체 노드가 왼쪽에 있을 경우:
- Case 1: 삼촌 노드가 빨간색인 경우
- 삼촌 노드와 부모 노드의 색상을 바꾸고 부모 노드를 기준으로 왼쪽으로 회전.
- Case 2: 삼촌 노드와 양쪽 자식 노드가 모두 검은색인 경우
- 삼촌 노드를 빨간색으로 변경하고 현재 노드를 부모 노드로 옮긴다.
- Case 3: 삼촌 노드의 오른쪽 자식이 검은색인 경우
- 왼쪽 자식의 색상을 검은색으로, 삼촌 노드의 색상을 빨간색으로 변경.
- 삼촌 노드를 기준으로 오른쪽으로 회전.
- 회전 후 적절한 색상 변경을 통해 균형을 맞춘다.
- Case 1: 삼촌 노드가 빨간색인 경우
- 대체 노드가 오른쪽에 있을 경우:
- 위의 경우와 비슷하나 방향만 반대로 적용.
- 루트 노드의 색상 변경:
- 마지막에 루트 노드의 색상을 검은색으로 설정하여 RB 트리의 특성을 유지.
이 외에도 최대값을 지닌 노드를 찾는 함수나 기타 여러가지 함수가 있지만 이는 삽입, 삭제에 비해 코드가 간단하고 중요도가 낮으니 따로 설명하지는 않겠다.
전체코드
#include "rbtree.h"
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
// 왼쪽 회전
void left_rotate(rbtree *T, node_t *cur_node)
{
node_t *target_node = cur_node->right;
cur_node->right = target_node->left;
if (target_node->left != T->nil)
{
target_node->left->parent = cur_node;
}
target_node->parent = cur_node->parent;
// 만약 현재 노드가 root였다면
if (cur_node->parent == T->nil)
{
T->root = target_node;
// 만약 cur 노드가 parant 기준 왼쪽에 존재하면
}
else if (cur_node == cur_node->parent->left)
{
cur_node->parent->left = target_node;
// 만약 cur 노드가 parant 기준 오른쪽에 존재하면
}
else
{
cur_node->parent->right = target_node;
}
target_node->left = cur_node;
cur_node->parent = target_node;
}
void right_rotate(rbtree *T, node_t *cur_node)
{
node_t *target_node = cur_node->left;
cur_node->left = target_node->right;
if (target_node->right != T->nil)
{
target_node->right->parent = cur_node;
}
target_node->parent = cur_node->parent;
// 만약 현재 노드가 root였다면
if (cur_node->parent == T->nil)
{
T->root = target_node;
// 만약 cur 노드가 parant 기준 왼쪽에 존재하면
}
else if (cur_node == cur_node->parent->left)
{
cur_node->parent->left = target_node;
// 만약 cur 노드가 parant 기준 오른쪽에 존재하면
}
else
{
cur_node->parent->right = target_node;
}
target_node->right = cur_node;
cur_node->parent = target_node;
}
rbtree *new_rbtree(void)
{
rbtree *p = (rbtree *)malloc(sizeof(rbtree));
if (p == NULL)
{
perror("Failed to allocate memory for RB tree");
exit(EXIT_FAILURE);
}
// TODO: initialize struct if needed
p->nil = (node_t *)malloc(sizeof(rbtree));
if (p->nil == NULL)
{
perror("Failed to allocate memory for sentinel node");
exit(EXIT_FAILURE);
}
p->nil->color = RBTREE_BLACK;
p->root = p->nil;
return p;
}
void delete_rbtree_recursive(node_t *node, node_t *nil) {
if (node == nil) {
return;
}
delete_rbtree_recursive(node->left, nil);
delete_rbtree_recursive(node->right, nil);
free(node);
}
void delete_rbtree(rbtree *t)
{
delete_rbtree_recursive(t->root, t->nil);
free(t->nil);
free(t);
}
void rbtree_insert_fixup(rbtree *t, node_t *new_node)
{
while (new_node->parent->color == RBTREE_RED)
{
// 만약 부모 노드가 할아버지 노드 기준 왼쪽에 있을때
if (new_node->parent == new_node->parent->parent->left)
{
node_t *uncle_node = new_node->parent->parent->right;
// 만약 RB트리 부모와 삼촌 노드가 모두 RED일때 쭈왑
if (uncle_node->color == RBTREE_RED)
{
new_node->parent->color = RBTREE_BLACK;
new_node->parent->parent->color = RBTREE_RED;
uncle_node->color = RBTREE_BLACK;
new_node = new_node->parent->parent;
// 바꿨으면 다시 반복문 초기화
continue;
// 만약 다른색이고 할아버지 노드와 부모 노드가 꺾여있다면
} if (new_node == new_node->parent->right)
{
new_node = new_node->parent;
// 펴주기
left_rotate(t, new_node);
}
new_node->parent->color = RBTREE_BLACK;
new_node->parent->parent->color = RBTREE_RED;
right_rotate(t, new_node->parent->parent);
}
else
{
node_t *uncle_node = new_node->parent->parent->left;
if (uncle_node->color == RBTREE_RED)
{
new_node->parent->color = RBTREE_BLACK;
new_node->parent->parent->color = RBTREE_RED;
uncle_node->color = RBTREE_BLACK;
new_node = new_node->parent->parent;
continue;
}
else if (new_node == new_node->parent->left)
{
new_node = new_node->parent;
right_rotate(t, new_node);
}
new_node->parent->color = RBTREE_BLACK;
new_node->parent->parent->color = RBTREE_RED;
left_rotate(t, new_node->parent->parent);
}
}
t->root->color = RBTREE_BLACK;
}
node_t *rbtree_insert(rbtree *t, const key_t key)
{
node_t *new_node = (node_t *)malloc(sizeof(node_t));
new_node->color = RBTREE_RED;
new_node->key = key;
new_node->left = new_node->right = t->nil;
node_t *cur_node = t->root;
node_t *prev_node = t->nil;
while (cur_node != t->nil)
{
prev_node = cur_node;
if (new_node->key < cur_node->key)
{
cur_node = cur_node->left;
}
else
{
cur_node = cur_node->right;
}
}
new_node->parent = prev_node;
// 만약 바로 반복문에 탈출했다면 루트라는 뜻
if (prev_node == t->nil)
{
t->root = new_node;
}
else if (new_node->key < prev_node->key)
{
prev_node->left = new_node;
}
else
{
prev_node->right = new_node;
}
// 노드 삽입 후 트리 재정렬
rbtree_insert_fixup(t, new_node);
// TODO: implement insert
return t->root;
}
node_t *rbtree_find(const rbtree *t, const key_t key)
{
// TODO: implement find
node_t *cur = t->root;
while (cur != t->nil)
{
if (cur->key == key)
{
return cur;
}
else if (cur->key < key)
{
cur = cur->right;
}
else
{
cur = cur->left;
}
}
return NULL;
}
node_t *smallest_value(node_t *cur_node, node_t *nil)
{
if (cur_node == nil) {
return nil;
}
node_t *left_node = smallest_value(cur_node->left, nil);
node_t *right_node = smallest_value(cur_node->right, nil);
if (left_node == nil && right_node == nil) {
return cur_node;
}
node_t *smallest = cur_node;
if (left_node != nil && left_node->key < smallest->key) {
smallest = left_node;
}
if (right_node != nil && right_node->key < smallest->key) {
smallest = right_node;
}
return smallest;
}
node_t * greatest_value(node_t *cur_node, node_t *nil)
{
if (cur_node == nil) {
return cur_node;
}
node_t *left_node = greatest_value(cur_node->left, nil);
node_t *right_node = greatest_value(cur_node->right, nil);
if (cur_node->key >= left_node->key && cur_node->key >= right_node->key)
return cur_node;
else if (left_node->key >= cur_node->key && left_node->key >= right_node->key)
return left_node;
else
return right_node;
}
node_t *rbtree_min(const rbtree *t)
{
node_t* res_node = smallest_value(t->root, t->nil);
return res_node;
}
node_t *rbtree_max(const rbtree *t)
{
node_t* res_node = greatest_value(t->root, t->nil);
return res_node;
}
void rb_transplant(rbtree *t, node_t *u, node_t *v){
// 만약 삭제 노드가 root면
if (u->parent == t->nil) {
t->root = v;
// 부모기준 왼쪽이면
} else if (u == u->parent->left) {
u->parent->left = v;
// 부모기준 오른쪽이면
} else {
u->parent->right = v;
}
// 양방향 매핑
v->parent = u->parent;
// 최종 삭제는 밖에서
}
node_t * find_successor(node_t *cur_node, node_t *nil) {
cur_node = cur_node->right;
while (cur_node->left != nil) {
cur_node = cur_node->left;
}
return cur_node;
}
void rbtree_erase_fixup(rbtree *t, node_t *x) {
while (x != t->root && x->color == RBTREE_BLACK) {
// 대체 노드가 왼쪽에 있을때
if (x == x->parent->left) {
node_t *w = x->parent->right;
// 삼촌 노드의 색이 빨강일 경우 부모와 삼촌 노드의 색을 바꾸고 왼쪽으로 rotate
if (w->color == RBTREE_RED) {
w->color = RBTREE_BLACK;
x->parent->color = RBTREE_RED;
left_rotate(t, x->parent);
// 회전 후 삼촌 노드의 위치를 재조정
w = x->parent->right;
}
if (w->left->color == RBTREE_BLACK && w->right->color == RBTREE_BLACK) {
w->color = RBTREE_RED;
x = x->parent;
// 만약 왼쪽 red 오른쪽 black이면
} else {
if (w->right->color == RBTREE_BLACK) {
// 색 변경
w->left->color = RBTREE_BLACK;
w->color = RBTREE_RED;
// 돌리고 오른 자식이 red가 되게끔 만든다.
right_rotate(t, w);
w = x->parent->right;
}
// 최종적으로 오른쪽 자식이 red일때 작업을 수행 "깜부깜"
w->color = x->parent->color;
x->parent->color = RBTREE_BLACK;
w->right->color = RBTREE_BLACK;
left_rotate(t, x->parent);
// 깜깜부가 수행되면 사실상 노드의 정렬이 끝났다고 봐도 무방함
x = t->root;
}
// 대체 노드가 오른쪽에 있을때 -> 정반대
} else {
node_t *w = x->parent->left;
// 삼촌 노드의 색이 빨강일 경우 부모와 삼촌 노드의 색을 바꾸고 왼쪽으로 rotate
if (w->color == RBTREE_RED) {
w->color = RBTREE_BLACK;
x->parent->color = RBTREE_RED;
right_rotate(t, x->parent);
// 회전 후 삼촌 노드의 위치를 재조정
w = x->parent->left;
}
if (w->left->color == RBTREE_BLACK && w->right->color == RBTREE_BLACK) {
w->color = RBTREE_RED;
x = x->parent;
// 만약 왼쪽 red 오른쪽 black이면
} else {
if (w->left->color == RBTREE_BLACK) {
// 색 변경
w->right->color = RBTREE_BLACK;
w->color = RBTREE_RED;
// 돌리고 오른 자식이 red가 되게끔 만든다.
left_rotate(t, w);
w = x->parent->left;
}
// 최종적으로 오른쪽 자식이 red일때 작업을 수행 "깜부깜"
w->color = x->parent->color;
x->parent->color = RBTREE_BLACK;
w->left->color = RBTREE_BLACK;
right_rotate(t, x->parent);
// 깜깜부가 수행되면 사실상 노드의 정렬이 끝났다고 봐도 무방함
x = t->root;
}
}
}
// 트리는 무조건 black
x->color = RBTREE_BLACK;
}
int rbtree_erase(rbtree *t, node_t *z)
{
node_t *y = z;
// 최초 target node 색깔 저장
color_t y_original_color = y->color;
// 대체 노드 초기화
node_t *x;
// 자식이 하나만 있는 경우
if (z->left == t->nil) {
x = z->right;
rb_transplant(t, z, z->right);
} else if (z->right == t->nil) {
x = z->left;
rb_transplant(t, z, z->left);
} else {
// 후임자 탐색
y = find_successor(z, t->nil);
y_original_color = y->color;
// 한번밖에 안들어가면 대체할 노드는 그대로
x = y->right;
// 만약 edge가 내려갔으면
if (y->parent == z) {
x->parent = y;
} else {
// 후임자의 오른쪽을 기존 후임자 노드 위치로 이동
rb_transplant(t, y, y->right);
// 후임자와 target node의 위치를 swap할 준비
y->right = z->right;
y->right->parent = y;
}
// target node와 후임자의 노드를 swap
rb_transplant(t, z, y);
// target의 속성을 물려받음
y->left = z->left;
y->left->parent = y;
y->color = z->color;
}
// 자유
free(z);
// 대참사 발생
if (y_original_color == RBTREE_BLACK) {
// 대체 노드부터 fixup
rbtree_erase_fixup(t, x);
}
return 0;
}
int inorder_rbtree(const rbtree *t, key_t *arr, node_t *cur_node, int index, const int arr_size) {
if (index >= arr_size) {
return index; // index 값 반환
}
if (cur_node == t->nil) {
// nil 노드를 만나면 index 값을 반환
return index;
}
index = inorder_rbtree(t, arr, cur_node->left, index, arr_size);
// RB트리를 전위순회 하며 얻은 값을 arr에 append하고 포인터 전진
arr[index++] = cur_node->key;
index = inorder_rbtree(t, arr, cur_node->right, index, arr_size);
return index; // 최종 index 값을 반환
}
int rbtree_to_array(const rbtree *t, key_t *arr, const size_t n)
{
inorder_rbtree(t, arr, t->root, 0, n);
return 0;
}
void rbtree_to_print(node_t *t, node_t *nil)
{
// TODO: implement to_print
if (t == nil)
{
printf("노드 바닥이에용\n");
return;
}
printf("key = %d, color = %d \n", t->key, t->color);
rbtree_to_print(t->left, nil);
rbtree_to_print(t->right, nil);
}
'Krafton_Jungle > Study' 카테고리의 다른 글
Krafton_jungle 5기 5주차 WIL - Exceptional Control Flow (0) | 2024.04.23 |
---|---|
Krafton_jungle 5기 5주차 WIL - Linker (0) | 2024.04.23 |
Krafton_jungle 5기 31 ~ 32일차 TIL - RB-Tree, 알고리즘 (2) | 2024.04.19 |
Krafton_jungle 5기 30일차 TIL - C언어 기본 개념 (0) | 2024.04.16 |
Krafton_jungle 5기 28 ~ 29일차 TIL - 자료구조 (2) | 2024.04.15 |