기존의 이진 탐색 트리(BST)는 최악의 경우 데이터가 한쪽으로 쏠려(예: 1, 2, 3, 4 순서로 삽입 시) 일직선의 연결 리스트처럼 변해버리는 치명적인 약점이 있습니다. 이를 해결하기 위해 등장한 구세주가 바로 레드-블랙 트리(Red-Black Tree)입니다.
레드-블랙 트리는 노드에 '빨강(Red)'과 '검정(Black)'이라는 색상 속성을 부여하고, 데이터가 한쪽으로 쏠리려고 할 때마다 스스로 트리를 회전(Rotation)시키고 색상을 바꿔(Color Flip) 항상 완벽한 균형(Balance)을 유지합니다.
1. 절대 어길 수 없는 4가지 절대 규칙
레드-블랙 트리는 아래의 4가지 규칙을 무조건 지켜야 합니다. 이 규칙이 깨지는 순간 좌회전, 우회전, 색상 반전이라는 복구 작업이 실행됩니다.
규칙 1. 모든 노드는 빨간색(Red) 아니면 검은색(Black)이다.
규칙 2. 최상단 뿌리 노드(Root Node)는 무조건 검은색(Black)이다.
규칙 3 (Double Red 금지).빨간색 노드의 자식은 연속으로 빨간색이 올 수 없다. (반드시 검은색이어야 함)
규칙 4 (Black Height 유지). 특정 노드에서 리프 노드 끝까지 내려가는 모든 경로에서 거치는 검은색 노드의 개수는 모두 똑같아야 한다.
2. 회전(Rotation)을 통한 자가 균형 시뮬레이션
💡 실무 지식: Java 컬렉션의 핵심 엔진
레드-블랙 트리는 구조가 매우 복잡해서 실제 실무 코드에서 밑바닥부터 짜는 경우는 극히 드뭅니다.
하지만 우리가 매일 쓰는 Java의 TreeMap, TreeSet, 그리고 C++의 std::map이 모두 내부적으로 이 레드-블랙 트리로 구현되어 있습니다. 즉, 여러분이 TreeMap을 사용해 데이터를 정렬할 때마다 보이지 않는 곳에서 수많은 노드들이 빨갛게, 검게 물들며 회전하고 있는 것입니다.
// 📂 RBTree.js (JavaScript)
// 레드-블랙 트리의 노드는 항상 '색상(Color)' 정보를 가집니다.
const RED = true;
const BLACK = false;
class Node {
constructor(key, color = RED) {
this.key = key;
this.left = null;
this.right = null;
this.parent = null; // 부모를 가리키는 포인터가 회전(Rotation) 시 필수적입니다.
this.color = color; // 새로 추가되는 노드는 무조건 RED로 시작합니다.
}
}
class RedBlackTree {
constructor() {
this.root = null;
}
// 🌟 핵심 원리: 좌회전 (Left Rotate)
// 오른쪽 자식이 무거워졌을 때, 중심축을 왼쪽으로 기울여 밸런스를 맞춥니다.
leftRotate(x) {
let y = x.right;
x.right = y.left;
if (y.left !== null) y.left.parent = x;
y.parent = x.parent;
if (x.parent === null) this.root = y;
else if (x === x.parent.left) x.parent.left = y;
else x.parent.right = y;
y.left = x;
x.parent = y;
console.log(`노드 ${x.key}를 기준으로 좌회전(Left-Rotate) 수행!`);
}
// 삽입 로직 (이진 트리 삽입 후 색상 규칙 위반 시 회전 및 색 변환 수행)
insert(key) {
// ... (이진 탐색 트리 삽입 코드) ...
// ... (삽입 후 fixViolation(newNode) 호출하여 RED-RED 충돌 해결) ...
console.log(`${key} 삽입 후 밸런스를 스스로 맞춥니다.`);
}
}
const rbt = new RedBlackTree();
rbt.insert(10);
rbt.insert(20);
rbt.insert(30); // 10-20-30 일직선 시 Left-Rotate 발생!
