레드 블랙 트리(Red-Black Tree)

Red-Black Tree란?

 

Red-Black 트리는 이진 탐색 트리(BST)의 한 종류입니다.

 

BST는 루트 노드의 값이 왼쪽 노드 보다는 크고 오른쪽 노드 보다는 작은 이진 트리입니다.

 

Red-Black트리와 BST와의 가장 큰 차이는 스스로 균형을 잡는 다는 점입니다.

 

BST의 경우 만약 값의 삽입이 2 - 3 - 5 - 7 과 같이 오름차순으로 삽입이 된다면

 

아래 그림과 같이 최악의 경우 O(n)의 탐색 시간복잡도를 지니게 됩니다.

 

Red-Black 트리는다음과 같은 문제를 해결하여 탐색 시 최악의 경우에도 O(logN)의 시간복잡도를 지닙니다.

 

 

 

---

Red-Black Tree의 속성

 

Red-Black 트리는 총 5가지의 속성을 지니고 있습니다. 하나씩 살펴보도록 하겠습니다.

 

 

1. 모든 노드는 red 혹은 black입니다.

 

2. 루트 노드는 black입니다.

 

3. 리프 노드는 nil 노드입니다. (노드의 자녀가 없을 경우 nil 노드로 표기, 모든 nil 노드는 black입니다.)  

출처 - 유튜브 쉬운코드

 

4. red의 자녀들은 black입니다. (red가 연속적으로 존재할 수 없다는 것을 의미합니다.)

 

5. 임의의 노드에서 리프노드(nil 노드) 까지 가는 경로들의 black 수는 같다. (자기 자신은 제외)

예시

이것이 무슨 말이냐면, 위 그림과 같은 Red-Black 트리의 루트 노드인 0002에서 리프노드(Null Leaf) 까지

가는 모든 경우 각각에서 거쳐가는 블랙 노드의 갯수는 2개로 일정한 것을 확인할 수 있습니다.

 

5번 속성에서 중요한 개념이 등장하는데 바로 black height라는 개념입니다.

이는 임의의 노드에서 리프노드 까지 내려가는 경로에서의 black의 수를 뜻합니다. (자기 자신은 카운트에 제외)

 

만약 5번 속성이 만족되지 안흔다면 black height는 각각의 경로마다 블랙의 수가 달라 성립되지 않는 개념이 될것입니다.

 

쉽게 예를 들자면, 위의 그림에서 0004의 black-height는 2입니다. 

 

모든 경우를 구해보자면,

0003 - Null Leaf (2개)

0003 - Nul Leaf (2개)

0006 - Null Leaf (2개)  <빨간색 노드인 005는 제외됩니다.>

0006 - Null Leaf(2개)  <빨간색 노드인 005는 제외됩니다.>

0006 - Null Leaf(2개)  <빨간색 노드인 007는 제외됩니다.>

0006 - Null Leaf(2개)  <빨간색 노드인 007는 제외됩니다.>

 

총 6가지의 경우의 수에서 거쳐가는 블랙 노드의 갯수는 2개로 동일한 것을 볼 수 있습니다. 따라서 0004의 black-height는 2가 되는 것입니다.

 

 

---

Red-Black Tree는 어떻게 균형을 유지하는가?

Red-Black Tree에 값을 삽입을 하게 되면, 4번과 5번 속성을 주로 위반하게 됩니다. 이를 해결하려고 구조를 바꾸다 보면 자연스럽게 균형을 이루게 됩니다. 

 

지금부터 RedBlack-Tree의 삽입에 대해 자세히 살펴보도록 하겠습니다.

 

 

 

---

삽입 과정

삽입 전 RB(Red-Black) 트리 속성을 만족한 상태라고 가정합니다.

또한 삽입 방식은 일반적인 BST 자료구조와 동일합니다 (루트노드는 왼쪽노드 보다 크고 오른쪽 노드 보다 작다)

 

