SWJungle Project 복기 - RB Tree

Lee Pil Ung·2022년 3월 15일
RB-Tree
0

SWJungle

목록 보기
1/1
post-thumbnail

Red-Black-Tree 란?

SWJungle - 5주차에 진행된 C언어 기반 프로젝트.

❓ 정의

BST(이진탐색트리)를 기반으로 하는 트리 자료구조. 동일한 노드의 개수에서 시간 복잡도를 줄이기 위해 complete binary tree를 만들어 depth를 최소화하는 것이 핵심이다.

📌 키워드 : 동적 메모리 할당, 포인터, 메모리 누수, 균형 이진 탐색 트리

C언어의 알파벳 C만 알고있던 상태에서 느닷없이 튀어나온 고난이도 프로젝트였다.

뭐 여러 레퍼런스를 참고하고 어떻게 구현목표가 있었기 때문에 하긴 했지만 여전히 원리에 대해 자세하게 이해하고있는가? 물어본다면 대답은 여전히 NO라고 할 수 있을 것이다.

❓ 조건

  1. 모든 노드는 빨간색 아니면 검은색이다.
  2. 루트는 검은색이다.
  3. 리프 노드(NIL)은 검은색이다.
  4. 만약 부모 노드가 빨간색이면, 자식 노드들은 모두 검은색이다.
  5. 각 노드로부터 그 노드의 자손인 리프 노드(NIL)로 가는 모든 경로(흑색 경로)는 같은 수의 검은색 노드를 포함한다.
루트 노드부터 모든 리프 노드로 가는 길은 흑색 노드가 2개이다.

☑️ 특징

  • BST의 일종이므로 그 특성을 모두 갖는다.
  • 각 노드에 색을 나타내는 한 비트의 메모리 공간이 추가로 있다.
  • Black height : 노드 x로부터 리프 노드까지의 경로에서 모든 black 노드들의 개수(노드 x를 포함하지 않음).
  • Balanced 상태 : 루트부터 리프 노드까지 모든 경로 중 최소 경로와 최대 경로의 크기 비율은 2보다 크지 않다. 이를 통해 RBT는 self-balancing tree로서 기능한다.
  • NIL : 노드의 child가 없을 경우 child를 가리키는 포인터는 NIL 값을 저장한다. 이러한 NIL들을 리프 노드로 간주한다.
  • N개의 내부 노드를 가지는 RBT는 최대 2log(N+1)의 높이를 가진다.
    - Search, Minimum, Maximum, Successor, Predecessor 등 동적 집합 연산을 O(logN) 안에 구현할 수 있다.

Red-Black-Tree의 구현

Sentinel Node와 T.nil

  • Sentinel Node 단말 노드
    • 경계 노드. 트리의 순회를 끝내는 기준이 된다.
  • T.nil(Tree 구조체의 nil 멤버)

    • 모든 NIL(리프 노드)를 하나의 객체로 관리한다. 메모리를 절약하고 경계 조건을 관리하기 편하다는 장점이 있다.

      💡 노드 하나를 할당하여 이를 리프로 정하고, 모든 NIL 리프에 대한 포인터가 이 노드를 가리키도록 한다.

h는 높이, bh는 blackHeight를 의미한다.

## Red-Black-Tree의 주요 기능들

Rotate

노드들을 nsert와 Delete 할 경우, RBT의 기본 속성을 위반하는 상황이 생긴다. 이를 수정하기 위해 일부 노드의 색깔과 포인터를 변경한다. 이 때 포인터를 변경하기 위해 Rotate를 사용한다.

Insert → O(logN)의 시간복잡도

참조 : https://nesoy.github.io/articles/2018-08/Algorithm-RedblackTree

💡 Insert Process
1. 새 노드 z를 삽입한다. → O(logN) : 이진탐색(트리의 높이)
2. 새 노드 z를 RED로 칠한다. → O(1)
3. 삽입한 후에 RBT의 규칙에 어긋난다면 insert_fixup()을 실행한다.

