My Trace

이진 탐색 트리(Binary Search Tree)는 자료의 검색이 주된 기능을 가진 이진 트리 이다. 즉,이진 탐색 트리는 효율적인 자료 검색을 목적으로 기존 이진 트리에 몇 가지 제약 사항을 추가한 트리를 말한다. 이진 탐색 트리는 특정 키 값에 해당하는 노드를 신속하게 찾는 것이 기본적인 기능이다. 이러한 탐색은 실생활에서 많이 사용 되는데 전화번호부에서 전화번호 찾기나 주민등록번호로 사람을 찾기 등 많이 사용되고 있다.

이진 트리 중 다음과 같은 특성을 만족해야 이진 탐색 트리가 될 수 있다.

1.     트리의 모든 노드는 유일한 키를 가진다.

2.     왼쪽 서브 트리에 있는 모든 노드의 키는 루트의 키보다 작다.

3.     오른쪽 서브 트리에 있는 모든 노드의 키는 루트의 키보다 크다.

4.     왼쪽 서브 트리와 오른쪽 서브 트리도 모두 이진 탐색 트리이다.