Red Black Tree의 개념과 삽입/삭제, C언어 구현

RB Tree(Red Black Tree)

- 이진 탐색 트리(BST) 기반의 self balanced tree

- 삽입/삭제는 BST와 동일하지만, 삽입/삭제 후 RB Tree의 5가지 속성을 만족하기 위한 재조정 작업이 필요하다.

- 스스로 좌/우 서브트리의 균형을 맞춘다

- 서브트리 간 height 차이는 최대 2이다.

 

RB Tree의 속성 5가지

1. 모든 노드는 red 혹은 black

2. 루트 노드는 black

3. 모든 nil 노드는 black

nil 노드

- 존재하지 않음을 의미하는 노드

- 자녀가 없을 때 자녀를 nil 노드로 표기함

- nil노드는 값이 있는 노드와 동등하게 취급

- RB트리에서 leaf노드는 nil노드이다.

4. red의 자녀는 모두 black이다 = red는 연속적으로 존재할 수 없다

5. 임의의 노드에서 자손 nil 노드까지 가는 경로들의 black 수는 같다 ( 자기 자신은 카운트에서 제외 )

5.1 그 black 수를 black height 라고 한다.

 

RB Tree 삽입/삭제

- 삽입/삭제 시 주로 속성 4, 5를 위반하며, 이들을 해결하려고 구조를 바꾸다 보면 자연스럽게 트리의 균형이 잡힌다.

- 속성을 위반했을 때 트리를 재조정하는 과정에서, 자연스럽게 트리의 균형이 잡히는 것.

- 회전 자체는 BST의 속성을 만족하기 위한 행위이고, 회전은 RB Tree의 속성을 만족하기 위해 이용되는 것이다.

- 삽입하는 노드는 항상 red이다.

-> red인 이유 : 삽입 후에도 5번 속성을 만족하기 위해

 

2번 속성을 위반했을 경우( root 노드가 black이 아닐 때 )

- root 노드를 black으로 바꾼다

 

4번 속성을 위반했을 경우의 3가지 case( red가 연속적으로 존재할 때 )

case1

- 삼촌이 red일 경우에 해당한다. (삼촌 : 부모의 형제 )

-> 할아버지 <-> 부모/삼촌의 색깔을 바꾼다

-> 바꿨으면 할아버지 노드를 기준으로 위반한 속성이 있는지 확인한다.

case2

- 삽입한 노드에서 할아버지까지 가는 경로가 꺾여있고 삼촌 노드가 black일 경우

-  꺾이다 : 할아버지가 부모를 가리키는 방향(left, right)이 부모가 자식을 가리키는 방향과 다른 경우

-> “부모 노드를 기준”으로 회전하여 1자로 펴 준다. case3 상태로 만든다.

-> case3 해결법을 진행한다

case3

- 문제 노드에서 할아버지까지 가는 경로가 1자이고 삼촌 노드가 black일 경우(nil 노드도 포함)

-> 부모와 할아버지의 색깔 바꾼 후 “할아버지 기준”으로 회전하기

 

 

아래는 문제 노드에서 할아버지까지의 경로가 꺾여있는 경우와 1자인 경우 예제이다.

꺾인 경우 / 1자인 경우

 

노드 D가 삽입되어 4번 속성을 위반한 경우이다. (정확히는 case 2와 case 3)

A는 할아버지, B는 부모, D는 문제 노드이다.

위 그림은 A의 left에 B가 있는데, D는 B의 right에 있다. 이것이 꺾인 것이다.

아래 그림은 A의 left에 B가 있는데, D도 B의 left에 있다. 이것이 1자다.

 

위쪽 그림의 경우 case 2에 해당되므로, 꺾인 경로를 1자로 펴준 후 case 3을 진행해야 한다.

 

 

삽입 예제 : case 1 ( 삼촌이 red인 경우 )

case 1

 

D가 삽입되었을 경우, D기준으로 삼촌(C)이 Red이다. 따라서 case 1에 해당한다. (1번)

case 1은 부모/삼촌 <-> 할아버지 색상을 바꾸면 된다. (2번)

하지만 A는 root이기 때문에 여기서 다시 2번 속성을 위반한다. 따라서 root를 Black으로 바꿔준다. (3번)

이제 RB Tree의 모든 속성을 만족한다.

 

삽입 예제 : case 2 ( 삼촌이 Black이고 경로가 꺾여있을 경우 )

case 2

 

D가 삽입되었을 경우, D기준 삼촌은 C이고 할아버지는 A이다. A까지의 경로가 꺾여 있으므로(1번) "부모 기준" 왼쪽 회전을 통해 1자로 펴줘야 한다.(2번)

case 2는 1자로 펴주는 회전 연산이 전부다. 하지만 case 2를 수행했다면 반드시 case 3을 수행해야 한다.

 