삽입을 완료한 후에 RB트리 속성을 위반했는지 확인하고 위반했다면 이를 재조정합니다.

 

또한 삽입하는 노드의 색은 항상 Red입니다. 임의의 노드를 제일 처음에 넣게 되면 그림은 다음과 같습니다.

임의의 노드 30을 삽입한 예제

분명 삽입하는 노드의 색은 항상 Red라고 했는데 왜 Black으로 삽입이 되었을까요? 바로 2번 속성인 

 

루트노드는 항상 Black 노드여야 하는 조건을 만족시키기 위해서입니다. 따라서 Red로 삽입된 노드를 Black으로 바꿔 

삽입해줍니다.

 

이후에 20의 값을 지니는 노드를 삽입하게 되면 그림은 다음과 같습니다.

 

그런데 왜 새로 삽입하는 노드의 색은 Red 여야 할까요? 이는 5번 속성을 만족시키기 위해서입니다.

 

5번 속성은 "임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 수는 같다" 였습니다.

 

만약 노드 20이 Black으로 삽입되게 된다면 경로에 따른 black height는 다음과 같을 것입니다.

30 - 20 - nil(3개)

30 - 20 - nil(3개)

30 - nil (2개)

 

삽입하는 색깔은 black으로 하게 되면 다음과 같이

임의의 노드 30에서 자손 nil 노드들 까지 가는 경로의 black 수가 같지 않게 됩니다. 따라서 삽입하는 노드의 색깔은 루트노드를 제외하고는 Red여아 하는 것입니다.

 

 

위에 20 노드를 삽입한 것에 이어서 값인 10인 노드를 삽입한다고 가정해보겠습니다.

삽입하는 노드의 색은 Red여야 하고 RB트리 또한 BST 작동 원리로 동작하기 때문에 그림은 다음과 같을 것입니다.

하지만 위의 그림은 RB 속성 4번인 "red 노드의 자식 노드는 black 노드여야 한다" 를 어기고 있습니다. 이런 상황을 Double-Red라고 합니다.

 

RB 트리는 Double-Red를 2가지 방법으로 해결합니다.

 

 

1. Recoloring(색깔 재배치)

- 새로 삽입된 노드의 삼촌 노드(부모 노드와 형제인 노드) 가 Red인 경우 수행됩니다.

- 새로 삽입된 부모 노드와 삼촌 노드를 Black으로 하고 조부모 노드를 Red로 합니다.

- 조부모 노드가 루트 노드가 아니면 Dobule Red가 발생할 수 있습니다.

- 만약 Dobule-Red가 다시 발생하게 된다면 재귀적으로 해당 상황에 따라 Recoloring과 Rotation중 하나를 선택하여 문제를 해결합니다.

 

 

2. Rotation(회전)

- 새로 삽입된 노드의 삼촌 노드가 Black이거나 null 일 경우 수행됩니다.

- 새로 삽입된 노드, 부모 노드, 조부모 노드를 오름차순으로 정렬합니다.

- 중간에 위치한 노드를 부모노드로 하고 나머지 두 노드를 자식 노드로 만듭니다. (BST 동작원리)

- 부모 노드를 Black으로 하고 두 자식들을 Red로 만듭니다. (RB 동작원리)

 

 

다시 위의 그림으로 돌아와서 새로 삽입된 노드 10은 부모 노드의 형제 노드가 존재하지 않습니다.

따라서 Rotation으로 Doulbe-Red 문제를 해결 할 수 있습니다. 순서대로 수행하자면 다음과 같습니다.

 

 

 

1. 노드를 오름차순으로 정렬합니다 (10, 20, 30)

 

2. 중간에 위치한 노드를 부모 노드로 하고 나머지 두 노드를 자식 노드로 만듭니다.

 

3. 부모 노드를 Black으로 하고 두 자식들을 Red로 만듭니다.

 

 

