Red-Black 트리
Red-Black 트리는 이진 탐색 트리의 한 종류로,
노드에 색상 정보를 추가하여 트리의 균형이 너무 무너지지 않도록 관리하는 자가 균형 이진 탐색 트리이다.
AVL 트리처럼 항상 엄격하게 균형을 맞추지는 않지만,
삽입과 삭제 과정에서 일정한 규칙을 유지하여 트리의 높이를 O(log N) 범위로 제한한다.
Red-Black 트리가 필요한 이유
이진 탐색 트리는 입력 순서에 따라 한쪽으로 치우친 편향 트리가 될 수 있다.
이 경우
- 탐색 시간 복잡도:
O(N) - 삽입 시간 복잡도:
O(N) - 삭제 시간 복잡도:
O(N)
이러한 문제를 줄이기 위해
Red-Black 트리는 색상 규칙과 회전을 이용해 트리의 높이가 지나치게 커지는 것을 방지한다.
노드의 색상
Red-Black 트리의 각 노드는 다음 두 가지 색상 중 하나를 가진다.
- Red
- Black
색상은 단순한 표시가 아니라,
트리의 균형 상태를 판단하고 유지하기 위한 규칙에 사용된다.
Red-Black 트리의 성질
Red-Black 트리는 다음 성질을 만족해야 한다.
1. 모든 노드는 Red 또는 Black이다
각 노드는 반드시 두 색상 중 하나를 가진다.
2. 루트 노드는 Black이다
트리의 시작점인 루트는 항상 Black이어야 한다.
3. 모든 리프 NIL 노드는 Black이다
실제 데이터를 가지지 않는 NIL 노드(끝을 나타내는 가상 노드)는 모두 Black으로 본다.
4. Red 노드의 자식은 모두 Black이다
즉, Red 노드가 연속해서 나타날 수 없다.
이를 통해 한쪽으로 길게 치우치는 구조를 방지한다.
5. 어떤 노드에서 출발하더라도, 그 노드로부터 모든 NIL 리프까지 가는 경로의 Black 노드 수는 같다
이 값을 보통 Black Height 라고 한다.
이 성질 덕분에 트리 전체 높이가 크게 무너지지 않는다.
핵심 개념
Red-Black 트리는 AVL 트리처럼
높이를 정확하게 맞추는 방식이 아니라,
Black 노드 수의 균형과 Red 연속 금지를 통해 대략적인 균형을 유지한다.
즉,
- AVL 트리: 더 엄격한 균형
- Red-Black 트리: 조금 느슨하지만 회전이 덜 자주 발생
이라는 차이가 있다.
삽입 시 기본 규칙
새로운 노드는 기본적으로 Red 로 삽입한다.
이유는
새 노드를 Black으로 넣으면 Black Height가 바로 변할 수 있기 때문이다.
반면 Red로 넣으면 일단 Black Height 변화 없이 삽입할 수 있다.
하지만 Red로 넣으면
부모도 Red인 경우 Red-Red 충돌이 발생할 수 있다.
이 경우 색상 변경(Recoloring)과 회전(Rotation)을 통해 문제를 해결한다.
삽입 후 확인해야 할 문제
삽입 후 가장 먼저 보는 것은 다음이다.
- 새 노드가 Red
- 부모도 Red
이 경우 Red-Black 트리의 성질 중
Red 노드의 자식은 모두 Black이어야 한다 는 규칙이 깨진다.
따라서 이 충돌을 해결해야 한다.
삽입 시 대표 상황 정리
삽입 시에는 보통 부모, 삼촌, 조부모 의 색과 위치를 기준으로 처리한다.
- 부모(Parent)
- 삼촌(Uncle)
- 조부모(Grandparent)
경우 1. 부모가 Black인 경우
아무 문제 없다.
- 새 노드는 Red
- 부모가 Black이면 Red-Red 충돌이 발생하지 않음
따라서 추가 작업 없이 종료한다.
경우 2. 부모가 Red이고, 삼촌도 Red인 경우
이 경우는 주로 색상 재조정(Recoloring) 으로 해결한다.
처리
- 부모를 Black으로 변경
- 삼촌을 Black으로 변경
- 조부모를 Red로 변경
이렇게 하면
부모와 삼촌 쪽의 Red-Red 충돌은 사라진다.
하지만 조부모가 Red가 되면서
조부모와 그 위의 부모 사이에 새로운 충돌이 생길 수 있으므로
조부모를 기준으로 다시 위쪽을 확인해야 한다.
경우 3. 부모가 Red이고, 삼촌이 Black이며 직선 형태인 경우
직선 형태란 다음과 같은 경우이다.
- LL 형태
- RR 형태
이 경우는 회전 1번 + 색상 변경으로 해결한다.
LL 형태
- 부모는 조부모의 왼쪽 자식
- 새 노드는 부모의 왼쪽 자식
처리
- 조부모 기준으로 Right Rotation
- 회전 후 부모와 조부모의 색을 교환
RR 형태
- 부모는 조부모의 오른쪽 자식
- 새 노드는 부모의 오른쪽 자식
처리
- 조부모 기준으로 Left Rotation
- 회전 후 부모와 조부모의 색을 교환
경우 4. 부모가 Red이고, 삼촌이 Black이며 꺾인 형태인 경우
꺾인 형태란 다음과 같은 경우이다.
- LR 형태
- RL 형태
이 경우는 회전 2번 + 색상 변경이 필요하다.
LR 형태
- 부모는 조부모의 왼쪽 자식
- 새 노드는 부모의 오른쪽 자식
처리 순서
- 부모 기준으로 Left Rotation
- 조부모 기준으로 Right Rotation
- 회전 후 새롭게 올라온 노드와 조부모의 색을 조정
RL 형태
- 부모는 조부모의 오른쪽 자식
- 새 노드는 부모의 왼쪽 자식
처리 순서
- 부모 기준으로 Right Rotation
- 조부모 기준으로 Left Rotation
- 회전 후 새롭게 올라온 노드와 조부모의 색을 조정
삽입 정리
삽입 시 핵심은 다음 두 가지이다.
- Red-Red 충돌이 있는가
- 삼촌의 색이 Red인가, Black인가
즉,
- 삼촌이 Red 이면 주로 색상 변경
- 삼촌이 Black 이면 주로 회전 + 색상 변경
으로 이해하면 된다.
삭제는 왜 더 어려운가
Red-Black 트리에서 삭제는 삽입보다 복잡하다.
이유는
Black 노드를 삭제할 경우
경로별 Black Height가 달라질 수 있기 때문이다.
특히 삭제 후 Double Black 이라는 개념으로 문제를 다루는 경우가 많다.
즉,
어떤 위치가 원래보다 Black을 하나 더 가져야 하는 상태처럼 보고
형제 노드의 색과 자식의 색을 기준으로 문제를 해결한다.
삭제에서 보는 대상
삭제 후에는 보통 다음을 본다.
- 현재 노드
- 형제 노드
- 형제의 자식들
- 부모 노드
삭제는 경우의 수가 많기 때문에
처음 정리할 때는 삽입처럼 전부 외우기보다
다음 관점으로 이해하는 것이 좋다.
삭제 핵심 관점
- 삭제된 Black을 어떻게 보충할 것인가
- 형제가 Red인가, Black인가
- 형제의 자식 중 Red가 있는가
AVL 트리와의 차이
AVL 트리
- 높이 균형을 더 엄격하게 맞춘다
- 탐색 성능이 더 안정적이다
- 삽입/삭제 시 회전이 더 자주 일어날 수 있다
Red-Black 트리
- 균형 조건이 더 완화되어 있다
- 삽입/삭제 성능이 실무에서 유리한 경우가 많다
map,set같은 자료구조 구현에 자주 사용된다
정리할 때 기억할 핵심
- Red-Black 트리는 색상 규칙으로 균형을 유지한다
- Red가 연속되면 안 된다
- 모든 경로의 Black 노드 수는 같아야 한다
- 삽입은 주로 Red-Red 충돌 해결
- 삭제는 주로 Black Height 보정
한 줄 요약
Red-Black 트리는
색상 규칙, 회전, 색상 변경을 이용해
트리의 균형이 크게 무너지지 않도록 유지하는 자가 균형 이진 탐색 트리이다.
AVL vs Red-Black 트리 비교
| 항목 | AVL 트리 | Red-Black 트리 |
|---|---|---|
| 균형 기준 | 높이 차이 | 색상 규칙 |
| 균형 정도 | 매우 엄격 | 완화됨 |
| 탐색 성능 | 더 빠름 (균형 좋음) | 약간 느릴 수 있음 |
| 삽입/삭제 | 회전 많음 | 회전 적음 |
| 구현 난이도 | 비교적 단순 | 더 복잡 |
| 실무 사용 | 상대적으로 적음 | 매우 많음 |
핵심 차이
- AVL: 탐색 최적화
- Red-Black: 삽입/삭제 효율
사용 예
- AVL: 읽기 위주 시스템
- Red-Black: 수정이 잦은 시스템
한 줄 비교
AVL은 “정확한 균형”
Red-Black은 “적당한 균형”