삽입 예제 : case 3 ( 삼촌이 Black이고 경로가 1자일 경우 )

case 3

 

위 case 2 예제 수행 결과가 case 3에 해당한다.(1번) 따라서 할아버지와 부모의 색깔을 바꾼 후(2번) "할아버지 기준" 오른쪽으로 회전한다.

 

 

간혹 회전을 수행할 때 남는 서브트리를 어디에 붙여야 할 지 헷갈릴 수 있다.

회전

 

위 그림 1번에서 A를 기준으로 오른쪽 회전할 때, D의 right 서브트리(E)는 D의 right에 A가 위치함으로써 연결이 끊기게 된다.

이 때 A도 left 서브트리(D)를 잃게 되는데, D가 놓친 서브트리(E)를 A의 left에 붙여주면 된다.

 

 

 

RB Tree 삭제 ( 여기서의 자녀는 nil 노드를 의미하지 않는다 즉, 값이 있는 노드를 의미 )

### 삭제되는 색이 red라면 어떠한 속성도 위반하지 않는다!!! ###

 

삭제되는 색을 먼저 알아야 한다. 삭제할 노드의 색이 삭제되는 색이 아닐 수 있다.

- 삭제하려는 노드의 자녀가 2개일 경우

-> 삭제되는 색 : successor(후임자)의 색, 삭제된 노드 위치로 대체된 후임자는 해당 위치의 색을 물려받는다.

- 삭제하려는 노드의 자녀가 없거나 1개일 경우

-> 삭제되는 색 : 삭제되는 노드의 색

 

삭제되는 색이 black일 때, 대부분의 상황에서 5번을 위반하게 된다.

5번을 위반했을 경우

-> 삭제된 black노드 위치에 extra black 부여 또는 삭제된 위치를 대체한 노드에게 부여

-> extra black이 부여된 black 노드는 doubly black 이라고 한다.

-> extra black이 부여된 red 노드는 red-and-black 이라고 한다.

-> extra black은 black height를 계산할 때 함께 계산되어, 결과적으로 black을 삭제하더라도 5번을 위반하지 않게 만든다.

 

red-and-black 해결 방법

- red-and-black을 black으로 바꿔주면 해결된다.

 

doubly black 해결 방법

- 4가지 case가 존재한다

- case는 doubly black의 형제의 색과, 그 형제의 자녀들의 색에 의해 분류된다.

 

doubly black을 제거하기 위한 4가지 case

case 4

doubly의 형제가 black이고 형제의 자식 red노드가 1자일 때

-> 부모의 색상을 형제가 받고, 부모와 형제의 자식을 black으로 만든 후 doubly 쪽으로 회전

 

case 3

doubly의 형제가 black이고 형제의 자식 red노드가 꺾여있을 때

-> 형제 자식과 형제 색깔을 바꾼 후 회전(1자로 만들기)하여 case 4 상태로 만든다.

-> 이후 case 4 해결법 진행

 

case 2

doubly의 형제가 black이고 자식도 다 black일 때

- doubly와 형제의 black을 부모에게 전달하고, 부모 레벨에서 해결하기( case 1, 2, 3, 4중 하나가 될 수 있다 )

- 이럴 경우 doubly 노드는 일반 black 노드가 되고, 형제는 red 노드가 된다.

 

case 1

doubly의 형제가 red일 때

-> 형제와 부모의 색상을 바꾼 후 doubly 쪽으로 회전

-> doubly에게 black 형제를 만들어 주는 작업이다. 이후 case 2, 3, 4 중 하나의 해결책을 찾는다.

 

 

삭제 예제 : case 1 ( doubly의 형제가 red일 때 )

case 1

 

A가 doubly black이고 형제(D)가 red이다. 따라서 case 1에 해당하며(1번), 형제와 부모의 색깔을 바꾼 후 doubly 쪽으로 회전하면 된다.(2번)

 

삭제 예제 : case 2 ( doubly의 형제가 black이고 형제의 자식들이 모두 black일 때 )

case 2

 

A가 doubly black이고 형제(D)가 black이다. 그리고 형제의 자식들(C, E)도 black이다.(1번) 이 상황에선 doubly black을 제거할 수 없기 때문에, black을 모아 부모(B)에게 전달하여 부모 레벨부터 올바른 case를 찾아 해결해야 한다.(2번)

이 때 부모(B)는 case 1, 2, 3, 4 중 1개에 해당할 수 있다.

 

삭제 예제 : case 3 ( doubly의 형제가 black이고 형제의 자식 red가 꺾여있을 때 )

case 3

 

doubly의 형제(D)의 자식 red(C)가 꺾여 있다.(1번) 이 상황에서 바로 해결하는 건 불가능하고, 1자로 펴서 case 3형태로 만든 후 해결해야 한다.