위 그림은 루트 노드인 20은 왼쪽 노드인 10보다 크고 오른쪽 노드인 30 보다 작은 BST의 속성도 만족시킵니다.

또한 원래 20의 색깔인 Red가 Black이 되고 원래 30의 색깔은 Black이 Red가 되면서 RB의 4번 속성도 만족시키고 있습니다.

 

그런데 만약 위나 밑에 서브트리가 존재한다면, RB트리 속성에 영향을 끼치진 않을까요? 해당 작업만 해주면 될까요?

연쇄적으로 Rotatin 작업을 해야하는건 아닐까요?

위와 같은 예시가 있다고 가정해봅시다. 기존의 30, 20 노드 말고도 50, 60, 70과 같은 서브 트리가 존재합니다.

 

위의 상황에서 노드 10을 추가하게 된다면 다음과 같이 서브트리의 RB속성을 꺠지 않고 기존 노드들 간의

 

배치와 색깔만 바꿔주면 작업이 완료됩니다.

왜 Rotatin은 다른 서브 트리에 영향을 주지 않고 작업을 완료할 수 있는걸까요?

 

삼촌 노드(삽인하는 노드의 부모노드의 형제노드) 가 없다면 블랙 노드의 갯수에 변화가 없게 됩니다.

 

삽입되는 노드는 Red이고 부모노드 또한 Red이고 Double-Red가 발생하지 않아야 하니까 조부모 노드는 Black입니다.

 

이는 다시말하자면, Black을 부모로 두고 Red를 자식으로 2개 두면 해당 범위 내에서 블랙 노드의 갯수의 변화 없이

 

해결이 가능하다는 말이됩니다. 

 

RB의 5번 속성이 "임의의 노드에서 Leaf 노드까지 가는 Black 노드의 수는 같다" 라고 했습니다. Rotation은

 

블랙 노드의 갯수를 건드리지 않기 때문에 5번속성을 위반할 일이 없고, 이에 따라 서브트리의 RB 속성에 영향을 주지 

않습니다. 따라서 추가적으로 서브트리의 RB속성을 체크해줄 필요가 없습니다.

 

 

반면에 Recoloring 같은 경우는 어떨까요?

 

다음과 같은 경우 값이 10인 노드를 똑같이 삽입하게 된다면 부모노드20의 형제노드인 35가 존재하므로

Recoloring 작업이 수행되게 됩니다.

Rotation은 부모 노드의 형제노드가 없으므로 블랙 노드 1개에 레드 노드 2개를 배치하면 해결됬지만

 

Recoloring은 부모 노드의 형제노드가 존재하므로 블랙 노드 1개와 레드 노드 3개가 존재하게 됩니다.

 

따라서 다음과 같은 순서로 문제를 해결합니다.

 

1. 새로 삽입된 부모 노드와 삼촌 노드를(20과 35) Black으로 합니다.

2. 조부모 노드 (30)을 Red로 합니다.

해당 작업을 수행하게 되면 원래 1개였던 블랙노드의 갯수가 2개로 늘어나게 됩니다.

 

이는 위의 서브트리들이 연쇄적으로 영향을 받을 수 있음을 의미합니다.

 

따라서 Recoloring은 삽입된 노드의 부분에만 그치는게 아니라 Root노드 까지 연쇄적으로 발생할 수 있는 것입니다.

 

 

하지만 여기서 중요한 점은 Recoloring을 하던 Rotatin을 하던 삽입의 시간복잡도는 O(logN)이라는 것입니다.

 

Rotatin의 경우 단 한번의 연산으로 삽입이 완료되지만 삽입될 노드를 찾는데 걸리는 탐색시간이 O(logN)이 되어

 

O(logN) * 1 = O(logN)이 되고

 

Recoloring의 경우 삽입될 노드의 위치를 찾는 탐색 시간 O(logN)과 연쇄적으로 연산이 발생할 수 있으므로 트리의

