[Red-Black 트리]삭제 - 구현

📌레드블랙 트리의 다섯가지 속성

1.모든 노드는 red 혹은 black
2.루트 노드는 black
3.모든 nil노드는 black
4.red의 자녀들은 반드시 black == red가 연속적으로 존재할 수 없다.
5.임의의 노드에서 자손 nii 노드들까지 가는 경로들의 black 수는 같다 (자기 자신은 카운트에서 제외)

 

📌rotatiom/recolor

Rotation 을 통해 이진 탐색트리의 특성을 보전하면서 트리의 구조를 수정해 나갈 수 있고, 각각의 경우에 알맞게 Recolor 해주어 레드-블랙 트리의 특성을 만족시키도록 트리를 구성할 수 있다.

RB tree 의 삭제 과정과, 삭제 후에 delete_fix_up 과정을 거치면서 RB tree의 특성을 만족시키도록 수정하는 과정들을 확인하려고 한다.

 

📌삭제

• 삭제 과정에서는 이진 탐색트리의 특성을 만족하면서 노드를 삭제할 것이다. 이후에 delete_fixup 과정에서 이진탐색트리의 특성과 RB 트리의 특성을 모두 만족시키기 위해 트리의 구조를 변형한다.
• 삭제 과정에서 2가지 상황이 빈번하게 일어난다.
  이를 함수화 시켜 놓은 것이 있는데, 슈도코드를 통해 그것을 먼저 검토하고, 삭제 과정을 살펴보자.

📌delete 슈도코드

---

📌이식

• 삭제될 노드를 target 노드라고 하자, target 노드는 루트노드가 아니라면 parent 노드의 왼쪽 자식 혹은 오른쪽 자식일 것이다.
• 각각의 노드들은 parent, left, right, key, color 필드를 갖고있다. 이식 (transplant) 과정에서는, target 노드와 그 노드의 parent 노드의 연결관계만을 처리하는 과정이다.
• target 노드를 대체할 노드를 구했다고 가정하고, target의 parent 입장에서 왼쪽 자식이었는지, 오른쪽 자식이었는지 파악한 후에 그 자식을 대체할 노드로 지정하고 대체할 노드 또한 target의 parent를 부모노드로 지정하여 두 노드를 연결한다.

u : 삭제할 노드, v : 대체할 노드

• line 1 : if 삭제할 노드(u)의 부모노드가 nil 일 때,
  -> 삭제할 노드가 루트노드라면,
• line 2 : 트리의 루트노드를 대체할 노드(v)로 설정.
• line 3 : else if 삭제할 노드(u)가 부모노드의 왼쪽 자식일 때,
• line 4 : 삭제할 노드(u)의 왼쪽 자식을 대체할 노드(v)로 설정.
• line 5 : else (삭제할 노드(u)가 부모노드의 오른쪽 자식일 때)
  -> 삭제할 노드(u)의 오른쪽 자식을 대체할 노드(v)로 설정.
• line 6 : 삭제할 노드(u)의 부모노드를 대체할 노드(v)의 부모노드로 설정.

---

📌최소값의 노드 산출

• tree_minimum 함수는 삭제할 노드의 위치를 대체할 노드를 산출한다.

• 키값이 10인 노드를 삭제할 때,
  이진검색트리의 특성을 유지하면서 10을 대체할 수 있는 노드는 5, 14 다.
• 대체할 노드는 삭제될 노드10의 오른쪽 서브트리에서 가장 작은 값 또는 왼쪽 서브트리에서 가장 큰 값이다.
• 오른쪽 서브트리에서 가장 작은 값은 오른쪽 서브트리의 루트노드(16)에서 리프노드(nil)을 만나기 직전 노드인 14 이고,
• 왼쪽 서브트리에서 가장 큰 값은 왼쪽 서브트리의 루트노드(13)에서 리프노드(nil)을 만나기 직전 노드인 5이다.
• 둘중에 아무거나 써도 되는데, 오른쪽 서브트리의 minimum 값을 대체할 노드로 설정하였기 때문에, minimum 함수를 사용할 것이다.

