[이진탐색] 이진탐색 (3) 이진 탐색 트리

이진 탐색 트리

• 이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조
• 이진 탐색 트리의 특징
  • 부모 노드보다 왼쪽 자식 노드가 크다
  • 부모 노드보다 오른쪽 자식 노드가 작다
  • 즉, 왼쪽 자식 노드 < 부모 < 오른쪽 자식 노드
  • 예시

• 이진 탐색 트리가 미리 구현되어 있을 때, 이진 탐색 트리에서 데이터를 조회하는 과정 예시 - 위 트리에서 찾는 원소가 37일 때
  1. 이진 탐색은 루트 노드부터 방문. 루드 노드인 30보다 target이 37이 더 크므로 오른쪽 노드 방문
  2. 오른쪽 자식 노드인 48이 이번에 루트 노드가 됨. 루트 노드인 48보다 target인 37이 작으므로 왼쪽 노드 방문
  3. 현재 방문한 노드인 37과 target인 37이 같으므로 탐색 종료
• 이처럼 이진 탐색 트리에서 데이터 조회는 루트 노드부터 왼쪽 자식 노드 or 오른쪽 자식 노드로 이동하며 반복적으로 방문 수행. 자식 노드가 없을 때까지 원소를 찾지 못했다면, 이진 탐색 트리에 원소가 없는 것.