[Data Structure] Tree(4) - Red-Black Tree

"Red Black Tree"(RB Tree)란 이진 검색 트리의 일종으로 자가 균형 이진 검색 트리(Self-Balancing BST)이다.

 

BST의 경우 평균적으로 $O(logN)$에 동작하지만, 최악의 경우 $O(N)$이 소요된다. 최악의 경우는 균형이 무너져 편향트리가 되었을 때 발생한다. 

따라서, 최악의 경우에도 $O(logN)$을 보장하는 자가 균형 이진 검색트리인 AVL, Red-Black Tree를 사용한다. 

특징 

"Red Black Tree"는 다음과 같은 규칙을 만족하는 BST이다.

#1: 모든 노드는 빨간색 혹은 검은색이다. 

#2: 루트노드는 검은색이다.

#3: 리프(NIL)노드는 검은색이다. 

#4: 빨간색 노드의 자식은 검은색이다.  (즉, 2 연속으로 빨간색이 나올 수 없다.)

#5: 어떤 노드에서 리프(NIL) 노드까지 가는 모든 경로상의 검은색의 수는 같다. (자신이 검은색인 경우 카운트에서 제외한다.)

 

RB 트리에서 모든 리프노드는 NIL노드로 아무 데이터도 가지고 있지 않는 더미 노드이다. 하지만, 형제노드 혹은 자식 노드로써의 역할은 할 수 있다. 이러한 특성은 이후에 삽입, 삭제 연산에서 중요하게 사용된다.

또한 #5 규칙에서의 어떤 노드 X 에서 자기 자신을 제외한 리프노드까지 가는 경로 상의 검은색 노드의 수를 "노드 X의 Black Height"라 부른다.

 

RB 트리는 모든 연산은 BST와 동일하게 수행한다. 하지만, 삽입, 삭제 연산 후 5가지 조건 중 특정 조건을 어기게 되며, RB 트리는 조건을 만족하기 위해 특정 연산을 수행하게 된다. 

주로 연산과정에서 #4, #5 번 조건을 위반하게 되며, 이를 만족하도록 변경하는 과정에서 트리는 균형을 이루게 된다.

 

5가지 조건들은 어떻게 균형을 이루게 하는가? 

#4번 조건에 의해 모든 빨간 노드는 2연속 나올 수 없지만, 검은색 노드는 연속적으로 등장할 수 있다. 

하지만, #5번 조건에 의해 리프노드까지 Black Height는 동일해야 한다. 

 

이를 고려하여 가장 Worst Case를 떠올려 본다면, 좌우 서브트리의 높이차가 최대인 경우는 다음과 같다. 

• 검은색 노드만 존재하는 서브트리 (높이가 최소인 경우)
• 검은색과 빨간색이 번갈아 등장하는 서브트리 (높이가 최대인 경우)

이때, 둘의 높이 차이는 최악의 경우 2배 차이가 나게 되며, 이는 결과적으로는 $O(logN)$에 동작한다고 볼 수 있다. 

 

정확하게는 높이가 최대인 트리에서의 연산이 일어났다 가정하게 되면, 시간 복잡도는 $2logN$ 보다 작은 것은 자명하다. 

즉, 점근적 상한이므로 Big-O Notation으로 다음과 같이 표기할 수 있다. 

$O(2logN)$ 

이때, Big-O Notation에서 상수는 무시할 수 있으므로 $O(logN)$이다. 

 

즉, RB Tree는 평균만이 아닌 최악의 상황에서도 시간 복잡도 $O(logN)$을 만족한다.

 

 

삽입

RB Tree에서 삽입 연산은 BST와 동일하게 수행되며, 

삽입 시 빨간색 노드로 삽입된다. 

빨간색 노드로 삽입해야 #5를 위반하지 않는다. 
#5: 어떤 노드에서 모든 리프(NIL) 노드까지의 Black Height는 동일하다.

 

새로운 노드가 검은색 노드의 자식으로 삽입되면 괜찮지만, 빨간색의 자식으로 삽입되게 되면 #4 조건을 위반하게 된다. 

#4: 빨간색 노드의 자식은 검은색이다.  (즉, 2연속으로 빨간색이 나올 수 없다.)

 

