Red-Black 트리 원리: 색과 검은 높이로 균형 읽기

적흑 트리는 모든 노드의 높이를 똑같이 맞추는 대신, 빨간 노드가 연속하지 않고 모든 아래쪽 경로의 검은 노드 수가 같게 유지하여 긴 편향을 막습니다.

선수 지식: 이진 탐색 트리, 루트와 잎, 경로의 길이

• 검은 높이를 한 가지 기준으로 셉니다.
• 검색 순서와 색 조건을 각각 검사합니다.
• 일반 적흑 트리와 LLRB의 추가 규칙을 구분합니다.

없는 자식도 검은 끝점으로 셉니다

적흑 트리도 먼저 이진 탐색 트리입니다. 현재 키보다 작은 값은 왼쪽, 큰 값은 오른쪽에 있어야 합니다. 이 글은 중복 없는 안전한 정수 키만 다룹니다. 노드에는 검정 또는 빨강 중 하나의 색이 있고, 루트는 검정입니다. 자식이 없는 연결도 검정인 끝점으로 생각합니다. 구현에 가짜 노드를 만들지 않아도 빈 연결을 검사할 때 같은 규칙을 적용할 수 있습니다.

핵심은 두 조건입니다. 빨간 노드의 자식은 모두 검정이어야 하며, 한 노드에서 아래의 모든 빈 연결까지 가는 경로의 검은 노드 수가 같아야 합니다. 이 글의 검사기는 현재 노드와 마지막 빈 연결을 포함해 검은 높이를 셉니다. 다른 책이 시작 노드를 제외하더라도 한 구현 안에서 기준을 섞지 않으면 경로가 같은지 비교하는 목적은 같습니다.

그림 대신 부모와 자식의 관계를 표로 적어도 불변식을 읽을 수 있습니다. 루트 2가 검정이고 자식 1과 3이 빨강인 트리를 생각해 보세요. 각 경로에는 검정인 2와 검정인 빈 연결이 있어 검은 높이는 2입니다. 빨강인 자식은 빈 연결만 가지므로 빨강 연속도 없습니다. 따라서 양쪽에 빨간 자식이 있다는 이유만으로 일반 적흑 트리를 잘못되었다고 판단해서는 안 됩니다.

검은 높이가 전체 높이를 제한하는 이유를 봅니다

검은 노드 사이에는 빨간 노드가 최대 하나만 들어갈 수 있습니다. 그래서 같은 검은 높이를 가진 두 경로 중 가장 긴 쪽도 검은 노드마다 빨강을 하나씩 끼워 넣는 정도로만 길어집니다. 짧은 경로는 거의 검정만 있을 수 있고 긴 경로는 검정과 빨강이 번갈아 나올 수 있지만 빨강 두 개가 붙어 길어지는 일은 허용하지 않습니다.

또한 모든 경로에 같은 수의 검은 노드가 있다는 조건은 한쪽만 깊게 뻗는 구조를 제한합니다. 검은 높이가 늘 때마다 양쪽에 필요한 부분 트리의 최소 크기도 함께 늘어납니다. 이 두 사실을 합치면 키가 많아져도 높이는 로그에 비례하게 됩니다. 각 노드의 자식 높이 차이를 1 이하로 유지하는 AVL과는 균형을 표현하는 방식이 다르지만, 탐색이 루트에서 한 경로만 따라간다는 점은 같습니다.

색만 무작위로 바꿔 이 조건을 맞출 수는 없습니다. BST 순서가 깨진 노드에 검은색을 칠해도 탐색은 실패합니다. 반대로 순서만 맞고 검은 높이가 다르면 최악의 탐색 경로가 길어질 수 있습니다. 따라서 검사 순서는 키의 엄격한 범위, 색의 유효성, 빨강 연속 여부, 왼쪽과 오른쪽 검은 높이의 일치로 나눕니다. 어느 조건이 깨졌는지 구체적으로 알 수 있어야 회전과 색 변환의 역할도 분명해집니다.

작은 트리 두 개의 경로를 비교합니다

첫 트리는 왼쪽과 오른쪽을 재귀 검사하면 각 자식에서 검은 높이 1을 반환합니다. 루트는 양쪽 결과가 같음을 확인하고 자신의 검정 하나를 더해 2를 반환합니다. 두 번째 트리는 왼쪽에서 2를 받지만 오른쪽 빈 연결에서는 1을 받아 즉시 차이를 발견합니다. 높이를 눈으로 어림잡는 대신 같은 계산을 모든 노드에서 반복하는 방식입니다.

