TIL(18일차) RB트리 삭제

레드 블랙 트리의 삭제는 글만 봐서는 굉장히 어렵기 때문에 유튜버 쉬운 코드 님의 영상을 보고 공부를 하였다.

 

다른 자료를 찾아봐도 괜찮을 것 같다.

 

successor를  어디다가 두냐에 따라 트리의 모양이 상이 하므로 그려보면서 연습을 하는 것이 나을 것 같다.

 

 

먼저 그전에 알아야할 RB트리의 5가지 속성

 

1. 모든 노드는 red 혹은 black 이다.

2. 루트 노드는 black

3. 모든 nil노드는 black

4. red의 자녀들은 black이어야한다.(red가 두번 나올 수 없다)

5. 임의의 노드에서 자손 nil노드들까지 가는 경로들의 black 수는 같다(자기 자신은 카운트에서 제외)

 

레드 블랙트리의 삭제

 

0. 삭제 전 RB트리 속성 만족한 상태확인

1. 삭제 방식은 일반적인 BST와 동일

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

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

4. RB트리 속성을 다시 만족하는지

 

삭제는 삭제되는 노드의 색이 속성 위반의 여부를 확인할때 굉장히 중요하게 판단하게 된다.

 

속성위반의 여부 확인 케이스는 다음과 같다.

 

1. 삭제하려는 노드의 자녀가 없거나 하나 => 삭제되는 색 = 삭제되는 노드의 색

 

2. 삭제하려는 노드의 자녀가 둘 => 삭제되는색 = 삭제되는 노드의 successor의 색

 

위 두개의 케이스를 염두해 두고 다시 케이스가 나뉜다.

 

red가 사라질 때

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

 

black가 사라질 때

RB트리의 2,4,5의 속성을 위반할 수 있다.

 

 

위반 여부를 확인하고 위반 행위가 생겼다면 재조정을 해줘야한다.

 

만약 속성 2를 어겼다면 루트 노드를 black로 바꾼다.

 

근데 보통 5번 속성을 위반하게 된다.

 

그래서 삭제될때의 black이 삭제 될때 그 부분의 찌꺼기 black을 남겨 black이 남아있다고 가정한다.

 

red노드가 찌꺼기 블랙을 만났을 때 그냥 red인 노드를 black으로 바꿔준다.

 

하지만 black노드에 black찌꺼기가 만난다면 이야기가 달라진다.

 

이 경우도 4가지 케이스로 나뉘는데,

 

사실상 이게 삭제의 핵심이다.

 

 

Doubly Black를 만났을 때

 

 

1. doubly Black(찌꺼기 블랙) 의 오른쪽 형제가 black 이면서 그 형제의 오른쪽 자녀가 red일때

 

해결 방안 => 오른쪽 형제는 부모의 색으로, 오른쪽 형제의 오른쪽 자녀는 black으로 부모는 black으로 바꾼뒤 부모를 기준으로 왼쪽 회전

 

2. doubly Black의 오른쪽 형제가 black 이면서 그 형제의 왼쪽 자녀가 red 오른쪽 자녀가 black일때

 

해결 방안 => doubly black의 형제의 오른쪽 자녀를 red가 되게 만들어서 해결.

 

3. doubly black의 형제가 black 이면서 그 형제의 두 자녀 모두 black일때

 

해결방안 => doubly black과 그 형제의 black을 보아서 부모에게 전달한다.

 

4. doubly black의 형제가 red이면서 그 형제의 두 자녀 모두 black일때

 

해결방안 => 부모와 형제의 색을 바꿔주고 부모를 기준으로 왼쪽으로 회전한 뒤 doubly black을 기준으로 위의 케이스중 하나로 해결한다.

 

 

 

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

Red/Black Tree Visualization