Krafton_jungle 5기 5주차 WIL - RB_Tree

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)을 수행.
• 루트 노드의 색상 변경:
  • 마지막으로, 루트 노드의 색상을 검은색으로 변경하여 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원칙에 위배되지 않도록 재정렬하는 함수.

 

노드를 재정렬하는 순서는 다음과 같다.

 

1. 초기 설정:
   • 삭제된 노드의 대체 노드와 삭제된 노드의 색상을 기반으로 고려해야 할 여러 상황을 검사.
2. 대체 노드가 왼쪽에 있을 경우:
   • Case 1: 삼촌 노드가 빨간색인 경우
     • 삼촌 노드와 부모 노드의 색상을 바꾸고 부모 노드를 기준으로 왼쪽으로 회전.
   • Case 2: 삼촌 노드와 양쪽 자식 노드가 모두 검은색인 경우
     • 삼촌 노드를 빨간색으로 변경하고 현재 노드를 부모 노드로 옮긴다.
   • Case 3: 삼촌 노드의 오른쪽 자식이 검은색인 경우
     • 왼쪽 자식의 색상을 검은색으로, 삼촌 노드의 색상을 빨간색으로 변경.
     • 삼촌 노드를 기준으로 오른쪽으로 회전.
     • 회전 후 적절한 색상 변경을 통해 균형을 맞춘다.
3. 대체 노드가 오른쪽에 있을 경우:
   • 위의 경우와 비슷하나 방향만 반대로 적용.
4. 루트 노드의 색상 변경:
   • 마지막에 루트 노드의 색상을 검은색으로 설정하여 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);
}