RED_BLACK_Tree 삭제

RB트리의 조건

번호	조건 설명
1	모든 노드는 레드 또는 블랙
2	루트 노드는 블랙
3	리프 노드(NIL)는 블랙
4	레드 노드의 자식은 모두 블랙 (연속 레드는 없음)
5	어떤 노드에서 리프까지의 모든 경로에 블랙 노드 수는 동일

삭제 Overview

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

2. 삭제 후 RB트리 속성 위반 여부 확인

RB트리에서 노드를 삭제할 때 어떤 색이 삭제되는지가 속성 위반 여부를 확인할 때 매우 중요

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

삭제하려는 노드의 자녀가 둘이라면
삭제되는 색 = 삭제되는 노드의 successor의 색 (successor: x보다 "크면서 가장 작은" 노드)
20 삭제 -> successor 25 -> red 삭제
35 삭제 -> successor 37 -> red 삭제
50 삭제 -> successor 80 -> black 삭제

1. 삭제되는 색이 red라면 어떠한 속성도 위반하지 않는다.

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

35 삭제

35의 black이 삭제, 2번을 위반한다

3. RB트리 속성을 위반했다면 재조정(black 삭제 시)

2번 속성 위반 해결하기

루트 노드를 black으로 바꾼다.
35 삭제

• 35는 자녀가 하나
• 35의 black이 삭제됨
• 50이 루트 노드가 되고 2번 속성 위반
• 50을 black으로 바꿔서 해결
  이러한 특수한 상황을 제회하면 5번 속성을 항상 위반하게 됨

5번 속성이 위반일 때 extra black 부여

5번 속성을 다시 만족시키기 위해 삭제된 색의 위치를 대체한 노드에 extra black을 부여
(extra black: 경로에서 black수를 카운트 할때 extra black은 하나의 black으로 카운트)

10 삭제

10은 자녀가 없음
삭제되는 색은 10의 black

black이 삭제됐으므로 5번 속성 위반했고 extra black을 부여해서 5번 속성을 다시 만족 시켜야함
어디에 extra black을 부여해야하나?
삭제된 색의 위치를 대체한 노드!
삭제된 색은 10의 black이므로 10의 위치를 대체한 노드인 nil 노드에 extra black을 부여

5번 속성 다시 만족

30삭제

30은 자녀가 하나라서 삭제되는 색은 30의 black

5번 속성 위반이므로 extra black 부여 삭제된 색은 30의 black이었으므로 30의 위치를 대체한 노드인 25에 extra black 부여!

30의 위치를 대체한 노드인 25에 extra black 부여 -> 5번 속성 다시 만족

50삭제

50은 자녀가 둘이라서 삭제되는 색은 50의 successor인 80의 black

80의 위치를 대체한 nil노드에 extra black 부여 -> 5번 속성 만족

extra black 부여 결과

extra black을 부여받은 노드는
doubly black이 되거나
red-and-black이 된다

red-and-black 해결하기

red-and-black을 black으로 바꾸면 해결

30삭제

30은 자녀가 하나라서 삭제되는 색은 30의 black -> 5번 위반,
20과 25가 바로 연결되면서 4번 위반

삭제된 색은 30의 black이었고 30을 대체하는 25의 red에 extra black 부여

25는 red-end-black이 됐으니 25를 black으로 바꿔주면 종료

4, 5번을 동시에 해결, red-black 트리의 모든 속성을 만족

doubly black 해결하기

extra black을 부여했더니 doubly black 노드가 생겼다면 결국 extra black을 어떻게 없앨것인지가 관건
doubly black의 extra black을 없애는 방법은 총 네가지 case로 분류됨
doubly black의 형제의 색과 그 형제의 자녀들의 색을 기준으로 나뉨

CASE.4 (doubly blakc의 오른쪽 형제가 black & 그 형제의 오른쪽 자녀가 red일 때)

그 red를 doubly black 위로 옮기고 옮긴 red로 extra black을 전달해서 red-and-black으로 만들면 red-and-black을 black으로 바꿔서 해결

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

