Red-Black Tree (레드 블랙 트리) 데이터 삭제.

학습에 참고한 영상입니다. 

*https://www.youtube.com/watch?v=6drLl777k-E

데이터 삭제

이진탐색 트리의 한 종류이기 때문에 기본적인 이진 탐색트리 삭제 방법을 따른다.

데이터 삭제 후, 레드 블랙 트리의 속성 5가지를 만족하는지 확인한다.

이를 불만족 한 노드가 발생한다면, 재조정을 한다

 

속성

1. 모든 노드는 Red/Black 두 가지중 하나의 색상값을 가진다.

2. Root노드는 반드시 Black 색상이다.

3. 없는 상태(Null, None, Nill)을 나타내는 노드는 Black 색상을 갖는다.

4. Red색상의 노드는 반드시 Black색상의 자식을 가져야 한다.(Black 노드는 Black/Red 어떤색이든 자식으로 가질 수 있다.)

5. 임의 노드에서 모든 Leaf 노드까지의 경로에서 시작 노드를 제외한, Black node의 개수(Black Height)는 동일하다.

 

삭제방법

 

1. 삭제되어야 할 노드를 선정한다

 

- 삭제를 하려는 값을 가진 노드가 "자식이 없거나 1개인 경우"

-> 그 값을 가진 노드를 삭제한다.

 

- 삭제를 하려는 값을 가진 노드가 "2개인 경우"

-> successor(큰 것중에 가장 작은 값을 가진 노드)와 "값만" 바꾸고 successor를 삭제.

 

2. 1번의 기준에 따라 삭제되는 색이 레드면, 레드 블랙 트리 원리상 어떤 속성도 불만족이 되지 않는다.

 

3. 1번의 기준에 따라 삭제되는 색이 블랙이면, 여러 불만족이 발생한다.

- 블랙 노드가 삭제 되면 속성5를 위반하게됨 --> extra black(임시의 추가적 블랙 색)을 "삭제된 노드 위치"에 1개 부여함

 

*그래프에서 null, nil 노드는 생략하여 그린 것.

 

delete 10

자식이 없으니까 10을 삭제

삭제후 nill 노드만 남음.

25번 노드의 nill 노드가 생략 되었기 때문에 다시 bh가 일정해짐. 

 

delete 30

자식이 1개이기 때문에 바로 30삭제.

속성4, 5번을 위반함

delete 50

50의 자식은 2개이기 때문에 successor인 80이랑 값만 바꾸고 삭제

삭제 후 nil 노드에 추가 블랙부여

4. extra black 처리하기.

- red and black --> 노드색을 단색 블랙으로 변경

- double black --> 경우에 따라 다르게 처리.

 

5. double black의 형제의 색과 형제의 자식의 색깔에 따라 다르게 처리한다.

 

- A기준 "형제가 블랙이고 D기준(꺽이지 않는)자식 E가 레드일 때

doubly black인 A를 red and black 으로 변경하여 노드색을 단색 블랙으로 확정하자!

 

일단은 D의 자식이 2개가 있으니까 extra black을 이용하여 D의 색을 교체한다.

 

B의 색이 검정이던 레드이던 상관없이, D의 색과 교환해도 속성위반을 하지 않는다.

(이미 증명된 사실 - 이 글에서는 따로 증명은 하지 않는다) 

왼쪽으로 회전

(이미 증명된 사실 - 이 글에서는 따로 증명은 하지 않는다)

2개의 extra black을 이용하여 부모노드와 색 바꿈을 함. 

red and black 으로 변경하여 노드색을 단색 블랙으로 변경.

 

* 요약.

부모랑 형제의 색을 교환해줌.

형제의 오른쪽 자녀는 블랙으로 해줌

부모를 중심으로 왼쪽 회전

 

*왼/오른쪽 이 대칭인 상황에도 적용 가능하다.

 

- A기준 "형제가 블랙이고 D기준(꺽이는)자식C가 레드, (안 꺽이는) 자식 E 블랙일 때.

 

bh(D) = k라면,  C가 레드기 때문에 bh(C) = k 이고, E가 블랙이기 때문에 bh(E) = k - 1 

즉 p, q의 내부 블랙 노드의 개수는 k,

     x, y의 내부 블랙 노드의 개수는 k-1

 

C와 D의 색깔을 바꾸어 준다( bh(D)가 속성5를 일시적으로 위배함)

D를 기준으로 왼쪽으로 회전한다. (bh(D)가 속성을 다시 맞춤)

그래프가 위와 같은 상태가 되면,

(A기준 "형제가 블랙이고 B기준(꺽이지 않는)자식이 레드일 때) 사용한 방법으로 해결 가능하다

 

- A기준 "형제가 블랙이고 B기준(꺽이는)자식이 블랙, 안꺽이는 자식이 블랙일 때.

A와 B의 블랙 색상을 extra black으로 만들어 부모 노드로 올려 보내서 D를 레드로 만든다.

 

B가 red and black이거나 root 라면 블랙으로 바꾸어 해결,

doubly black 이라면,  재귀적으로 B(doubly black)을 기준으로 다시 불만족을 해결한다. 

 

- A기준 "형제가 레드인 경우(형제의 자식들은 어짜피 둘다 블랙)"

 

bh(B) = k 라면

i, j, 내부 블랙노드의 개수는 k-2

p, q, x, y 내부 블랙노드의 개수는 k-1

 

B와 D의 색상을 바꿔줌 (일시적으로 bh(B) = k가 아 아니게됨.)

이후, B를 기준으로 왼쪽으로 회전시킨다(다시 속성5를 만족하게됨.)

 

A(doubly black)의 형제인 C가 블랙이 되었기 때문에 기존의 방법대로 해결 가능하다.