코드 9-1은 RBNode 클래스를 보여 줍니다. 이진 탐색 트리를 구현할 때 사용했던 노드에 color 멤버만 추가되었습니다. 컬러는 기본값으로 RED를 설정하도록 했습니다. 이번 코드에서는 멤버 각각에 대해 프로퍼티로 캡슐화하지 않았는데, 이는 단순히 코드 길이를 줄이기 위해서였습니다. 프로퍼티로 캡슐화해도 됩니다.

실제 구현을 할 때 모든 외부 노드의 인스턴스를 만들어서 리프 노드나 자식이 하나인 노드에 연결해 주는 것은 매우 번거로운 일입니다. 구현도 그만큼 복잡해집니다. 이를 해결할 수 있는 방법이 있는데, 모든 빈 노드가 하나의 외부 노드를 가리키게 하는 것입니다.

그림으로 살펴봅시다.

▲ 그림 9-11 레드 블랙 트리의 외부 노드 구현