이진 탐색 트리(binary search tree)는 BST라는 이름으로 더 잘 알려져 있는데, 그만큼 중요한 자료 구조입니다. 많은 언어에서 지원하는 집합과 딕셔너리가 내부적으로는 이진 탐색 변형인 균형 이진 탐색 트리를 사용합니다. 또 다른 변종인 B 트리는 데이터베이스에서 매우 중요한 역할을 합니다. 이런 응용 분야를 알려면 먼저 기본이 되는 이진 탐색 트리부터 잘 이해해야겠지요. 이전 장들에 비해 이 장부터는 난이도가 부쩍 올랐다고 느낄지도 모르겠습니다. 실제로도 BST는 자료 구조를 공부할 때 봉착하는 난관과 같습니다만, 천천히 고민하고 들여다보면 충분히 이해할 수 있습니다. 그럼 시작해 볼까요?