[자료구조] Red-Black tree란? / Red-Black tree의 원리 및 활용

Red-Black tree란?

 

Red-Black tree(R-B tree)는 AVL tree, Splay tree와 같은 Self-balanced Binary Search Tree입니다. 

Red-Black tree는 말그대로 모든 노드가 빨간색과 검정색으로 표현됩니다.

 

 

이러한 R-B tree는 균형을 유지하기 위해 아래 다섯가지 조건을 만족해야 합니다.

 

1. 모든 노드는 빨간색 혹은 검은색이어야 합니다.
2. 루트 노드는 검은색이다.

3. 모든 NIL은 검은색이다. (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 리프 노드)

4. 빨간색 노드의 자식은 반드시 검은색이다.
5. NIL에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다.

 

Red-Black tree의 원리

 

위의 5가지 조건이 어떻게 R-B tree의 균형을 유지시키는지 알아보겠습니다.

 

먼저, 조건 2와 3에서 루트 노드와 리프 노드는 모두 검은색으로 설정되어 있습니다. 또한 조건 4에서 빨간색 노드의 자식 노드는 반드시 검은색입니다. R-B tree에서 새로운 노드가 삽입될 때, 해당 노드의 첫 색깔은 항상 빨간색입니다. 검은색 노드의 자식 노드로 빨간색 노드가 들어오면 조건을 위배하지 않지만, 만약 빨간색 노드에 자식 노드가 생겨 또 빨간색 노드가 들어오게 된다면(Red-Red) 조건 4를 위배하게 됩니다. 따라서 이 경우 Restructing 혹은 Recoloring을 통해 균형을 유지합니다. 조건 5에서 NIL에서 루트 노드까지의 경로에서 검은색 노드의 수가 모두 같다고 했으므로 트리의 각 경로의 길이또한 비슷해지며 트리가 균형을 유지하게 됩니다.

 

그렇다면 노드 삽입 시 Recoloring과 Restructing은 어떻게 이루어질까요?

 

Recoloring에 대해 먼저 살펴보겠습니다.

삽입될 노드의 부모 노드가 빨간색이며, 동시에 삼촌 노드(부모 노드와 같은 부모(=할아버지)를 가진 다른 노드)가 빨간색일 경우 Recoloring이 발생합니다. Recoloring은 아래 일련의 과정을 따릅니다.

 

1. 부모 노드와 삼촌 노드를 검은색으로 변경하고, 할아버지 노드를 빨간색으로 변경합니다.

2. 그 후, 할아버지 노드를 기준으로 같은 연산을 재귀적으로 진행합니다.

3. 이러한 과정을 반복하여 루트까지 Red-Red 문제가 올라가게 되면, 루트 노드의 color를 검은색으로 바꾸어 Red-Red 문제를 해소하고 트리의 균형을 유지합니다.

 

Restructing은 삽입될 노드의 부모 노드가 빨간색이지만 삼촌 노드(부모 노드와 같은 부모를 가진 다른 노드)는 검은색일 경우 수행합니다. Restructing은 rotation과 recoloring을 동시에 수행하는데, 아래 두 케이스에 따라 방식이 다릅니다.

 

1. 삼촌 노드가 조부모 노드의 오른쪽 자식이고, 새로운 노드가 부모 노드의 왼쪽 자식인 경우

 

이 경우, 부모 노드와 조부모 노드에 대해 right-rotation을 진행한 뒤 부모 노드와 조부모 노드의 color를 바꿔주면 됩니다.

 

2. 삼촌 노드가 조부모 노드의 오른쪽 자식이고, 새로운 노드가 부모 노드의 오른쪽 자식인 경우

 

이 경우, 부모 노드와 새로운 노드에 대해 left-rotation을 진행한 뒤 1번 과정을 똑같이 진행하면 됩니다.

 

참고로 삼촌 노드가 조부모 노드의 왼쪽 자식일 경우에, left-right만 대칭적으로 바꿔서 똑같이 실행하면 됩니다.

해당 과정을 그림으로 나타내면 다음과 같습니다.

 

 

Red-Black Tree는 노드 삭제 시에도 문제가 발생할 수 있습니다.

 

Red 노드를 삭제하면 조건에 위배되는게 없지만, Black 노드를 삭제한다면 Red-Red 상황이 생겨 R-B tree의 조건을 위배합니다. 이 경우, 아래와 같이 해결할 수 있습니다. 참고로 아래에서 나오는 대체 노드는 삭제된 자리에 들어갈 노드로, 삭제된 노드의 오른쪽 subtree에서 가장 작은 값을 가지는 노드(=오른쪽 subtree의 가장 왼쪽 노드)가 될 것입니다.

 

   1. 삭제된 노드의 대체 노드가 빨간색인 경우

