[Data Structure] Red-Black Tree

Red-Black Tree

Red-Black Tree는 이진 탐색 트리(Binary Search Tree)기반 트리 형식의 자료구조이다.

이진 탐색 트리는 저장, 삭제, 탐색 시 O(logN)의 시간 복잡도를 갖지만, 한 쪽으로 편향될 경우(최악의 경우) 시간 복잡도가 O(N)이 될 수 있다.
👉 이러한 단점을 보완하기 위해 스스로 높이 균형을 유지하는 Red-Black Tree가 고안됨.

특징

탐색, 삽입, 삭제에 대해 Binary Search Tree의 특성을 사용한다.

각 노드는 Red or Black 색상이 할당된다.

Rotation과 Recoloring을 통해 균형을 유지한다.

탐색, 삽입, 삭제 시 O(logn)의 시간복잡도를 가진다.

삽입, 삭제 시 Red-Black Tree의 5가지 조건을 유지한다.

조건

1. 노드의 색상은 레드 or 블랙이다.

2. 루트 노드는 블랙이다.

3. 모든 리프 노드(NIL)는 블랙이다.

4. 모든 레드 노드는 2개의 블랙 자식 노드를 가진다. (연속된 2개의 노드가 레드면 위배)

5. 어떤 노드에서 리프 노드까지의 모든 경로는 같은 수의 블랙 노드를 포함한다.

Insertion(삽입)

추가되는 노드의 색상은 레드이다.

추가되는 레드 노드는 2개의 블랙 NIL 노드를 가진다.

트리의 균형을 잡기 위해 삼촌 노드의 색상을 확인한다.

Reblancing이 필요한 경우

조건 4가 위배되는 경우 → 레드 노드가 추가될 때, 블랙 노드를 레드로 색상 변경할 때, 회전할 때

조건 5가 위배되는 경우 → 블랙 노드가 추가될 때, 레드 노드를 블랙으로 색상 변경할 때, 회전할 때

삽입의 4가지 케이스

N → 추가할 노드(레드)

P → N의 부모 노드

G → P의 부모 노드

U → N의 삼촌 노드(P의 형제 노드)

 

1. N이 루트 노드인 경우

2. P가 블랙인 경우

3. P와 U가 레드인 경우

4. P가 레드고 U가 블랙인 경우

Case 1. N이 루트 노드인 경우

조건 2를 만족하기 위해 N을 블랙으로 변경한다.

조건 5가 위배되는가 ❔❔

루트 노드에 블랙 노드가 추가되는 것이기 때문에 모든 경로에 블랙 노드가 추가됨으로 위배되지 않는다!

 

Case 2. P가 블랙인 경우

조건 4가 위배되는가 ❔❔

추가되는 노드(레드)의 부모가 블랙이기 때문에 위배되지 않는다!

조건 5가 위배되는가 ❔❔

추가되는 노드의 부모 노드는 블랙 노드를 자식으로 가진다. (블랙 노드 2개)

추가되는 레드 노드는 2개의 블랙 노드를 자식으로 가지기 때문에(조건 4) 레드 노드가 추가되어도(블랙 노드 2개) 조건 5가 위배되지 않는다!

 

Case 3. P와 U가 레드인 경우

P와 U가 모두 레드인 경우 두 노드 모두 블랙으로 색상을 변경하고 G의 색상을 레드로 변경한다.

조건 4가 위배되는가 ❔❔

추가된 노드의 부모 노드를 블랙으로 변경했기 때문에 더블 레드가 발생하지 않음!

조건 5가 위배되는가 ❔❔

N이 추가되기 이전에 G 서브 트리의 블랙 노드 갯수는 2개이다. N을 추가하고 P, U를 블랙으로 변경하면 G 서브 트리의 블랙 노드 갯수는 3개가 된다. 이는 조건 5가 위배되기 때문에 G 노드의 색상을 레드로 변경해 조건 5를 충족한다.

하지만 G 노드가 루트 노드라면 ❔❔

이는 조건 2(G 노드가 루트 노드)가 위배된다. 

👉 조건을 충족하기 위해 G 노드를 기준으로 Case 1을 수행한다.

G 노드의 부모 노드가 레드 노드라면 ❔❔

조건 4(G 노드의 부모 노드가 레드 노드)가 위배된다.

👉 조건을 충족하기 위해 G 노드를 기준으로 Case 4 or 5를 수행한다.

 

