이진 탐색 트리(Binary Search Tree)

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

 

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

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

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

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

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

위 트리는 이진 탐색 트리의 특성을 모두 가지고 있다. 루트 노드의 왼쪽 서브 트리의 모든 값은 루트 노드의 값보다 작고, 오른쪽 서브 트리 값은 모두 크다. 또 각 노드의 값들은 모두 고유한 값을 가지고 있으며 서브 트리들도 이진 탐색 트리의 특성을 모두 가지고 있다.

출처 : http://blog.naver.com/songsmir?Redirect=Log&logNo=100117234824

[출처] 이진 탐색 트리(Binary Search Tree)|작성자 싸마