Red-BlackTree

Red-Black 트리

- 이진 탐색 트리(BST)의 한 종류

- 스스로 균형 잡는 트리

- BST의 worst case의 단점을 개선( O(N) -> O(logN)

- 모든 노드는 red or black

 

RBTree 특성

#1 모든 노드는 Red or Black

#2 루트 노드는 Black

#3 모든 nil(leaf)는 Black

#4 Red의 자녀들은 black -> red가 연속적으로 존재할 수 없다

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

 

 

nil노드란?

• 존재하지 않음을 의미하는 노드
• 자녀가 없을 때 자녀를 nil노드로 표기
• 값이 있는 노드와 동등하게 취급
• RB 트리에서 leaf 노드(자식 없는 노드)는 nil노드

 

노드 x의 black height

- 노드 x에서 임의의 자손 nill노드까지 내려가는 경로에서의 black 수 (자기 자신을 카운트에서 제외)

 -> #5 속성을 만족해야 성립하는 개념

 

식을 바꾸면서도 #5 속성 유지하기

- RB트리가 #5 속성을 만족하고 있고 두 자녀가 같은 색을 가질 때 부모와 두 자녀의 식을 바꿔줘도 #5 속성은 여전히 만족한다.

---

RB 트리는 어떻게 균형을 잡는가?

 

💡 삽입/삭제시 #2, #4, #5 속성을 위반함. 이들을 해결하기 위해서 구조를 바꾸면, 자연스럽게 균형이 잡히게 된다.

 

삽입처리

insert (노드삽입)

• 삽입 전 RB트리 속성을 만족한 상태
• 삽입 방식은 일반적인 BST(이진탐색트리)와 동일 (삽입노드의 색깔은 항상 RED)
  • 삽입 노드의 색깔이 항상 RED인 이유는 삽입 후에도 #5 속성을 만족하기 위해서
  • #2 속성을 위반한 경우에는 루트 노드를 BLACK으로 바꿔준다.
• 삽입 후 RB트리 속성 위반 여부 확인
• RB트리 속성을 위반했다면 재조정 (insert-fixup)
• RB트리 속성을 다시 만족

 

insert-fixup (삽입시 속성위반 재조정)

삽입 후#2, #4 속성을 위반할 경우가 발생하므로, 다음의 알고리즘을 수행해서 속성 위반을 해결

while(부모가 RED) {
	
    //CASE 1.
    if 부모/삼촌 == RED이면,
    	부모/삼촌 모두 BLACK으로 바꾸고, 할아버지를 RED로 변경
        할아버지에게 다시 시작
        
    //CASE 2/3. 삼촌 == BLACK
   	else {
    	//CASE 2.
        if 할아버지/부모/자신 꺾인 상태
        	회전해서 부모/자신을 펴준다. CASE 3 상태가 됨
           
        //CASE 3. 할아버지/부모/자신 펴진 상태
        부모/할아버지 서로 색 바꾸기
        할아버지 기준 회전
    }
}

//종료전
루트를 BLACK으로 변경

 

삽입시 조정 CASE 1,2,3

💡 아래의 CASE 2,3은 좌우 대칭으로 동작

 

 

 

삭제처리

delete( 노드 삭제)

• 삭제 전 RB트리 속성 만족한 상태
• 삭제 방식은 일반적인 BST와 동일
• 삭제 후 RB트리 속성 위반 여부 확인
• RB트리 속성 위반했다면 재조정
• RB트리 속성 다시 만족

 

삭제 색 결정 법

1. 삭제하려는 노드의 자녀(유효한 값을 가지는 자녀(nil x))가 없거나

     하나라면 삭제되는 색 = 삭제되는 노드의 색

 

2. 삭제하려는 노드의 자녀가 둘이라면 삭제되는 색 = 삭제되는 노드의 successor의 색

• successor - 노드 x의 오른쪽 서브트리의 최솟값

 

✔️속성 위반 여부 확인 -> 삭제되는 색을 통해

 

- 삭제되는 색이 red이면 어떠한 속성 위반 x

- 삭제되는 색이 black이면 #2, #4, #5 위반

 

삭제되는 색이 black일 때, #2번 위반 해결하기

-> 루트 노드를 black으로 바꾸면 된다.

 

* 특수한 상황을 제외하면 #5 속성은 항상 위반!!!

 

삭제 되는 색이 black이고 #5위 반이면

-> #5 속성 만족 위해 삭제된 색의 위치를 대체한 노드에 extra black 부여

(경로에서 black 수를 카운트할 때 extra black은 하나의 black으로 카운트)

 

double black- extra black이 부여된 black 노드

red and black - extra black이 부여된 red 노드, black으로 바꿈

 

extra black 부여 후 double black 해결하기 위해서는 네 가지 case로 분류된다. 

분류 기준은 double black의 형제의 색과 그 형제의 자녀들의 색으로 분류한다.

 

#case 4

double black의 오른쪽 형제가 black & 그 형제의 오른쪽 자녀가 red

-> 오른쪽 형제는 부모의 색으로, 오른쪽 형제의 오른쪽 자녀, 부모는 black으로 바꾼 후, 부모를 기준으로 왼쪽으로 회전

(오른쪽 왼쪽을 바꿔도 성립)

 

#case 3

double black의 오른쪽 형제가 black & 그 형제의 왼쪽 자녀 red & 그 형제의 오른쪽 자녀 black

-> double black의 형제의 오른쪽 자녀가 red가 되게 만들어야 한다.(부모랑 왼쪽 자녀 색을 바꾸고 부모를 기준으로 회전) 그런 후 #case 4 적용하여 해결!

(오른쪽 왼쪽을 바꿔도 성립)

 

#case 2

double black의 형제가 black & 그 형제의 두 자녀 모두 black

-> double black과 그 형제의 black을 모아 부모에게 전달해서 부모가 extra black 해결

-> double black의 형제는 red가 되지만 double black은 여전히 black, 

    부모가 red-and-black이면 black으로 바꿔줌

 

#case 1

double black 오른쪽 형제가 red

-> 부모와 형제 색 바꾸고, 부모를 기준으로 회전, double black 기준으로 case 2,3,4 중 하나를 사용해서 해결

(회전 후에도 #5 속성을 만족하려면 회전하기 전에 부모와 형제의 색을 바꿔야 함)

 

delete-fixup (삭제 시 속성위반 재조정)

while (타겟이 루트아님 && 타겟 == BLACK) {

    // CASE 1.
    if **형제 == RED**
        형제/부모 서로 색바꾸기, 부모기준 회전 (타겟이 내려가도록)

    // CASE 2.
    if **형제 == BLACK, 형제의 자식 둘다 블랙**
        형제/자신의 블랙을 부모로 올리기 -> 형제를 RED로 변경, 부모에서 다시 fixup

    else {
        // CASE 3.
        if 형제 == BLACK, (**형제의 꺾인 자식**) == RED
            자식 RED와 형제 서로 색바꾸기, 펴지게 회전 (RED가 바깥쪽에 오게)
            CASE 4가 됨

        // CASE 4. 형제 == BLACK, (**형제의 펴진 자식**) == RED
        부모/형제 서로 색바꾸기
        형제의(펴진 자식) = BLACK
        부모기준 회전 (타겟이 내려가도록)
        타겟을 루트로 설정 -> while 종료
    }
}

// 종료전
타겟을 BLACK으로 변경

 

삭제 조정 CASE 1,2,3,4

 

 

자료구조 (rbtree, node_t)

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);
int rbtree_erase(rbtree *, node_t *);

// 삽입/삭제 fixup
void rb_insert_fixup(rbtree *t, node_t *z);
void rb_erase_fixup(rbtree *t, node_t *x);

// 노드 검색
node_t *rbtree_find(const rbtree *, const key_t);
node_t *rbtree_min(const rbtree *);
node_t *rbtree_max(const rbtree *);

// 트리를 배열로 변환 -> inorder traversing으로 구현!!! 
// traversing 순서: node, node->left, node->right
int rbtree_to_array(const rbtree *, key_t *, const size_t);

 

 

참고

https://youtu.be/2MdsebfJOyM

https://youtu.be/6drLl777k-E