Red-Black 트리 삽입: LLRB 회전과 색 변환

LLRB 삽입은 새 키를 빨간 잎으로 넣고 재귀가 돌아오면서 연결 방향·빨강 연속·색 묶음을 순서대로 고칩니다. 마지막에는 루트를 검정으로 만들어 다음 연산의 출발 조건을 회복합니다.

선수 지식: BST 삽입, 적흑 트리 불변식, 왼쪽·오른쪽 회전

• 새 잎을 빨강으로 만드는 이유를 설명합니다.
• 세 가지 복구를 정해진 순서로 적용합니다.
• 모든 삽입 후 순서·색·검은 높이·크기를 점검합니다.

검은 높이를 늘리지 않는 빨간 잎으로 시작합니다

먼저 보통의 BST처럼 키를 비교하여 빈 자리를 찾습니다. 새 노드는 빨강으로 만듭니다. 검은 빈 연결 하나를 빨간 노드와 그 아래의 검은 빈 연결로 바꾸면 그 경로의 검은 수가 늘지 않기 때문입니다. 검은 잎을 바로 넣으면 그 경로에만 검정 하나가 추가되어 다른 경로와 검은 높이가 달라집니다. 빨강 삽입도 부모가 빨강이면 연속 조건을 위반하므로 위로 돌아오며 복구해야 합니다.

이 글은 일반 적흑 트리의 한 변형인 LLRB를 구현합니다. 완료된 트리는 루트 검정, 빨강 연속 금지, 같은 검은 높이라는 일반 조건과 함께 빨간 연결이 왼쪽으로만 향한다는 조건을 만족합니다. 첨부 자료처럼 부모와 삼촌의 색을 분기하는 일반 구현과 코드 구조가 다릅니다. 어느 방식이든 규칙을 한 세트로 유지해야 하며 서로의 일부 분기만 섞으면 올바름을 보장할 수 없습니다.

키는 안전한 정수이며 중복은 하나만 저장합니다. 같은 키를 다시 넣으면 새 노드를 만들지 않고 거짓을 반환합니다. 크기는 실제 노드 수를 나타냅니다. 예제에는 부모 포인터가 없고, 자식 연결과 새 부분 트리 루트를 재귀 반환으로 전달합니다. 회전 함수가 돌려주는 루트를 무시하면 고친 부분 트리가 부모에게 연결되지 않는다는 점은 AVL과 같습니다.

방향·연속·묶음 순서로 세 조건을 고칩니다

첫째, 오른쪽 연결이 빨강이고 왼쪽이 빨강이 아니면 왼쪽으로 회전합니다. 오른쪽으로 붙은 같은 묶음을 왼쪽 표현으로 돌리는 단계입니다. 올라온 노드는 이전 루트의 색을 이어받고 내려온 노드는 빨강이 됩니다. 키 순서만 바꾸고 색을 그대로 두면 이전의 검은 높이가 유지되지 않을 수 있으므로 색 처리도 회전의 일부입니다.

둘째, 왼쪽 자식과 그 왼쪽 자식이 모두 빨강이면 오른쪽으로 회전합니다. 한 경로의 빨강 연속을 펴서 가운데 키를 위로 올립니다. 셋째, 양쪽 자식이 모두 빨강이면 부모와 두 자식의 색을 뒤집습니다. 삽입에서는 아래로 이어졌던 묶음을 위쪽으로 넘기는 효과가 있으며 양쪽 경로의 검은 수는 함께 변합니다. 위쪽에 새 빨강 연속이 생기면 다음 재귀 반환에서 같은 규칙으로 처리합니다.

이 세 조건은 서로 배타적인 선택지가 아닙니다. 한 번의 반환에서 회전 뒤 색 변환까지 이어질 수 있으므로 각각 순서 있는 조건문으로 둡니다. 회전 후에는 자식 구성이 바뀌었으므로 다음 조건은 바뀐 노드를 기준으로 읽어야 합니다. 마지막에 자식 크기와 현재 노드 하나를 합해 크기를 고치면 회전된 부분 트리의 크기도 일치합니다.

3, 1, 2를 넣어 가운데 키가 올라오는 과정을 봅니다

마지막 결과의 중위 순서는 [1,2,3]입니다. 단순히 2가 가운데 값이어서 선택한 것이 아니라, BST의 빈 자리에 추가한 뒤 방향 규칙과 빨강 연속을 고치면서 그 모양에 도달했습니다. 이 순서를 이해하면 다음에 5와 4가 들어와도 전체 트리를 정렬해서 다시 만들 필요가 없다는 점이 보입니다. 각 삽입은 자신의 탐색 경로만 고칩니다.

최종 루트를 검정으로 만드는 단계는 색 분리와 구분합니다. 루트에서 색 분리가 일어나면 루트가 빨강이 될 수 있는데 그 위에는 검은 높이를 맞출 부모가 없습니다. 루트를 검정으로 바꾸면 모든 루트 경로의 검은 수가 함께 하나 늘어나므로 경로 간 동일성은 유지됩니다. 이 처리를 재귀의 모든 노드에 적용하면 의미가 달라지므로 공개 삽입의 맨 끝에서 한 번만 합니다.

정렬된 입력에서도 매 단계의 불변식을 확인합니다

