레드 블랙 트리 (Red-Black Tree) 삭제

레드 블랙 트리 삭제

• 삭제하는 node(x)가 Black일 때 실행

• 이중 흑색 노드일 경우 Case 파악

  • 이중 흑색 노드: 검은색 node를 다시 검은색으로 칠하는 경우

< 삭제 node(x)가 Red인 경우 >

• 그냥 삭제 합니다.

< 삭제 node(x)가 Black 인 경우 >

(무조건 실행)

• 이진 검색 트리 삭제 이용

• 자리를 대체하는 node를 검정색으로 변환

  • Red -> Black : 괜찮다

  • Black -> Black : 이중 흑색 노드

< x가 Black인 경우 + 이중 흑색 노드>

Case change)

• x의 형제가 Red

1. x의 형제 Red -> Black

2. x의 부모 * -> Red

3. x의 부모를 기준으로 왼쪽 회전

4. 다른 Case 이동

Case 1)

• x의 형제가 Black

• x의 형제 자식 모두 Black

1. x의 형제 Black -> Red

2. x의 Black 1개를 x의 부모로 이동

• 이중 흑색노드 부모로 이동(x의 부모가 Black)

• 부모 Black으로 변환 (x의 부모 Red)

3. 이중 흑색 노드가 Root에 도달시 끝

Case 2)

• x의 형제가 Black

• x 형제의 왼쪽 자식 Red

• x 형제의 오른쪽 자식 Black

1. x의 형제 Black -> Red

2. x 형제의 왼쪽 자식 Red -> Black

3. x 형제 기준으로 오른쪽 회전

Case 3)

• x의 형제가 Black

• x의 형제의 오른쪽 자식 Red

1. x의 부모의 색을 x의 형제에게 넘긴다.

2. x의 부모를 Black

3. x 형제의 오른쪽 자식 Black

4. x 부모 기준 왼쪽 회전

좋은 자료
https://assortrock.com/88