레드-블랙 트리 시각화
삽입·삭제 시 색상 규칙과 회전 연산으로 균형을 유지하는 자가균형 BST를 단계별로 학습하세요
자료구조★★★
속도
1 / 1노드 수: 0트리 높이: 0블랙 높이: 1
연산 선택
빨간 노드검은 노드현재 노드회전 중색상 변경 중삽입됨
레드-블랙 규칙
- 모든 노드는 빨간색 또는 검은색
- 루트는 항상 검은색
- 빨간 노드의 자식은 모두 검은색
- 루트까지 모든 경로의 블랙 높이가 동일
레드-블랙 트리가 어떻게 색상 규칙으로 균형을 유지하는지 관찰하세요.
비교
삽입
색상 변경
회전
값을 입력하고 실행을 눌러 시작하세요.
레드-블랙 트리란?
각 노드에 빨강/검정 색상을 부여하고 5가지 규칙을 유지하여 최악 O(log n) 검색을 보장하는 자가균형 이진탐색트리입니다. Java TreeMap, C++ std::map의 내부 구조입니다.
사용 방법
- 1값을 입력하고 삽입 버튼을 클릭하세요
- 2삽입 후 색상 변경과 회전 과정을 단계별로 확인하세요
- 3노드를 클릭하여 삭제할 수 있습니다
- 4랜덤 버튼으로 여러 값을 빠르게 추가해보세요
동작 원리
- 1새 노드는 항상 빨간색으로 삽입됩니다
- 2부모가 빨간색이면 규칙 위반 → 삼촌 노드 색상에 따라 리컬러링 또는 회전 수행
- 3회전(좌/우)으로 트리 구조를 재배치하여 균형을 회복합니다
- 4삭제 시에는 이중 검정(Double Black) 처리로 블랙 높이를 유지합니다
실무 활용
- •Java TreeMap/TreeSet, C++ std::map/std::set의 내부 구현
- •Linux 커널 CFS 스케줄러의 프로세스 관리
- •데이터베이스 인메모리 인덱스 구조
- •Java HashMap(8+)의 버킷 충돌 시 트리 변환
비슷한 알고리즘
- •AVL 트리 vs 레드-블랙 — AVL이 더 엄격하게 균형을 유지하여 검색이 빠르지만 삽입/삭제 시 회전이 더 많음
- •B-트리 — 디스크 기반 저장에 최적화된 다진 트리, 레드-블랙은 메모리 기반에 적합
- •스킵리스트 — 확률적 자료구조로 구현이 단순하지만 캐시 효율이 낮음
학습 팁
- •삽입 후 어떤 규칙이 위반되는지 먼저 확인하세요
- •삼촌 노드의 색상이 리컬러링/회전 결정의 핵심입니다
- •AVL 트리와 비교하며 회전 횟수 차이를 관찰해보세요
자주 묻는 질문
Q. 왜 AVL 대신 레드-블랙을?
A. 삽입/삭제가 빈번한 경우 회전 횟수가 적어 실용적으로 더 빠릅니다.
Q. 블랙 높이란?
A. 루트에서 리프까지 경로의 검정 노드 수입니다. 모든 경로에서 동일해야 합니다.