[CS] RB트리(Red-black tree)의 삽입과 회전

RB트리(Red-black tree)의 삽입과 회전

RB트리는 기본적으로 이진 탐색 트리(BST)와 동일한 방식으로 노드를 삽입합니다. 즉, 삽입할 값이 현재 노드보다 작으면 왼쪽 서브트리로, 크면 오른쪽 서브트리로 내려가며 적절한 위치를 찾아가는 것이죠.

 

다만 BST와는 다른 두 가지 중요한 차이가 있는데, 이는 다음과 같습니다.

1. 새로 삽입되는 노드는 항상 빨강 노드(Red)이다.
2. 삽입 이후, RB트리의 규칙을 하나라도 위반할 경우, 이를 해결할 때까지 재조정(회전 및 색상 교환 등) 이 반복된다.

 

RB 트리의 삽입

RB 트리에서는 앞서 말했듯이 기존 BST와 동일한 방식으로 Red 노드가 삽입됩니다. 이후 RB 트리의 모든 규칙을 만족하는지를 검사하게 되는데요. 만약 하나라도 규칙을 위반하게 되면, 트리는 이를 해결하기 위해 재조정(색상 반전 또는 회전)을 수행합니다.

 

이때 주로 재조정이 발생하는 원인은 다음과 같습니다.

• 4번 규칙: Red 노드의 자식은 반드시 Black이어야 한다.
• 5번 규칙: 어떤 노드에서 리프 노드까지 가는 모든 경로에는 동일한 개수의 Black 노드가 존재해야 한다.

RB 트리는 조상으로부터의 Black height를 유지하기 위해 삽입되는 노드를 항상 Red로 지정합니다. 따라서 재조정은 보통 Red 노드의 자식으로 또 다른 Red 노드가 삽입되는 상황에서 발생하게 되며, 이는 곧 4번 규칙(Red-Red 충돌)을 위반한 상황입니다. 이러한 재조정 상황은 크게 세 가지 케이스로 나눌 수 있습니다.

 

1. Red가 한쪽으로 쏠린 상태
   • 일자로 쏠린 경우 (Case 3)
   • 꺾이면서 쏠린 경우 (Case 2)
2. Red가 포화된 상태 (Case 1)

이 각각의 경우에 따라 회전 또는 색상 교환을 통해 트리의 균형이 복구됩니다.

 

 

RB 트리 삽입 시 재조정 유형

RB트리 삽입 과정은 보통 Case 3부터 거꾸로 설명되고는 하는데요. 이는 구조적인 충돌(일자 모양)을 먼저 해결하고, 그 전 단계들(Case 2와 Case1)을 점차 일반화하며 설명하는 것이 더 직관적이고 실제 구현 흐름과도 잘 맞기 때문입니다.

 

Case3: Red가 일자로 쏠린 상태

먼저 삼촌(부모의 형제)이 Black이고, 할아버지, 부모, 새 노드(자식)가 일자로 놓인 4번 규칙을 위반하는 상태를 Case3라 합니다. 이를 해결하기 위해서는 다음과 같은 과정을 거칩니다.

1. 할아버지와 부모의 색을 교환한다.
2. 할아버지를 축으로 기존 Red가 쏠린 방향의 반대쪽으로 회전시킨다.

Case3: Red 쏠림 상태(일자형)의 재조정 과정

 

Case2: Red가 꺾이면서 쏠린 상태

이어서 삼촌(부모의 형제)이 Black이고, 할아버지, 부모, 새 노드(자식)가 꺾인 상태로 놓인 4번 규칙을 위반하는 상태를 Case2라 합니다. 이를 해결하기 위해서는 먼저 꺾인 상태를 회전을 통해 일자로 놓인 상태로 만드는 과정, 즉 Case3로 만드는 과정을 거치게 되는데요. 그 뒤에는 Case3를 해결 방식을 적용하면 됩니다. 이를 정리하면 아래와 같습니다.

1. 부모를 축으로 꺾인 방향의 반대로 회전시킨다. (Case3로 만들기)
2. 할아버지와 부모의 색을 교환한다.
3. 할아버지를 축으로 기존 Red가 쏠린 방향의 반대쪽으로 회전시킨다.

 

Case2: Red 쏠림 상태(꺾임형)의 재조정 과정

 

