"이진 검색 트리"(Binray Search Tree)는 다음과 같은 성질을 만족하는 이진트리이다. 각 노드에 들어가는 값들은 대소관계를 비교할 수 있다. 노드의 왼쪽 서브트리는 작은 값들을 가진 노드들로 이루어져 있다. 노드의 오른쪽 서브트리는 큰 값들을 가진 노드들로 이루어져 있다. 좌우 서브트리는 각각 위의 2 조건을 만족한다.이러한 특성 때문에 정렬된 이진 트리(Sorted Binary Tree)라고도 부른다.  이진 검색 트리는 검색, 삽입, 삭제 연산들이 평균적으로 $O(logN)$에 동작한다. 해시의 경우, 위의 연산들을 $O(1)$에 제공하지만, 원소 간의 대소관계는 비교할 수 없다. 하지만, 이진 검색 트리의 경우 "5 보다 큰 최초의 원소"와 같은 대소비교 관련 연산을 수행할 수 있다...