[자료구조] 레드 블랙 트리(Red-Black Tree) 정리 (2) - 삭제

muchan

∙2026년 4월 26일

자료구조

저번 정리에 이어서 써보겠습니다.
[자료구조] 레드-블랙 트리(Red-Black Tree)정리 (1) - 삽입
아래 유튜브 영상을 참고하여 작성했습니다.
레드 블랙 트리 삭제

개요

삭제 전 RB 트리 속성을 만족한 상태
삭제 방식은 일반적인 BST와 동일
삭제 후 RB 트리 속성 위반 여부 확인
RB 트리 속성을 위반 했다면 재조정
RB 트리 속성을 다시 만족

속성 위반 여부 확인이 중요한 포인트다 - 어떤 색이 삭제 되는지

속성 위반 여부 확인

삭제되는 색

삭제하려는 노드의 자녀가 없거나 하나라면 삭제되는 색은 삭제되는 노드의 색
삭제하려는 노드의 자녀가 둘이라면 삭제되는 색은 삭제되는 노드의 successor의 색

case 1: 삭제하려는 노드의 자녀가 없거나 하나라면 삭제되는 색 = 삭제되는 노드의 색
25 삭제:
25 삭제 -> red 삭제
80 삭제:
80 삭제 -> black 삭제
40 삭제:
40 삭제 -> black 삭제

case 2: 삭제하려는 노드의 자녀가 둘이라면 삭제되는 색 = 삭제되는 노드의 successor의 색
20 삭제:
20 삭제 -> successor 25가 20의 자리로 온다 -> red삭제(25의 색) -> 25가 20의 색 red를 갖게됨
35 삭제:
35 삭제 -> successor 37가 35의 자리로 온다 -> red 삭제(37의 색) -> 37가 35의 색 black을 갖게됨
50 삭제:
50 삭제 -> successor 80이 50의 자리로 온다 -> black 삭제(80의 색) -> 80이 50의 색 red를 갖게됨

successor란?
해당 노드보다 값이 큰 노드들 중 가장 작은 노드 (= 바로 다음으로 큰 값)

우선 레드 블랙 트리의 5가지 규칙을 다시 봐보자

모든 노드는 빨간색 혹은 검은색이다.
루트 노드는 검은색이다
모든 리프 노드는 검정색이다 (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타냄)
빨간색 노드의 자식은 검은색이다 = No Double Red(빨간색 노드가 연속으로 나올 수 없다)
모든 리프 노드에서 Black Depth는 같다 = 리프 노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다

삭제되는 색이 red일때

삭제되는 색이 red라면 위의 5가지 규칙 중 어떠한 것도 위반하지 않는다

삭제되는 색이 black일 때(이 부분이 중요)

삭제되는 색이 black이라면 #2, #4, #5 속성을 위반할 수 있다

위의 상황에서 40을 삭제했을 때

40의 자식은 1개이므로 40의 색인 검정색이 삭제되고 50과 37이 바로 연결된다
이러면 #4, #5번의 규칙이 깨지게 된다

위의 예제에서 35를 삭제했을 때

35의 자식도 1개이므로 black이 삭제되고 50이 그대로 올라오게 된다
이때는 #2의 규칙을 위반하게 된다

RB 트리 속성을 위반했다면 재조정

삭제되는 색이 red일 때는 아무일이 없으니 black일 때만 재조정을 해주면 된다

#2 규칙 위반 해결하기
간단하게 루트 노드를 black으로 바꾸면 된다

#5 규칙 위반 해결하기(메인 포인트)

삭제되는 색이 black일 때 특수한 상황을 제외하면 항상 #5 규칙을 위반하게 된다

삭제되는 색이 black이고 #5규칙 위반일 때는 extra black을 부여한다

#5 규칙을 다시 만족시키기 위해 삭제된 색의 위치를 대체한 노드에 extra black을 부여한다

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

위의 예제에서 10을 삭제해보자

10의 위치를 대체한 nil 노드에 extra black을 부여 -> #5 규칙 다시 만족

다음과 같이 black인 노드에 extra node가 붙게 되면 doubly black이라고 부르게 된다

위의 예제에서 30을 삭제하면

삭제된 색은 30의 black이고 25가 30의 위치를 대체했기에 25에 extra black을 부여한다
다음과 같이 red 노드에 extra black이 부여되면 red-and-black이라고 한다

위의 예제에서 50을 삭제하면

50은 자식이 두개이므로 50의 successor인 80이 오게 되고 80의 색인 black이 없어진다
이후 nil 노드에 extra node를 부여한다

정리)

삭제되는 색이 black이고 #5 규칙을 위반할 때

extra black을 부여받은 노드가 doubly black이 된다

extra black을 부여받은노드가 red-and-black이 된다

red-and-black 해결하기

