코드 8-2에서 TreeNode 생성자를 보면, key와 왼쪽·오른쪽 자식 노드, 그리고 부모를 가리키는 참조만 있습니다. 목적이 이진 탐색 트리의 작동을 살펴보고 구현해 보는 것이기 때문에 일부러 데이터의 참조는 구현하지 않았습니다. 필요하다면 data 멤버를 만들면 그만입니다.

이진 탐색 트리의 정의는 다음과 같습니다.

1. 모든 키는 유일합니다.

2. 어떤 노드를 특정했을 때 이 노드의 키 값은 왼쪽 서브 트리의 그 어떤 키보다 큽니다.

3. 어떤 노드를 특정했을 때 이 노드의 키 값은 오른쪽 서브 트리의 그 어떤 키 값보다 작습니다.

4. (재귀적 정의)노드의 서브 트리도 이진 탐색 트리입니다.

그림으로 살펴보겠습니다. 그림 8-2를 보면 노드 6의 왼쪽 서브 트리의 모든 키 값은 6보다 작고, 노드 6의 오른쪽 서브 트리의 모든 키 값은 6보다 큽니다.

▲ 그림 8-2 BST 1