Red-Black 트리

1. 자기 균형 이진 탐색 트리, 레드-블랙 트리 개념

- 각 노드에 레드 또는 블랙 색상 속성이 부여된 이진 탐색 트리로 특정 규칙을 통해 항상 균형 형태를 유지하는 트리

특징) worst-case guarantees, 실시간 처리에 유용

 

2. 레드-블랙 트리 개념도 및 규칙

가. 레드-블랙 트리 개념도

 

나. 레드-블랙 트리 규칙

번호	조건	설명
1	Root Property	루트 노드는 모두 블랙이다
2	External Property	모든 리프(NULL)은 블랙이다
3	Internal Property	레드 노드의 자식은 항상 블랙이다
4	Depth Property	노드에서 리프 노드까지 가는 모든 경로에는 동일한 블랙 노드가 있다

 

 

3. Double Red 해결 방법 Restructuring, Recoloring

구분	설명
Restructuring	1. 새로운 노드, 부모 노드, 조상 노드 오름 차순 정렬 2. 셋 중 중간 값을 부모로 나머지 둘을 자식으로 3. 새로 부모가 된 노드는 블랙, 나머지 자식은 레드
Recoloring	1. 새로운 노드의 부모와 삼촌을 블랙으로, 조상을 레드로 변경 2. 조상이 루트면 블랙으로 변경