👉🏻step1 : target, target color 저장

• target = 35
• target_original_color = target -> color
  • 지워질 노드의 색을 변수에 저장

👉🏻step2 : target의 자식 정보확인

• 삭제할 노드를 y에 복사하여 포인터처럼 활용
• 대체할 노드를 x에 따로 저장

👉🏻step3 :

• case는 3가지 case로 나뉜다.
• 예시는 case 1에 해당한다.

✏️case.1 : 왼쪽 자식이 없을때 ( 자식이 둘다 없을 때도 해당)

• target의 오른쪽 자식을 x로 설정
• 오른쪽 자식을 target 노드에 이식한다.

✏️case.2 : 오른쪽 자식이 없을때

• target의 왼쪽 자식을 x로 설정
• 왼쪽 자식을 target 노드에 이식

✏️case.3 : 자식이 둘다 있을때

---

📌delete_fix_up

• when : y-original color is black
• while문 조건 : x 노드의 색이 블랙 또는 x가 루트가 아닐때.
• while문 종료 후 : x 의 컬러를 블랙으로 칠함.

💡35를 삭제할때

y-original color = black, x = y-> right이므로 x = nil이며, x - color = black

delete_fix_up 에 들어간다.

 

📌delete_fix_up 슈도코드

📌case.1

📌case.2

• case.1 이후 왼쪽자식이 red이면 case2는 수행하지 않는다.

📌case.3

• case 3의 경우 항상 case 4로 경유한다.

📌case.4

• case.3을 거치면 case 4의 형태로 바뀐다.
• case.4를 거치면 fix_up 과정이 종료된다. (case2를 거치고 종료되는 경우도 있다.)

📌delete_fix_up 과정에서 탈출하는 경우

1. while -> case

• case 1 :
  -> case 2 -> ? (END or continue while)
  -> case 3 -> case 4 (END)
• case 2 :
  -> END
  -> ?(while)
• case 3 :
  -> case 4 -> END
• case 4 :
  -> END

2. while 해당안됨

• x 의 color 를 검정색으로 칠하고 종료.

---

/*
#레드-블랙 트리 조건
1.모든 노드는 red 혹은 black
2.루트 노드는 black
3.모든 nil노드는 black
4.red의 자녀들은 반드시 black == red가 연속적으로 존재할 수 없다.
5.임의의 노드에서 자손 nii 노드들까지 가는 경로들의 black 수는 같다 (자기 자신은 카운트에서 제외)

#Rotation
Rotation을 통해 이진 탐색트리의 특성을 보전하면서 트리의 구조를 수정해 나갈 수 있다.

#Recolor
각각의 경우에 알맞게 recolor 해주어 레드-블랙 트리의 특성을 만족시키도록 트리를 구성할 수 있다.
2
*/
#include "rbtree.h"
#include <stdlib.h>

rbtree *new_rbtree(void){
    rbtree *p = (rbtree *)calloc(1, sizeof(rbtree));
    node_t *NIL = (node_t *)calloc(1, sizeof(node_t));
    p -> nil = NIL;
    p -> root = NIL;
    NIL -> color = RBTREE_BLACK;
    return p;
}

// void DeleteByPostOrder(node_t *root, rbtree *t){
//     if (root == t -> nil)
//     {
//         return;
//     }
//     DeleteByPostOrder(root -> left, t);
//     DeleteByPostOrder(root -> right, t);
//     free(root);
// }


// 노드 메모리 해제
void delete_node(node_t *node, rbtree *t) {
  // 현재 노드가 nil이면 return : 아무 값이 없어서 할당될 것도 없음
  if (node == t -> nil) { return; }
  // 재귀호출로  끝까지 간 후 해제
  delete_node(node -> left, t);
  delete_node(node -> right, t);
  free(node);
  node = NULL; //할당 해제 후 현재 노드 값을 null로 초기화함
  return;
}