이때 RB Tree는 해결하기 위해 2가지 방법을 사용한다. 

• Restructing 
• Recoloring

우선, 가장 간단한 방법은 빨간색 노드 한개를 반대쪽으로 넘기는 것이며, AVL Tree 포스팅에서 살펴보았듯이 이는 Rotation으로 해결이 가능하다. 이를 "Restructing"이라 부른다.

 

하지만, 반대편 노드에서도 #4를 위반하게 되는 경우 Restructing이 아닌 "Recoloring"작업이 수행된다. 

 

즉, 일반화하자면 다음과 같다. 

• Restructing: 삼촌노드가 검은색인 경우 
• Recoloring: 삼촌노드가 빨간색인 경우

이때 삼촌 노드는 NIL노드도 포함된다. 

 

Restructing 

우선, 다음과 같은 상황을 살펴보자. 

해당 상황에서 새로운 노드(N)만 검은색으로 바꾸게 되면 #5 규칙을 위반하게 될 것이다. 

 

따라서 빨간색 노드 한개를 삼촌(U)쪽으로 넘겨주어야 하는데, 

해당 상황은 이전 AVLTree 포스팅에서 진행했던 LL Case와 동일하다. 

 

이렇게 RB Tree의 Restructing은 AVLTree와 마찬가지로 4가지 Case에 따라 다른 Rotation을 수행한다.

• LL Case
• RR Case
• LR Case
• RL Case

결론부터 말하자면, 삼촌(U)의 색깔을 빨간색으로 변경한 후, 새로운 노드(N)의 색깔을 검은색으로 변경한다. 

이후 상황에 맞는 Rotation만 수행하면 된다.

 

 

LL Case, RR Case

이전 AVLTree의 LL Case에서 그랬듯, Right Rotation을 다음과 같이 진행한다. 

 

부모(P)와 조부모(G) 색깔을 변경해주면, #4, #5를 만족하게 된다. 

 

마찬가지로 RR Case의 경우 Left Rotation만 수행해주면 된다.

 

즉, 이를 일반화해보자면 다음과 같다. 

(그림상에선 이해의 편의를 위해 Rotation은 우선으로 수행했다)

• 조부모 노드(G)와 부모 노드(P)의 색상을 서로 변경한다. 
• Right / Left Rotation 작업을 수행한다.

 

LR Case, RL Case

이역시 AVL Tree와 동일하다. Left Rotation을 통해 LL Case로 만들어 준 후에,

해당 트리에서 조부모 노드(G)와 새로운 노드(N)의 색상을 변경해준 후, Right Rotation 작업을 진행한다.

Rotation 작업 이후, 이전의 새로운 노드(N)가 이전의 부모 노드(P)의 부모가 된다. 
따라서, LL Case로 만들어 준 이후, 부모 노드와 조부모 노드의 색상을 변경하는 것은 동일하다. 
다만, 이를 Rotation 작업 이전 관점으로 본다면 새로운 노드와 조부모 노드의 색상을 변경하는 것이 된다.

 

마찬가지로 RL Case역시 AVL Tree와 동일하게 Right Rotation과 Left Rotation을 수행하면 된다.

 

즉, 이를 일반화하면 다음과 같다.

• 새로운 노드(N)와 조부모 노드(G)의 색상을 변경해준다. 
• Left Rotation을 진행한다. (RL Case의 경우 Right Rotation)
• Right Rotation을 진행한다. (RL Case의 경우 Left Rotation)

 

Recoloring 

삼촌 노드(U)가 검은색인 경우라면, 빨간색 노드를 Rotation을 통해 삼촌노드(U) 쪽으로 넘기는 "Restructing"을 통해 해결이 가능했다. 

 

하지만, 다음과 같이 삼촌 노드(U)도 빨간색인 경우라면 "Restructing"이 아닌 "Recoloring"을 진행한다. 

 

 

"Recoloring"은 다음과 같이 수행한다.

• 부모 노드(P)와 삼촌 노드(U)를 검은색으로 변경한다. 
• 이후 조부모 노드(G)를 빨간색 변경한다. 

다음과 같이 진행하면, Black Height는 같아지게 되어 #5번을 만족하게 될 것이다. 

 

