Acanel Blog

Red-Black 트리

개요

레드-블랙 트리는 1972년 루돌프 바이어가 창안했으며, 이를 "대칭형 이진 B-트리"(symmetric binary B-tree)라고 불렀고, 1978년 Leo J. Guibas와 로버트 세지윅이 발표한 논문에서 현재의 이름이 등장하게 되었다.
레드-블랙 트리는 내부적으로 균형을 이룬 이진 탐색 트리(balanced binary search tree)로, 현재 고안되어 사용되는 이진 탐색 트리 중 가장 효율적인 자료구조이다. 비록 복잡한 자료구조이지만, 실 사용에서 효율적이고, 최악의 경우에도 상당히 우수한 실행 시간을 보인다. 트리에 n개의 원소가 있을 때 O(log n) 의 시간복잡도로 삽입, 삭제, 검색을 할 수 있다. 따라서 운영체제의 가상 메모리 관리 등등 많은 효율성이 필요한 프로그램에서 이를 사용하고 있다. 레드-블랙 트리는 직관적이지 않기 때문에 여러 개념들에 대해 실제로 수행해보는 것이 습득에 많은 도움을 줄 것이다.

[그림 1] 레드-블랙 트리 예제

용어 설명

레드-블랙 트리는 일반적인 이진 탐색 트리에서 사용되는 개념 외에도 추가적으로 사용되는 용어가 있으므로 이를 짚고 넘어가도록 한다.

Node의 Color

레드-블랙 트리에서는 각 노드마다 Color를 가지며, 빨간색 또는 검은색을 지닌다.

실제 구성 시에는 노드에 Color Field를 포함시킬 수도 있고, 링크에 Color 속성을 포함시킬 수도 있으나 모두 동일하게 작동한다.

NIL Leaf Node

레드-블랙 트리에서의 잎 노드(말단 노드)는 반드시 검은색이어야 한다는 조건이 있다.

그렇기 때문에 트리의 끝에서 포인터가 NULL을 가리키는 대신, 데이터가 없고 검은색인 NIL Leaf Node를 가리키도록 구성한다.

Uncle Node

부모 노드의 형제 노드. 조부모 노드의 자식 중 부모 노드가 아닌 다른 노드를 의미한다.

Right-Rotation, Left-Rotation

이진 트리의 구조를 변경하는 연산이다. Right-Rotation의 경우 우측으로 트리가 회전하며, Left-Rotation의 경우 좌측으로 트리가 회전한다.

[그림 2] Right-Rotation, Left-Rotation

레드-블랙 트리의 조건, 성질
레드-블랙 트리는 다음과 같은 조건을 만족하는 이진 탐색 트리의 특수한 형태이다.
1) 노드는 빨간색 또는 검은색 중 하나의 색을 지닌다.
2) 루트 노드(Root Node)는 검은색이다.
3) 모든 말단 노드(Leaf Node)는 검은색이다.
4) 빨간색 노드의 자식은 무조건 검정색이다. 하지만 검정색 노드의 자식은 검정색, 빨간색 모두 가능하다.
5) 특정 노드로부터 말단 노드(Leaf Node)에 도달하는 모든 경로에는 모두 같은 개수의 검정색 노드가 있다.

위 다섯 가지 조건을 만족하는 경우, 다음과 같은 성질을 가지게 된다.

레드-블랙 트리의 최장 깊이는 최단 깊이의 2배를 넘지 못한다.

이런 성질을 가지는 이유는, 조건 4)에 따라 어떤 경로에도 빨간색 노드가 연이어 나타날 수 없다는 것 때문이다.

최단 경로가 모두 검정색 노드로 구성되어 있다고 했을 때, 최장 경로는 검정색 노드와 빨간색 노드가 번갈아 나오는 경우이다.

또한 조건 5)에서 모든 말단 노드로의 경로에서 검정색 노드의 수가 같다고 하였기 때문에 2배 이하의 관계가 이루어지는 것이다.

결과적으로 레드-블랙 트리는 적절한 균형을 이루는 성질을 가지게 된다.

아래의 그림은 최악의 경우의 레드-블랙 트리의 한 예를 나타낸 것이다.

[그림 3] 레드-블랙 트리의 조건을 만족하는 Worst Case 예제

노드의 구조 정의

노드는 일반적인 이진 탐색 트리에서의 노드와 같이 정렬을 위한 key를 가지고 있으며 자식 노드를 가리키는 left, right 포인터를 가진다.

추가적으로 data를 포함할 수 있으며 부모 노드를 가리키는 parent 포인터를 가지고 있을 수도 있다.

레드-블랙 트리에서의 필수적인 추가 요소는 color 속성이다.

아래는 c언어로 표현한 노드의 일반적인 구조이다.

struct node 
{
    int key;                 //key for sort
    DATA data;               //node data
    struct node *parent;     //point to parent
    struct node *left;       //point to left child
    struct node *right;      //point to right child
    int color;               //node color(red or black)
};

레드-블랙 트리의 삽입 절차

레드-블랙 트리의 삽입 절차는 기본적으로 이진 탐색 트리와 동일하다. 단, 아래의 조건에 맞추어 따라가게 된다.