색을 바꾸면서도 5번 속성을 유지하기
RB트리가 5번 속성을 만족하고 있고 두 자녀가 같은 색을 가질 때 부모와 두 자녀의 색을 빠꿔줘도 5번 속성은 여전히 만족

red를 왼쪽으로 보내기 위해서는 D의 위치가 red가 돼야 하고 이를 위해 D의 black을 C와 E로 보내고 D를 red로 바꾼다

doubly black의 오른쪽 형제가 black & 그 형체의 오른쪽 자녀가 red일 때 여전히 5번 속성 만족

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

B를 기준으로 왼쪽으로 회전한다

회전 후에도 5번 속성을 만족한다

이전 모습에서도 5번을 만족함으로 회전 후에도 5번 속성 만족

A와 C의 extra black을 B로 올린다. 그렇게 해도 여전히 5번을 반족

B는 red-and-black이 됐기 때문에 B의 색을 black으로 바꿔서 extra black을 제거하면 문제 해결

지금까지의 과정을 결과론적 관점에서 보면 이 과정을 간략하게 줄여서 해결할 수 있다.(오른쪽 왼쪽을 바꿔도 성립)

• 오른쪽 형제는 부모의 색으로
• 오른쪽 형제의 오른쪽 자녀는 black으로,
• 부모는 black으로 바꾼 후에
• 부모를 기준으로 왼쪽으로 회전하면 해결
  
  
  

CASE.3 (doubly blakc의 오른쪽 형제가 black & 그 형제의 왼쪽 자녀가 red일 때 & 그 형제의 오른쪽 자녀는 black일 때)

doubly black 형제의 오른쪽 자녀가 red가 되게 만들어서 이후엔 case.4를 적용하여 해결

E 위치에 red가 오도록 만들기 위해 C와 D의 색을 바꾼 후에 D를 기준으로 오른쪽으로 회전하면 된다.


case.4의 해당하는 모습
C는 B의 색으로 B와 D는 black으로 바꾼 후 B를 기준으로 왼쪽으로 회전하면 해결

doubly black의 형제의 오른쪽 자녀를 red가 되게 만들어서 이후엔 case.4를 적용(오른쪽 왼쪽을 바꿔도 성립)

CASE.2 (doubly blakc의 형제가 black & 그 형제의 자녀가 모두 black일 때)

A와 A의 형제인 D의 black을 모아서 부모에게 전달하게 되면 A와 D에서 black을 모았기 때문에 A는 여전히 black이고 D는 red가 된다.

black을 전달받은 B는 red-and-black 혹은 doubly black이 된다.
5번 속성은 여전히 만족
B가 red-and-black이 됐다면 black으로 바꿔주면 상황은 종료되지만 B가 doubly black이 됐다면 B가 루트 노드라면 black로 바꿔서 해결, 아니라면 case1,2,3,4 중에 하나로 해결

CASE.1 (doubly black의 형제가 red일 때)

doubly black의 형제를 black으로 만든 후 case2,3,4 중에 하나로 해결
B를 기준으로 왼쪽으로 회전하면 doubly black A의 형제는 C가 되 즉, black이 된다.

회전 후에도 5번 속성을 만족하려면 왼쪽으로 회전하기 전에 B와 D의 색을 바꿔준다.

B를 기준으로 왼쪽으로 회전한다.

case2,3,4중에 하나로 해결(오른쪽 왼쪽을 바꿔도 성립)

5번 위반 해결하기

삭제되는 색이 black일 때 삭제되는 색이 있던 위치를 대체한 노드에 extra black을 부여한다.
대체한 노드가 red-and-black이 됐다면 black으로 바꿔주면 끝
대체한 노드가 doubly black이 됐다면 case1,2,3,4 중에 하나로 해결

delete(15)

삭제되는 노드는 15, 삭제되는 색은 15의 black, 15의 위치를 대체할 nil 노드에 extra black을 부여한다.