Case 4. P가 레드고 U가 블랙인 경우

4-1. N이 G의 왼쪽(오른쪽) 노드의 왼쪽(오른쪽) 자식일 경우

→ G 노드 기준 Right(Left) Rotation 후 P와 G 색상 변경

4-2. N이 G의 왼쪽(오른쪽) 노드의 오른쪽(왼쪽) 자식일 경우

→ P 노드 기준 Left(Right) Rotation 후 4-1 케이스 실행

 

조건 5가 위배되는가 ❔❔

Rotation 전과 후의 Black 노드 갯수 변화가 없기 때문에 위배되지 않는다!

삭제(Delection)

Red-Black Tree의 삭제는 BST의 삭제 방법을 따른다. 따라서 삭제할 노드의 왼쪽 서브트리에서 최댓값을 찾거나, 오른쪽 서브트리에서 최솟값을 찾아 해당 값을 지우고자 하는 노드로 옮긴다. 그리고나서 삭제할 값을 대체한 노드를 지우는데, 이 노드는 반드시 최대 하나의 non-leaf 자식을 갖고 있다.

이때 가능한 경우의 수는 아래 그림과 같이 3가지 경우밖에 없다.

 

M → 삭제할 노드

C → 자식 노드

M이 레드인 경우

레드 노드는 반드시 2개의 리프 노드를 가진다. 왜냐하면 레드 노드가 한 쪽은 리프 노드를 가지고 다른 한 쪽은 non-leaf 노드를 가지면 조건 5를 위배하게 되기 때문이다.

따라서 레드 노드는 그냥 삭제해도 무방하다.

M이 블랙이고 C가 레드인 경우

M을 삭제하고 C를 블랙으로 색상을 변경하면 조건을 위배하지 않는다.

❗❗❗ 삭제할 노드(D)와 그의 자식 노드(C)가 모두 블랙일 경우 ❗❗❗

삭제할 노드와 그의 자식 노드가 모두 블랙인 경우에 노드를 그냥 삭제하면 해당 경로에 검은 노드 한 개를 삭제하는 것이기 때문에 조건 5에 위배된다. 따라서 트리의 균형을 맞추기 위해 몇몇 고려되어야 할 사항들이 있다.

N → M을 C로 치환한 노드

P → 부모 노드

S → 형제 노드

SL → S의 왼쪽 자식 노드

SR → S의 오른쪽 자식 노드

Case 1: N이 루트 노드인 경우

이 경우 더 할 일이 없다. 모든 경로에서 하나의 블랙 노드를 삭제했고, 루트 노드는 블랙이므로 모든 조건이 충족한다.

void delete_case1(struct node *n)
{
    if (n->parent != NULL)
        delete_case2(n);
}

 

 

Case 2: S가 레드일 경우

S가 레드일 경우 P는 무조건 블랙이다(조건 4). 이 경우 P와 S의 색을 바꾸고 P에서 왼쪽으로 회전한다.

출처: https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC#%EC%82%AD%EC%A0%9C(Removal)

모든 경로에서 블랙 노드의 수가 같지 않으므로 아직 끝나지 않았다. 이제 N이 블랙 형제 노드와 레드 부모 노드를 갖으므로 case 4, 5, 6을 수행할 수 있다.

void delete_case2(struct node *n)
{
    struct node *s = sibling(n);

    if (s->color == RED) {
        n->parent->color = RED;
        s->color = BLACK;
        if (n == n->parent->left)
            rotate_left(n->parent);
        else
            rotate_right(n->parent);
    }
    delete_case3(n);
}

 

Case 3: P, S, S의 자식이 블랙인 경우

이 경우 S의 색상을 레드로 변경한다.

출처: https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC#%EC%82%AD%EC%A0%9C(Removal)

이로 인해 S를 지나는 모든 경로들은 하나 적은 블랙 노드를 갖게 된다. 또한 N의 원래 부모 노드를 삭제하는 과정에서 N을 지나는 모든 경로들은 하나 적은 블랙 노드를 갖게되므로 양쪽은 같은 수의 블랙 노드를 가진다.

하지만 P를 지나는 모든 경로들은 P를 지나지 않는 모든 경로보다 블랙 노드가 하나 적게 가지기 때문에 전체적으로 조건 5를 위배하게 된다. 이를 위해 P에서 case 1부터 시작하는 Rebalancing 과정을 수행해야 한다.