먼저 형제(D)와 red(C)의 색을 바꾸고(2번) 형제(D) 기준으로 회전하여 1자로 펴 준다.(3번) 이후 case 4를 수행한다.

case 3을 수행했다면, 반드시 case 4를 수행해야 한다.

 

삭제 예제 : case 4 ( doubly의 형제가 black이고 형제의 자식 red가 1자일 때 )

case 4

 

doubly(A)의 형제(D)의 red자식(E)이 1자로 뻗어 있다.(1번) 이 상태는 case 4에 해당하며, 이 상황을 해결할 수 있는 공식이 있다.

형제(D)는 부모(B)의 색깔을 받고, 부모(B)와 red자식(E)는 black으로 만들고(2번) doubly 쪽으로 회전하면 된다.(3번)

case 4를 수행하면 doubly black은 사라진다.

 

 

 

 

 

RB Tree C언어 구현

헤더 파일

#ifndef _RBTREE_H_

#define _RBTREE_H_

#include <stddef.h>

#include <stdio.h>

#include <stdlib.h>

typedef enum { RBTREE_RED, RBTREE_BLACK } color_t;

typedef int key_t;

typedef struct node_t {

  color_t color;

  key_t key;

  struct node_t *parent, *left, *right;

} node_t;

typedef struct {

  node_t *root;

  node_t *nil;  // for sentinel

} rbtree;

rbtree *new_rbtree(void);

void delete_rbtree(rbtree *);

node_t *rbtree_insert(rbtree *, const key_t);

node_t *rbtree_find(const rbtree *, const key_t);

node_t *rbtree_min(const rbtree *);

node_t *rbtree_max(const rbtree *);

int rbtree_erase(rbtree *, node_t *);

int rbtree_to_array(const rbtree *, key_t *, const size_t);

// rotate 함수

void left_rotate(rbtree *, node_t *);

void right_rotate(rbtree *, node_t *);

// 삽입 fixup 함수

void insert_fixup(rbtree *, node_t *);

// 트리 print 함수

void postOrder(rbtree *, node_t *);

// 노드, 트리 통째로 삭제 함수

void postOrderDelete(rbtree *, node_t *);

// 중위 순회 + arr에 담기 함수

void inOrder(const rbtree *t, key_t *arr, const size_t n, size_t *index, node_t *cur);

// 삭제 fixup 함수

void rbtree_erase_fixup(rbtree *, node_t *);

// 노드 대체 함수

void rbtree_transplant(rbtree *, node_t *, node_t *);

// 후임자 찾기 함수

node_t *node_successor(rbtree *, node_t *);

#endif  // _RBTREE_H_

rbtree.h

 

rbtree 헤더 파일이다. node_t 구조체는 노드, rbtree 구조체는 tree를 의미한다.

노드는 color, key, left, right, p 필드를 가진다.

트리는 root, nil 필드를 가진다.

root의 부모, 그리고 모든 leaf노드의 자식은 nil이며, 모두 하나의 nil을 가리킨다. ( nil을 일일이 할당할 수도 있지만, 메모리를 낭비하지 않기 위함 )

 

 

트리 생성

// 트리 생성

rbtree *new_rbtree(void) {

  // 트리, nil노드 할당

  rbtree *p = (rbtree *)calloc(1, sizeof(rbtree));

  node_t *nil = (node_t *)calloc(1, sizeof(node_t));

  nil->color = RBTREE_BLACK;

  // tree의 nil과 root 노드를 방금 만든 nil로 설정

  p->nil = nil;

  p->root = nil;

  return p;

}

 

새로운 트리를 만드는 함수이다.

nil의 색상을 black으로 할당 후 tree의 root와 nil을 모두 nil로 설정한다.

이렇게 하면 비어있는 트리가 생성된다.

 

 

트리 삭제(트리 자체를 삭제)

// 트리 삭제1

void delete_rbtree(rbtree *t) {

  // TODO: reclaim the tree nodes's memory

  node_t *cur = t->root;

  // 노드 지우기

  postOrderDelete(t, cur);

  free(t->nil);

  t->nil = NULL;

  // 트리 지우기

  free(t);

  t = NULL;

}

// 트리 삭제2

void postOrderDelete(rbtree *t, node_t *cur) {

    if(cur == t->nil) {

        return;

    }

    postOrderDelete(t, cur->left);

    postOrderDelete(t, cur->right);

   

    // 메모리 해제

    free(cur);

    cur = NULL;

}

 

트리의 모든 노드의 메모리를 할당 해제한 후 트리 자체와 nil의 메모리도 할당 해제한다.

즉 트리를 삭제한다.

 

트리를 후위 순회하면서 차례대로 free()하는 것으로 구현했다.

또한 dangling pointer를 만들지 않기 위해 할당해제한 주소는 NULL로 바꿔 주었다.

 

 

좌회전 함수

