13-3. 레드 블랙 트리

03. 레드 블랙 트리

레드 블랙 트리의 정의

- 효율적인 기억 장소 사용을 위하여 2-3-4트리를 이진 트리로 나타낸 탐색 트리

- 레드 간선과 블랙 간선의 서브트리 포인터를 가짐

- 레드 간선은 2-3-4트리의 한 노드 내에 있던 노드의 관계이고, 블랙 간선은 2-3-4트리의 부모-자식 관계임

- 레드 블랙 트리의 탐색 방법은 보통의 이진 탐색 트리의 탐색 알고리즘과 동일함

 

3-노드에 대응하는 레드 블랙 트리

- 구분을 위해 레드 간선은 점선으로 블랙 간선은 실선으로 나타냄

 

 

레드 블랙 트리에서 삽입 연산을 위한 노드 분리

- 4-노드가 루트 노드인 경우 레드 블랙 트리의 노드 분리

 ( 점선(레드 간선) → 실선(블랙 간선) )