void delete_case3(struct node *n)
{
    struct node *s = sibling(n);

    if ((n->parent->color == BLACK) &&
        (s->color == BLACK) &&
        (s->left->color == BLACK) &&
        (s->right->color == BLACK)) {
        s->color = RED;
        delete_case1(n->parent);
    } else
        delete_case4(n);
}

 

Case 4: S와 S의 자식들은 블랙이고 P는 레드인 경우

이 경우 P와 S의 색을 바꾼다.

출처: https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC#%EC%82%AD%EC%A0%9C(Removal)

이는 S를 지나는 경로의 블랙 노드 개수에는 영향을 주지 않지만, N을 지나는 경로에 블랙 노드 개수를 1개 증가한다. 이를 통해 양쪽의 블랙 노드 개수가 균형을 이룬다.

void delete_case4(struct node *n)
{
    struct node *s = sibling(n);

    if ((n->parent->color == RED) &&
        (s->color == BLACK) &&
        (s->left->color == BLACK) &&
        (s->right->color == BLACK)) {
        s->color = RED;
        n->parent->color = BLACK;
    } else
        delete_case5(n);
}

 

Case 5: S가 블랙, S의 왼쪽 자식이 레드, 오른쪽 자식이 블랙인 경우

S를 오른쪽으로 회전시키고 S의 색을 부모 노드의 색상(S의 왼쪽 자식)으로 바꾼다.

출처: https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC#%EC%82%AD%EC%A0%9C(Removal)

모든 경로는 여전히 같은 수의 블랙 노드를 가지지만(P 노드 기준 5번 조건 위배), N이 레드 노드를 자식으로 둔 블랙 형제 노드를 갖게 되었기 때문에 case 6를 진행할 수 있다.

void delete_case5(struct node *n)
{
    struct node *s = sibling(n);

    if  (s->color == BLACK) {
        /* 이 문은 자명하다,
            case 2로 인해서(case 2에서 '''N'''의 형제 노드를 원래 형제 노드 '''S'''의 자식노드로 바꾸지만,
            빨강 부모노드는 빨강 자식 노드를 가질 수 없기 때문에 '''N'''의 새로운 형제노드는 빨강일 수 없다). */
        /* 다음의 문은 빨강을 '''N'''의 부모노드의 오른쪽 자식의 오른쪽 자식으로 두기 위함이다.
            혹은 '''N'''의 부모노드의 왼쪽 자식의 왼쪽 자식으로 두기 위함. case 6에 넘기기 위해 */
        if ((n == n->parent->left) &&
            (s->right->color == BLACK) &&
            (s->left->color == RED)) { /* this last test is trivial too due to cases 2-4. */
            s->color = RED;
            s->left->color = BLACK;
            rotate_right(s);
        } else if ((n == n->parent->right) &&
            (s->left->color == BLACK) &&
            (s->right->color == RED)) {/* this last test is trivial too due to cases 2-4. */
            s->color = RED;
            s->right->color = BLACK;
            rotate_left(s);
        }
    }
    delete_case6(n);
}

 

Case 6: S가 블랙, S의 오른쪽 자식이 레드, 왼쪽 자식이 블랙인 경우

이 경우 P를 왼쪽으로 회전한 뒤, P와 S의 색을 바꾸고 S의 오른쪽 자식 노드를 블랙으로 바꾼다.

출처: https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC#%EC%82%AD%EC%A0%9C(Removal)

 

이 서브트리의 루트 노드는 색상이 변하지 않았지만 N의 상위 노드에 블랙 노드가 추가 되었기 때문에 양쪽의 블랙 노드 수가 일치하게 된다.

void delete_case6(struct node *n)
{
    struct node *s = sibling(n);

    s->color = n->parent->color;
    n->parent->color = BLACK;

    if (n == n->parent->left) {
        s->right->color = BLACK;
        rotate_left(n->parent);
    } else {
        s->left->color = BLACK;
        rotate_right(n->parent);
    }
}

 

Red-Black Tree는 Java Collection에서 ArrayList를 구현하는 데에 사용되고, HashMap에서 Seperte Chaining을 구현하는 데에 사용된다.

---

Reference

https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC#%EC%82%AD%EC%A0%9C(Removal) 

레드-블랙 트리 - 위키백과, 우리 모두의 백과사전