레드 블랙 트리 - 삭제

김민호·2025년 10월 17일

🏁 전체적인 흐름: "일단 지우고, 나중에 고친다!"

레드-블랙 트리의 삭제는 복잡해 보이지만, 핵심 전략은 아주 간단합니다.

먼저 일반적인 이진 탐색 트리(BST)의 방식으로 노드를 삭제한다.

삭제로 인해 레드-블랙 트리의 속성이 깨졌는지 확인한다.

속성이 위반되었다면, 회전(Rotation)과 색상 변경(Recoloring)으로 재조정(Fix-up)한다.

모든 속성을 다시 만족하는 유효한 레드-블랙 트리로 만든다.

결국 "BST처럼 일단 지우고, RBT 규칙에 맞게 사후 처리한다"가 전부입니다. 여기서 가장 중요한 첫 단추는 바로 '어떤 색의 노드가 실제로 삭제되었는가?'를 파악하는 것입니다.

🔑 핵심 분기점: '삭제되는 색'은 무엇인가?

삭제 후 재조정이 필요한지 아닌지를 결정하는 유일한 기준은 '실제로 트리에서 제거되는 노드의 색' 입니다. 이 '삭제되는 색'을 판별하는 기준은 삭제할 노드의 자식 수에 따라 나뉩니다.

1. 삭제할 노드의 자식이 0개 또는 1개일 때

이 경우는 간단합니다. 삭제되는 색 = 삭제되는 노드 본인의 색입니다.

			 35(B)
		 /           \
	   20(R)           50(R)
	  /    \         /      \
	10(B)  30(B)    40(B)    80(B)
           /         /
         25(R)     37(R)

// 25(R) 삭제 -> RED 삭제
// 80(B) 삭제 -> BLACK 삭제
// 40(B) 삭제 -> BLACK 삭제

2. 삭제할 노드의 자식이 2개일 때

BST 삭제 규칙에 따라, 삭제할 노드의 직후 원소(In-order Successor)를 찾아 값을 복사한 뒤, 그 Successor 노드를 대신 삭제합니다. 따라서 이 경우 삭제되는 색 = Successor 노드의 색이 됩니다.

             35(B)
		 /           \
	   20(R)           50(R)
	  /    \         /      \
	10(B)  30(B)    40(B)    80(B)
           /         /
         25(R)     37(R)

// 20(R) 삭제 -> Successor는 25(R) -> RED 삭제
// (20번 노드의 '값'만 25로 바뀌고, 실제로는 25(R) 노드가 제거됨)

// 35(B) 삭제 -> Successor는 37(R) -> RED 삭제
// 50(R) 삭제 -> Successor는 80(B) -> BLACK 삭제

✅ 쉬운 길: RED가 삭제될 때

만약 '삭제되는 색'이 RED라면, 우리는 운이 좋은 겁니다! 아무런 추가 조치 없이 삭제 작업이 그대로 종료됩니다. RED 노드는 Black-Height에 영향을 주지 않기 때문에, 어떤 속성도 위반하지 않습니다.

#1 (색상): 당연히 만족.
#2 (루트): 루트가 아닌 RED를 지웠으니 불변.
#3 (NIL): NIL 노드는 불변.
#4 (연속 RED): RED를 제거했으므로 연속될 위험 없음.
#5 (Black-Height): 경로의 BLACK 노드 수에 영향을 주지 않음.

⚫️ 어려운 길: BLACK이 삭제될 때

문제는 지금부터입니다. 만약 '삭제되는 색'이 BLACK이라면, 상황이 복잡해집니다. BLACK 노드는 경로의 Black-Height를 지탱하는 기둥과 같아서, 이 기둥이 빠지면 여러 속성이 연쇄적으로 무너질 수 있습니다.

삭제되는 색이 BLACK이라면 #2(루트), #4(연속 RED), #5(Black-Height) 속성을 위반할 수 있습니다.

#2번을 위반 했을때 루트 노드를 black으로 바꾸면 된다.

특히 #5 속성(Black-Height)은 거의 항상 위반된다고 볼 수 있습니다. 삭제된 BLACK 노드를 지나던 경로는 다른 경로보다 Black-Height가 1만큼 낮아지기 때문이죠.

RBT 삭제의 핵심은 바로 이 Black-Height 불균형 문제를 어떻게 해결하느냐에 있습니다.

✨ 마법의 도구: Extra Black

개발자들은 이 문제를 해결하기 위해 재미있는 개념을 도입했습니다. 바로 'Extra Black' 입니다.

#5 속성을 다시 만족 시키기 위해서 삭제된 BLACK 노드의 자리를 대체한 노드에게 임시로 '추가적인 Black 속성'을 부여하여 Black-Height의 균형을 일단 맞추는 것입니다.

경로에서 black 수를 카운트 할 때 extra black은 하나의 black으로 카운트 된다.

삭제되는 색이 Black이고 #5 속성 위반일 때 Extra Black을 부여받은 노드는 두 가지 상태가 될 수 있습니다.

Red-and-Black: 원래 RED였던 노드가 Extra Black을 부여받은 상태.
Doubly Black: 원래 BLACK이었던 노드(NIL 노드 포함)가 Extra Black을 부여받은 상태.

이제 이 두 가지 특수 상태를 어떻게 정상으로 되돌리는지 알아보겠습니다.

1. Red-and-Black 해결하기 (가장 간단한 케이스)

Red-and-Black은 "나는 원래 RED지만, 없어진 부모의 BLACK 역할까지 임시로 맡고 있어!"라는 의미입니다. 해결책은 놀랍도록 간단합니다.

Red-and-Black 노드의 색을 그냥 BLACK으로 바꾸면 모든 문제가 해결됩니다.

예시: 30(B) 삭제
- 30(B)의 자리는 자식인 25(R)가 대체합니다.
- Black-Height가 1 부족하므로 25(R)에게 Extra Black을 부여하여 25(RB) 상태가 됩니다.
- 해결: 25(RB)의 색을 최종적으로 BLACK으로 변경합니다.
- 결과: 부족했던 Black-Height 1이 25의 새로운 BLACK 색으로 완벽하게 채워지며, 다른 어떤 속성도 위반하지 않습니다.

2. Doubly Black 해결하기 (진짜 RBT 삭제)

Doubly Black은 "나는 원래도 BLACK인데, 추가로 BLACK 역할까지 떠안아서 너무 무거워!"라는 의미입니다. 이 문제를 해결하는 것이 RBT 삭제의 하이라이트입니다.

Doubly Black 문제를 해결하는 전략은 "문제를 나 혼자 해결하지 않고 주변(형제 노드)의 도움을 받는다" 입니다.

Doubly Black 노드 x의 형제(sibling) 노드와 형제 노드 자식들의 색상에 따라 총 4가지의 복잡한 케이스로 나뉘며, 회전(Rotation)과 색상 변경(Recoloring)을 조합하여 Extra Black을 제거해 나갑니다. 이 과정은 다음과 같은 목표를 가집니다.