1) 삽입하는 노드는 빨간색 노드이다.

2) 삽입 과정에서 루트 노드가 빨간색이 되는 경우, 검은색으로 변경한다.

3) 삽입 시 부모 노드가 검은색인 경우, 레드-블랙 트리의 조건에 위배되는 것이 없으므로 변경이 없다.

4) 부모 노드가 빨간색인 경우, 삼촌 노드가 빨간색인 경우 조건 4)에 위배되므로 다음과 같은 절차를 따른다.

부모 노드(P) : 빨간색, 삼촌 노드(U) : 빨간색 인 경우

① : 노드 삽입 시, 부모 노드(P)와 삼촌 노드(U)가 모두 빨간색인 경우.

② : 부모 노드(P)와 삼촌 노드(U)를 검정색으로 칠하고, 조부모 노드(G)를 빨간색으로 변경한다.

③ : 조부모 노드(G)가 빨간색이 되었으므로 조건 4)에 위배될 가능성이 있다. 따라서 이를 새로 삽입한 노드로 간주하고 재귀적으로 다시 검사를 시작한다.

5) 부모 노드가 빨간색인 경우, 삼촌 노드가 검정색인 경우는 조건 4)에 위배되며 빨간색 노드가 적어도 2개 이상 차이난다.

따라서 색의 변경 뿐만 아니라 불균형을 해결하기 위해 Rotation도 수행하게 된다. 삽입되는 위치에 따라 네 가지 경우로

구분지어 처리하게 된다.

5.1) 조부모 노드의 왼쪽 자식이 부모 노드, 부모 노드의 왼쪽 자식이 삽입 노드인 경우(Left-Left)

부모 노드(P) : 빨간색, 삼촌 노드(U) : 검은색, Left-Left 인 경우

① : 노드 삽입 시, 부모 노드(P)는 빨간색, 삼촌 노드(U)는 검정색인 경우, 또한 Left-Left인 경우.

② : 조부모 노드(G)를 기준으로 Right-Rotation을 수행한다.

③ : 기존의 부모 노드(P)를 검정색으로, 조부모 노드(G)를 빨간색으로 변경한다

5.2) 조부모 노드의 왼쪽 자식이 부모 노드, 부모 노드의 오른쪽 자식이 삽입 노드인 경우(Left-Right)

부모 노드(P) : 빨간색, 삼촌 노드(U) : 검은색, Left-Right 인 경우

① : 노드 삽입 시, 부모 노드(P)는 빨간색, 삼촌 노드(U)는 검정색인 경우, 또한 Left-Right인 경우.

② : 부모 노드(P)를 기준으로 Left-Rotation을 수행한다.

③ : 조부모 노드(G)를 기준으로 Right-Rotation을 수행한다.

④ : 삽입 노드(N)을 검정색으로, 조부모 노드(G)를 빨간색으로 변경한다.

5.3) 조부모 노드의 오른쪽 자식이 부모 노드, 부모 노드의 오른쪽 자식이 삽입 노드인 경우(Right-Right)

부모 노드(P) : 빨간색, 삼촌 노드(U) : 검은색, Right-Right 인 경우

① : 노드 삽입 시, 부모 노드(P)는 빨간색, 삼촌 노드(U)는 검정색인 경우, 또한 Right-Right인 경우.

② : 조부모 노드(G)를 기준으로 Left-Rotation을 수행한다.

③ : 기존의 부모 노드(P)를 검정색으로, 조부모 노드(G)를 빨간색으로 변경한다.

5.4) 조부모 노드의 오른쪽 자식이 부모 노드, 부모 노드의 왼쪽 자식이 삽입 노드인 경우(Right-Left)

부모 노드(P) : 빨간색, 삼촌 노드(U) : 검은색, Right-Left 인 경우

① : 노드 삽입 시, 부모 노드(P)는 빨간색, 삼촌 노드(U)는 검정색인 경우, 또한 Right-Left인 경우.

② : 부모 노드(P)를 기준으로 Right-Rotation을 수행한다.

③ : 조부모 노드(G)을 기준으로 Left-Rotation을 수행한다.

④ : 삽입 노드(N)을 검정색으로, 조부모 노드(G)를 빨간색으로 변경한다.

레드-블랙 트리의 삭제 절차

레드-블랙 트리의 삭제 절차는 조금 더 복잡하다. 기본적으로 다음 세 단계를 거쳐 진행하게 된다.

①Exchange -> ②Rebalancing -> ③Delete

다음은 각 단계에 대한 설명이다.

1) Exchange Stage

삭제할 노드의 위치로 새로 들어올 노드를 선정하여 서로 교체하는 단계이다.

일반적으로 삭제할 노드의 위치로 들어오는 노드는 자식 트리 내에서 삭제할 노드의 키값과 가장 가까운 키를 가진 노드를 선택한다.

즉, "좌측 자식 트리에서 가장 오른쪽에 위치한 노드" 또는 "우측 자식 트리에서 가장 왼쪽에 위치한 노드"중 하나를 선택하여 교체한다.

