레드-블랙 트리

도입

레드-블랙 트리는 BST의 정렬 검색 성질은 유지하면서, 색 규칙과 회전(rotation)으로 트리 높이가 과하게 무너지는 것을 막는 균형 이진 검색 트리다.

AVL 트리가 높이 차이를 강하게 제한하는 방식으로 균형을 유지한다면, 레드-블랙 트리는 조금 더 느슨한 규칙으로 균형을 관리합니다. 대신 삽입과 삭제에서 필요한 재균형 패턴이 상대적으로 유연하고, 실제 라이브러리 구현에서 매우 널리 쓰입니다.

즉 레드-블랙 트리는 단순히 색이 붙은 BST가 아니라, 검색 규칙과 균형 규칙을 함께 유지해 ordered set/map 연산을 안정적으로 제공하려는 구조입니다.

그래서 레드-블랙 트리를 이해한다는 것은 BST 위에 균형을 어떻게 얹을지, 그리고 왜 실무 라이브러리들이 AVL 대신 이 구조를 자주 택하는지 이해하는 일과 연결됩니다.

필요성

정렬 기반 탐색이 필요하면서도 plain BST처럼 입력 순서에 따라 성능이 쉽게 무너지는 것은 피하고 싶을 때, 레드-블랙 트리는 가장 실무적인 균형 검색 트리 중 하나가 된다

일반 BST는 검색 규칙 자체는 훌륭하지만, 삽입 순서가 편향되면 한쪽으로 길게 무너질 수 있습니다. 이런 경우 탐색과 삽입, 삭제가 모두 긴 경로를 따라가게 되어 성능이 불안정해집니다.

레드-블랙 트리는 이 문제를 완화하기 위해, 각 노드에 색을 두고 red-red 금지와 black-height 규칙을 유지합니다. 이 규칙 덕분에 트리 높이가 로그 범위 안에 머물고, ordered map/set의 기본 연산을 안정적으로 유지할 수 있습니다.

특히 Java의 TreeMap처럼 정렬된 키 기반 map을 구현할 때 레드-블랙 트리가 자주 쓰이는 이유도 여기에 있습니다. 검색은 빠르고, 갱신은 균형 규칙으로 통제할 수 있기 때문입니다.

레드-블랙 트리가 특히 강한 지점

• 정렬된 키 기반 검색과 삽입·삭제를 함께 처리해야 할 때
• 최악의 경우에도 로그 높이를 보장하고 싶을 때
• ordered map, ordered set, range query 기반 자료구조가 필요할 때
• AVL보다 조금 느슨하지만 실용적인 균형 구조가 필요할 때

정의

레드-블랙 트리는 각 노드에 red 또는 black 색을 붙이고, red-red 금지와 동일한 black-height 규칙을 이용해 높이를 제한하는 nearly-balanced BST다

NIST 기준으로 레드-블랙 트리는 노드마다 추가 비트 하나를 사용해 균형을 유지하는 거의 균형 잡힌 트리입니다. 직관적으로는 어떤 leaf도 다른 leaf보다 루트에서 두 배 이상 멀어지지 않도록 통제됩니다.

GNU libavl 기준으로 balancing rule의 핵심은 두 가지입니다. 첫째, red 노드는 red 자식을 가질 수 없습니다. 둘째, 어떤 노드에서 말단 방향으로 내려가는 모든 단순 경로는 같은 수의 black 노드를 포함해야 합니다.

많은 구현은 여기에 root를 black으로 두는 추가 규칙을 함께 사용합니다. 이 조건은 개념의 본질은 아니지만 구현을 단순하게 만드는 데 자주 쓰입니다.

핵심 메시지

"레드-블랙 트리의 본질은 색 자체가 아니라

색 규칙으로 black-height를 통제해 BST의 높이를 로그 범위로 묶어 두는 데 있습니다."

핵심 원리

레드-블랙 트리의 핵심은 BST의 중위 순서는 보존하면서도, 색 변경과 회전으로 경로 길이가 과도하게 벌어지는 것을 막는 데 있다

검색 자체는 BST와 같습니다. 루트에서 시작해 작으면 왼쪽, 크면 오른쪽으로 내려갑니다. 따라서 읽기 연산의 논리는 plain BST와 다르지 않습니다.

