RB-Tree 구현하기 (C언어) - Part.5 삭제 이론 설명

이 전 포스팅에서 RB-Tree의 삽입에 대해 구현을 진행했다. 이제 RB-Tree의 마지막 관문 삭제 기능에 대해 본격적으로 구현에 들어가기 전에 이론 설명을 진행하겠다.

---

RB-Tree 노드 삭제

RB-Tree의 삭제는 일반 이진 탐색 트리(BST)처럼 노드를 제거하지만, Red-Black Tree의 5가지 속성을 유지하기 위한 추가적인 재조정(Fix-up)이 필요하다.

1. 기본 삭제 절차

Step 1: 일반 BST 삭제 수행

• 삭제하려는 노드 z가 자식이 0개 또는 1개면 그대로 삭제
• 자식이 2개인 경우, z의 후계자(successor) 노드 y를 찾아 z의 위치에 복사하고, 후계자 y를 삭제

Step 2: 삭제된 노드의 색 확인

• 삭제된 노드의 색이 Red인 경우 → 문제없음 (속성 위반 X)
• 삭제된 노드가 Black이면 → 속성 5 위반 가능 → delete_fixup() 필요

---

2. 왜 Black 노드 삭제는 문제가 되는가?

RB-Tree는 모든 리프까지의 경로에 같은 수의 Black 노드가 있어야 한다 (속성 5).
Black 노드가 사라지면, 경로마다 Black 개수가 달라질 수 있으므로 트리를 재조정해야 한다.

---

3. 삭제 후 재조정 (Delete Fix-Up)

기본 아이디어

• 삭제로 인해 Black 개수가 모자라는 노드를 x라고 하고,
• x는 "추가적인 Black"을 갖고 있다고 가정 (일종의 Double Black 상태)
• x의 형제(sibling)의 색과 자식의 색에 따라 4가지 경우로 나뉜다.

Case	조건	처리 방식	목표
1	형제 Red	색 바꾸고 부모 회전	Case 2~4로 전환
2	형제 Black, 자식 둘 다 Black	형제 Red, 부모에 Double Black 전달	재귀적 처리
3	형제 Black, 가까운 자식 Red	형제 중심 회전	Case 4로 유도
4	형제 Black, 먼 자식 Red	색 조정 + 부모 중심 회전	Double Black 제거

---

더블 블랙(Double Black)이란?

"더블 블랙"은 Red-Black Tree에서 Black 노드를 삭제했을 때, 그 자리 또는 그 자리를 대체한 노드가 'Black이 하나 더 부족하다'는 논리적 상태를 나타내는 개념이다."

왜 필요한가?

Red-Black Tree는 다음과 같은 규칙을 지켜야 한다:

속성 5: "어떤 노드에서 리프(NIL)까지 가는 모든 경로에는 같은 수의 Black 노드가 있어야 한다."

그런데 만약 Black 노드를 삭제해버리는 경우

• 그 경로에서는 Black 노드 하나가 사라진다 → 속성 5 위반
• 그래서 삭제된 자리에 "Black이 하나 부족함"이라는 표시로 Double Black을 부여하는 것

---

Double Black은 어떻게 쓰이는가?

우리가 구현하는 코드에서 Double Black이라는 상태는 사실상 없다. 즉 더블 블랙이라는 것을 노드에 메타데이터 속성으로 포함시키지 않는다는 것이다.

• Double Black은 Fix-Up 과정에서 점점 줄어들거나 이동하면서 제거됨
• 예를 들어,
  • 형제를 Red로 바꾸고 회전하거나,
  • 형제를 Red로 바꾸고 부모에 Double Black을 전이하거나,
  • 색상 조정과 회전을 통해 완전히 제거됨

즉 직접 속성을 관리하는 것이 아니라 결과론적? 방법에 따라 일반화된 구현 방법에 의해 더블 블랙을 처리하는 로직을 구현하여 조정을 한다.

더 자세한 내용은 직접 구현해 보며 알아보자