하지만, "Recoloring"은 조부모 노드가(G)에서 #4를 위반할 수 있기 때문에, 재귀적으로 #4를 만족할 때까지 "Restructing" 혹은 "Recoloring"을 진행해야 한다.

 

 

삭제

삭제된 노드가 빨간색인 경우 문제되지 않지만, 검은색 노드를 삭제하게 되면 #5번과 선택적으로 #2번 조건을 위배할 수 있다. 

즉, 삭제의 경우, 검은색 노드를 삭제한 경우에만 문제가 발생할 수 있다.

#2: 루트노드는 검은색이다.
#5: 어떤 노드에서 모든 리프(NIL) 노드까지의 Black Height는 동일하다.

 

우선, 삭제되는 경우의 수는 이전 BinarySearchTree에서 살펴보았던대로 3가지 경우의 수로 나뉜다.

• 삭제하는 노드가 리프 노드인 경우
• 삭제하는 노드가 자식이 한개인 경우 
• 삭제하는 노드가 자식이 두개인 경우 

이때, 리프노드인 경우 혹은 자식이 한개인 경우라면, 삭제되는 노드를 기준으로 색깔을 생각하면 된다. 

하지만, 삭제하려는 노드가 자식이 두개인 경우라면, 다음과 같이 실제 삭제되는 노드는 "successor"가 된다. 

즉, 자식이 없거나 한개인 경우라면, 삭제된 노드의 색을 고려하지만, 

자식이 두개인 경우는 삭제되는 노드가 아닌 successor의 색을 고려해야 한다. 

 

정리하자면 다음과 같다. 

RB 트리의 삭제 연산에서 문제되는 상황은 다음과 같다. 

• 삭제하는 노드의 자식이 없거나, 한개인 경우 : 삭제되는 노드가 검은색
• 삭제하는 노드의 자식이 두개인 경우 : successor가 검은색

여기서의 자식의 수는 리프(NIL) 노드를 제외하고 생각한다. 

 

Extra-Black

검은색 노드 삭제로 문제가 발생할 때, #2를 위반하는 경우라면 단순 루트노드만 검은색으로 변경해주면 된다. 

 

하지만, #5를 위반하는 경우 상황에 따라 다른 정책을 적용해야 한다. 

이 경우, RB Tree는 다음 노드에 Extra Black을 부여한다. 

• 삭제하는 노드의 자식이 없거나, 한개인 경우 : 삭제되는 노드에 위치한 노드에 Extra Black을 부여
• 삭제하는 노드의 자식이 두개인 경우 : successor에 위치한 노드에 Extra Black을 부여

"Extra Black"은 검은색 노드와 동일하게 동작한다. 즉, Black Height를 1증가 시키는 역할을 한다. 

 

자식이 없거나 한개인 경우 

우선, 자식이 없거나 한개인 노드가 삭제되는 경우를 살펴보자. 

앞서 언급했지만, 자식의 수는 리프(NIL)노드를 제외하고 생각한다. 

 

자식이 없는 노드를 삭제하게 되면, NIL노드가 해당 자리를 대체하게 될 것이다. 

해당 경우에는 대체된 NIL노드에 Extra Black을 부여한다. 따라서, 삭제되었음에 Extra Black에 의해 Black Height는 2를 유지하게 되어 #5를 위반하지 않는다.

 

자식이 한개인 노드를 삭제한다면, 그 자식이 해당자리를 대체하게 될것이다. 

다음과 같은 경우엔 대체된 노드에 Extra Black을 부여한다. 

이때, 다음과 같이 검은색 노드에 Extra Black이 부여된 경우를 "Doubly Black"이라 부르고 

빨간색 노드에 Extra Black이 부여된 경우를 "Red-And-Black"이라 부른다. 

 

자식이 두개인 경우

자식이 2개가 삭제되는 경우는 successor가 삭제된 자리를 대체되게 된다. 

즉, 실제로 노드가 사라지는 위치는 successor의 위치가 된다. 

RB Tree는 이 삭제된 successor에 위치한 노드에 Extra Black을 부여한다. 

 

이 역시 마찬가지로 successor의 자식노드에 따라 "Red-And-Black" 혹은 "Doubly Black"으로 된다. 

 

