하루 요약

✏️오늘의 한 일

• RB 트리 삭제
• gdb 디버거

🌈오늘의 성장?

RB 트리 삭제

🌳 Red-Black Tree 삭제 및 Fix-Up 로직 정리

---

✅ 삭제 시 서브트리 재조정

1. 서브트리 이동
   • u: 삭제되는 노드
   • v: u를 대체할 노드 (u의 successor 등)

---

✅ 삭제 진행

삭제되는 노드에 따라 세 가지 케이스로 나뉨:

1. 자식이 없는 경우: 그대로 삭제
2. 자식이 1개인 경우: 해당 자식이 u의 위치로 이동
3. 자식이 2개인 경우:
   • successor(중위 순회 시 다음 노드)를 찾아서 u를 대체
   • successor의 값을 u로 복사하고, successor는 삭제 (1 또는 0개의 자식만 가짐)

---

🛠️ delete_fix_up

• 삭제 후 Red-Black 속성을 유지하기 위한 Fix-Up 처리
• Doubly Black (DB) 상황 발생 시 처리 로직

---

🎯 핵심 개념

• DB: 삭제된 노드를 대체한 노드 (Fix-Up 대상).
  NIL 노드여도 DB 가능
• bro: DB 노드의 형제 노드

---

CASE 별 처리 로직

---

🟥 CASE 1: 형제가 RED

• bro가 RED

1. bro와 부모 색 교환
2. 부모 기준으로 회전
3. 이후 CASE 2~4 중 하나로 이동

---

⚫ CASE 2: 형제가 BLACK + 자식 둘 다 BLACK

• bro가 BLACK, 두 자식도 BLACK

1. bro를 RED로 변경
2. DB를 부모로 이동
3. 부모가 BLACK이면 재귀적으로 Fix-Up
4. 부모가 RED면 BLACK으로 바꾸고 종료

---

🔁 CASE 3: 형제가 BLACK + 왼쪽 자식 RED, 오른쪽 자식 BLACK

• bro의 왼쪽 자식만 RED

1. bro와 그 왼쪽 자식 색 교환
2. bro 기준으로 우회전
3. CASE 4로 진입

---

✔️ CASE 4: 형제가 BLACK + 오른쪽 자식 RED

• bro의 오른쪽 자식이 RED

1. bro의 색 ← 부모의 색
2. 부모와 bro의 오른쪽 자식 색 ← BLACK
3. 부모 기준으로 좌회전
4. Fix-Up 종료

Extra black 주는 기준

예시 1: 리프 노드 삭제

삭제 노드: 10 (Black, 리프)
대체 노드: NIL
→ NIL이 Extra Black을 받음
→ Fix-Up(NIL)

예시 2: 자식 1개 (Red)만 있는 경우

삭제 노드: 10 (Black)
자식: 5 (Red)
→ 5가 올라감 → Black으로 바꾸면 끝
→ ❌ Extra Black 없음

예시 3: 자식 1개 (Black)만 있는 경우

삭제 노드: 10 (Black)
자식: 5 (Black)
→ 5가 Extra Black을 받음
→ Fix-Up(5)

예시 4: 자식 2개 → successor 사용

삭제 노드: 10
successor: 12 (대체 노드)
→ 12가 삭제되고 그 자리에 successor 자식이 올라감 (보통 NIL or 하나)
→ 그 자식이 Extra Black 받음
→ Fix-Up(그 자식)

⛏오늘의 삽질

Double Free 해제로 하루 죙일 삽질중