// 좌회전

void left_rotate(rbtree *t, node_t *x) {

  // y 설정

  node_t *y;

  y = x->right;

  // 서브트리 옮겨달기

  x->right = y->left;

  // y왼쪽 자식이 nil이 아니라면, 부모 설정해주기 ( nil이라면 parent 설정이 의미없다 )

  if(y->left != t->nil) {

    y->left->parent = x;

  }

  // x 부모를 y에게 주기

  // x가 root 였다면 y를 root로

  // 그게 아니라면 부모의 왼쪽/오른쪽 자식 중 하나로 달기

  y->parent = x->parent;

  if(x->parent == t->nil) {

    t->root = y;

  }

  else if(x == x->parent->left) {

    x->parent->left = y;

  }

  else {

    x->parent->right = y;

  }

  // 옮길 거 다 옮겼으니 x, y 관계 역전

  y->left = x;

  x->parent = y;

}

 

왼쪽으로 회전하는 함수이다.

 

 

우회전 함수

// 우회전

void right_rotate(rbtree *t, node_t *y) {

 

  // x 설정

  node_t *x;

  x = y->left;

  // 서브트리 옮겨달기

  y->left = x->right;

  if(x->right != t->nil) {

    x->right->parent = y;

  }

  // 부모 옮겨달기

  x->parent = y->parent;

  if(y->parent == t->nil) {

    t->root = x;

  }

  else if(y == y->parent->left) {

    y->parent->left = x;

  }

  else {

    y->parent->right = x;

  }

  // 옮겨달았으니 x, y 관계역전

  x->right = y;

  y->parent = x;

}

 

오른쪽으로 회전하는 함수이다. 좌회전 함수와 방향만 다르다.

회전은 삽입, 삭제, 재조정 등에 다양하게 이용된다.

 

 

노드 삽입 함수

// key 입력받아서 node_t 형태로 tree에 삽입

node_t *rbtree_insert(rbtree *t, const key_t key) {

  // TODO: implement insert

  // z노드에 key 넣고 로직 시작

  node_t *z = (node_t *)malloc(sizeof(node_t));

  node_t *y;

  node_t *x;

  z->key = key;

  y = t->nil;

  x = t->root;

  // y는 leaf node, x는 leaf까지 가기 위한 임시변수

  // leaf node 까지 파고들기

  while(x != t->nil) {

    y = x;

    if(z->key < x->key) {

      x = x->left;

    }

    else {

      x = x->right;

    }

  }

  // z의 부모를 y로 설정하고 left/right 배정하기

  // 부모 노드가 없다면 z를 root로 설정한다

  z->parent = y;

  if(y == t->nil) {

    t->root = z;

  }

  else if(z->key < y->key) {

    y->left = z;

  }

  else {

    y->right = z;

  }

  // z의 자식을 nil로 설정, color Red로 지정

  z->left = t->nil;

  z->right = t->nil;

  z->color = RBTREE_RED;

  // 삽입 후 트리 재조정

  insert_fixup(t, z);

  return t->root;

}

 

key값을 입력받아 tree에 노드를 삽입한다.

위 RB Tree 삽입 예제와 마찬가지로 똑같이 구현했다. 삽입 후 RB Tree 속성 위반 여부를 확인하고 재조정 하기 위해, 즉시 insert_fixup 함수(재조정 함수)를 호출한다.

 

 

삽입 후 재조정 함수

// 삽입 후 트리 재조정 함수

void insert_fixup(rbtree *t, node_t *z) {

 

  // red가 연속되지 않을 때 까지 반복한다

  while(z->parent->color == RBTREE_RED) {

    node_t *y;

    // 왼쪽/오른쪽 기준 잡기

    if(z->parent == z->parent->parent->left) {

      y = z->parent->parent->right; // 삼촌을 y에 저장

     

      // case 1 : 삼촌이 RED일 경우

      if(y->color == RBTREE_RED) {

        // 부모삼촌 <-> 할배 색깔 뒤집기

        z->parent->color = RBTREE_BLACK;

        y->color = RBTREE_BLACK;

        z->parent->parent->color = RBTREE_RED;

        // 뒤집은 후 할배기준 다시 확인하기

        z = z->parent->parent;

        continue;

      }

      // case 2 : 삼촌이 BLACK인데 꺾여있을 경우

      else if(z == z->parent->right) {

        //부모기준 회전하기 + case 3 진행

        z = z->parent;

        left_rotate(t, z);

        // case 2 수행 후에 case 3 수행

        z->parent->color = RBTREE_BLACK;

        z->parent->parent->color = RBTREE_RED;

        right_rotate(t, z->parent->parent);

      }

      // case 3 : 삼촌이 BLACK인데 1자일 경우

      else {

        z->parent->color = RBTREE_BLACK;

        z->parent->parent->color = RBTREE_RED;

        right_rotate(t, z->parent->parent);

      }

    }

    else {

      // 삼촌을 y에 저장

      y = z->parent->parent->left;

      // case 1 : 삼촌 RED일 때

      if(y->color == RBTREE_RED) {

        z->parent->color = RBTREE_BLACK;

        y->color = RBTREE_BLACK;

        z->parent->parent->color = RBTREE_RED;

        // 뒤집은 후 할배기준 다시 확인

        z = z->parent->parent;

      }

      // case 2 : 삼촌 BLACK인데 꺾여있을 때

      else if(z == z->parent->left) {

        z = z->parent;

        // 부모기준 회전 후 case 3 실행

        right_rotate(t, z);

        // case 3

        z->parent->color = RBTREE_BLACK;

        z->parent->parent->color = RBTREE_RED;

        left_rotate(t, z->parent->parent);

      }

      // case 3 : 삼촌 BLACK인데 1자일 때

      else {

        z->parent->color = RBTREE_BLACK;

        z->parent->parent->color = RBTREE_RED;

        left_rotate(t, z->parent->parent);

      }

    }

  }

  t->root->color = RBTREE_BLACK;

}

 

