그림을 하나 더 보겠습니다.

▲ 그림 8-3 BST 2

그림 8-3을 보면 노드를 3으로 특정했을 때 키 3은 노드 3의 왼쪽 서브 트리의 모든 키보다 크고, 오른쪽 서브 트리의 모든 키보다 작다는 것을 알 수 있습니다. 이는 노드 8을 특정해서 살펴보아도 마찬가지입니다. 어디서 많이 본 특징 아닌가요? 그렇습니다. 바로 이진 검색 알고리즘의 특징이지요. 키 6을 기준으로 앞의 요소들은 모두 6보다 작고 뒤의 요소들은 6보다 크니까요.

이진 탐색 트리의 ADT를 기술해 보겠습니다.