이진 탐색 트리는 키의 대소관계에 따라 왼쪽과 오른쪽 부분 트리를 나누어 저장하는 이진 트리이다.
원리
찾는 키를 현재 노드와 비교하고 한쪽 부분 트리로 내려간다. 탐색·삽입·삭제의 비용은 높이 h에 비례하는 O(h)이며, 균형을 유지할 때 O(log n)을 기대할 수 있다.
예시
10, 5, 15를 넣으면 10의 왼쪽에서 5, 오른쪽에서 15를 찾는다. 중위 순회는 키의 정렬 순서를 얻는 데 사용할 수 있다.
주의할 점
정렬된 입력을 단순 삽입하면 긴 사슬이 되어 최악 O(n)이 된다. 중복 키 처리와 삭제 시 후계자 선택을 정해야 하며, 균형 트리와 구별한다.