Case1: Red가 포화된 상태

마지막으로 일자인 상태, 꺾인 상태 상관 없이 4번 규칙을 위반한 상태에서 삼촌까지 Red인 경우를 Case1이라 합니다. 바로 이 경우에 활용되는 파생 개념이 Color Flip(색상 반전)인데요. 할아버지와 두 자식(부모, 삼촌)의 색상을 서로 교환함으로써 해당 영역에 한해서 RB 트리 규칙을 만족하게끔 만들 수 있습니다.

 

다만 이렇게 재조정이 종료되는 건 아닌데요. 이제 할아버지가 새롭게 Red가 됐기 때문에, 이제 할아버지의 조상 영역에 대해 다시금 4번 규칙을 만족하는지 확인해야 합니다.

1. 할아버지와 두 자식(부모, 삼촌)의 색을 교환한다. (Color Flip)
2. 이후 할아버지와 그 조상에 대해 4번 규칙을 만족하는지 확인한다.
3. 4번 규칙을 만족한다면 재조정을 종료하고, 위반했다면 새로운 재조정에 들어간다.

Case1: Red 포화 상태의 재조정 과정

 

 

RB트리의 회전 쉽게 이해하기

RB트리의 균형을 맞추는 대표적인 방식 중 하나는 회전(Rotation)입니다. 이는 특정 노드를 축으로 삼아, 한쪽 서브트리는 계층이 올라가고, 다른 쪽 서브트리는 계층이 내려가는 방식으로 트리의 구조를 재조정하는 과정입니다.

 

회전은 단순히 할아버지, 부모, 자식 노드 세 개만 바꾸면 될 것 같지만, 실제로는 그렇지 않습니다. 이들 각각은 자신만의 서브트리를 가지고 있기 때문에, 회전 과정에서 이 서브트리들까지 함께 고려해야 하는데요. 결국 단순한 노드 교환이 아닌, 구조 전체를 보존하면서 일부 계층만을 조정하는 정교한 작업이 필요하게 됩니다.

 

그렇다면 도대체 어떤 노드와 어떤 서브트리들이, 어떻게 회전하는 걸까요?

 

핵심 개념: "축 노드는 항상 한 칸 내려간다"

예를 들어, 오른쪽 회전을 한다고 가정해 보겠습니다.

 

1. 먼저 회전의 중심(축)이 되는 노드는 한 계층 아래로 내려가고,
2. 그 왼쪽 자식 노드는 한 계층 위로 올라가며 새 부모 노드가 됩니다.
3. 이때 그 왼쪽 자식 노드가 가지고 있던 오른쪽 서브트리는 연결이 단절된 상태가 되는데, 이 서브트리는 자연스럽게 이진 탐색 트리(BST)의 정렬 성질을 유지하기 위해 기존 축 노드의 왼쪽 자식으로 옮겨 붙습니다.

회전 동작 요약 (오른쪽 회전 기준)

회전 대상	회전 결과
축 노드	오른쪽으로 한 계층 내려감
축의 오른쪽 자식과 그 서브트리들	함께 오른쪽으로 한 계층 내려감
축의 왼쪽 자식과 그 왼쪽 서브트리	오른쪽으로 한 계층 올라감 (새 부모)
축의 왼쪽 자식의 오른쪽 서브트리	축 노드의 새 왼쪽 자식이 됨

 

그리고 이를 그림으로 나타내면 다음과 같습니다.

RB트리의 우측 회전 (초록색 - 한 계층 상승 / 파란색 - 한 계층 하강 / 보라색 - 기존 루트의 왼쪽 자식이 됨)

마찬가지로 좌측 회전의 경우에도 축이 되는 노드는 한 계층 아래로 내려가고, 회전 방향 반대편 자식은 한 계층 위로 올라가며 부모 자리를 대신하는데요. 이때 역시 BST의 정렬 특성을 유지하기 위해, 연결이 단절된 서브트리도 알맞은 위치로 재배치됩니다.

 

결국 RB트리에서의 회전은 단순히 노드의 위치만 바꾸는 것이 아니라, BST의 정렬 규칙을 지키면서 전체 구조의 계층을 재조정하는 작업입니다. 즉, 트리의 모양을 정리하고 균형을 맞추는 정교한 재배치 과정인 것이죠.