[CS] RB트리(Red-black tree)의 개념과 규칙, 파생 개념

RB트리(Red-Black tree)

RB트리의 개념

RB트리(Red-Black Tree)는 이진 탐색 트리(BST)의 한 종류로, 스스로 균형을 유지하는(Self-balancing) 특성을 지닌 자료구조입니다. 일반적인 BST는 삽입이나 삭제가 한쪽으로만 치우치는 경우, 트리의 높이가 불균형해지며 최악의 경우 시간 복잡도가 O(N)까지 떨어질 수 있는데요. RB트리는 이러한 단점을 균형 유지 규칙을 통해 보완하며, 삽입과 삭제 시에도 시간 복잡도 O(log N)을 보장합니다.

이 트리의 이름처럼, 모든 노드는 Red 또는 Black 중 하나의 색상을 가지며, 이 색상을 기반으로 트리의 균형을 유지하는 규칙들이 정의되어 있습니다.

 

RB트리의 규칙

1. 모든 노드는 빨강(Red) 또는 검정(Black)이다.
2. 루트 노드는 항상 검정이다.
3. 모든 리프(NIL 노드, 즉 NULL 노드)는 검정이다.
4. 빨강 노드의 자식은 반드시 검정이다. (즉, 빨강 노드가 연속으로 나타날 수 없음)
5. 어떤 노드에서 리프 노드까지 가는 모든 경로에는 동일한 개수의 검정 노드가 존재한다.

 

RB트리의 파생 개념

NIL 노드

존재하지 않음을 의미하는 특별한 노드. 자녀가 없을 때 이를 NIL 노드로 표기하고, 이후 값이 있는 노드와 동등한 취급을 받는다. 곧 leaf 노드는 NIL노드로, 검정색이다. (2번 규칙)

 

Black-height (흑색 높이)

임의의 노드에서 리프 노드(NIL)까지 가는 경로에 포함된 검정 노드의 개수를 말합니다. 5번 규칙에 의해, 하나의 노드에서 출발하는 모든 경로는 동일한 Black Height를 가져야 하며, 이를 통해 트리의 균형이 보장됩니다.

 

Color Flip (색상 반전, 부모-두 자식 간 색상 바꾸기)

RB트리에서는 부모가 검정, 두 자식이 모두 빨강인 경우가 발생할 수 있습니다. 이때는 다음 삽입·회전 등의 과정에서 트리 규칙을 위반할 수 있으므로, 색상 반전을 통해 구조를 재정비합니다.

• 구체적으로는,
  • 검정 부모 노드를 빨강으로,
  • 두 자식 빨강 노드를 검정으로 바꾸는 연산입니다.

RB트리는 색상 반전 연산을 수행하더라도 5번 규칙(black-height 동일)을 여전히 만족하는 구조를 유지합니다. 이 연산은 주로 삽입 과정 중 삼촌 노드가 빨강일 때 발생하며, 트리의 균형을 회전 없이 잠정적으로 안정화시키는 데 효과적입니다.

 

특히, 색상 반전은 4번 규칙(빨강 노드의 자식은 검정이어야 함) 위반을 방지하면서도, 트리 전체의 black-height가 바뀌지 않도록 구성되어 있어, 트리의 균형 유지와 규칙 보존이라는 두 가지 목적을 동시에 달성할 수 있습니다.