반응형
레드-블랙 트리
개요
자가 균형 이진 탐색 트리. 다음과 같은 조건을 만족.
- 모든 노드는 빨간색 혹은 검은색.
- 루트 노드는 검은색.
- 모든 리프 노드(NIL)는 검은색.
- 빨간색 노드의 자식은 검은색. (No Double Red)
- 모든 리프 노드에서 Black Depth는 같음.
삽입 과정
- 새로운 노드는 항상 빨간색으로 삽입.
- 삽입 후 Double Red 문제 발생 가능.
- 해결 방법:
- 삼촌 노드가 검은색: Restructuring 수행.
- 삼촌 노드가 빨간색: Recoloring 수행.
Restructuring (재구축)
- 새로운 노드(N), 부모 노드(P), 조상 노드(G)를 오름차순으로 정렬.
- 중간값을 부모 노드로 설정, 나머지 둘을 자식 노드로 변경.
- 새 부모 노드를 검은색으로, 자식들을 빨간색으로 변경.
예제
초기 상태: 재구축 후:
G (검) P (검)
/ \ / \
P U(검) N(빨) G(빨)
/
N(빨)
Recoloring (재색칠)
- 부모(P)와 삼촌(U)을 검은색으로 변경.
- 조상(G)을 빨간색으로 변경.
- 조상이 루트라면 검은색으로 유지.
- 조상이 Double Red를 유발하면 다시 Restructuring 또는 Recoloring 수행.
예제
초기 상태: 재색칠 후:
G (검) G (빨)
/ \ / \
P(빨) U(빨) P(검) U(검)
/
N(빨)
예제 삽입 수행
삽입 순서: 8, 7, 9, 3, 6, 4, 5, 12
초기 상태: 최종 상태:
8(검) 6(검)
/ \ / \
4(빨) 9(검) 3(검) 8(검)
/ \ / \ \
3(검) 6(검) NIL 5(빨) 12(검)
/
5(빨)
레드-블랙 트리 시뮬레이터
레드-블랙 트리의 삽입 과정을 시각적으로 확인 가능.
반응형
'SW개발 > 면접을 위한 CS 전공지식 노트' 카테고리의 다른 글
5.3 비선형 자료 구조 (Non-Linear Data Structures) (1) | 2025.02.05 |
---|---|
5.2 선형 자료 구조 (Linear Data Structures) (0) | 2025.02.05 |
5.1 복잡도 (1) | 2025.02.05 |
참고. 데이터베이스 관련 면접 질문 리스트 (0) | 2025.01.24 |
4.7 조인의 원리 (1) | 2025.01.22 |