이진 탐색 트리란?

모든 노드에 대해서,

• 왼쪽 서브트리의 데이터는 모두 현재 노드의 값보다 작고
• 오른쪽 서브트리의 데이터는 모두 현재 노드의 값보다 큰

위와 같은 성질을 만족하는 이진 트리

단, 여기서 중복되는 데이터 원소는 없는 것으로 가정한다.

이진 탐색 트리의 예

루트 노드의 데이터가 5일 때, 6을 찾아야 한다.

1. 루트 노드의 왼쪽 서브트리는 5보다 작으므로 볼 필요가 없다.
2. 오른쪽 자식인 8은 6보다 크므로 왼쪽 자식으로 이동한다.
3. 6 탐색 성공

이러한 탐색법은 배열을 이용한 이진 탐색과 비슷하다.

(정렬된) 배열을 이용한 이진 탐색과 비교

장점