검사 예제의 성공 결과에는 노드 수와 검은 높이가 함께 나옵니다. 실패 결과에는 순서 위반, 빨강 연속, 검은 높이 불일치처럼 첫 원인을 담습니다. 이 검사기는 일반 적흑 조건을 확인하므로 오른쪽의 빨간 연결도 허용합니다. 입력은 유한한 비순환 트리라는 전제이며, 임의의 순환 객체를 탐지하는 그래프 검사기는 아닙니다.

LLRB는 일반 조건에 왼쪽 규칙을 더합니다

좌편향 적흑 트리인 LLRB는 빨간 연결을 왼쪽으로 향하게 유지하는 변형입니다. 빨간 연결은 부모와 자식을 하나의 묶음으로 읽는 표시이며 왼쪽 규칙을 더하면 같은 논리적 묶음을 표현하는 방향을 통일할 수 있습니다. 이어지는 삽입과 삭제 예제는 이 변형을 사용합니다. 일반 적흑 트리에서 유효한 빨간 오른쪽 자식도 LLRB의 작업 완료 상태에서는 허용하지 않습니다.

이 글의 일반 검사기는 그 추가 방향 조건을 일부러 검사하지 않습니다. 일반 적흑 불변식과 특정 구현의 표현 규칙을 구분하기 위해서입니다. 삽입·삭제 구현을 검증할 때는 일반 조건에 더해 빨간 오른쪽 연결이 없는지도 확인합니다. 작업 도중에는 임시로 색이나 방향 조건이 달라질 수 있으므로 공개 연산이 끝나고 루트를 검정으로 되돌린 시점을 기준으로 검사합니다.

학습할 때 회전 그림의 모양을 외우기보다 어떤 조건을 회복하는지 먼저 말해 보세요. 회전은 정렬 순서를 유지하며 연결 방향을 바꾸고, 색 변환은 논리적 묶음을 나누거나 합칩니다. 두 작업을 알맞게 결합해야 검은 높이를 지킬 수 있습니다. 다음 예제의 코드를 읽을 때도 함수 이름보다 회전 전후의 경로에서 검은 수가 왜 유지되는지를 설명하는 연습이 도움이 됩니다.

전체 코드와 직접 실행

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

function inspectRB(root) {
  try {
    if (root && root.red !== false) throw new Error('root must be black');
    function visit(node, low, high) {
      if (!node) return { size: 0, blackHeight: 1 };
      if (!Number.isSafeInteger(node.key) || node.key <= low || node.key >= high) {
        throw new Error('strict BST order required');
      }
      if (typeof node.red !== 'boolean') throw new Error('color must be boolean');
      if (node.red && (node.left?.red || node.right?.red)) {
        throw new Error('consecutive red nodes');
      }
      const left = visit(node.left, low, node.key);
      const right = visit(node.right, node.key, high);
      if (left.blackHeight !== right.blackHeight) throw new Error('black height mismatch');
      return {
        size: 1 + left.size + right.size,
        blackHeight: left.blackHeight + (node.red ? 0 : 1)
      };
    }
    return { valid: true, ...visit(root, -Infinity, Infinity) };
  } catch (error) {
    return { valid: false, error: error.message };
  }
}
const validTree = {
  key: 2, red: false,
  left: { key: 1, red: true, left: null, right: null },
  right: { key: 3, red: true, left: null, right: null }
};
const invalidTree = { key: 2, red: false, left: { key: 1, red: false }, right: null };
console.log(JSON.stringify(inspectRB(validTree)));
console.log(inspectRB(invalidTree).valid);

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

{"valid":true,"size":3,"blackHeight":2}
false

비용과 적용 범위

유효한 적흑 트리의 높이는 O(log N)이므로 한 경로의 탐색은 O(log N)입니다. 이 글의 전체 검사기는 모든 노드를 보므로 O(N) 시간, O(H) 재귀 공간입니다. 검사할 입력이 잘못 편향되었다면 H가 N이 될 수 있습니다.

직접 확인해 보기

루트 1B의 오른쪽에 잎 2R만 있다면 일반 RB와 LLRB 중 어디에서 허용하나요?

함께 읽을 글

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

참고 자료

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