[알고리즘] 레드-블랙트리(Red-BlackTree) -Insert

 

 

---

이진탐색트리(BST)를 기반으로 구성된 자료구조입니다.

BST의 설명은 여기에 있습니다. 따라서 BST의 설명은 본 게시물에서는 하지 않습니다. 

---

 

 

개념설명

 

: 우선 이진탐색트리를 잠깐 봅시다. 이진탐색트리는 Search, Insert, Delete 가 가능한 이진트리였습니다. 이때, 평균 시간복잡도는 O(log n) 이였죠. 하ㄴ지만 이진트리가 극단적으로 편향됬을때시간복잡도는 O(N) 이 됩니다. 이건 이진트리의 깊이(h) 많큼 탐색을 한다는 의미입니다. 

이러한 문제들을 해결하기 위해 나온 것이 바로 레드-블랙트리(Red-BlackTree) 입니다. 다른 말로 Balanced Binary Search Tree 라고도 합니다. 이유는 이진탐색트리의 깊이를 항상 log N 으로 유지시켜주기 때문입니다. 따라서 최악의 경우에도 시간복잡도가 O(2log n) 으로 매우 안정적입니다.

 

레드-블랙트리의 조건

 

1. 각 노드는 RED 혹은 BLACK 이다.

2. 루트노드는 항상 BLACK 이다.

3. 모든 리프노드(즉 NIL노드)는 전부 BLACK이다.

4. RED 노드의 자식들은 전부 BLACK 이다. (즉, RED 노드는 연속되어 등장할 수 없다.)

5. 루트노드로부터 리프노드에 이르는 모든 경로에는 동일한 개수의 BLACK 노드가 존재한다.

 

동작원리(Rotation)

: 사입을 하기 위해서는 트리의 모양을 이진트리구조를 유지하면서 바꾸는 방법인 회전(Rotation)을 먼저 이해하셔야 합니다. 이때 회전은 우회전과 좌회전으로 나뉩니다.

< Right Rotation >

: 왼쪽의 있는 그림을 오른쪽으로 바꾸는 것이 우회전입니다. 

1. P의 오른쪽 자식으로 Q 를 연결해준다.

2. Q의 왼쪽자식으로 B를 연결한다. 

(이 두 트리는 임의의 큰 트리의 서브트리인 점을 유의하시기 바랍니다.)

< Left Rotation >

: 오른쪽에 있는 그림을 왼쪽으로 바꾸는 것이 우회전입니다. 

1. Q의 왼쪽 자식으로 P를 연결해준다.

2. P의 오른쪽 자식으로 B를 연결해준다.

삽입

1. 처음에 root 로 삽입되는 경우
2. 부모노드가 Black 인 경우 
3. 부모노드가 Red, 삼촌노드가 Red 인 경우
4. 부모노드가 Red, 삼촌노드가 Black 인 경우

< Root 로 삽입되는 경우 >

: 새로 입력되는 모든 값은 Red 라는 규칙이 존재하지만, Root는 무조건 Black 이라는 조건을 성립시키기 위해 Black 으로 새로운 노드를 할당한다.

void insert_case1(Node node)
{
    if (node->parent == NULL)
        node->color = BLACK;
    else
        insert_case2(node);
}

 

< 부모노드 Black >

: 이때는 단순히 새로운 노드를 Red 로 할당한다. 위배되는 조건이 없기 때문에 트리는 유지된다.

void insert_case2(Node node)
{
    if (node->parent->color == BLACK)
        return; 
    else
        insert_case3(node);
}

< 부모노드 Red, 삼촌노드 Red >

: 이때 부모와 삼촌의 색을 모두 Black 으로 바꿔준다. ( Recoloring) 

 

void insert_case3(Node node)     
{
    if (uncle(node) != NULL && uncle(node)->color == RED)
    {
        node->parent->color = BLACK;
        uncle(node)->color = BLACK;
        grandparent(node)->color = RED;
 
        insert_case1(grandparent(node));
    }
    else
        insert_case4(node);
}

< 부모노드 Red, 삼촌노드 Black >

: 이때 두가지 경우가 존재합니다. 그리고 과정이 복잡한 편입니다.

1. 입력 노드(z)가 오른쪽자식, 부모노드(p)가 왼쪽 자식인 경우

: 부모노드(p)를 기준으로 좌회전을 하면 부모노드 위치에 입력 노드(z)가 온다.

회전을 마치고 입력노드(z)기준 왼쪽 자식노드(p) 를 기준노드로 변경한다

다시 기준노드의 부모노드(z)의 색을 Black, 조상노드의 색을 Red로 바꾼다.

마지막으로 조상노드를 기준으로 우회전을 하면 끝난다.

1. 입력 노드(z)가 왼쪽자식, 부모노드(p)가 오른쪽 자식인 경우

: 부모노드(p)를 기준으로 우회전을 하면 부모노드 위치에 입력 노드(z)가 온다.

회전을 마치고 입력노드(z)기준 오른쪽 자식(p)를 기준노드로 변경한다.

다시 기준노드의 부모노드(z)를 Black, 조상노드를 Red 로 변경한다.

마지막으로 조상노드를 기준으로 좌회전을 하면 끝난다.

void insert_case4(Node node)
{
    if (node == node->parent->right && node->parent == grandparent(node)->left)
    {
        rotate_left(node->parent);
        node = node->left;
    }
    else if (node == node->parent->left && node->parent == grandparent(node)->right)
    {
        rotate_right(node->parent);
        node = node->right;
    }
    insert_case5(node);
}
 
void insert_case5(Node node)
{
    node->parent->color = BLACK;
    grandparent(node)->color = RED;
 
    if (node == node->parent->left && node->parent == grandparent(node)->left)
    {
        rotate_right(grandparent(node));
    }
    else
    {
        rotate_left(grandparent(node));
    }
}

 

 

출처 : https://zeddios.tistory.com/237