차이는 수정 연산 뒤에 드러납니다. 삽입이나 삭제가 끝난 직후에는 red-red 위반이나 black-height 불균형이 생길 수 있습니다. 이때 recoloring과 rotation을 사용해 균형 규칙을 다시 맞춥니다.

중요한 점은 회전이 정렬을 깨뜨리는 재배열이 아니라, in-order 순서를 유지하면서 위아래 관계만 조정하는 지역적 연산이라는 것입니다. 그래서 검색 규칙은 그대로 두고도 높이만 통제할 수 있습니다.

즉 레드-블랙 트리는 “BST + 색 규칙 + 회전 복구”라는 세 층이 합쳐진 구조라고 보는 편이 가장 정확합니다.

Red-Black Tree Model
1) BST 규칙으로 탐색한다
2) 삽입 또는 삭제를 수행한다
3) 색 규칙 또는 black-height 규칙이 깨졌는지 본다
4) recoloring 과 rotation 으로 복구한다
5) ordered search 성질과 logarithmic height 를 함께 유지한다

핵심 불변식

레드-블랙 트리를 제대로 이해하려면 BST property 와 색 기반 balancing rule 을 동시에 보는 편이 가장 정확하다

불변식	의미	실무 해석
BST Property	왼쪽 서브트리 키 < 현재 키 < 오른쪽 서브트리 키	검색과 ordered traversal 의 기반
Color Bit	각 노드는 red 또는 black	균형 상태를 추적하는 추가 메타데이터
No Red-Red	red 노드는 red 자식을 가질 수 없음	너무 긴 빨간 연쇄를 막아 경로 폭주를 방지
Equal Black Height	같은 노드에서 내려가는 모든 경로가 같은 수의 black 노드를 가짐	경로 길이를 전역적으로 통제하는 핵심 규칙
Black Root (common convention)	많은 구현이 root 를 black 으로 둠	분석과 구현을 단순화하는 관례

기본 구조

레드-블랙 트리는 기본 BST 노드에 color 메타데이터를 추가하고, 필요에 따라 parent 참조를 함께 둬 회전과 재균형을 더 쉽게 처리하는 구조다

red-black-tree/
├── root
└── node
    ├── key
    ├── color (red / black)
    ├── left
    ├── right
    └── parent (often useful)

구조만 보면 일반 BST와 크게 다르지 않지만, 각 노드가 색을 하나 더 갖고 있고, 회전과 재균형 과정에서 부모 방향으로 올라갈 일이 많기 때문에 parent 포인터를 두는 구현이 흔합니다.

기본 구현

레드-블랙 트리 구현의 중심은 검색이 아니라 회전과 색 복구이며, 노드 구조와 회전 함수부터 정확해야 나머지 로직이 성립한다

enum Color {
    RED, BLACK
}

class Node {
    int key;
    Color color;
    Node left;
    Node right;
    Node parent;

    Node(int key, Color color) {
        this.key = key;
        this.color = color;
    }
}

Node rotateLeft(Node root, Node x) {
    Node y = x.right;
    x.right = y.left;
    if (y.left != null) y.left.parent = x;

    y.parent = x.parent;
    if (x.parent == null) {
        root = y;
    } else if (x == x.parent.left) {
        x.parent.left = y;
    } else {
        x.parent.right = y;
    }

    y.left = x;
    x.parent = y;
    return root;
}

Node rotateRight(Node root, Node y) {
    Node x = y.left;
    y.left = x.right;
    if (x.right != null) x.right.parent = y;

    x.parent = y.parent;
    if (y.parent == null) {
        root = x;
    } else if (y == y.parent.left) {
        y.parent.left = x;
    } else {
        y.parent.right = x;
    }

    x.right = y;
    y.parent = x;
    return root;
}

실전 포인트

레드-블랙 트리 구현에서 가장 자주 터지는 버그는 회전 자체보다도, 회전 후 부모 포인터와 루트 갱신이 빠지는 경우입니다. 그래서 insert/delete fixup 보다 먼저 left/right rotation 을 독립적으로 검증하는 편이 안전합니다.

패턴 1. 색 변경과 회전으로 복구한다

레드-블랙 트리의 수정 연산은 값을 넣고 빼는 것보다, 그 직후 색 위반과 black-height 위반을 recoloring 과 rotation 으로 복구하는 과정이 본질에 더 가깝다