새 노드를 적색으로 칠하는 이유

  • 위에서 언급한 RB-Tree의 조건들 중 아래의 3가지 조건만 변경하면 된다.

    1. 루트는 검은색이다.
    2. 리프 노드(NIL)은 검은색이다.
    3. 만약 부모 노드가 빨간색이면, 자식 노드들은 모두 검은색이다.

Insert_fixup → O(1)의 시간복잡도

💡 RB-Tree의 규칙을 위반한 부분을 바로잡는 부분이다.

  • 삽입한 노드가 root면 노드를 BLACK으로 칠한다. → O(1)의 시간복잡도
  • 삽입한 노드의 삼촌이 RED면 Recolor 진행 → O(1)의 시간복잡도
  • 삽입한 노드의 삼촌이 BLACK이면 Restructure 진행 → O(1)의 시간복잡도 : Rotation

Recolor

Recolor는 삽입한 노드의 삼촌이 RED일 때 진행한다.

  • 새 노드의 부모, 삼촌을 BLACK으로 바꾸고, 조부모를 RED로 바꿔준다. 이래야만 black Height를 맞춰줄 수 있다.

  • 조부모의 부모가 RED인 경우, 다시 한 번 전체적인 Fixup 절차를 거쳐야 한다.(while문을 다시 한번 돌아야 함)

Restructure

Restructure는 삽입한 노드의 삼촌이 BLACK일 떄 진행한다.

Triangle 형태를 지나면 필연적으로 Line의 형태가 되고, Line 형태를 거치면 균형 잡힌 이진 트리를 무조건 만들 수 있다.

  • Trinagle 형태란?
    새 노드가 부모의 왼쪽 노드이고, 부모는 조부모의 오른쪽 노드일 때 or 새 노드가 부모의 오른쪽 노드이고 부모는 조부모의 왼쪽 노드일 때
    💡 새 노드와 그 부모를 회전시킨다.

    회전시키고 아직 색깔을 바꾸지 않았으므로, Line 형태의 Restructure를 바로 실행해야 한다.

    위의 이미지가 Triangle 형태이다.

    에서 새노드와 부모를 회전시킨 형태

  • Line 형태의 경우
    새 노드가 부모의 왼쪽 노드이고 부모도 조부모의 왼쪽 노드일 때 or
    새 노드가 부모의 오른쪽 노드이고 부모도 조부모의 오른쪽 노드일 때

    💡 새 노드의 조부모를 회전시키고 부모와 조부모의 색깔을 바꾼다.

    부모 노드의 색깔이 BLACK으로 RBT의 규칙을 위배하지 않으므로, 여기서 fixup 함수는 끝나게 된다.

    Line 형태 조부모를 회전시키고 부모와 조부모의 색깔을 바꾼다.

Transplant(T,u,v) -> O(1)의 시간복잡도

  • Transplant(T,u,v)는 u->parent의 자식 노드를 u대신 v로 바꿔준다. 따라서 u의 자식들과 v를 따로 이어줘야 한다.
  • u는 삭제되지 않는다. 단지 u->parent로부터의 접근이 불가능하게 됐음을 의미한다.

Deletion(T, p) → O(logN), fixup 없이도 O(logN)

p : 지워질 노드를 의미 	y : 지워질 노드(case1,2에 해당), 대체할 노드(case3에 해당)	 x : y의 자리를 대체할 노드

지워지거나 삭제될 노드 y의 색을 미리 지정해 둔다.

만약 지워진 노드 y의 색이 Black일 경우 문제가 되므로, fixup 함수를 호출하여 문제를 해결해야 한다.

deletion은 크게 3가징 경우로 나뉘어 진다.

case 1, 2

  • 노드의 한 자식이 nil이거나 두개 다 nil인 경우
    - 나머지 자식을 x로 두고 y와 대체한다.

