루트 노드를 기준으로 왼쪽 서브 트리의 모든 데이터는 루트 노드의 데이터인 6보다 작습니다. 오른쪽 서브 트리의 모든 데이터는 6보다 크지요. 확실하게 이해하고자 루트 노드의 왼쪽 자식 노드와 오른쪽 자식 노드를 기준 노드로 하여 살펴보겠습니다.

그림 14-2 이진 탐색 트리의 특징 ②

그림 14-2에서 루트 노드의 왼쪽 자식 노드가 기준 노드일 때, 기준 노드의 왼쪽 서브 트리의 모든 데이터는 기준 노드의 데이터인 3보다 작습니다. 오른쪽 서브 트리의 모든 데이터는 3보다 큽니다. 기준 노드가 루트 노드의 오른쪽 자식 노드일 때도 같은 조건이 성립합니다. 즉, 특정 노드를 기준으로 그 노드의 서브 트리도 모두 이진 탐색 트리인 것을 알 수 있습니다.

이진 탐색 트리의 두 번째 특징은 이진 탐색 트리는 중복 데이터를 가질 수 없다는 것입니다. 첫 번째 특징을 생각해 보면 당연합니다. 특정 노드가 기준일 때 왼쪽 서브 트리의 모든 데이터는 노드 데이터보다 작고 오른쪽 서브 트리의 모든 데이터는 노드 데이터보다 커야 하므로 값이 같은 데이터는 존재할 수 없습니다.