코드가 좀 긴데, 왼쪽/오른쪽만 다른 로직이 2개가 있어서 그렇다.

마찬가지로 로직은 위에 설명한 것과 동일하다.

 

 

 

특정 노드 찾기

// 특정 key에 해당하는 노드 찾기

node_t *rbtree_find(const rbtree *t, const key_t key) {

  // TODO: implement find

  node_t *cur = t->root;

  while(cur != t->nil) {

    // key를 찾았을 경우

    if(cur->key == key) {

      return cur;

    }

    // cur->key보다 작으면 left, 크면 right 탐색

    else if(cur->key > key) {

      cur = cur->left;

    }

    else {

      cur = cur->right;

    }

  }

  // 해당하는 key가 없을 경우 NULL 반환

  return NULL;

}

 

key값을 입력받아, tree에서 특정 노드를 찾는다.

BST 특성을 이용해 현재 노드 key보다 작으면 왼쪽 크면 오른쪽 순서로 탐색하며, 만약 찾지 못했을 경우 NULL을 반환한다.

 

 

가장 작은 값 찾기

// 가장 작은 값 찾기

node_t *rbtree_min(const rbtree *t) {

  // TODO: implement find

  node_t *cur = t->root;

  node_t *mini;

  // tree가 비어있을 경우 NULL 반환

  if(cur == t->nil) {

    return NULL;

  }

  while(cur != t->nil) {

    mini = cur;

    cur = cur->left;

  }

  return mini;

}

 

tree에서 가장 작은 key를 갖는 노드를 찾는 함수이다.

RB Tree에서 가장 작은 값은, root부터 left 방향으로만 쭉 파고 들어갔을 때 nil이 아닌 마지막 노드이다.

만약 tree 자체가 비어있을 경우엔 NULL을 반환한다.

 

 

가장 큰 값 찾기

// 가장 큰 값 찾기

node_t *rbtree_max(const rbtree *t) {

  // TODO: implement find

  node_t *cur = t->root;

  node_t *maxx;

  if(cur == t->nil) {

    return NULL;

  }

  while(cur != t->nil) {

    maxx = cur;

    cur = cur->right;

  }

  return maxx;

}

 

tree에서 가장 큰 key를 갖는 노드를 찾는 함수이다.

가장 작은 값과 반대로, root부터 right 방향으로만 쭉 파고 들어갔을 때 nil이 아닌 마지막 노드이다.

 

 

노드 대체 함수

// 노드 대체 함수, v를 u자리로 옮긴다

void rbtree_transplant(rbtree *t, node_t *u, node_t *v) {

  // u가 root였을 경우 v를 root로 설정

  // 아니라면 left, right 중 맞는 자리로 설정

  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;

}

 

노드 대체 함수이다. 즉 어떤 노드의 자리를 다른 노드로 대체하는 함수이다. u의 자리에 v가 대체된다.

삭제 로직에서 사용되며, 어떤 노드가 root였다면 root로 만들고 아니라면 부모 노드를 교체하여 달아준다.

 

단, 부모 노드만 달아주는 것이고 자식 노드는 달아주지 않는다. 이 함수를 실행한 후 따로 자식 노드를 달아주는 작업이 필요하다.

 

 

후임자 찾기 함수

// 특정 노드의 후임자 찾기

node_t *node_successor(rbtree *t, node_t *node) {

  // TODO: implement find

  node_t *cur = node->right;

  node_t *mini;

  // 후임자가 없을 경우 NULL 반환

  if(cur == t->nil) {

    return NULL;

  }

  while(cur != t->nil) {

    mini = cur;

    cur = cur->left;

  }

  return mini;

}

 

