🐶 좋아, 문식이도 이해할 수 있게 레드-블랙 트리를 정말 쉽게 설명해볼게!
🐾 레드-블랙 트리란?
레드-블랙 트리Red-Black Tree는 정보를 잘 정리해두는 똑똑한 나무야.
강아지 장난감을 정리해두는 나무 선반이라고 생각하면 돼!
근데 이 선반은 정리 규칙이 있어서, 장난감을 빨리 찾을 수 있게 도와줘! (즉, 검색이 빠름!)
🌳 이 선반의 특별한 규칙 (레드-블랙 트리의 규칙)
- 장난감에는 색깔이 있어!
→ 장난감(노드)은 빨간색Red 아니면 검정색Black 이야. - 맨 위 선반(루트)은 항상 검정색이야!
- 두 개의 빨간색 장난감은 연속으로 놓을 수 없어!
→ 빨강 옆에는 항상 검정색이 있어야 해.
(빨강 빨강은 안 돼!) - 어떤 경로로 가든, 지나가는 검정색 장난감 수는 같아야 해!
→ 왼쪽으로 가든, 오른쪽으로 가든 검정색 개수는 똑같아야 해.
이 규칙들 덕분에 나무가 너무 한쪽으로 치우치지 않고 균형 있게 유지돼서,
어떤 장난감을 찾든 시간이 오래 안 걸려! ⏱️
🐶 예를 들어 볼까?
- 문식이가 뼈다귀 장난감🍖을 찾고 싶어!
- 레드-블랙 트리는 규칙 덕분에 정리정돈이 잘 되어 있어서 뼈다귀 장난감이 어디 있는지 쏙쏙 찾아줘!
요약!
- 레드-블랙 트리는 색깔 규칙을 가진 똑똑한 나무야!
- 규칙 덕분에 나무가 균형을 유지해!
- 그래서 검색, 추가, 삭제가 빠르고 안정적이야!
🌪️ 회전Rotation이란?
회전은 뭐냐면…
선반이 삐뚤어졌을 때 다시 반듯하게 고쳐주는 동작이야!
🎢 좌회전Left Rotation
오른쪽이 너무 무거워서 선반이 기울어졌어!
그래서 오른쪽 장난감을 위로 올려서 다시 평평하게 해.
🌀 우회전Right Rotation
왼쪽이 너무 무거우면 반대로!
왼쪽 장난감을 위로 올려서 평형을 맞춰줘.
📌 회전은 레드-블랙 트리의 균형을 맞춰주는 도구야!
선반이 기울어지지 않도록 돌려주는 거지!
🎁 삽입Insertion
새로운 장난감(노드)이 생겼을 때, 선반에 넣어야 해!
근데 레드-블랙 트리는 예의 바른 나무야 😎
규칙을 어기면 안 돼!
삽입 절차 요약:
- 일단 새 장난감은 빨간색으로 넣어!
(왜냐면 검정은 규칙에 영향이 커서 일단 빨강으로 시작) - 만약 빨강 옆에 또 빨강이 생기면,
→ 규칙 위반! 그래서 색 바꾸기나 회전으로 고쳐줘! - 이렇게 고치다 보면,
전체 나무가 다시 균형 잡힌 상태로 유지돼!
🗑️ 삭제Deletion
어떤 장난감이 없어졌어!
그럼 선반에서 꺼내야지?
삭제 절차 요약:
- 장난감을 뺀다
→ 근데 만약 그 장난감이 검정색이면, 균형이 무너질 수 있어! - 그래서 대체할 장난감을 찾고,
색을 바꾸거나 회전해서 규칙을 다시 맞춰줘! - 때로는 이중 검정 같은 이상한 상태가 생기기도 해!
이럴 땐 형제 장난감 색 보고 처리하거나 회전해서 해결해!
🐾 요약 정리!
| 동작 | 쉽게 말하면 | 왜 필요해? |
| 회전 | 선반 기울어졌을 때 돌려서 바로잡기 | 균형 유지! |
| 삽입 | 새 장난감 넣고, 규칙에 맞게 조정 | 빨강 옆 빨강 막기! |
| 삭제 | 장난감 뺀 후, 규칙 지키며 정리 | 검정색 개수 맞추기! |
🎁 삽입Insertion – 장난감 넣기
1. 처음엔 그냥 이진 탐색 트리(BST)처럼 삽입
- 숫자를 비교하면서 왼쪽/오른쪽으로 내려가다가
자리가 비는 곳에 빨간색 노드로 삽입해.
왜 빨간색?
검은색은 균형에 큰 영향을 줘서 조심스러워.
빨강은 넣기 편하고, 수정하기도 쉬워서!
2. 규칙 확인 후 수정Fix-up
삽입하면서 규칙 위반이 생기면 고쳐줘야 해!
가장 흔한 위반: 부모도 빨강, 나도 빨강! (빨강 옆 빨강 ❌)
🔧 고치는 방법 3가지 (삼형제 패턴!)
Case 1: 삼촌도 빨강! (색 변경)
- 부모가 빨강인데 삼촌도 빨강이면, → 부모, 삼촌 → 검정,
→ 할아버지 → 빨강 - 그리고 할아버지로 올라가서 다시 검사!
Case 2: 삼촌은 검정 or 없음, 내가 부모의 반대쪽 자식
→ 회전해서 Case 3로 만든다!
(ex: 부모는 왼쪽 자식인데 나는 오른쪽 자식)
Case 3: 삼촌은 검정, 내가 부모의 같은 쪽 자식
→ 부모와 할아버지의 색 바꾸고, 회전한다
결국, 색 변경이나 회전을 반복해서
규칙을 다시 지켜주는 거야!
🗑️ 삭제Deletion – 장난감 빼기
삭제는 좀 더 까다로워!
특히 검정색 노드를 삭제하면 규칙이 깨질 수 있어서
조심해서 “균형 복원”을 해줘야 해.
1. 일단 이진 탐색 트리처럼 삭제!
- 삭제하려는 노드가 두 자식이 없으면 그냥 제거
- 자식이 한 명이면 그 자식이 올라감
- 자식이 두 명이면?
→ 오른쪽에서 가장 작은 노드(후임자)를 찾아서 교체한 후, 그 후임자를 삭제
2. 삭제 후 규칙 복원Fix-up
특히 문제가 되는 경우:
검정색 노드가 사라졌을 때
→ 검정 개수가 달라져서 규칙 위반!
이럴 때 이중 검정double black 상태가 생겨!
(검정이 모자란 것처럼 처리됨)
🛠️ 이중 검정 해결 방법 4가지 (형제 노드 보고 결정)
Case 1: 형제가 빨강
- 부모와 색 바꾸고 회전해서
→ 검정 형제로 만든 다음 다른 Case로 넘어가
Case 2: 형제, 형제의 자식들 모두 검정
- 형제를 빨강으로 바꾸고
→ 부모를 이중검정으로 올려서 재귀적으로 처리
Case 3: 형제는 검정, 가까운 자식은 빨강, 먼 자식은 검정
- 형제랑 자식 색 바꾸고 회전해서 Case 4로 변경
Case 4: 형제는 검정, 먼 자식이 빨강
- 형제와 부모의 색을 바꾸고
→ 회전한 뒤, 문제 해결!
🐾 요약 정리!
| 구분 | 과정 요약 | 핵심 포인트 |
| 삽입 | 빨강으로 넣고, 규칙 위반 시 색 바꾸거나 회전 | “빨강 옆 빨강” 없애기 |
| 삭제 | BST처럼 삭제한 후, 이중 검정이면 형제 기준으로 처리 | “검정 개수” 맞추기 |
🎁 삽입 단계별 예시
삽입할 값: 10, 20, 30
✅ Step 1: 10 삽입
- 트리가 비어있음 → 10은 루트
- 루트는 무조건 검정색
✅ Step 2: 20 삽입
- 20 > 10 → 오른쪽 자식으로 삽입
- 삽입된 노드는 빨강
규칙 위반 없음 (빨강 옆 빨강 아님)
❌ Step 3: 30 삽입
- 30 > 20 > 10 → 오른쪽 자식으로 또 삽입
- 삽입된 30은 빨강 → 부모 20도 빨강 ❌ 위반!
빨강 옆 빨강! → Case 3 (삼촌 없음, 같은 방향)
✅ 해결 방법:
- 10을 왼쪽으로 회전 → 20이 새로운 루트
- 색깔 조정: 20은 검정, 10, 30은 빨강
짠! 균형도 맞고 규칙도 지켰어 🎉
🗑️ 삭제 단계별 예시
시작 트리:
✅ Step 1: 10 삭제
- 10은 검정이고 자식도 없음
검정 노드 삭제 → 검정 하나가 사라짐
→ 왼쪽 경로의 검정 개수가 1 부족!
이제 이중검정을 해결해야 해.
❌ 이중 검정 처리
현재 상태:
- 10 삭제 → 이중검정(∅BB)
- 형제는 30B, 자식 없음 → Case 2 (형제와 자식 모두 검정)
✅ 해결 방법:
- 30을 빨강으로 바꿈
- 부모인 20이 검정이었으므로 → 다시 이중검정으로 올라감
→ 20은 루트니까 이중검정 해제!
→ 20은 검정으로 유지되고 트리 종료
해결 완료! 🎉
📌 정리 그림 요약
삽입 후 트리:
삭제 후 트리 (10 삭제):
[참고자료]
[알고리즘] Red-Black Tree : 레드 블랙 트리
스스로 공부해 본 후, 다시 정리하는 내용의 글 입니다. 틀린부분과 실수가 있다면 지적해주시면 감사하겠습니다. 레드 블랙 트리 또한 binary-search tree(이진탐색트리) 의 일종이다. 기존의 이진탐
blogshine.tistory.com
'Krafton Jungle > 3. TIL' 카테고리의 다른 글
| [WEEK06] RB 트리 삽입/삭제 예제 (0) | 2025.04.21 |
|---|---|
| [WEEK06] RB트리의 삽입/삭제에 대해 우리집 강아지 문식이도 알기 쉽게 설명해줘 (0) | 2025.04.19 |
| [WEEK05] 파이썬과 다른 C언어의 특성들 (0) | 2025.04.10 |
| [WEEK05] Ubuntu에 C 작업환경 설정하기 (0) | 2025.04.10 |
| [WEEK04] 트리 동형 사상 (0) | 2025.04.09 |