우선 다음과 같이 successor가 리프노드인 경우를 살펴보자.

삭제되는 노드가 빨간색이더라도, successor가 검은색이기에 #5를 위반하게 된다. 

자식이 2개인 노드가 삭제되는 경우라면, successor의 색깔을 고려해야 한다.

따라서, succesor가 위치했던 노드에 Extra Black을 부여하게 된다. 

 

다음과 같은 경우도 마찬가지로 삭제되는 successor의 색깔이 검은색이다. 하지만 이전의 케이스와는 다르게 successor에 한개의 자식이 존재한다. 

 

해당 경우에는 삭제되는 successor에 위치에 그의 자식이 위치하게 된다. 따라서, 해당 자식에 Extra Black을 부여한다. 

 

successor는 오른쪽 서브트리에서 가장 작은(왼쪽) 노드이거나, 왼쪽 서브트리에서 가장 큰(오른쪽)노드이다.
따라서, 자식이 2개인 경우는 절대로 존재할 수 없다. 

 

Red-And-Black 해결 

Red-And-Black은 단순하게 검은색 노드로 변경시켜주면 문제가 해결된다. 

이렇게 되면, RB 트리는 #4번과 #5을 위반했던 것이 만족하게 되면서, 삽입 연산이 종료된다. 

 

Doubly-Black 해결

Doubly-Black의 경우 총 4가지 케이스로 구분된다. 

이때 케이스는 Doubly-Black노드의 "형제노드"와 "그 형제의 자식노드"를 기준으로 분류된다.

• case 4: 오른쪽 형제가 검은색 & 형제의 오른쪽 자식이 빨간색인 경우
• case3: 오른쪽 형제가 검은색 & 형제의 왼쪽 자식이 빨간색, 오른쪽 자식이 검은색인 경우
• case2: 오른쪽 형제가 검은색 & 형제의 두 자식이 모드 검은색인 경우 
• case1: 형제가 빨간색인 경우 

 

해당 모든 케이스는 왼쪽 오른쪽이 바뀌어도 성립한다. 

 

 

case 4: 오른쪽 형제가 검은색이고, 형제의 오른쪽 자식이 빨간색인 경우 

우선, 오른쪽 형제가 검은색 & 형제의 오른쪽 자식이 빨간색인 경우부터 살펴보자.

 

Doubly Black 노드(B)의 형제 노드(C)는 검은색이고, 그 형제의 오른쪽 자식(E)는 빨간색이다. 

이때, A, D같은 경우는 검은색이던지 빨간색이던지 상관이 없다. 

 

이때 빨간색 노드(E)를 Doubly-Black노드(B) 측으로 넘기고 검은색으로 변경하게 되면 Extra Black을 해결하게 된다. 

이는 형제노드(C)를 빨간색으로 변경 후 Rotation 작업으로 해결이 가능하다. 

 

따라서, 형제노드(C)를 빨간색으로 변경을 한다. 이때, #5번을 만족하기 위해 두 자식에게 Extra Black을 부여한다. 

이때 형제노드의 오른쪽 자식노드(E)는 Red-And-Black이 되기에 검은색 노드로 변경한다. 

 

Left Rotation을 통해 Doubly Black 노드(B) 측으로 빨간색 노드를 넘겨주면 된다. 

넘겨주기 위해 우선적으로 부모 노드(A)와 형제 노드(C)의 색상을 바꿔주자.

 

이후, 부모노드(A)를 기준으로 형제노드(C)를 pivot으로 해 Left Rotation을 진행한다. 

 

 

Rotation 이후, A노드의 자식에 모두 Extra-Black이 있다. 이를 부모 쪽으로 옮겨도 #5번을 만족하게 된다. 

B와 D에서는 모두 Extra Black이 부여되어져 있다. 즉, 한개의 추가적인 Black Height가 필요하단 의미이다. 
따라서, 이를 부모쪽으로 합쳐도 Black Height에는 지장이 가지 않는다.

 

 

이때 A노드는 Red-And-Black이기 때문에, A노드를 검은색으로 바꾸면 삭제 과정이 종료된다. 

 

 

과정이 길었지만, 결과론적인 관점에선 다음과 같다. 