높이만큼 O(logN) 수행되어

 

O(logN) * O(logN) = O(logN^2)이 됩니다. 이는 시간복잡도O(N) 보다 작으므로 결론적으로는 O(logN)의 시간복잡도를

지닌다고 할 수 있습니다.

 

정리하자면 Red-Black 트리의 삽입 시간복잡도는 O(logN)을 지니게 됩니다.

 

 

---

BST와 Red-Black 트리 간의 비교

BST의 경우 10, 20, 30, 40, 50 을 순서대로 입력하게 되면 다음과 같은 그림이 된다했습니다.

반면 Red-Black Tree의 경우 다음과 같은 순서로 진행됩니다.

 

먼저 10 노드를 삽입합니다. 루트 노드이기 때문에 색깔은 Black 입니다.

그리고 20 노드를 삽입합니다. 루트 노드가 아니면 삽입하는 색깔은 항상 Red입니다. 따라서 다음과 같이 됩니다.

그리고 30 노드를 삽입합니다.

Double-Red가 발생했으므로 삽입한 노드의 삼촌 노드가 있는지 파악합니다. 20 노드의 형제 노드는 없습니다.

따라서 Rotation으로 해당 문제를 처리합니다.

오름차순으로 정렬 뒤 중간값인 20을 부모 노드로 올려주고 

부모 노드를 Black으로 자식 노드 2개를 Red로 설정합니다.

 

 

이제 40 노드를 삽입합니다.

30을 삽입할 떄와 마찬가지로 Dobule-Red가 발생했으므로 삼촌 노드의 유무를 파악합니다.

30노드의 형제 노드인 10이 존재하므로 Recoloring으로 문제를 해결합니다.

 

삼촌 노드와 부모 노드를 Black으로 하고 조부모 노드인 20을 Red로 설정합니다.

2번 속성인 루트노드는 Black이어야 한다에 의해 20 노드 또한 Black이 됩니다.

 

 

이제 마지막으로 50 노드를 삽입해보겠습니다.

마찬가지로 Dobule-Red가 발생했습니다. 삽입한 노드의 부모노 40의 형제 노드가 있는지 파악합니다.

형제 노드가 없으므로 Rotation으로 문제를 해결합니다.

 

30 - 40 - 50을 오름차순으로 정렬하고 가운데 노드인 40을 부모노드로 위치시킵니다.

그리고 부모노드를 Black으로 자식 노드를 Red로 설정합니다.

최종적으로 모든 노드들을 삽입하게 되면 아래와 같은 모양이 되게 됩니다.

만약 50을 넘어서 무한으로 오름차순으로 삽입을 한다해도

Red-Black Tree의 속성인 루트 노드에서 리프 노드까지의 Black 노드의 갯수는 같다라는 조건에 의해

트리간의 높이 차이는 최대 2배까지만 나게 됩니다.

 

예를 들자면

 

가장 짧은 경우 - Black - Black - Black ....

가장 긴 경우 - Black - Red - Black - Red ....

즉 Black사이 마다 Red가 끼어들면 이것이 가장 긴 depth가 되는것이죠.

 

반면 BST의 경우에는 리프노드까지 가장 짧은 depth와 가장 긴 depth의 차이가 무한으로 커질 수 있습니다.

 

Red-Black Tree의 이러한 속성 덕분에 O(n)보다 작은 O(logN) 트리의 높이에 해당하는 시간 복잡도 안에 탐색을 

수행할 수 있는 것입니다.

 

 

---

이상으로 Red-Black Tree에 대해서 알아봤습니다.

 

긴 글 읽어주셔서 감사합니다!

 

 

참고자료

https://www.youtube.com/watch?v=2MdsebfJOyM 

https://zeddios.tistory.com/237

알고리즘 ) Red-Black Tree

https://hongcoding.tistory.com/178

[자료구조] 레드 블랙 트리