후임자 찾기 함수이다. 후임자(successor)는 특정 노드보다 큰 노드 중에서 가장 작은 노드를 말한다.

이것을 찾는 이유는 삭제 로직에서 삭제된 노드 자리를 후임자가 대체할 수 있기 때문이다. 물론 이것도 위에서 설명했기 때문에 더 설명하지 않겠다.

 

특정 노드보다 큰 노드 중 가장 작은 노드는, 특정 노드에서 right로 딱 한칸 간 후 left로 쭉 내려간 마지막 노드를 말한다.

 

 

노드 삭제 함수

// 노드 삭제

int rbtree_erase(rbtree *t, node_t *p) {

  // TODO: implement erase

  node_t *x;

  node_t *y = p;

  color_t y_origin_color = y->color;

  // 자녀가 1개 이하일 때

  if(p->left == t->nil) {

    x = p->right;

    rbtree_transplant(t, p, p->right);

  }

  else if(p->right == t->nil) {

    x = p->left;

    rbtree_transplant(t, p, p->left);

  }

  // 자녀가 2개일 때

  else {

    // 후임자 y에 담기

    y = node_successor(t, p);

    y_origin_color = y->color;

    // x는 y자식이다

    x = y->right;

    // y가 삭제노드 자식이면 x는 y의 right에 그대로 연결되어 있다

    if(y->parent == p) {

      x->parent = y;

    }

    else {

      // 아닐 경우 y자식을 y자리에 대체한다

      rbtree_transplant(t, y, y->right);

      // 삭제노드 right 자식을 y에 달기

      y->right = p->right;

      y->right->parent = y;

    }

   

    // y를 삭제노드 자리로 옮기기

    rbtree_transplant(t, p, y);

    y->left = p->left;

    y->left->parent = y;

    y->color = p->color;

  }

  // 노드 삭제 후 메모리 반환

  free(p);

  p = NULL;

  // y 원래 자리를 x가 대체했는데 삭제된 색이 black이라면 x가 doubly black 또는 red and black 이므로 fixup 실행

  if(y_origin_color == RBTREE_BLACK) {

    rbtree_erase_fixup(t, x);

  }

  return 0;

}

 

삭제할 노드의 자식이 1개 이하라면 해당 노드의 색을 삭제하고, 자식을 삭제된 위치로 대체시키면 끝이다.

 

다만 삭제할 노드의 자식이 2개라면 후임자로 대체해야 한다. y에 후임자를 담고 삭제되는 색은 후임자의 색이기 때문에 y_origin_color에 색깔을 저장해 두고 로직을 시작한다.

 

y가 삭제되는 노드의 바로 아래 자식이면, y의 right 자식은 그대로 두면 된다.

y가 삭제되는 노드의 바로 아래 자식이 아니라면, y의 right 자식은 y자리에 대체시킨 후,

y의 left, right엔 삭제되는 노드의 left, right를 달아준다.

최종적으론 y가 삭제노드 자리에 대체되고 그 자리에 있던 원래 색깔을 물려받는다.

 

이제 삭제할 노드를 free()로 할당 해제시키고 값을 NULL로 바꿔주면 된다.

 

마지막으로 y_origin_color(삭제된 색)을 확인한다. 위에도 써 놨듯 red면 아무런 문제도 없지만 black일 경우 재조정을 해 줘야 한다. 따라서 rbtree_erase_fixup() 함수를 호출한다.

여기서 기준 노드가 x로 설정되는데, x는 삭제된 노드를 대체하러 사라진 후임자(y)의 자리를 대체한 노드이다.

 

black이 삭제되었다면 x에 extra black이 붙어서 doubly black 또는 red and black이 되었기 때문에, 이걸 처리하기 위해 fixup 함수를 호출하는 것이다.

 

 

 

삭제 후 재조정 함수

// x가 red(red and black)라면 while문 넘겨서 바로 black

// x가 black(doubly black)이라면 while문 진행