• 형제 노드(C)를 부모노드(A)의 색을 서로 swap한다. 
• 형제 노드의 오른쪽 자식노드(E)는 검은색으로 변경한다.
• 부모노드(A)는 검은색으로 변경한다. 
• 이후 부모노드(A)를 기준으로 Left Rotation을 진행한다.

이때, 오른쪽 왼쪽을 변경해도 성립한다.

즉, Doubly Black의 왼쪽 형제노드가 검은색이고 형제의 왼쪽 자식이 빨간색인 경우 동일하게 진행한 후, Rotation만 Right Rotation으로 진행하면 된다. 

 

case 3: 오른쪽 형제가 검은색 & 형제의 왼쪽 자식이 빨간색, 오른쪽 자식이 검은색인 경우 

 

우선, D를 E쪽으로 넘기게 되면 case 4"오른쪽 형제가 검은색이고, 형제의 오른쪽 자식이 빨간색인 경우"가 된다. 

이를 위해 C와 D의 색깔을 서로 변경해주자.

 

이후, C를 기준으로 D를 pivot으로 해 Right Rotation을 진행한다. 

이렇게 진행하게 되면 "case 4"가 된다.

이때부터는 위의 케이스대로 해결하면 된다.

정리하자면 다음과 같다. 

• 오른쪽 형제 노드(C)를 빨간색으로, 그의 왼쪽 자식노드(D)를 검은색으로 변경한다.
• 형제 노드(C)를 기준으로 Right Rotation을 진행한다. 
• case4 상태가 되므로, case4를 통해 해결한다.

 

case 2: 오른쪽 형제가 검은색 & 형제의 두 자식이 모드 검은색인 경우

 

이때, C를 빨간색 노드로 변경하고 Extra Black을 부여해도 #5번을 위반하지 않는다. 

 

 

자식의 Extra-Black 모두를 부모노드에 전달해도 RB Tree의 조건을 만족하기에, B와 C의 Extra Black을 A노드에 전달한다.

이후로는 부모가 Extra-Black을 처리하도록 위임한다. 

 

case1: 형제가 빨간색인 경우

 

해당 경우에는 Doubly Black 노드(B)의 형제 노드(C)를 검은색으로 만들어 앞선 상황 중 하나로 만들어 해결한다. 

 

이를 위해선, 부모노드(A)를 기준으로 Light Rotation을 진행한다.

이때, 회전 후에도 #4, #5번 속성을 만족시키기 위해서는 부모노드(A)에 위치할 노드의 색깔이 검은색이어야 한다. 

 

따라서, 부모노드(A)와 형제노드(C)의 색깔을 swap한 후, Light Rotation을 진행한다. 

이후, Double-Black 노드(B)의 형제 노드(D)가 검은색이 되었으므로 각 case2, 3, 4에 맞게 처리하면된다.

 

 

vs. AVL Tree

AVL 트리의 특징은 좌우 서브트리의 높이차가 최대 1이라는 점이다. 즉, AVL 트리의 불균형 조건이 더 깐깐하다고 생각하면 된다. 

반면, RB 트리의 경우 좌우 서브트리의 높이차가 최대 2배이다. 

 

불균형의 조건이 더 깐깐하다는 것은 Self-Balancing 작업이 더 빈번하게 일어난다는 것을 의미한다. 

 

이러한 불균형이 일어나는 연산은 삽입, 삭제 연산이기에 

삽입, 삭제가 빈번하게 일어난다면 RB 트리가 적절하고, 

조회가 빈번하게 일어난다면 AVL트리가 더 적절하다 볼 수 있다. 

 

마지막으로 AVL Tree의 경우 Balance Factor를 저장하기 위한 최소 32bit의 공간이 필요하다. (Integer는 32bit) 

RB Tree의 경우 빨간색인지 검은색인지의 여부를 1bit의 공간이 필요하기 때문에 메모리적인 이점이 있다. 

 

하지만, 현대 CPU는 Byte단위로 처리하기 때문에 Boolean이더라고 1bit가 아닌 8bit가 할당될 뿐더러, 메모리가 저렴해진 관계로 저정도의 메모리 차이는 고려대상이 아닐듯 하다. 

 

 

References

위키백과

• Red-black tree

https://www.youtube.com/watch?v=6drLl777k-E&t=822s