카테고리 없음
이진 탐색(Binary Search),이진탐색트리
setposs
2022. 11. 12. 11:33
• 자료가 정렬되어 있을 때, 중앙에 있는 값을 기준으로 왼쪽과 오른쪽 자료를 비교하면서 탐색하는 방법 • 장점 - 탐색의 범위를 반으로 줄이기 때문에 순차 탐색보다 원하는 자료를 빠르게 찾을 수 있음 • 단점 - 순차 탐색에 비해 복잡 - 탐색을 하기 전에 자료를 미리 정렬해야 함 - 동적으로 크기가 달라지는 데이터 집합에 적용 불가능
이진탐색트리
• 이진 탐색은 데이터 집합이 배열인 경우에만 사용 가능 - 데이터의 중앙 요소의 위치를 계산하여 즉시 접근 할 수 있어야 함 - 링크드 리스트는 처음과 끝의 위치는 알 수 있어도 중앙 요소의 위치는 알 수 없음 • 자료의 탐색이 효율적으로 되는 이진 트리 - 데이터의 크기에 따라 위치가 정해져 있어서 탐색, 삽입, 삭제가 효율적인 구조
이진 탐색 트리 조건
1. 모든 노드는 다른 값을 갖는다. 2. 왼쪽 서브 트리의 데이터 값은 부모 노드의 데이터 값보다 작은 값을 갖 는다. 3. 오른쪽 서브 트리의 데이터 값은 부 모 노드의 데이터 값보다 큰 값을 갖는다. 4. 왼쪽, 오른쪽 서브 트리도 이진 탐색 트리이다.