case 3

  • 노드의 두 자식 모두 nil이 아닌 경우
    - p의 오른쪽 자식의 왼쪽 자식이 없는 경우
    • p의 오른쪽 자식의 왼쪽 자식이 있는 경우(successor가 있는 경우에 해당)
      • 삭제하려는 노드의 다음으로 가장 큰 원소 y를 찾아서 오른쪽 자식을 원소 y의 원래 위치로 옮겨준다.(transplant)
        • y를 삭제하려는 노드 자리로 옮겨준다.(transplant)
        • y의 색을 삭제하려는 노드 색으로 바꿔준다(이 경우 y가 대체하는 공간의 색은 rb-tree의 규칙에 어긋날 일이없게 된다)
  • 그 후, 대체되거나 지워진 노드 y의 색이 BLACK일 경우, BLACK노드를 지웠으므로 그 경로의 Black Height가 1 낮아진다. 이는 RBT의 규칙 5에 어긋나므로 수정하기 위해 fixup(T,x) 함수를 실행시킨다.
  • p의 메모리 공간을 free로 바꿔준다.

Delete_fixup(T, x) → O(logN)

Delete하며 바뀌거나 삭제된 노드의 색이 BLACK이라면, RBT 규칙 5번에 위반된다.
이를 해결하기 위해, 빈 공간을 대체한 노드 x에 가상의 BLACK을 하나 더 추가한다. 즉, 함수가 시작될 때 x는 여분의 B를 하나 더 들고 있다.

  1. 대체된 노드 x의 색깔이 RED일 때

  2. 대체된 노드 x가 root일 때

  3. 대체된 노드 x의 색깔이 BLACK일 때

    논외. 삭제된 노드 y의 색깔이 RED일 때

Delete_fixup 논외, 삭제된 노드의 색깔이 RED일 때

Black height에 변화가 없다. 그냥 Delete만 진행하고 그 자리를 대체하는 노드에게 색깔을 덮어주면 끝이다.

p의 자식이 둘 다 NIL이 아니고, y가 RED, x가 NIL이다.

  • y가 BLACK이고 x의 색깔이 RED일 때
    규칙대로 자리를 메꾼 후 x의 색깔만 BLACK으로 덮어주면 된다.

    p = 18, y = 22, x = 26. y == BLACK이지만 x = RED라서 그냥 while문 돌지 않는다.

  • x가 root일 때
    그냥 root이므로 BLACK으로 칠해준다.

Delete_fixup 3. 대체된 노드 x의 색깔이 BLACK일 때

4가지 케이스가 존재한다.

Case 1 : x의 형제 노드 w가 RED → O(1)
Case 2 : x의 형제 노드 w가 BLACK, w의 왼쪽, 오른쪽 자식이 모두 BLACK → O(logN), while문이 실행되는 경우가 이 부분.
Case 3 : x의 형제 노드 w가 BLACK, w의 왼쪽 자식 RED, 오른쪽 자식 BLACK → O(1)
Case 4 : x의 형제 노드 w가 BLACK, w의 오른쪽 자식 RED → O(1)