삽입은 보통 BST처럼 leaf 쪽에 새 노드를 붙이고, 삭제도 BST처럼 successor 치환이나 splice를 이용합니다. 하지만 이 단계만으로는 레드-블랙 규칙이 보장되지 않습니다.

그래서 실제 핵심은 그 다음입니다. 색만 바꿔도 되는 경우가 있고, 회전이 필요한 경우가 있으며, 둘이 함께 들어가는 경우도 있습니다. 즉 검색 트리 연산 자체보다 “수정 후 복구”가 훨씬 큰 비중을 차지합니다.

Update Flow
1) BST 규칙으로 insert / delete
2) red-red 위반 또는 black-height 위반 확인
3) recoloring 적용
4) 필요하면 rotation 적용
5) root / parent / child 링크 재정렬
6) balancing rule 복구 확인

패턴 2. 2-4 트리 관점으로 보면 이해가 쉬워진다

Open Data Structures 는 레드-블랙 트리를 2-4 트리를 시뮬레이션한 구조로 설명하며, 이 관점을 잡으면 왜 recoloring 과 rotation 이 필요한지 훨씬 자연스럽게 보인다

ODS는 레드-블랙 트리를 단순 색칠된 BST로만 보지 않고, 2-4 트리를 이진 트리로 시뮬레이션한 구조로 설명합니다. 이 관점에서는 split, merge, borrow 같은 연산이 색 변경과 회전으로 나타납니다.

즉 색은 장식이 아니라, 상위의 다진수 검색 트리 구조를 이진 트리 안에서 흉내 내기 위한 표현 장치라고 볼 수 있습니다. 이 관점을 잡으면 복잡한 케이스 분기가 조금 더 체계적으로 보입니다.

패턴 3. AVL 보다 느슨하지만 실무에서 많이 쓴다

레드-블랙 트리는 AVL 보다 덜 빡빡하게 균형을 잡지만, 수정 연산에서의 재균형 비용과 라이브러리 구현 관점에서는 더 실용적인 선택이 되는 경우가 많다

GNU libavl은 레드-블랙 트리가 AVL보다 최대 높이가 더 크다고 설명합니다. 즉 같은 노드 수라면 AVL이 더 촘촘하게 균형을 맞춥니다.

반면 같은 문서는 AVL 삭제가 경우에 따라 log2(n) 회전이 필요할 수 있지만, 레드-블랙 트리 삭제는 세 번을 넘는 회전을 요구하지 않는다고 설명합니다. ODS도 update당 회전 수가 amortized constant라고 정리합니다.

그래서 레드-블랙 트리는 AVL보다 덜 엄격한 대신, 업데이트 재균형이 실무 라이브러리 구현에 더 잘 맞는 균형점으로 자주 선택됩니다. Java TreeMap이 대표적인 예입니다.

핵심 포인트

레드-블랙 트리가 많이 쓰이는 이유는 AVL보다 “더 균형 잡혀서”가 아닙니다. 균형을 조금 덜 엄격하게 잡는 대신, ordered map/set 구현에서 충분한 로그 높이와 실용적인 update 비용을 동시에 제공하기 때문입니다.

한계와 주의점

레드-블랙 트리는 강력하지만, plain BST 보다 구현 복잡도가 크게 올라가고 불변식이 두 겹이라 작은 실수도 전체 구조를 쉽게 무너뜨린다

ODS도 레드-블랙 트리의 장점 뒤에는 구현 복잡도가 따른다고 분명히 말합니다. 높이 상한과 수정 연산 효율을 얻는 대신, 색 규칙과 회전 케이스를 정확히 처리해야 합니다.

즉 레드-블랙 트리는 “BST에 색만 하나 추가하면 끝”인 구조가 아닙니다. 회전 한 번, recoloring 한 번이 잘못되면 ordered traversal은 맞는데 balancing이 깨지거나, balancing은 맞는 것처럼 보여도 BST property가 깨질 수 있습니다.

그래서 실무에서는 직접 구현보다 검증된 라이브러리를 쓰는 편이 일반적이고, 학습 목적이라면 불변식 검사기와 함께 구현하는 편이 훨씬 안전합니다.

주의해야 할 지점

• BST property 와 red-black balancing rule 을 동시에 유지해야 함
• 회전 후 parent / root / child 포인터 갱신을 놓치기 쉬움
• 색 규칙만 맞고 black-height 가 깨지는 버그가 자주 생김
• 삭제는 삽입보다 케이스 분기가 더 복잡하게 느껴질 수 있음