오름차순 키를 넣으면 일반 BST는 오른쪽으로 길게 뻗지만 LLRB는 오른쪽 빨강을 즉시 회전하고 필요하면 색을 나누어 높이를 제한합니다. 다만 최종 정렬 배열만 확인해서는 중간에 깨진 색이나 잘못 저장된 크기를 발견하지 못할 수 있습니다. 삽입 하나가 끝날 때마다 루트 검정, 오른쪽 빨강 없음, 빨강의 자식 검정, 양쪽 검은 높이 동일을 모두 검사해야 합니다.

검증은 자식의 검사 결과를 부모로 올리는 방식으로 작성할 수 있습니다. 빈 연결은 검은 높이 1을 반환하고 부모는 두 값이 같은지 비교한 뒤 자신이 검정이면 1을 더합니다. 동시에 키의 하한과 상한을 내려 보내 전체 BST 순서를 확인합니다. 바로 옆 자식과만 비교하면 손자가 조상의 범위를 벗어난 경우를 놓치므로 전체 범위를 전달해야 합니다.

빈 트리, 한 키, 같은 키 반복, 음수 키, 오름차순과 내림차순을 나누어 실습해 보세요. 숫자가 아닌 값이나 비교 순서가 성립하지 않는 값은 삽입 전에 거부합니다. 안전한 정수만 받는 계약 덕분에 비교와 중복 판정이 일관됩니다. 삭제 예제도 같은 삽입과 회전 규칙을 포함하므로 두 예제를 이어 읽을 때 서로 다른 색 규약을 새로 외울 필요가 없습니다.

전체 코드와 직접 실행

개념을 읽었다면 아래 예제를 직접 실행하며 상태 변화를 확인할 수 있습니다.

function requireKey(key) {
  if (!Number.isSafeInteger(key)) throw new TypeError('key must be a safe integer');
}
class RBNode {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
    this.red = true;
    this.size = 1;
  }
}
function isRed(node) { return node !== null && node.red; }
function sizeOf(node) { return node ? node.size : 0; }
function refresh(node) {
  node.size = 1 + sizeOf(node.left) + sizeOf(node.right);
  return node;
}
function rotateLeft(node) {
  const top = node.right;
  node.right = top.left;
  top.left = node;
  top.red = node.red;
  node.red = true;
  refresh(node);
  return refresh(top);
}
function rotateRight(node) {
  const top = node.left;
  node.left = top.right;
  top.right = node;
  top.red = node.red;
  node.red = true;
  refresh(node);
  return refresh(top);
}
function flipColors(node) {
  node.red = !node.red;
  node.left.red = !node.left.red;
  node.right.red = !node.right.red;
}
function balance(node) {
  if (isRed(node.right) && !isRed(node.left)) node = rotateLeft(node);
  if (isRed(node.left) && isRed(node.left.left)) node = rotateRight(node);
  if (isRed(node.left) && isRed(node.right)) flipColors(node);
  return refresh(node);
}
function insertNode(node, key) {
  if (!node) return new RBNode(key);
  if (key < node.key) node.left = insertNode(node.left, key);
  else if (key > node.key) node.right = insertNode(node.right, key);
  else return node;
  return balance(node);
}
class RedBlackTree {
  constructor() { this.root = null; }
  get size() { return sizeOf(this.root); }
  has(key) {
    requireKey(key);
    let node = this.root;
    while (node) {
      if (key === node.key) return true;
      node = key < node.key ? node.left : node.right;
    }
    return false;
  }
  insert(key) {
    requireKey(key);
    const before = this.size;
    this.root = insertNode(this.root, key);
    this.root.red = false;
    return this.size !== before;
  }
  values() {
    const result = [];
    function visit(node) {
      if (!node) return;
      visit(node.left); result.push(node.key); visit(node.right);
    }
    visit(this.root);
    return result;
  }
}
const tree = new RedBlackTree();
[3, 1, 2, 5, 4].forEach(key => tree.insert(key));
console.log(JSON.stringify(tree.values()));
console.log(JSON.stringify({ size: tree.size, rootBlack: !tree.root.red }));

node algorithm-red-black-tree-insertion.mjs

[1,2,3,4,5]
{"size":5,"rootBlack":true}

비용과 적용 범위

유효한 LLRB에 키 N개가 있을 때 삽입과 존재 검사는 O(log N) 시간, 재귀 삽입의 추가 공간은 O(log N)입니다. 부분 트리마다 상수 번 회전·색 변환·크기 갱신을 합니다. values()는 O(N) 시간과 O(N) 결과 공간을 사용합니다.

직접 확인해 보기

빈 트리에 1, 2를 넣으면 1B의 오른쪽 2R을 그대로 둘 수 있나요?

함께 읽을 글

• JavaScript 이진 탐색 트리 구현: 중복 키와 세 가지 삭제 처리 — 균형 복구와 별개인 BST 삭제의 세 가지 구조를 확인합니다.
• JavaScript AVL 트리: 높이 불변식과 LL·RR·LR·RL 삽입 회전 — 삭제 전에 높이 갱신과 네 방향 회전의 연결 관계를 복습합니다.
• 트리 자료구조 차이: 이진 트리 BST MST 구분하기 — 정렬을 위한 탐색 트리와 다른 트리의 목적을 구분합니다.

참고 자료

• Algorithms, 4th Edition — Balanced Search Trees — 균형 탐색 트리의 높이, 2–3 트리와 좌편향 적흑 트리의 대응, 회전·색 변환을 설명하는 저자 자료입니다. 예제의 추적과 검사는 직접 작성했습니다.