x는 두 개의 B를 들고 있다. 이 때 case는 x가 왼쪽 자식일 때, 오른쪽 자식일 때 각각 4 case가 있다.

  • Case 1 : x의 형제 노드 w가 RED → O(1)

    • x의 부모와 w의 색을 교환한다.
    • x의 부모를 기준으로 Left Rotate한다.
    • 결과 : Case 2, 3, 4 중 하나(w가 BLACK)로 바꾼다.

  • Case 2 : x의 형제 노드 w가 BLACK, w의 왼쪽, 오른쪽 자식이 모두 BLACK → O(logN)

    • x와 w에서 각각 BLACK을 하나씩 뺀다.
    • x의 부모를 새 x로 만들어준다.
    • 결과 : while문을 탈출하거나 새 x로 다시 while문을 돈다.

  • Case 3 : x의 형제 노드 w가 BLACK, w의 왼쪽 자식 RED, 오른쪽 자식 BLACK → O(1)

    • w와 w의 왼쪽 자식의 색을 교환한다.
    • w를 중심으로 Left Rotate한다.
    • 결과 : Case 4(w.right == RED)로 바꾼다.

  • Case 4 : x의 형제 노드 w가 BLACK, w의 오른쪽 자식 RED → O(1)

    • w의 부모의 색을 w로 옮긴다.
    • x의 부모를 BLACK으로 만든다.
    • w의 오른쪽 자식을 BLACK으로 만든다.
    • 결과 : 조정이 완료되면 RBT의 규칙을 지키게 된다. 끝.