// 트리 메모리 해제
void delete_rbtree(rbtree *t) {
  // TODO: reclaim the tree nodes's memory
  // 트리 없으면 return
  if (t == NULL) { return; }

  delete_node(t ->root, t); //생성된 노드들의 공간 해제
  free(t->nil); //nil 노드 해제
  t->nil = NULL; //할당 해제 후 nil 값 NULL 값으로 초기화 : 예기치않은 오류와 안정성 확보를 위함
  free(t);
  t = NULL;
  return;
}
// x가 부모이고 y가 오른쪽 노드일때 y를 부모로 바꾸고 x를 왼쪽 노드로 회전 시키는 함수
void left_rotation(rbtree *t, node_t *x)
{
  node_t *y = x->right; // x의 오른쪽 노드의 주소를 선언함
  x->right = y->left;   // y의 왼쪽 노드를 x의 오른쪽으로 옮김
  if (y->left != t->nil)
  {                      // 만약 y의 왼쪽 노드가 NIL이 아니라면,
    y->left->parent = x; // 기존 y의 왼쪽에 있던 노드의 parent 노드를 x로 맞추어준다.
  }
  y->parent = x->parent; // x의 자리에 y가 올라왔으므로, 기존 x의 부모를 y의 부모로 바꾸어준다.
  if (x->parent == t->nil)
  {              // 만약 x의 부모가 NIL 이라면, root 노드라는 의미이므로,
    t->root = y; // y를 트리의 root로 선언한다.
  }
  else if (x == x->parent->left)
  {                      // 만약 x가 회전 되기 전에 부모의 왼쪽에 위치한 노드였다면,
    x->parent->left = y; // x부모의 왼쪽을 y로 바꾸어준다.
  }
  else
  {                       // 아니라면, x가 회전 되기 전에 부모의 오른쪽에 위치했다는 의미이므로,
    x->parent->right = y; // x부모의 오른쪽을 y로 바꾸어준다.
  }
  y->left = x;   // y의 왼쪽을 x로 바꾸어준다.
  x->parent = y; // x의 부모를 y로 바꾸어준다.
}

// y가 부모이고 x가 왼쪽 노드일때 x를 부모로 바꾸고 y를 오른쪽 노드로 회전 시키는 함수
void right_rotation(rbtree *t, node_t *y)
{
  node_t *x = y->left; // y의 왼쪽 노드를 선언함
  y->left = x->right;  // x의 오른쪽 노드를 y의 왼쪽으로 옮겨줌
  if (x->right != t->nil)
  {                       // x의 오른쪽이 NIL이 아니라면,
    x->right->parent = y; // 기존 x의 오른쪽에 있었던 노드의 parent 노드를 y로 맞추어준다.
  }
  x->parent = y->parent; // y의 자리에 x가 올라왔으므로, 기존 y의 부모를 x의 부모로 바꾸어준다.
  if (y->parent == t->nil)
  {              // 만약 y의 부모가 NIL 이라면, root 노드라는 의미이므로,
    t->root = x; // x를 트리의 root로 선언한다.
  }
  else if (y == y->parent->left)
  {                      // 만약 y가 회전 되기 전에 부모의 왼쪽에 위치한 노드였다면,
    y->parent->left = x; // y부모의 왼쪽을 x로 바꾸어준다.
  }
  else
  {                       // 아니라면, y가 회전 되기 전에 부모의 오른쪽에 위치했다는 의미이므로,
    y->parent->right = x; // y부모의 오른쪽을 x로 바꾸어준다.
  }
  x->right = y;  // x의 오른쪽을 y로 바꾸어준다.
  y->parent = x; // y의 부모를 x로 바꾸어준다.
}

