Red-Black Tree (4) 삽입(insert, insert_fix_up)

이후띵·2021년 12월 8일
C 언어RB-Treerb_insert
0

RB Tree

목록 보기
4/5

레드-블랙 트리의 특성(조건)

  1. 모든 노드는 적색이거나 흑색이다.
  2. 루트는 흑색이다.
  3. 모든 리프(NIL)는 흑색이다.
  4. 노드가 적색이면 그 노드의 자식은 모두 흑색이다.
  5. 각 노드로부터 그 노드의 자손인 리프로 가는 경로들은 모두 같은 수의 흑색 노드를 포함한다.

삽입(insertion)

  • 레드-블랙 트리에서 새로운 노드를 삽입할 때, 새로운 노드는 항상 적색으로 입력한다.

  • 만약 트리가 레드블랙 트리의 특성을 위반하면, 두가지 operation 을 통해 트리의 구조를 조정한다.

(1) Recolor (2) Rotation.

insert 과정

키 값이 20인 노드를 삽입하는 과정을 생각해보자,
중요 : target Node를 20으로 설정하고 시작.

  • key = 20인 노드가 들어갈 위치 탐색

  • key = 20 < 28 이고, 28의 왼쪽 노드가 nil.

  • 새로운 노드(20)을 삽입완료.

insert-fixup 과정

****중요 : while문 조건 : target의 부모가 적색.

case 1:

부모 노드의 컬러가 적색 & 삼촌 노드의 컬러가 적색.


target node(18) -> color = red, parent -> color = red
특성4. 노드가 적색이면 그 노드의 자식은 모두 흑색이다.
-> 어라? 위반했네..

  • uncle node 는 할아버지 노드의 다른 자식이다.
  • uncle node(12)색과 부모노드의 색이 모두 적색임을 확인.(case 1)

  • 할아버지 노드는 흑색(부모노드가 적색이었으므로)
  • Recolor : 할아버지 노드 색과 부모 & uncle 색을 바꿔서 칠해준다.
  • target node를 20의 할아버지 노드(18)로 설정!

case 1 결과 :

-> 18을 루트노드인 서브트리는 레드-블랙 트리의 특성을
(fix-up 과정의 마지막에 트리의 루트노드를 흑색으로 칠해주는 과정이 있다. 만약, 18이 루트노드 였다면, 흑색으로 색칠하여 레드-블랙 트리의 특성을 보전할 수 있다.)

-> target node를 18 로 설정한다. (할아버지)

case 2:

부모 노드의 컬러가 적색 & 삼촌 노드의 컬러가 흑색.


target node(18) -> color = red, parent -> color = red
특성4. 노드가 적색이면 그 노드의 자식은 모두 흑색이다.

-> 어라? 위반했네..

  • 부모노드의 색이 적색이다, uncle 노드(50)는 흑색이다!!(case 2)

  • Rotation : 부모노드가 왼쪽 자식이면 left rotation / 오른쪽 자식이면 right rotation
  • target node를 부모노드로 설정 후, 좌회전 실시.
  • target node = 18 -> 10(new)
  • 좌회전 실시!

case 2결과 :

사실 지금까지 했던 것은 case 2 - (1) 이었다.

case 2 - (1) 인 경우에는 case 2 - (2)의 형태로 바꾸고 case 2 - (2) 를 진행한다고 생각하면 된다.

case 2 - (2) 는 부모노드가 할아버지노드의 왼쪽 자식이며, target 또한 부모노드의 왼쪽자식일 때이다.
(혹은 오른쪽 자식의 오른쪽 자식이 target일 때)

여기까지 정리해보면,
1. Fix-up 과정은 부모노드가 적색일 때 일어난다.
2. case 1 은 부모노드와 삼촌 노드가 모두 적색일 때,
3. case 2 는 2가지로 나뉜다.

case 2 : 부모노드는 적색, 삼촌노드는 흑색일 때.

case 2 - (1) :

grandparent -> left -> right = target 또는 grapndparent -> right -> left = target.

case 2 - (2) :

grandparent -> left -> left = target 또는 grandparent -> right -> right - target

처음에 case 2 - (2) 형태로 들어올 수도 있고,
case 2 - (1) 형태이면 이어서 case 2 - (2) 를 바로 진행하게 된다.

case 2 - (2):

case 2 : 부모 노드의 컬러가 적색 & 삼촌 노드의 컬러가 흑색.

case 2 - (2) : grandparent -> left -> left = target

(또는 grandparent -> right -> right - target)

target 노드 = 10

  • Rotation : 부모노드가 오른쪽 자식이면 right rotation / 왼쪽 자식이면 left rotation

  • Recolor : 부모노드(18)를 흑색으로 바꾼다, 할아버지 노드(30)를 적색으로 바꾼다.

  • 우회전 실시!

case 2 - (2) 결과 :

while 문의 조건이 target의 부모노드가 적색 노드일 때다. target node(18)의 부모노드는 nil 노드로, 흑색으로 설정되어 있다. 따라서, while 문이 종료된다.