자주 하는 실수

레드-블랙 트리를 어렵게 만드는 가장 흔한 원인은 색 규칙만 외우고, 그 규칙이 왜 높이 상한과 연결되는지까지는 같이 보지 않는 데 있다

• 레드-블랙 트리는 그냥 “색칠된 AVL”이라고 단순화함
• root가 black인지 여부만 보고 핵심 balancing rule 을 놓침
• 회전만 맞으면 색은 대충 처리해도 된다고 생각함
• insert fixup 과 delete fixup 을 같은 난이도로 생각함
• inorder 정렬 순서 검증 없이 색 정보만 보고 맞다고 판단함
• TreeMap 이 레드-블랙 트리라는 사실만 알고 ordered semantics 는 놓침

실무 루틴

레드-블랙 트리를 다룰 때는 먼저 ordered map/set 요구가 분명한지 확인하고, 직접 구현한다면 회전 함수와 불변식 검사부터 먼저 고정하는 편이 가장 안전하다

1. 먼저 문제에 ordered search / ordered map / ordered set 이 정말 필요한지 확인한다.
2. plain BST 로 충분한지, 아니면 worst-case 로그 높이 가 필요한지 판단한다.
3. 직접 구현한다면 left/right rotation 을 먼저 독립적으로 검증한다.
4. BST property, no red-red, equal black height 검사 함수를 따로 만든다.
5. insert 와 delete fixup 은 따로 테스트하고, 특히 delete 는 root replacement 와 black-height 를 집중 검증한다.
6. 실서비스에서는 가능하면 검증된 라이브러리 구조를 우선 사용한다.

디버깅

레드-블랙 트리 디버깅은 색만 보는 것이 아니라, 중위 순서와 red-red 금지와 black-height 가 동시에 맞는지 확인하는 과정이다

1

먼저 중위 순회 결과가 정렬 순으로 나오는지 확인해 BST property 를 본다.

2

red 노드가 red 자식을 가지는 곳이 없는지 전수 검사한다.

3

각 노드에서 말단 방향 경로들의 black count 가 같은지 확인한다.

4

회전 뒤 부모 포인터, 루트 교체, 자식 재연결이 모두 반영됐는지 본다.

5

성능이 이상하면 height bound 가 실제로 깨졌는지, 혹은 fixup 이 중간에 빠졌는지 확인한다.

점검 체크리스트
- inorder 결과가 정렬 순인가
- red 노드가 red 자식을 가지는가
- black-height 가 모든 경로에서 같은가
- 회전 후 root / parent / child 링크가 정상인가
- insert / delete fixup 이 끝까지 수행됐는가

요약

레드-블랙 트리의 핵심은 BST의 ordered search 성질을 유지하면서, 색 규칙과 black-height 규칙과 회전 복구를 통해 높이를 로그 범위로 묶어 두는 데 있으며, 이 특성 때문에 ordered map/set 구현에서 매우 널리 쓰인다

• ✅ 레드-블랙 트리는 색 비트를 추가한 nearly-balanced BST 다.
• ✅ 핵심 규칙은 no red-red 와 equal black height 다.
• ✅ 루트가 black 인 구현이 흔하지만 본질은 색 규칙과 black-height 유지에 있다.
• ✅ 높이는 로그 범위로 제한되며 검색·삽입·삭제는 O(log n) 범위에 머문다.
• ✅ 수정 연산의 핵심은 recoloring 과 rotation 을 통한 fixup 이다.
• ✅ 2-4 tree 관점으로 보면 왜 split/merge 와 비슷한 동작이 필요한지 이해가 쉬워진다.
• ✅ AVL 보다 덜 엄격하게 균형을 잡지만 실무 라이브러리에서 매우 널리 쓰인다.
• ✅ Java TreeMap 같은 ordered map 구현의 대표적인 기반 자료구조다.

 

RELATED POST

AVL 트리와 레드-블랙 트리는 무엇이 다를까
TreeMap 은 왜 레드-블랙 트리를 사용할까
rotation 은 어떻게 BST 순서를 보존할까

 

REFERENCE

red-black tree
left rotation
right rotation
Open Data Structures - Red-Black Trees
GNU libavl - Red-Black Trees
GNU libavl - RB Balancing Rule
GNU libavl - Analysis of Red-Black Balancing Rule
JDK TreeMap