void rbtree_erase_fixup(rbtree *t, node_t *p) {

  // p가 root거나 red and black이라면 조건 없이 black으로 바꾸기

  while(p != t->root && p->color == RBTREE_BLACK) {

    node_t *w;

    // 형제 지정

    if(p == p->parent->left) {

      w = p->parent->right;

     

      // case 1 : 형제가 red일 경우, 색깔 바꾸고 부모기준 돌리기

      // 형제가 black 되었으므로 case 2, 3, 4 중 한개 하기

      if(w->color == RBTREE_RED) {

        w->color = RBTREE_BLACK;

        p->parent->color = RBTREE_RED;

        left_rotate(t, p->parent);

        // 돌렸으니 형제 재지정

        w = p->parent->right;

      }

      // case 2 : 형제가 black인데 형제 자식도 다 black인 경우, 나/형제꺼 black 올리기

      // 올린후 부모 기준으로 "처음부터" 시작하기

      if(w->left->color == RBTREE_BLACK && w->right->color == RBTREE_BLACK) {

        // doubly는 정상 black이 되니까 색깔변경 안함, 형제만 red가 됨

        w->color = RBTREE_RED;

        // 부모에게 extra black 줬으니 부모부터 다시 시작한다

        p = p->parent;

      }

      // case 3: 형제의 red자식이 꺾여있을 경우

      else if(w->right->color == RBTREE_BLACK) {

        // 형제와 형제자식 색 바꾸고 회전 ( 1자로 만들기 )

        w->left->color = RBTREE_BLACK;

        w->color = RBTREE_RED;

        right_rotate(t, w);

        // case 3 이후엔 case 4를 꼭 해야 한다.

        // 형제 재지정 후 case 4 실행

        w = p->parent->right;

       

        // 형제는 부모 색 물려받기

        // 부모/형제자식은 black으로 만들고 회전

        // 이러면 doubly는 없어진다.

        w->color = p->parent->color;

        p->parent->color = RBTREE_BLACK;

        w->right->color = RBTREE_BLACK;

        left_rotate(t, p->parent);

       

        // case 4를 했으면 무조건 doubly가 없어지므로, while문 탈출을 위해 root를 넣어준다.

        p = t->root;

      }

      // case 4 : 형제는 black, 형제 red자식이 1자일 경우

      else {

        // 형제는 부모 색 물려받기

        // 부모/형제자식은 black으로 만들고 회전

        // 이러면 doubly는 없어진다.

        w->color = p->parent->color;

        p->parent->color = RBTREE_BLACK;

        w->right->color = RBTREE_BLACK;

        left_rotate(t, p->parent);

       

        // case 4를 했으면 무조건 doubly가 없어지므로, while문 탈출을 위해 root를 넣어준다.

        p = t->root;

      }

    }

    //////////////////////////반대 경우//////////////////////////////////

    else {

      w = p->parent->left;

     

      // case 1 : 형제가 red일 경우, 색깔 바꾸고 부모기준 돌리기

      // 형제가 black 되었으므로 case 2, 3, 4 중 한개 하기

      if(w->color == RBTREE_RED) {

        w->color = RBTREE_BLACK;

        p->parent->color = RBTREE_RED;

        right_rotate(t, p->parent);

        // 돌렸으니 형제 재지정

        w = p->parent->left;

      }

      // case 2 : 형제가 black인데 형제 자식도 다 black인 경우, 나/형제꺼 black 올리기

      // 올린후 부모 기준으로 "처음부터" 시작하기

      if(w->left->color == RBTREE_BLACK && w->right->color == RBTREE_BLACK) {

        // doubly는 정상 black이 되니까 색깔변경 안함, 형제만 red가 됨

        w->color = RBTREE_RED;

        // 부모에게 extra black 줬으니 부모부터 다시 시작한다

        p = p->parent;

      }

      // case 3: 형제의 red자식이 꺾여있을 경우

      else if(w->left->color == RBTREE_BLACK) {

        // 형제와 형제자식 색 바꾸고 회전 ( 1자로 만들기 )

        w->right->color = RBTREE_BLACK;

        w->color = RBTREE_RED;

        left_rotate(t, w);

        // case 3 이후엔 case 4를 꼭 해야 한다.

        // 형제 재지정 후 case 4 실행

        w = p->parent->left;

       

        // 형제는 부모 색 물려받기

        // 부모/형제자식은 black으로 만들고 회전

        // 이러면 doubly는 없어진다.

        w->color = p->parent->color;

        p->parent->color = RBTREE_BLACK;

        w->left->color = RBTREE_BLACK;

        right_rotate(t, p->parent);

       

        // case 4를 했으면 무조건 doubly가 없어지므로, while문 탈출을 위해 root를 넣어준다.

        p = t->root;

      }

      // case 4 : 형제는 black, 형제 red자식이 1자일 경우

      else {

        // 형제는 부모 색 물려받기

        // 부모/형제자식은 black으로 만들고 회전

        // 이러면 doubly는 없어진다.

        w->color = p->parent->color;

        p->parent->color = RBTREE_BLACK;

        w->left->color = RBTREE_BLACK;

        right_rotate(t, p->parent);

       

        // case 4를 했으면 무조건 doubly가 없어지므로, while문 탈출을 위해 root를 넣어준다.

        p = t->root;

      }

    }

  }

  p->color = RBTREE_BLACK;

}

 

이것도 코드가 좀 긴데.. 왼쪽 오른쪽만 바뀐 로직이 2개이기 때문에 그렇다.

 

우선, 입력받은 노드(p)가 root거나 red였다면 while문을 거치지 않고 맨 아래로 내려와 바로 black으로 바꿔준다.