nil 노드는 doubly black이 됐기 때문에 어떤 case인지 분류해야 한다.
doubly black의 왼쪽 형제도 black이고 그 형제의 왼쪽 자녀가 red여서 case.4에 해당한다.

5를 부모 노드의 색인 red로 바꾸고 5의 부모인 10과 5의 왼쪽 자녀인 2는 black으로 바꾼 뒤 10을 기준으로 오른쪽으로 회전

모든 속성 만족

delete(33)

삭제되는 노드는 33, 삭제되는 색은 33의 black, 33의 위치를 대체할 nil 노드에 extra black을 부여

nil 노드는 doubly black이 됐기 때문에 어떤 case인지 분류해야 한다.
doubly black의 왼쪽 형제가 black이고 그 형제의 왼쪽 자녀는 black이고 오른쪽 자녀가 red여서 case.3에 해당

case.4의 방식으로 해결할 수 있게 case.4의 형태로 먼저 만들려면 25와 27의 색을 바꾸고 25를 기준으로 왼쪽으로 회전한다.


case.4 형태가 됐으므로 27의 색을 부모인 30의 색으로 바꾸고 27의 부모와 왼쪽 자녀는 black으로 바꾼 뒤 30을 기준으로 오른쪽으로 회전한다.


모든 속성 만족

delete(37)

삭제되는 노드는 37, 삭제되는 색은 37의 red, red가 삭제되므로 37 삭제 후 상황 종료

delete(35)

삭제되는 노드는 35, 삭제되는 색은 40의 black, 40의 위치를 대체할 45에 extra black을 부여한다.

45는 red-and-black이 됐기 때문에 45를 black으로 바꾸면 RB트리의 모든 속성을 만족하면 상황 종료

delete(40)

삭제되는 노드는 40, 삭제되는 색은 45의 black, 40의 위치를 대체할 nil node에 extra black을 부여한다.

nil node는 doubly black이 됐기 떄문에 어떤 case인지 분류해야 한다.
doubly black의 형제도 black이고 그 형제의 두 자녀도 black이기 때문에 case.2에 해당

nil 노드의 extra black과 80의 black을 모아서 50으로 올리고 80은 red로 바꿔준다.
50은 extra black을 가진다.

이제 50이 doubly black이 됐기 때문에 이버엔 어떤 case인지 분류해야 함
doubly black의 왼쪽의 형제가 black이고 그 형제의 왼쪽 자녀가 red이기 때문에 case.4에 해당
20을 부모 노드의 색인 black으로 바꾸고 20의 부모인 45와 20의 왼쪽 자녀인 5는 black으로 바꾼 뒤 45를 기준으로 오른쪽 회전

delete(50)

삭제되는 노드는 50, 삭제되는 색은 50의 black, 50의 위치를 대체할 80에 extra black을 부여

80은 red-and-black이 됐기 때문에 80을 black으로 바꾸면 RB트리의 모든 속성 만족하며 상황 종료

delete(80)

삭제되는 노드 80, 삭제되는 색은 80의 black, 80의 위치를 대체할 nil 노드에 extra black을 부여


nil 노드는 doubly black이 됐기 때문에 어떤 case인지 분류해야함
doubly black의 형제가 red이기 떄문에 case.1에 해당한다.
case.1의 형태를 바꿔서 case.2,3,4 중에 하나의 형태로 만든다.
형제와 부모의 색을 바꾼 뒤, 45를 기준으로 오른쪽으로 회전한다.


doubly black의 형제가 black이고 형제의 두 자녀가 모두 black이기 때문에 case.2의 방식으로 해결

delete(27)

삭제되는 노드 27, 삭제되는 색은 30의 red, red가 삭제되므로 27 삭제 후 상황 종료

출처

쉬운코드 유튜브
https://www.youtube.com/watch?v=6drLl777k-E&ab_channel=%EC%89%AC%EC%9A%B4%EC%BD%94%EB%93%9C