이진 탐색(Binary Search),이진탐색트리

• 자료가 정렬되어 있을 때, 중앙에 있는 값을 기준으로 왼쪽과 오른쪽 자료를 비교하면서 탐색하는 방법 • 장점 - 탐색의 범위를 반으로 줄이기 때문에 순차 탐색보다 원하는 자료를 빠르게 찾을 수 있음 • 단점 - 순차 탐색에 비해 복잡 - 탐색을 하기 전에 자료를 미리 정렬해야 함 - 동적으로 크기가 달라지는 데이터 집합에 적용 불가능

​

이진탐색트리

• 이진 탐색은 데이터 집합이 배열인 경우에만 사용 가능 - 데이터의 중앙 요소의 위치를 계산하여 즉시 접근 할 수 있어야 함 - 링크드 리스트는 처음과 끝의 위치는 알 수 있어도 중앙 요소의 위치는 알 수 없음 • 자료의 탐색이 효율적으로 되는 이진 트리 - 데이터의 크기에 따라 위치가 정해져 있어서 탐색, 삽입, 삭제가 효율적인 구조

​

이진 탐색 트리 조건

1. 모든 노드는 다른 값을 갖는다. 2. 왼쪽 서브 트리의 데이터 값은 부모 노드의 데이터 값보다 작은 값을 갖 는다. 3. 오른쪽 서브 트리의 데이터 값은 부 모 노드의 데이터 값보다 큰 값을 갖는다. 4. 왼쪽, 오른쪽 서브 트리도 이진 탐색 트리이다.