root 노드는 원래 바로 black으로 바꿔줘도 되고, red였다면 red and black이므로 이것도 바로 black으로 바꿔주면 되기 때문이다.

 

만약 입력받은 노드(p)가 doubly black이라면 while문을 거치게 된다.

p의 형제 노드는 w에 저장하고 로직을 시작한다. 만약 형제(w)가 red라면 case 1에 해당되어, 형제와 부모의 색깔을 바꾸고 rotate한다. 이제 형제가 바뀌었으므로 w를 재지정해준 후 다음 케이스(2 또는 3 또는 4)로 넘어간다.

 

형제(w)가 black인데 형제의 왼쪽/오른쪽 자식이 모두 black일 경우 case 2에 해당한다. 이 상황은 p가 doubly black이고 형제인 w가 black인 상황인데, 이 둘의 black을 모아 부모에게 전달해야 한다. 그러면 w는 red가 되고 p는 일반 black이 된다.

이제 부모가 extra black을 갖고 있으므로, p->parent를 기준으로 로직을 다시 시작한다. case 1, 2, 3, 4가 해당될 수 있다.

 

형제(w)가 black이고 형제의 red자식이 꺾여있을 경우 case 3에 해당한다. case 3은 꺾여있는 걸 1자로 풀어주기만 하면 된다.

형제(w)와 형제의 red자식의 색깔을 바꾸고 회전하여 1자로 만든다. 회전으로 인해 형제가 바뀌었으니 w를 재지정 해준 후 바로 case 4를 진행한다. case 3을 진행했으면 반드시 case 4를 해야 한다.

 

형제(w)가 black이고 형제의 red자식이 1자일 경우 case 4에 해당한다. 

형제(w)는 부모(p->parent)의 색을 물려받고, 부모(p->parent)와 형제의 red자식은 black으로 만든 후 doubly black(p)방향으로 회전한다.

 

이렇게 하면 doubly black을 없앨 수 있다.

 

 

주어진 arr에 node를 key 오름차순으로 n개 넣는 함수

// 주어진 arr에 node를 오름차순으로 넣기, 최대 n개 까지만1

int rbtree_to_array(const rbtree *t, key_t *arr, const size_t n) {

  // TODO: implement to_array

  node_t *cur = t->root;

  size_t *index;

  size_t x = 0;

  index = &x;

  inOrder(t, arr, n, index, cur);

  return 0;

}

// 주어진 arr에 node를 오름차순으로 넣기, 최대 n개 까지만2

void inOrder(const rbtree *t, key_t *arr, const size_t n, size_t *index, node_t *cur) {

  if(cur == t->nil) {

    return;

  }

  inOrder(t, arr, n, index, cur->left);

  if(*index < n) {

    arr[*index] = cur->key;

    *index = *index + 1;

  }

  else {

    return;

  }

  inOrder(t, arr, n, index, cur->right);

}

 

inOrder 함수는 트리를 후위 순회하며 arr에 값을 넣는 함수인데, rbtree_to_array 에서만 호출된다. 즉 두개의 함수는 하나라고 봐도 무방하다.

 

 

 

미친 듯이 도움이 많이 된 RB Tree 영상

RB Tree 개념/특징/삽입 : https://www.youtube.com/watch?v=2MdsebfJOyM&list=WL&index=7&t=1129s

 

RB Tree 삭제 : https://www.youtube.com/watch?v=6drLl777k-E&list=WL&index=8&t=1194s

 

 

 

======================================================

 

 

이렇게 RB Tree를 공부하고 구현해 보았다. 생각보다 어렵지 않은 듯 하면서도, 이해했다고 생각하면 또 헷갈리곤 한다. 지난 일주일간 이렇게 열심히 공부했는데 제대로 기록해 두지 않는다면 공부한 게 무의미해질 것 같아 시간을 들여 기록했다.

 

RB Tree는 무작정 코드부터 입력하고 계속 돌려보는 것 보다, 시간들 좀 들여서라도 트리 개념과 삽입/삭제 로직을 명확히 숙지한 후 코드를 짜는 게 오히려 빠른 길인 것 같다.

 

생각했던 것 보다는 RB Tree가 그렇게까지 어렵다는 느낌은 아니었다. 물론 당연히 어려웠지만 일주일 동안 공부할 정도로 어렵지는 않았다. 하지만 코치님들도 이미 그걸 아시는 건지 CSApp 과제를 엄청나게 많이 주셨다.... RB Tree보다도 이게 더 문제다.

 

다음 주는 malloc() 함수를 구현하게 될 텐데 난이도가 감이 오지 않는다. 포인터도 잘 이해했다고 생각했는데 오늘 포인터 쪽지시험도 망해버렸고... 배운 걸 제대로 내 것으로 만들 시간, 즉 복습할 시간이 없는 게 조금 아쉽다.