레드 블랙 트리(Red Black Tree)는 트리의 모든 노드가 빨강(Red) 또는 검정(Black) 중 하나로 색칠되는 자가 균형 이진 탐색 트리(Self-Balanced Binary Search Tree)입니다. 레드 블랙 트리에서 수행할 수 있는 연산은 크게 세 가지로 나뉩니다. 바로 탐색(Searching), 삽입(Insertion), 삭제(Deletion)입니다.
이번 글에서는 다음과 같은 레드 블랙 트리에 새로운 원소를 삽입하는 과정을 단계별로 살펴보겠습니다.
삽입의 기본 아이디어
레드 블랙 트리에 원소를 삽입하는 기본 아이디어는 매우 간단합니다. 일반적인 이진 탐색 트리에서처럼 루트 노드부터 시작해 노드의 값을 비교하며 적절한 위치를 찾아 삽입하면 됩니다. 다만, 레드 블랙 트리는 일반 이진 트리와 달리 삽입 후에도 트리의 균형을 유지해야 하기 때문에 추가적인 재조정 절차(색상 변경 및 회전)가 필요합니다.
레드 블랙 트리가 균형 잡힌 상태로 유지되려면 다음 네 가지 조건을 만족해야 합니다.
루트 노드는 반드시 검정이어야 합니다.
모든 노드는 빨강 또는 검정이어야 합니다.
노드가 빨강이라면, 그 자식 노드들은 반드시 검정이어야 합니다.
루트에서 말단(리프)까지의 모든 경로에는 동일한 개수의 검정 노드가 포함되어야 합니다.
새 노드를 삽입할 때 위 조건들이 깨지지 않도록, 아래의 삽입 절차를 따르게 됩니다.
레드 블랙 트리 삽입 단계
1단계: 먼저 트리가 비어 있는지 확인합니다. 트리가 비어 있다면 새 노드를 삽입하고 색을 검정으로 지정합니다. (루트 노드는 항상 검정이어야 하기 때문입니다.)
2단계: 트리가 비어 있지 않다면, 새 노드를 말단(리프) 위치에 삽입하고 색을 빨강으로 지정합니다.
3단계: 새 노드의 부모가 빨강이고, 부모의 형제 노드도 빨강이라면 부모·형제·조부모 노드의 색을 모두 뒤집습니다. (단, 조부모가 루트 노드라면 부모와 형제 노드의 색만 뒤집습니다.) 즉, 빨강을 검정으로 변경하여 규칙을 복원합니다.
4단계: 새 노드의 부모가 빨강이고, 부모의 형제 노드가 비어 있거나 NULL이라면 새 노드와 부모를 대상으로 회전(Rotation)을 수행합니다. (좌-좌 회전 또는 좌-우 회전)
회전의 종류와 적용 조건
회전에는 두 가지 유형이 있습니다. 좌-좌 회전(Left-Left Rotation)과 좌-우 회전(Left-Right Rotation)이며, 회전은 특정 조건에서만 적용됩니다.
새 노드의 부모가 빨강이고 형제 노드가 비어 있거나 NULL인 경우, 좌측 또는 우측 회전을 수행합니다.
좌-좌 회전에서는 부모와 조부모의 색을 뒤집고, 부모를 조부모 자리로 올린 뒤 조부모를 자식으로 내립니다.
알고리즘
위 내용을 의사 코드(Pseudocode)로 표현하면 다음과 같습니다.
RBTreeInsertion(root, key)
// 삽입되는 새 노드의 색은 빨강
color[key] ← Red
while(key≠root and color(p[key])=Red)
do if p[key]= left(p[p[key]])
Then y←right[p[p[key]]]
// 새 노드의 부모가 빨강이면(조부모가 루트가 아닌 경우) 색을 뒤집음
if color[y]← Red
then color(p[key])← Black
color(p[p[key]])← Red
key← p[p[key]]
else if key← right[p[key]]
then key← p[key]
// 새 노드의 부모가 빨강이고 형제가 NULL인 경우
LeftRotate(root,key)
color(p[key]) ← Black
color(p[p[key]]) ← Red
RotateRight(root,p[p[key]])
else 좌우 요소를 교환하여 균형을 맞춤
color(root)← Black