(자료구조) 레드-블랙(red-black) 트리의 삭제 동작 방식과 시간복잡도 PART2 (예제 포함!!!!!)

레드-블랙 트리의 삭제 동작 방식과 시간복잡도

레드-블랙 트리(Red-Black Tree)는 삽입보다 삭제가 더 복잡한 구조적 조정을 필요로 한다.
이는 트리의 속성(#2~#5)이 깨질 가능성이 높기 때문이며,
특히 Black 노드가 삭제되는 경우 트리의 균형이 크게 영향을 받는다.

 

참고 (레드-블랙 트리의 5가지 주요 속성)

1. 모든 노드는 Red 또는 Black이다.
2. 루트 노드는 항상 Black이다.
3. 모든 leaf 노드(NIL 노드)는 Black이다.
   • 실제 값이 없는 NIL 노드는 트리의 균형 계산에 사용됨.
4. Red 노드의 자식은 모두 Black이다.
   • 즉, Red 노드가 연속적으로 나타날 수 없다.
5. 임의의 노드에서 그 자손인 모든 NIL 노드로 가는 경로에는 같은 수의 Black 노드가 있다.
   • 이를 Black Height라고 부르며, 균형 유지의 핵심 조건이다.

 

---

✅ 삭제 개요 (Overview)

1. 삭제 전, 레드-블랙 트리의 속성은 모두 만족된 상태
2. 삭제 자체는 일반 BST의 삭제 방식과 동일
   • 삭제할 노드에 자식이 0개 또는 1개 → 단순 삭제
   • 자식이 2개 → 후임자(Successor) 로 교체한 뒤 후임자 삭제
3. 삭제 이후, 레드-블랙 트리의 속성(#2, #4, #5) 위반 여부를 점검
4. 위반 시 회전 및 색상 조정을 통해 트리 복원

 

사진 출처 - 유튜브 쉬운코드

 

 

---

✅ 삭제 시 중요한 판단 기준: 삭제된 노드의 색

• 삭제된 노드가 Red:
  • 아무런 속성도 위반되지 않음 → 추가 조정 불필요
• 삭제된 노드가 Black:
  • 다음 속성이 위반될 수 있음:
    • #2: 루트는 Black이어야 한다
    • #4: Red 노드의 자식은 Black이어야 한다
    • #5: 모든 경로의 Black 노드 개수는 같아야 한다

---

✅ 해결 전략: Extra Black (Double Black) 개념

삭제로 인해 Black 높이(#5) 가 불균형해지는 경우,
삭제된 위치를 대체한 노드에 "Extra Black(=Double Black)" 이 부여된다.

• 이 상태는 일반적인 Black보다 하나 더 많은 Black을 가진 것으로 간주
• 해결 방법:
  • 색상 변경
  • 회전
  • 상위 노드로 전달

---

✅ Doubly Black 제거를 위한 4가지 Case

모든 경우에서 "Doubly Black 노드(D)"의 형제(Sibling) 와 형제의 자식들의 색이 판단 기준이다.
(설명에서는 D의 형제가 오른쪽 형제(S) 라고 가정)

---

S는 형제 노드 의미

▶ Case 1: S가 Red인 경우

• 형제 S가 Red면 부모는 반드시 Black
• 해결:
  1. S를 Black, 부모를 Red로 변경
  2. 부모 기준으로 회전 (D가 왼쪽 자식이면 왼쪽 회전)
  3. → 구조가 Case 2/3/4 중 하나로 바뀜 → 그 중 하나로 재처리

* 형제 노드가 RED

---

▶ Case 2: S는 Black이고, S의 두 자식도 모두 Black

• 해결:
  1. S를 Red로 변경 (즉, S의 Black을 D와 공유해 상위로 올림)
  2. D의 부모에게 Extra Black을 전달
     • 부모가 Red이면 Black으로 바꿔 해결 끝
     • 부모가 Black이면 다시 Doubly Black으로 간주 → 재귀적 처리

* 형제의 두 자식도 블랙인 경우

---

▶ Case 3: S는 Black, S의 가까운 자식은 Red, 먼 자식은 Black

• 해결:
  1. S와 S의 가까운 자식의 색을 바꿈
  2. S를 기준으로 회전 (D가 왼쪽 자식이면 S 기준 오른쪽 회전)
  3. → Case 4의 구조로 변경됨 → Case 4로 이어서 처리

* 형제의 가까운 자식이 레드  , 먼 자식은 블랙 

 

여기서 가까운 자식이란???????

예제1.

D : Doubly Black 노드
S : 형제 노드
   
   	P
       / \
      D   S
         / \
     near   far

 

 

예제2.

D : Doubly Black 노드
S : 형제 노드

	P
       / \
      S   D
     / \
  far   near

 

 

---

▶ Case 4: S는 Black, S의 먼 자식은 Red

• 해결:
  1. S의 색을 부모의 색으로 변경
  2. 부모와 S의 먼 자식을 Black으로 변경
  3. 부모 기준으로 회전 (D가 왼쪽 자식이면 왼쪽 회전)
  4. Doubly Black 제거 → 종료

* 형제의 가까운 자식이 레드일때..

 

 

TIP-   CASE3 , 4 구분시    형제의 자식 노드 중 먼자식만 체크하면 3인지 4인지 확인 가능

* 1. 먼 자식이 RED면 CASE4   

   2.  먼자식 BLACK 가까운 자식 RED면 CASE 3 

   3. 자식 둘다 BLACK 이면 CASE2

   4. 형제가 RED면 CASE 1

 

---

✅ Doubly Black Case 별 예제

 1. Case 4 상황 예제 

 

 

 

case4  해결책

 

최종 결과

 

 2. Case 3 상황 예제 

2-1  33 delete 

 

 

 

 

 

case4로 변경을 위해  부모와 색 변경후 왼쪽 회전 준비중

 

 

위치 변경 후 27의 부모와 자식의 색을 블랙으로 바꿔준다.

 

27을 오른쪽으로 회전해서 위치 조정

 

 

 3. Case 2 상황 예제 

3-1 35 delete  35 삭제시 석세서인 40이 대체됨 . (그럼 40의 블랙이 삭제되는거임. 엑스트라 블랙 부여.)

 

 

40 delete 

 

 

case2 해당됨.

 

 

-case2 일때 블랙을 모아서 위 부모로 올리고 자식은 red로 변경 

그리고 이제 case4로  변경됨

 

 

아래 사진과 같이 자식 5를 블랙으로 변경하여 오른쪽 회전을 함.

 

 

완료

 

 4. Case 1 상황 예제 

4-1. 80 delete 

 

 

 

 

 

 

 

 

해결.

 

 

 

 

✅ 정리: 삭제 시 Doubly Black 처리 플로우

1. 삭제된 노드가 Red → 아무 문제 없음
2. 삭제된 노드가 Black:
   • 대체 노드에 Extra Black (Doubly Black) 부여
   • Red-and-Black 상태면 → Black으로 색 변경 (종료)
   • Doubly Black 상태면 → Case 1~4에 따라 처리
   • 경우에 따라 재귀적으로 부모에게 Extra Black을 전달

---

✅ 레드-블랙 트리의 시간복잡도

연산평균 시간복잡도최악 시간복잡도

검색	O(log N)	O(log N)
삽입	O(log N)	O(log N)
삭제	O(log N)	O(log N)

 

→ 모든 연산이 균형 유지를 통해 로그 시간에 수행됨

---

✅ 레드-블랙 트리 vs AVL 트리 비교

항목Red-Black TreeAVL Tree

균형 기준	느슨한 균형 유지	엄격한 균형 유지
삽입/삭제	빠름 (회전 적음)	느림 (회전 많음)
검색 성능	약간 느림	더 빠름 (트리 높이 작음)
회전 횟수	적음	많음
사용 사례	시스템/라이브러리 등	검색 최적화가 필요한 경우

 

예: Java의 TreeMap, C++ STL의 map/set은 Red-Black Tree 기반

 

 

* 사진 및 자료 출처 - 유튜브 쉬운 코드