[WIL-250625]이번 주의 트러블슈팅: 첫 번째 벽이 재귀였다면, 두 번째 벽은 RED-BLACK TREE

Red-Black Tree를 직접 구현하며 마주한 의문과 핵심 개념 정리

---

🔎 RED-BLACK TREE 보러가기

• 👉 Red-Black 트리 쉽게 이해하기 : 삽입부터 균형유지까지
• 👉 Red-Black 트리 삭제 정리

---

이번 주는 Red-Black Tree를 직접 구현해보는 과정을 진행했습니다.
처음에는 "이론만 잘 이해하면 구현은 쉽게 따라오겠지" 라는 생각을 했지만, 실제로 코딩을 시작하면서 그게 큰 착각이었다는 걸 바로 깨달았습니다.

조건 분기와 예외 처리, 그리고 색상 규칙의 조합 속에서 논리적 사고의 체력이 점점 바닥나는 느낌이었죠.

---

🤔 구현 중 떠오른 두 가지 의문

1. 왜 처음에 Red로 넣는 걸까?
2. Black으로 먼저 넣거나, 다 넣고 나중에 한꺼번에 회전하면 더 쉬운 것 아닌가?

이 두 질문을 실마리 삼아, RBT의 설계 철학과 규칙을 다시 되짚어보게 되었습니다.

---

📐 Red-Black Tree의 핵심 규칙은?

"모든 리프까지의 경로에서 Black 노드의 개수는 동일해야 한다"

이 규칙 덕분에 RBT는 트리의 균형을 유지하고, 최악의 경우에도 O(log n) 높이를 보장합니다.

하지만 삽입/삭제 때마다 전체 트리를 순회하며 조정한다면 성능이 크게 저하되겠죠.
그래서 RBT는 이러한 비용을 피하고자 지역적 수정(local fix) 방식으로 동작합니다.

✅ 지역적 수정이란?

• 문제 발생 지점 주변 노드 몇 개만 수정
• 전체 트리를 다시 짜는 것이 아님
• 색 변경 또는 회전만으로 조건 복구

---

🔴 왜 Red로 먼저 삽입할까?

• Red는 Black Height에 영향을 주지 않음
• 따라서 Red 상태로 삽입해도 균형을 바로 깨지 않음
• → 삽입 후 조건 위반 시에만 가볍게 색 바꾸거나 회전

반면에:

• Black으로 삽입하면 해당 경로의 Black Height가 증가
• → 트리 전체 균형이 즉시 깨지고
• → 복구 시 전역적 수정이 필요해짐

✅ 그래서 RBT는 일단 Red로 가볍게 삽입한 뒤, 문제가 생긴 경우에만 부분적으로 고치는 전략을 씁니다.

---

⚠️ Red-Red는 왜 안 되는가?

Red 노드는 Black Height에 영향을 주지 않기 때문에 연속해서 등장하면 규칙 위반이 됩니다.

• Red → Red는 허용되지 않음
• 반드시 사이에 Black이 하나 있어야 함

이 규칙이 깨지는 순간, 색 변경 혹은 회전을 통해 바로 복구해야 합니다.

---

🔁 "그냥 다 넣고 마지막에 회전하면 안 돼?"

이 질문은 자연스럽게 떠오를 수 있습니다.

"모든 노드를 다 넣은 후에 한 번에 균형을 맞추는 게 더 효율적이지 않나?"

하지만 현실은 다음과 같습니다:

• 어떤 규칙이 어디서 깨졌는지 추적이 어려워짐
• 전체 트리에 대해 회전/색 변경을 반복 적용해야 함
• → 시간 복잡도, 구현 난이도 모두 증가

RBT는 이러한 상황을 피하기 위해 삽입 중 바로 고치는 설계(Local Fix) 를 택합니다.
AVL Tree처럼 전체 균형을 유지하려는 접근과는 철학이 다르죠.

---

🧩 결론 요약

• ✅ Red는 유연한 삽입이 가능 → Black Height 영향 없음
• ⚠️ Black은 경로 전체에 영향을 줌 → 조정 비용 큼
• ❗ Red-Red는 반드시 피해야 할 조건
• 💡 "다 넣고 회전" 전략은 구현 복잡도와 성능 모두에서 비효율
• 🔁 RBT는 즉시 조정(Local Fixing)이 핵심 전략

---

🧠 직접 구현하며 느낀 점

단순해 보이는 규칙도 직접 구현하려 하면
예외처리, 조건 분기, 디버깅 이슈가 쌓여 꽤나 버겁다는 걸 실감했습니다.

특히 Red-Black Tree처럼 간단한 아이디어 + 복잡한 분기 구조는,
단지 이론이 아니라 논리적 사고력과 체력이 필요한 영역이었습니다.

앞으로 새로운 자료구조를 공부하거나 구현할 때는,

“핵심 불변 조건은 무엇이고, 임시로 허용되는 상태는 어떤 것인가”

이것부터 먼저 명확히 구분하는 습관을 가져야겠다고 느꼈습니다.