target 노드가 case 1 의 결과처럼 적색 노드이고, 루트노드일 경우가 있으므로, while문이 끝나고 마지막에 루트노드의 색을 흑색으로 칠하고 insertion fix-up을 종료한다.

레드-블랙 트리의 특성을 만족하는 트리가 완성되었다.

슈도 코드는 다음과 같다.

rb_insert (tree* T, node* z)

rb_insert_fix_up (tree* T, node* z)

* 주의 : else if 가아니라 else안에 if문임.

C 언어 구현 코드.

좌회전 (left rotation)

void left_rotate(rbtree *t, node_t *x){
    node_t *y;
    y = x->right;
    x->right = y->left;
    if (y->left != t->nil){
        y->left->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->left = x;
    x->parent = y;
}

우회전 (right rotation)

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

삽입 수정 (insert-fix-up)

void *rb_insert_Fixup(rbtree *t, node_t *z)
{
    node_t *uncle;
    while (z->parent->color == RBTREE_RED){
        if (z->parent == z->parent->parent->left){
            uncle = z->parent->parent->right;
            //경우1
            if (uncle->color == RBTREE_RED){
                z->parent->color = RBTREE_BLACK;
                uncle->color = RBTREE_BLACK;
                z->parent->parent->color = RBTREE_RED;
                z = z->parent->parent;
            }
            //경우2 (경우 2는 경우 3을 경유)
            else {
                if (z == z->parent->right){
                    z = z->parent;
                    left_rotate(t, z);
                }
                //경우3
                z->parent->color = RBTREE_BLACK;
                z->parent->parent->color = RBTREE_RED;
                right_rotate(t, z->parent->parent);
            }
        }
        //반대로
        else
        {
            uncle = z->parent->parent->left;
            //경우1
            if (uncle->color == RBTREE_RED){
                z->parent->color = RBTREE_BLACK;
                uncle->color = RBTREE_BLACK;
                z->parent->parent->color = RBTREE_RED;
                z = z->parent->parent;
            }
            //경우2 (경우2는 경우3을 경유)
            else {
                if (z == z->parent->left){
                    z = z->parent;
                    right_rotate(t, z);
                }
                //경우3
                z->parent->color = RBTREE_BLACK;
                z->parent->parent->color = RBTREE_RED;
                left_rotate(t, z->parent->parent);
            }
        }
    }
    t->root->color = RBTREE_BLACK;
}

삽입 (insert)

node_t *rbtree_insert(rbtree *t, const key_t key){
    // TODO: implement insert
    node_t *parent = t->nil;
    node_t *p = t->root;
    //새 노드가 들어갈 자리 찾기
    while (p != t->nil){
        parent = p;
        if (key < p -> key){
            p = p->left;
        }
        else{
            p = p->right;
        }
    }
    node_t *new_node = (node_t *)calloc(1, sizeof(node_t));
    new_node->parent = parent;
    // 트리의 첫 노드일 때 - 루트가 된다
    if (parent == t->nil){
        t->root = new_node;
        new_node->color = RBTREE_BLACK;
    }
    //찾은 부모노드보다 새로운 노드가 작을때 - 왼쪽 자식으로
    else if (key < parent->key){
        parent->left = new_node;
        new_node->color = RBTREE_RED;
    }
    //크거나 같을때 - 오른쪽 자식으로
    else{
        parent->right = new_node;
        new_node->color = RBTREE_RED;
    }
    //새로운 노드 설정
    new_node->key = key;
    new_node->left = t->nil;
    new_node->right = t->nil;

    rb_insert_Fixup(t, new_node);
    return t->root;
}

배운점 :

포인터 변수, 메모리 할당(malloc, free), stack & heap 메모리, call by reference, call by value, 단순 이진 탐색 트리와 달리 최악의 경우에도 O(log(n))을 보장하는 RB 트리의 위대함. RB 트리는 이진탐색트리를 유지하면서 RB 트리의 특성을 만족시키기 위해 color demotion, color promotion, rotation 등을 통해 근사적인 균형을 이룬다.

궁금 했던 것 :

  • 노드를 삽입할 때, 왜 항상 적색노드로 할까?
  • 답 : 적색 노드 삽입은 레드-블랙 트리의 5번 특성을 위반하지 않는다. 5번 속성은 특정 노드를 선택했을 때, 자신과 리프(nil)노드를 제외한 마주치는 흑색노드의 개수가 모두 같아야 한다는 특성이다. 적색 노드를 삽입할 때는 4번 속성을 위반이 발생하지만, 훨씬 간단하게 해결되기 때문에 적색노드를 삽입한다.
    -> 흑색노드를 삽입하면, 양쪽 서브트리의 균형을 계속 확인해야하고 굉장히 복잡할듯.
profile
이후띵
이후띵's 개발일지
이전 포스트

Red-Black Tree (3) 회전 rotation

다음 포스트

Red-Black Tree (5) 삭제(deletion) - delete, delete_fix_up, 전체구현코드

0개의 댓글