🔴⚫️ Red-Black Tree의 삭제 연산

설현아·2025년 4월 18일

👉 RB Tree의 속성

모든 노드는 red 혹은 black 의 색으로 구성된다.(1 bit)
root 노드는 black이다.
모든 NIL(leaf 노드)는 black이다.
red 노드는 연달아 나타날 수 없다.(red 노드의 자식 양쪽은 언제나 black)
임의의 노드로부터 NIL 노드에 도달하는 모든 경로의 black 수는 같다.(본인 제외)

👉 이에서 파생되는 규칙

5번 속성을 만족하고 있다면 두 자녀가 같은 색을 가질 때, 부모와 두 자녀의 색을 바꿔도 여전히 속성을 만족한다.
삽입/삭제 시 주로 4번, 5번 속성에 위배되며 이를 해결하면 균형이 유지된다.
삭제되는 노드의 색이 black이면 보통 5번 규칙이 위배된다.

삽입 연산에 이어, 삭제 연산에서도 속성과 규칙이 아주 중요하다!

위의 속성과 규칙에서 우리는 삭제 연산을 할 떄 어떤 부분을 신경써주어야 하는 지 알 수 있다.
1. 삭제되는 노드의 색이 black이면 재조정이 필요하다. 2. 삭제를 하고 속성을 위배하지 않았는지 확인해야 한다.

삭제도 잘 기억하면서 시작해보자!(삽입보다 더 많은 케이스를 고려해야하니, 정신 빠딱! 붙들자!)

Red-Black Tree 삭제

삭제하는 노드를 z라고 하자.

RB Tree에서 삭제 연산을 할 때는 두 가지 요소를 잘 확인해야 한다.
1. z 노드를 대체하는 노드가 어디에서 오는지?
2. 대체하는 노드(실제로 삭제되는 노드)의 색이 뭔지?

이게 중요한 이유는 z를 대체하는 노드는 매번 다르기 때문이다.

z가 하나 이하의 자식을 가지고 있을 때는 z를 삭제한다.
하지만 z가 두개의 자식을 가지고 있을 때는 z의 successor가 z를 대체한다. 이 경우, z의 successor의 색이 삭제된다.

이게 무슨 말인지 감이 안 잡힐테니, 그림으로 확인해보자. (fixup은 고려하기 전으로, 실제 삭제하는 노드를 대체하는 노드에 집중해보자!)

successor란? 오른쪽 서브트리에서 가장 작은 값

자, 이제 시작해보자.
우선 크게 두 가지 경우로 나뉜다. 삭제할 노드의 색이 red / black인 경우다.

삭제할 노드의 색이 red인 경우

이 경우는 당연하고 감사하게도
RB Tree 속성의 변동이 없다. 따라서 그냥 삭제해주면 된다.
(RB Tree는 임의의 노드에서 nil 노드까지의 black 노드 수가 같아야 한다. 이런 속성으로 red가 삭제될 때는 RB Tree 속성에 영향을 끼치지 않는다.)

삭제할 노드의 색이 black인 경우

▶︎ 삭제할 노드의 색이 black일 경우 Delete-fixup을 통해 균형을 유지한다.

우선 RB Tree에서 black이 삭제될 때는 속성 5번을 위배하게 되므로,
대체된 노드에 extra black을 부여하고 이를 적절하게 해결하면서 균형을 유지할 수 있다.
※ extra black은 삭제된 노드의 자식(자식이 없을 경우 NIL)에 부여하거나, 대체된 노드에 부여하게 된다.

extra black을 부여받으면 아래 두 가지로 귀결된다.(우리는 노드의 색을 두 개로 한정하기 때문이다!)

이 두 가지를 잘 다루어 해결해주면 된다.
이 과정을 Delete-fixup 이라고 하고, 아래에서 모든 case를 다뤄보자.