전체 코드(rbtree.c) 보기
``` #include "rbtree.h"

#include <stdlib.h>

rbtree new_rbtree(void) {
rbtree p = (rbtree )calloc(1, sizeof(rbtree));
// TODO: initialize struct if needed
p->nil = (node_t )calloc(1, sizeof(node_t));
p->nil->color = RBTREE_BLACK;

p->root = p->nil;

return p;
}

node_t postOrder(rbtree t, node_t * curr){
if(curr->left == t->nil && curr->right == t->nil){
return curr;
}
if(curr->left != t->nil){
free(postOrder(t, curr->left));
}
if(curr->right != t->nil){
free(postOrder(t, curr->right));
}
return curr;
}

void delete_rbtree(rbtree *t) {
// TODO: reclaim the tree nodes's memory
if(t->root != t->nil){
free(postOrder(t, t->root));
}
free(t->nil);
free(t);
}

void right_Rotate(rbtree T, node_t x){
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->left){
x->parent->left = y;
}
else {x->parent->right = y;}
y->right = x;
x->parent = y;
}

void left_Rotate(rbtree T, node_t x){
node_t* y = x->right; // y 설정
x->right = y->left; // y의 왼쪽 서브 트리를 x의 오른쪽 서브 트리로 옮기기
if (y->left != T->nil){
y->left->parent = x;
}
y->parent = x->parent; // x의 부모를 y로 연결한다.
if(x->parent == T->nil){
T->root = y;
}
else if(x == x->parent->left){
x->parent->left = y;
}
else x->parent->right = y;
y->left = x; // x를 y의 왼쪽에 놓는다.
x->parent = y;
}

void rbtree_insert_fixup(rbtree t, node_t node) {
while(node->parent->color == RBTREE_RED){
if (node->parent == node->parent->parent->left){
node_t tmp = node->parent->parent->right;
if (tmp->color == RBTREE_RED) { // 경우 1
node->parent->color = RBTREE_BLACK;
tmp->color = RBTREE_BLACK;
node->parent->parent->color = RBTREE_RED;
node = node->parent->parent;
}
else {
if ( node == node->parent->right){ // 경우 2
node = node->parent;
left_Rotate(t,node);
}
node->parent->color = RBTREE_BLACK;
node->parent->parent->color = RBTREE_RED;
right_Rotate(t,node->parent->parent);
}
}
else {
node_t tmp = node->parent->parent->left;
if (tmp->color == RBTREE_RED) { // 경우 1
node->parent->color = RBTREE_BLACK;
tmp->color = RBTREE_BLACK;
node->parent->parent->color = RBTREE_RED;
node = node->parent->parent;
}
else {
if ( node == node->parent->left){ // 경우 2
node = node->parent;
right_Rotate(t,node);
}
node->parent->color = RBTREE_BLACK;
node->parent->parent->color = RBTREE_RED;
left_Rotate(t,node->parent->parent);
}
}
}
}

node_t rbtree_insert(rbtree t, const key_t key) {
// TODO: implement insert
node_t new_node = (node_t )calloc(1,sizeof(node_t));
node_t y = t->nil;
node_t x = t->root;

while (x != t->nil){
y = x;
if (key < x->key){
x = x->left;
}
else{
x = x->right;
}
}
new_node->parent = y;
if (y == t->nil){
t->root = new_node;
}
else if (key < y->key){
y->left = new_node;
}
else {
y->right = new_node;
}

new_node->key = key;

new_node->left = t->nil;
new_node->right = t->nil;
new_node->color = RBTREE_RED;

rbtree_insert_fixup(t,new_node);
t->root->color = RBTREE_BLACK;
return new_node;
}

node_t rbtree_find(const rbtree t, const key_t key) {
// TODO: implement find
if (t->root == t->nil){
return NULL;
}
node_t *curr = t->root;
while(curr != t->nil){
if(key < curr->key) {
curr = curr->left;
}
else if (key > curr->key){
curr = curr->right;
}
else {
return curr;
}
}
return NULL;
}

node_t rbtree_min(const rbtree t) {
// TODO: implement find
if (t->root == t->nil) {
return NULL;
}
node_t *curr = t->root;
while (curr->left != t->nil){
curr = curr->left;
}
return curr;
}

node_t rbtree_max(const rbtree t) {
// TODO: implement find
if (t->root == t->nil){
return NULL;
}
node_t *curr = t->root;
while(curr->right != t->nil){
curr = curr->right;
}
return curr;
}

void transplant(rbtree t, node_t u, node_t *v){
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;
}

void delete_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;
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;
}
else if (w->right->color == RBTREE_BLACK) {
w->left->color = RBTREE_BLACK;
w->color = RBTREE_RED;
right_Rotate(t,w);
w = x->parent->right;
}
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;
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->right->color == RBTREE_BLACK && w->left->color == RBTREE_BLACK) {
w->color = RBTREE_RED;
x = x->parent;
}
else{
if (w->left->color == RBTREE_BLACK) {
w->right->color = RBTREE_BLACK;
w->color = RBTREE_RED;
left_Rotate(t,w);
w = x->parent->left;
}
w->color = x->parent->color;
x->parent->color = RBTREE_BLACK;
w->left->color = RBTREE_BLACK;
left_Rotate(t,x->parent);
x = t->root;
}
}
}
x->color = RBTREE_BLACK;
}

int rbtree_erase(rbtree t, node_t p) {
// TODO: implement erase
if (p == NULL) {
return 0;
}
node_t y = p;
node_t x;
color_t y_original = y->color;
if (p->left == t->nil){
x = p->left;
transplant(t,p,p->right);
}
else if (p->right == t->nil) {
x = p->left;
transplant(t,p,p->left);
}
else {
y = p->right;
while (y->left != t->nil){
y = y->left;
}
y_original = y->color;
x = y->right;
if (y->parent == p) {
x->parent = y;
}
else {
transplant(t,y,y->right);
y->right = p->right;
y->right->parent = y;
}
transplant(t,p,y);
y->left = p->left;
y->left->parent = y;
y->color = p->color;
}
if (y_original == RBTREE_BLACK) {
delete_fixup(t,x);
}
free(p);
return 0;
}

void inOrder(const rbtree t, node_t curr, key_t arr, size_t pcnt, const size_t n){
if(curr == t->nil){
return;
}
inOrder(t, curr->left, arr, pcnt, n);
if(pcnt < n){
arr[(pcnt)++] = curr->key;
}
else{
return;
}
inOrder(t, curr->right, arr, pcnt, n);
}

int rbtree_to_array(const rbtree t, key_t arr, const size_t n) {
// TODO: implement to_array
if(t->root == t->nil){
return 0;
}
else{
size_t cnt = 0;
inOrder(t, t->root, arr, &cnt, n);
}
return 0;
}

</div>
</details>
profile
Lee Pil Ung
Frontend SoftWare Engineer(2022.06.27 ~)

0개의 댓글