간단하게 red-and-black을 black으로 바꾸면 해결된다

해당 예제에서 30을 삭제하면

25가 30의 위치를 대체하고 30의 black이 사라지므로 25의 red가 유지된다
이때 25는 red-and-black이 됐으니 25를 black으로 바꿔주면 종료된다

doubly black 해결하기 (이 문제가 중요!)

doubly black을 해결하기 위해 4가지 경우로 나누는데
그 기준은 doubly black의 형제의 색과 그 형제의 자녀들의 색으로 나뉜다

case 4: doubly black의 오른쪽 형제가 black & 그 형제의 오른쪽 자녀가 red 일때
그 red를 doubly black 위로 옮기고
옮긴 red로 extra black을 전달해서
red-and-black으로 만들면
red-and-black을 black으로 바꿔서 해결

다음 예제를 살펴보자 (여기서 B와 C는 red 아니면 black이고 둘이 같이 색일 필요도 없다)

doubly black의 extra black을 없애기 위해 E(red)를 A와 B 사이에 옮겨서
extra black을 red로 옮겨 red-and-black으로 바꾼 뒤 black으로 바꾸면 된다

이때 red를 왼쪽으로 보내기 위해서는 D의 위치가 red가 돼야한다

여기서 레드-블랙 트리의 속성을 먼저 살펴보자면
1번 그림에서 A의 자식 노드인 B,C가 둘다 red일 때
A를 red로, B와C를 black으로 바꿔도 #5규칙을 만족하면 그 반대 상황도 똑같이 적용 된다

위의 속성을 적용하면
E를 black으로 바꿔주고 D를 red로 바꿔준다
이때 C는 red인지 black인지 모르게 되는데
이때 extra black을 할당하여 #5의 규칙도 만족하며
위의 속성을 적용시킬 수 있다

이후 red가 왼쪽으로 넘어갈 수 있도록 왼쪽으로 회전 전에 B와 D의 색을 바꿔준다

회전을 하여 다음과 같은 상황을 만들어 준다
회전을 해도 #5 규칙을 만족하는데 이 증명은 유튜브 영상에서 일단 넘어갔다..

그러면 이제 A와 C에 있는 extra black을 합쳐서 B에 넘길 수 있게 된다
이때 B는 red-and-black이 되는데 그러면 B의 색을 black으로 바꿔 문제를 해결할 수 있다

지금까지 이 과정을 결과론적 관점에서 간략하게 줄여서 해결할 수 있다

doubly black의 오른쪽 형제는 부모의 색으로
오른쪽 형제의 오른쪽 자녀는 black으로
부모는 black을 바꾼 후

부모를 기준으로 왼쪽으로 회전하면 해결된다

doubly black의 오른쪽 형제가 black & 그 형제의 오른쪽 자녀가 red일때

오른쪽 형제는 부모의 색으로

오른쪽 형제의 오른쪽 자녀는 black으로

부모는 black으로 바꾼 후에

부모를 기준으로 왼쪽으로 회전

(오른쪽 왼쪽을 바꿔도 성립한다 - 루트 노드를 기준으로 좌우 대칭)

case 3: doubly black의 오른쪽 형제가 black & 그 형제의 왼쪽 자녀가 red & 그 형제의 오른쪽 자녀는 black일 때
doubly black의 형제의 오른쪽 자녀가 red가 되게 만들고
이후 case 4를 적용하여 해결

우선 C와 D의 색을 바꿔준 뒤 회전을 적용하면 된다

우선 C와 D의 색을 바꿔준 뒤

회전을 해주면 다음과 같은 모습이 된다

이후 case4 방식을 적용하여 해결한다

doubly black의 오른쪽 형제가 black & 그 형제의 왼쪽 자녀가 red & 그 형제의 오른쪽 자녀는 black 일 때

doubly black의 형제의 오른쪽 자녀를 red가 되게 만들고

이후 case 4를 적용하여 해결

(루트를 기준으로 오른쪽 왼쪽 대칭이여도 성립)

case 2: doubly black의 형제가 black & 그 형제의 두 자녀가 모두 black일 때
doubly black과 그 형제의 black을 모아서 부모에게 전달
이후 부모가 extra black을 해결하도록 위임한다

우선 아이디어는 A의 doubly black과 D의 black을 부모에 전달해
아까와 같은 전환 속성을 적용시켜 doubly black을 해결한다

black을 전달받은 B는 red-and-black 혹은 doubly black이 된다
이때 #5 규칙은 여전히 만족하고 있다
이때 또 두 가지 경우의 수가 생기는데
1. B가 red-and-black이 됐다면 black으로 바꿔준다
2. B가 doubly black이 됐다면
- B가 루트 노드라면 black으로 바꿔서 해결
- 아니라면 case 1,2,3,4 중에 하나로 해결