// 색 변경 함수
void rbtree_insert_fixup(rbtree *t, node_t *z) {
  while (z -> parent -> color == RBTREE_RED) { //z의 부모가 red일때
  // Case # 1 현재 노드의 삼촌, 부모가 red, 할아범이 black : !회전 안 함!
    if (z -> parent == z -> parent -> parent -> left) { //z의 부모가 z의 조상의 왼쪽 자식이면
      node_t *uncle = z -> parent ->parent -> right; //z의 부모의 형제노드 = 삼촌
      if (uncle -> color == RBTREE_RED) { // 삼촌이 red라면
        z -> parent -> color = RBTREE_BLACK; // 부모 red > black
        uncle -> color = RBTREE_BLACK; // 삼촌 red > black
        z -> parent -> parent -> color = RBTREE_RED; // 할아범 black > red
        z = z -> parent -> parent; // 할아버지 가리켜야 다시 while문을 돈다!
      } else { // 삼촌이 black Case 2, 3
        if (z == z -> parent ->right) { //꺾새 모양
          z = z -> parent;
          left_rotation(t, z); // 좌회전
        } // Case 3이 됨 > 색 바꿔주고 우회전하면 끝남
        z -> parent -> color = RBTREE_BLACK;
        z -> parent -> parent -> color = RBTREE_RED;
        right_rotation(t, z -> parent -> parent); // 조상 기준으로 우회전해야함
      }
    } else { //z의 부모가 z의 조상의 오른쪽이면 위의 과정을 반대로
      node_t *uncle = z -> parent -> parent -> left;
      if (uncle -> color == RBTREE_RED) {
        z -> parent -> color = RBTREE_BLACK;
        uncle -> color = RBTREE_BLACK;
        z -> parent -> parent -> color = RBTREE_RED;
        z = z -> parent -> parent;
      } else {
        if (z == z -> parent -> left) {
          z = z -> parent;
          right_rotation(t, z);
        }
        z -> parent -> color = RBTREE_BLACK;
        z -> parent -> parent -> color = RBTREE_RED;
        left_rotation(t, z -> parent ->parent);
      }
    }
  } //While문 끝
  t -> root -> color = RBTREE_BLACK; // 규칙 2를 위해서 root는 항상 black
  return; //void형
}

// 데이터 삽입
node_t *rbtree_insert(rbtree *t, const key_t key) {
  // TODO: implement insert
  node_t *y = t -> nil; // y = 트리의 nil 노드
  node_t *x = t -> root; // x = 트리의 root
  
  while (x != t -> nil) { //x가 nil에 도달할때까지 반복
    y = x;
    if (key < x->key) { //만약 x의 key값보다 삽입할 key의 값이 작으면
      x = x -> left; //x를 x의 왼쪽으로 변경
    } else { //만약 x의 key값보다 삽입할 key값이 크거나 같으면
      x = x -> right;  // x를 x의 오른쪽으로 변경
    }
  }
  //x가 nil을 가리킴 > z를 삽입할 시기
  node_t *z = (node_t *)calloc(1, sizeof(node_t)); // z 노드 생성
  z -> key = key; // z의 key값 넣어줌

  z -> parent = y; // z의 부모는 y
  if (y == t -> nil) { //y가 트리의 nil일때, 비어있던 애(첫 노드)
    t -> root = z; // Case 1 (고려할 필요 없는 경우임 걍 들어감)
  } else if (z -> key < y -> key) { // y의 key값이 삽입할 key값보다 작을 때
    y -> left = z; // y의 왼쪽 자식으로 감
  } else {
    y -> right = z;
  }
  
  z -> left = t -> nil; // z 왼쪽 자식 nil
  z -> right = t -> nil; // z 오른쪽 자식 nil
  z -> color = RBTREE_RED; // 삽입은 늘 red
  // left_rotation(t,z);
  // if (z->parent->parent != NULL) {
  //   right_rotation(t,z);
  // }
  
  rbtree_insert_fixup(t, z);

  return t->root;
}

// 데이터 검색
node_t *rbtree_find(const rbtree *t, const key_t key) {
  // TODO: implement find
  node_t *x = t -> root; //x는 root, root에서부터 검색 시작
  while (x != t -> nil && key != x -> key) { //x가 nil노드가 아니거나 찾는 key값이 x가 아닐때
    if (x -> key < key) { // 찾는 key값보다 key가 클때
      x = x -> right; //x의 오른쪽 자식으로 이동
    } else { //찾는 key값이 더 작을 때
      x = x -> left; //x의 왼쪽 자식으로 이동
    }
  }
  if (x == t -> nil) { // x가 nil 노드 = key값을 찾지 못했을때
    return NULL; // NULL 반환
  }
  return x;
  // return t->root;
}