1. • 대체 노드를 검은색으로 변경합니다.
   • 대체 노드가 검은색이고, 대체 노드의 자식 노드가 빨간색인 경우, 대체 노드의 자식 노드를 검은색으로 변경합니다.
2. 삭제된 노드의 대체 노드가 루트 노드일 경우
   • 대체 노드가 루트 노드인 경우에는 트리의 높이가 1 감소하므로 균형이 유지됩니다.
   • 이 경우 대체 노드를 검은색으로 변경하여 트리의 색 조건을 유지합니다.
3. 삭제된 노드와 대체 노드가 검은색인 경우
   • 삭제된 노드와 대체 노드 모두 검은색인 경우 트리의 색상 조건에 위배될 수 있습니다.
   • 이를 해결하기 위해 Restructuring과 Recoloring 연산을 적용합니다.
   • 대체 노드의 형제 노드의 색상에 따라 경우를 나누어 처리합니다.
   •  3-1. 대체 노드의 형제 노드가 빨간색인 경우:
     • 대체 노드의 형제 노드를 검은색으로 변경하고, 부모 노드를 빨간색으로 변경합니다.
     • 대체 노드가 오른쪽 자식인 경우에는 왼쪽 회전을 수행합니다.
     • 이렇게 하면 대체 노드의 형제 노드가 검은색이 되고, 색상 속성을 만족시킵니다.
   •  3-2. 대체 노드의 형제 노드가 검은색이며, 형제 노드의 자식 노드들도 모두 검은색인 경우:
     • 형제 노드를 빨간색으로 변경하고, 문제를 삭제된 노드의 부모 노드로 이동합니다.
     • 이렇게 하면 부모 노드에서부터 시작하여 Rebalancing을 수행해야 합니다.
     • 이는 삭제 연산 시 Restructuring과 Recoloring을 적용하는 과정과 유사합니다.
   •  3-3. 대체 노드의 형제 노드가 검은색이며, 형제 노드의 오른쪽 자식은 빨간색이고, 왼쪽 자식은 검은색인 경우:
     • 형제 노드의 오른쪽 자식을 검은색으로 변경하고, 형제 노드를 빨간색으로 변경합니다.
     • 형제 노드를 기준으로 왼쪽 회전을 수행합니다.
     • 이렇게 하면 형제 노드의 왼쪽 자식이 검은색이 되고, 다음 단계로 넘어갑니다.
   •  3-4. 대체 노드의 형제 노드가 검은색이며, 형제 노드의 왼쪽 자식이 빨간색인 경우:
     • 형제 노드의 왼쪽 자식을 검은색으로 변경하고, 형제 노드의 색상을 부모 노드의 색상과 동일하게 변경합니다.
     • 부모 노드를 검은색으로 변경합니다.
     • 부모 노드를 기준으로 오른쪽 회전을 수행합니다.
     • 이렇게 하면 트리의 색상 속성이 유지되고, 재균형이 완료됩니다.

이를 통해 트리의 균형을 유지하고 Red-Black tree의 조건을 만족시킬 수 있습니다.

 

Red-Black tree의 활용

 

Self-balanced Binary Search Tree(자가 균형 이진 탐색 트리)의 종류로 AVL tree, Splay tree, B-tree 등이 있는데

그중에서도 Red-Black tree는 왜, 언제 사용해야 할까요?

우선, Red-Black Tree는 상대적으로 간단한 규칙을 가지며 구현이 직관적이어서, 다른 트리에 비해 유지보수가 더 쉽고 더 널리 사용될 수 있습니다.

또한 노드의 color 값을 저장하는 메모리 사용량이 1bit밖에 안되며, 트리의 균형을 다시 잡는 연산 과정이 O(1)에 끝나기에 성능면에서도 우수합니다. 이러한 장점으로 Red-Black tree는 아래와 같이 다양하게 활용됩니다.

 

- C++의 표준 라이브러리인 STL에서 Red-Black Tree를 기반으로 한 map, set 컨테이너를 제공합니다.

- Java8 이후로, 기존에 LinkedList로 Chainning기법을 사용한 TreeMap을 Red-Black Tree로 변경하여 시간복잡도를 O(n)에서 O(logn)으로 줄일 수 있었습니다.