단, 레드-블랙 트리에서는 트리의 위치를 교체하더라도 색상은 교체되는 노드의 색을 그대로 따른다. 즉, 색상은 교체되지 않는다.

또한, 교체는 자식 노드가 없을 때까지 재귀적으로 수행된다. 즉, 삭제할 노드가 리프노드가 될 때까지 재귀적으로 수행된다.

아래의 그림은 Exchange Stage의 한 예이다.

키 값이 "50"인 노드를 삭제하려는 경우

① : 삭제하려는 노드가 "50"일 때, 자식 노드가 있는 경우 교체할 노드를 탐색한다.

② : 교체 가능한 노드는 "45", "65"이며, 그 중 "45"를 선택하여 위치를 교체한다.(Color는 교체되는 위치의 색을 따른다)

③ : 위치 변경 후, 다시 확인하여 자식 노드가 있는 경우 다시 교체할 노드를 탐색한다.

④ : 교체 가능한 노드는 "42"이며, 위치를 교체한다. (Color는 교체되는 위치의 색을 따른다)

⑤ : 위치 변경 후, 다시 확인하여 자식 노드가 없는 경우 Exchange Stage를 마친다.

※Exchange 단계 이후, 삭제 노드는 더 이상 자식이 없다.

2) Rebalancing Stage

삭제할 노드의 주변 상황에 따라 트리를 변경하여 균형을 맞추는 단계이다.

기본적인 원리는, 삭제할 노드가 사라지더라도 기존의 조건에 맞도록 트리를 변형시키는 것이다.

여기서는 기준 노드라는 개념이 포함되며, 삭제 절차 이후에 기준 노드로부터 리프 노드까지의 BLACK NODE 수가 1 감소함을 의미한다.

Rebalancing 연산은 기준 노드를 중심으로 처리된다.

삭제할 노드가 검은색인 경우 기준 노드는 삭제할 노드가 되며, 빨간색인 경우 기준 노드가 없으므로 단계를 마친다.

즉, 삭제할 노드가 검은색인 경우에만 삭제 노드를 기준 노드로 삼고 Rebalancing Stage를 수행하게 된다.

Rebalancing 연산은 조건에 따라 다음과 같은 절차를 따른다.

(1) 기준 노드의 형제 노드(S)가 빨간색인 경우

형제 노드(S) : 빨간색 인 경우

① : 형제 노드(S)를 검은색, 부모 노드(P)를 빨간색으로 칠한다.

② : 부모 노드(P)를 기준으로 삭제 노드 방향으로 회전한다.

③ : 아직 균형이 맞지 않으므로 다시 삭제 노드를 기준 노드로 삼고 Rebalancing 연산을 재귀호출한다.

④ : Rebalancing Stage를 끝마친다.

(2) 기준 노드의 형제 노드가 검은색인 경우

(2.1) 형제 노드의 자식 노드 중 빨간색 노드가 있는 경우

형제 노드(S) : 검은색 인 경우

자식노드(Ci, Co) 중 하나라도 빨간색 이 존재하는 경우

① : 만일 형제 노드(S)의 자식 노드 중 내측 자식(Ci) 만이 빨간색인 경우 형제 노드의 트리 구조를 변형한다.

변형하는 이유는 외측 자식(Co)가 빨간색일 경우로 통일하여 처리하는 것이 수월하기 때문이다.

=> 이제 형제 노드(S)의 외측 자식(Co)은 빨간색이며, 내측 자식(Ci)은 빨간색, 검은색 모두 가능하다.

② : 형제 노드(S)는 부모 노드(P) 색으로 변경하고, 부모 노드(P)와 형제 노드(S)의 외측 자식 노드(Co)를 검은색으로 변경한다.

③ : 부모 노드(P)를 기준으로 삭제 노드 방향으로 회전한다.

④ : Rebalancing Stage를 끝마친다.

(2.2) 부모 노드가 빨간색인 경우, 형제 노드의 자식 노드가 모두 검은색인 경우

형제 노드(S) : 검은색 인 경우

부모 노드(P) : 빨간색, 모든 자식노드(Ci, Co) : 검은색 인 경우

① : 형제 노드(S)를 빨간색으로, 부모 노드(P)를 검정색으로 변경

② : Rebalancing Stage를 끝마친다.

(2.3) 부모 노드가 검은색인 경우, 형제 노드의 자식 노드가 모두 검은색인 경우

형제 노드(S) : 검은색 인 경우

부모 노드(P) : 검은색, 모든 자식노드(Ci, Co) : 검은색 인 경우

① : 형제 노드(S)를 빨간색으로 변경한다.
② : 부모 노드(P) 입장에서는 균형이 맞지만, 조부모 노드 입장에서는 균형이 맞지 않는다.
따라서 부모 노드(P)를 기준노드로 삼고 Rebalancing 연산을 재귀호출한다.
③ : Rebalancing Stage를 끝마친다.

3) Delete : 노드 삭제

삭제할 노드를 삭제하는 단계이다. 앞의 두 단계를 처리한 이후에는 삭제하더라도 레드-블랙 트리의 조건을 만족하게 된다.