// 트리의 최소값 = BST특성
node_t *rbtree_min(const rbtree *t) {
  // TODO: implement find
  node_t *x = t -> root; //x는 트리의 루트
  while (x -> left != t -> nil) { //x의 왼쪽 자식이 nil이 아닐때
    x = x -> left; // 왼쪽이 제일 작은 값임
  }
  return x;
}

// 트리의 최대값 = BST특성
node_t *rbtree_max(const rbtree *t) {
  // TODO: implement find
  node_t *x = t -> root; //x는 트리의 루트
  while (x -> right != t -> nil) { //x의 왼쪽 자식이 nil이 아닐때
    x = x -> right; // 오른쪽이 제일 큰 값임
  }
  return x;
}

// 삭제될 노드를 떼어내기 위해 대체노드를 붙이는 함수
void rbtree_transplant(rbtree *t, node_t *u, node_t *v) {
  // u는 삭제될 노드, v는 대체될 노드 u를 지우고 v를 u.p에 연결시킬거임
  // u가 있던 자리에 걍 v 집어넣는 식 = u에 이어진 노드가 없어 고립되어 자동으로 떨어짐
  // 삭제 연산할때 default로 실행됨
  if (u -> parent == t -> nil) { // u의 부모가 nil = u가 root라는 소리
    t -> root = v; // 트리의 root 자리에 v를 집어넣음
  } else if (u == u -> parent -> left) { // 삭제될 노드가 왼쪽 자식일때
    u -> parent -> left = v; // u는 버려지고, v가 붙음
  } else { // 삭제될 노드가 오른쪽 자식
    u -> parent -> right = v; //오른쪽 자식은 이제 v가 됨
  }
  v -> parent = u -> parent; // v의 부모는 u의 부모
  return; //void형
}

