이진 탐색 트리 (Binary Search Tree)

이진탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조의 일종

전체 노드에 대하여 왼쪽 자식 노드는 부모노드보다 값이 작고, 오른쪽 자식 노드는 부모노드보다 값이 큰 값을 가지도록 이진트리 구성 (왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드)

 

= 부모 노드는 모든 왼쪽 자식노드와 비교하였을 때 값이 크고, 모든 오른쪽 자식노드와 비교하였을 때 값이 작다.

 

이진탐색트리에서의 데이터 조회 과정

1. 루트 노드부터 방문하여 탐색 진행 (현재 노드와 찾는 원소를 비교. 찾는 원소가 더 작다면 왼쪽/크다면 오른쪽 방문)

2. 현재 노드와 찾는 원소를 비교 -> 찾는 원소가 더 작다면 왼쪽/크다면 오른쪽 방문

2번 과정 반복하다가 원소를 찾으면 탐색 종료

(이상적인 경우 탐색 범위가 절반 가까이 줄어들기도 함)