레드 블랙 트리(red black tree)란 모든 노드의 컬러가 레드 혹은 블랙인 이진 탐색 트리입니다. 루트와 외부 노드는 무조건 블랙입니다. 이외에도 몇 가지 특징이 있는데, 알아보기 전에 레드 블랙 트리를 그림으로 살펴봅시다(그림 9-3).

▲ 그림 9-3 레드 블랙 트리

그림 9-3은 레드 블랙 트리입니다. 여기서 눈여겨볼 점은 이 트리도 이진 탐색 트리라는 것이고, 루트와 외부 노드가 모두 블랙이라는 것입니다.

레드 블랙 트리의 특징을 알아볼까요?

1. 트리의 모든 노드는 레드 아니면 블랙입니다.

2. 루트 노드와 외부 노드는 블랙입니다.

3. 루트 노드에서 외부 노드까지 경로에서 레드 노드가 연속으로 나올 수 없습니다.

4. 루트 노드에서 외부 노드까지 모든 경로에서 블랙 노드 개수는 같습니다.