void rbtree_erase_fixup(rbtree *t, node_t *x)
{
  node_t *w;
  while (x != t->root && x->color == RBTREE_BLACK) // x가 root가 아니고, x의 색이 BLACK일 동안
  {
    if (x == x->parent->left) // doubly black인 x가 왼쪽 자식일 경우
    {
      w = x->parent->right; // w는 x의 형제 노드
      if (w->color == RBTREE_RED)
      {                                // x의 오른쪽 형제 w가 RED인 경우 -> case 1) doubly black의 형제가 RED인 경우에 해당
        w->color = RBTREE_BLACK;       // 형제의 색을 BLACK으로 변경하고
        x->parent->color = RBTREE_RED; // 형제의 부모의 색을 RED로 변경한다.
        left_rotation(t, x->parent);     // 부모를 기준으로 왼쪽 회전 수행
        w = x->parent->right;          // x의 위치가 바뀌었으므로, x의 형제인 w의 위치 또한 갱신해줌
      } // 이후 경우1은 경우 2,3,4 중 하나로 변환 되었음
      if (w->left->color == RBTREE_BLACK && w->right->color == RBTREE_BLACK) // 형제의 자식이 모두 BLACK일 경우 case 2) doubly black의 형제의 자식이 모두 BLACK일 경우에 해당
      {
        w->color = RBTREE_RED; // 형제의 검은색을 부모에게 주므로 기존 BLACK에서, RED로 변함
        x = x->parent;         // x의 부모가 x의 extra black을 물려받아, 새로운 red and black 또는 doubly black이 됨
      }
      else // 형제의 자식 중 RED인 자식이 있을 경우 case 3)에 해당, 회전을 통해 case 4)로 변경해주어야함
      {
        if (w->right->color == RBTREE_BLACK) // 형제 자식의 오른쪽 노드가 BLACK이고, 왼쪽 노드가 RED일 경우
        {
          w->left->color = RBTREE_BLACK; // 형제의 왼쪽 노드를 RED -> BLACK으로 변경
          w->color = RBTREE_RED;         // 형제의 색깔을 BLACK -> RED로 변경
          right_rotation(t, w);            // 오른쪽 회전 시켜서 꺾이지 않도록 함
          w = x->parent->right;          // x의 위치가 바뀌었으므로, x의 형제인 w의 위치 또한 갱신해줌
        }
        // case 4)에 해당
        w->color = x->parent->color;     // 형제의 색을 부모의 색으로 변경
        x->parent->color = RBTREE_BLACK; // 부모의 색을 BLACK으로 변경
        w->right->color = RBTREE_BLACK;  // 형제의 오른쪽 자식의 색을 BLACK으로 변경
        left_rotation(t, x->parent);               // 왼쪽 회전 시킴
        x = t->root;
      }
    }
    else // doubly black인 x가 오른쪽 자식일 경우
    {
      w = x->parent->left; // w는 x의 형제 노드
      if (w->color == RBTREE_RED)
      {                                // 형제의 색깔이 RED인 경우 -> case 1)에 해당
        w->color = RBTREE_BLACK;       // 형제의 색을 BLACK으로 변경한다.
        w->parent->color = RBTREE_RED; // 형제의 부모의 색을 RED로 변경한다.
        right_rotation(t, x->parent);    // 부모를 기준으로 오른쪽 회전 수행
        w = x->parent->left;           // x의 위치가 바뀌었으므로, x의 형제인 w의 위치 또한 갱신해준다.
      } // 이후 경우1은 경우 2,3,4 중 하나로 변환 되었음
      if (w->left->color == RBTREE_BLACK && w->right->color == RBTREE_BLACK) // case 2)에 해당
      {
        w->color = RBTREE_RED; // 형제의 검은색을 부모에게 주므로 기존 BLACK에서, RED로 변함
        x = x->parent;         // x의 부모가 x의 extra black을 물려받아, 새로운 red and black 또는 doubly black이 됨
      }
      else // 형제의 자식 중 RED인 자식이 있을 경우 case 3)에 해당, 회전을 통해 case 4)로 변경해주어야함
      {
        if (w->left->color == RBTREE_BLACK) // 형제의 자식의 오른쪽 자식 색깔이 RED인 경우 -> 오른쪽 자식이 red인 상태에서 왼쪽 자식이 red인 상태로 바꾸어 준다.
        {
          w->right->color = RBTREE_BLACK; // 형제 오른쪽 노드를 RED -> BLACK
          w->color = RBTREE_RED;          // 형제 색깔을 BLACK -> RED
          left_rotation(t, w);              // 왼쪽으로 회전
          w = x->parent->left;            // x의 위치가 바뀌었으므로, x의 형제인 w의 위치 또한 갱신해줌
        }
        // 형제의 자식의 왼쪽 노드의 자식 색깔이 RED인 경우 case 4)에 해당
        w->color = x->parent->color;     // 형제의 색을 부모의 색으로 변경
        x->parent->color = RBTREE_BLACK; // 부모의 색을 BLACK으로 변경
        w->left->color = RBTREE_BLACK;   // 형제의 왼쪽 자식의 색을 BLACK으로 변경
        right_rotation(t, x->parent);              // 오른쪽 회전 시킴
        x = t->root;                     
      }
    }
  }
  x->color = RBTREE_BLACK;
  }

// 직후 원소 찾기, 오른쪽 서브트리의 min값 = 제일 오른쪽 값
node_t *rbtree_successor(rbtree *t, node_t *x) {
  node_t *y = x; // y는 직후 원소
  while (y -> left != t -> nil) { //y의 왼쪽 자식이 nil일때까지 반복
    y = y -> left; //y는 y의 왼쪽 자식이 됨
  }
  return y;
}

