레드-블랙 트리 (삭제)

---

---

📌 Red-Black 삭제

요번 포스팅에서는 레드-블랙 트리의 삭제에 대해 알아보자. 이전 포스트에서도 말했듯이 레드-블랙 트리는 이진 탐색 트리 중에서 균형을 보장하는 대표적인 자료구조이다.

 

삭제하기전 알아야 할 개념

- Extra Black

삭제시 필요한 개념으로 노드에 임시로 부여 할 수 있다.

 

- Doubly Black

Black 노드에 Extra Black이 붙은 경우이다.

 

- Red-and-Black

Red 노드에 Extra Black이 붙은 경우이다.

 

- Successor

오른쪽 서브트리에서 가장 작은 값

 

❗ 레드-블랙 트리에서 삭제 대상 노드가 자식 들을 가질 경우, 실제로 삭제되는 노드는 successor이다

 

 

레드-블랙 트리 삭제의 흐름

1. 삭제할 노드를 찾는다.
2. 자식이 둘이면 successor와 교체하고, successor를 삭제
3. 삭제된 노드의 색이 검정이면 -> Extra-Black 발생
4. extra-black 해결을 위한 회전 및 색상 변경으로 트리의 균형 복구

---

📌 Red-Black 삭제 case

 

✏️ 오른쪽 형제가 black & 그형제의 오른쪽 자녀가 red

처리 방법

• s를 부모의 색으로 칠하고
• 부모를 black으로 바꾸고
• s.right를 black으로 바꾼다
• 부모를 기준으로 left-rotate 한다.

 

 

✏️ 오른쪽 형제가 black이고 그 형제의 왼쪽 자녀가 red 그 형제의 오른쪽 자녀는 black

처리 방법

• s를 red로 바꾼다
• s.left를 black으로 바꾼다
• 형제 s를 기준으로 오른쪽 회전(right-rotate) 한다
• Case 1 상황(오른쪽 자식 red)으로 만든 후 처리

 

 

Doubly Black을 해결하기 위해 이후 1번 케이스 (오른쪽 형제가 black & 그형제의 오른쪽 자녀가 red) 로 해결

 

✏️ 형제가 black & 그형제의 두 자녀 모두 black일때

처리 방법

• s를 red로 바꾼다
• x의 부모를 새로운 문제 노드(x)로 삼아서 위로 계속 올라가면서 문제를 해결한다 (부모 쪽에서 black-height 부족이 생김)

 

s를 red로 만들면서 x가 위치한 부분의 black 수를 맞췄지만, 대신 부모에서 black 하나 부족 현상이 생김. 그래서 위로 올라가면서 계속 수정해야 한다.

 

✏️ 형제가 red일 때

처리 방법

• 부모와 s의 색깔을 서로 바꾼다
• 부모를 기준으로 left-rotate (혹은 right-rotate, x가 왼쪽/오른쪽에 따라 다름)
• 회전한 후, 이제 x의 새 형제는 black이 된다 → 이후 Case 1,2,3으로 넘어간다.

---

📌 Red-Black 삭제 정리표

 

CASE	상황	조치
1	형제 black, 오른쪽 자식 red	부모-형제 색 바꾸고 부모 기준 left-rotate
2	형제 black, 왼쪽 자식 red, 오른쪽 black	형제 색 바꾸고 형제 기준 right-rotate, Case 1로 전환
3	형제 black, 양쪽 자식 모두 black	형제를 red로 칠하고 부모로 올라감
4	형제 red	부모-형제 색 바꾸고 부모 기준 회전 후 Case 1~3으로 진행

 

📢 핵심 요약

• 형제가 red이면 → 먼저 회전해서 black으로 만들어야 함
• 형제가 black이면 → 형제 자식들의 색을 보고
  • 오른쪽이 빨강이면 → 바로 큰 회전
  • 왼쪽이 빨강이면 → 작은 회전 후 큰 회전
  • 둘 다 검정이면 → 형제 빨강으로 칠하고 부모로 문제 넘김

 

---

🤔 느낀점

레드 블랙 트리 삭제 너무 어렵다. 잘 짜여진 코드가 있으니 사용하면 될 것 같다.