/*
보통의 bst처럼 delete한다.
실제로 삭제된 노드 y가 red였으면 종료
y가 black이었을 겨우 rb-delete-fixup을 호출한다.
*/
int rbtree_erase(rbtree *t, node_t *z)
{
  node_t *y = z; // z는 삭제 대상의 주소 값, y는 자식 갯수에 따라서 그대로 z가 될 수도 있고, z의 successor의 주소가 될 수도 있다.
  node_t *x;     // y의 원래 위치로 이동시키는 용도의 노드 x. y의 오른쪽 자식 또는 자식이 없을 경우 t->nil 로 설정된다.

  color_t y_original_color = y->color; // y의 색깔은 변경될 가능성이 존재하므로, 미리 새로운 변수에 y의 원래 색깔을 저장해둔다.
  if (z->left == t->nil)
  {                                    // z의 왼쪽 노드가 없다면
    x = z->right;                      // z의 오른쪽 노드를 x로 선언한다.
    rbtree_transplant(t, z, z->right); // z의 오른쪽 노드를 z의 자리에 교체한다.
  }
  else if (z->right == t->nil)
  { // z의 오른쪽 노드가 없다면
    x = z->left;
    rbtree_transplant(t, z, z->left); // z의 왼쪽 노드를 z의 자리에 교체한다.
  }
  else // z의 자식 노드가 둘 다 있을 경우
  {
    y = rbtree_successor(t, z->right); // z의 오른쪽 서브트리의 successor를 찾는다.
    y_original_color = y->color; //짝대기 떄고 갈아 끼운다
    x = y->right;

    if (y->parent == z)
    {                // 만약 z의 오른쪽 서브트리의 successor가 z의 오른쪽 노드라면
      x->parent = y; // x의 부모를 y로 선언
    }
    else
    {
      rbtree_transplant(t, y, y->right); // z에 z의 successor인 y를 이식하기 전에, y의 자리에 y의 자식을 이식 시켜둔다
      y->right = z->right;               // z 자리에 y를 이식하기 전, y의 오른쪽 자식을 z의 오른쪽 자식으로 교체
      y->right->parent = y;              // z자리에 y를 이식하기 전, y의 오른쪽 자식의 부모 노드를 y로 교체
    }

    rbtree_transplant(t, z, y); // z의 자리에 y를 이식한다.
    y->left = z->left;          // z의 왼쪽 자식이 y의 왼쪽 자식이 된다.
    y->left->parent = y;        // z의 왼쪽 자식의 부모가 곧, y가 된다.
    y->color = z->color;        // y가 z의 자리에 이식되고, y는 z의 색깔만 물려 받는다(값은 본래 y의 값 유지)
  }
  // 만약 삭제 대상의 색깔이 BLACK이라면, 각 경로의 BLACK 노드의 갯수의 균형이 깨지게 되므로, 균형을 맞춰 주어야 한다.
  if (y_original_color == RBTREE_BLACK)
  {
    rbtree_erase_fixup(t, x);
  }

  free(z); // z가 삭제 되었으므로, z의 메모리 주소를 비워준다.
  return 0;
}

//트리 중위순회하는 함수, 재귀
int rbtree_inorder(node_t *nil, node_t *root, key_t *arr, const size_t n, int index) {
  if (root == nil) { //root가 nil이면
    return index; //index 반환
  }
  // 재귀 종료 조건
  if (index == n) { 
    return index;
  }
  index = rbtree_inorder(nil, root->left, arr, n, index); //root의 왼쪽 자식으로 재귀
  if (index < n) { //index가 n보다 작을때만 arr에 값을 추가함
    arr[index++] = root -> key; //arr[현재 index] = 현재 노드의 key 값
  }
  index = rbtree_inorder(nil, root->right, arr, n, index); //root의 오른쪽 자식으로 재귀
  return index;
}

// 트리를 이용한 오름차순 arr 구현
int rbtree_to_array(const rbtree *t, key_t *arr, const size_t n) {
  // TODO: implement to_array
  if (t -> root == t -> nil) { //트리의 루트가 nil이면 반환
    return 0;
  }
  rbtree_inorder(t->nil, t -> root, arr, n, 0); //중위 순회
  return 0;
}