검색4 이진 트리 검색(Binary Tree Search) 이진 트리 검색(Binary Tree Search) 루트 노드를 기준으로 왼쪽 서브 트리는 루트 노드보다 키 값이 작은 원소들로, 오른쪽 서브 트리는 루트 노드보다 키 값이 큰 원소들로 구성된 '이진 탐색 트리'를 사용하여 중위 순회 방법으로 검색. 삽입, 삭제 연산 후에는 항상 이진 탐색 트리를 재구성해야 한다. 예시 1) 20를 찾는 경우 9 /\ 4 17 /\ /\ 1 7 14 20 1. 루트 노드에서 검색을 시작하여 키 값과 비교한다. 키 값이 루트 노드보다 크기 때문에 오른쪽 노드로 이동한다. 9 /\ 4 17 /\ /\ 1 7 14 20 2. 이동한 오른쪽 노드와 키 값을 비교한다. 키 값이 17보다 크기 때문에 오른쪽 노드로 이동한다. 9 /\ 4 17 /\ /\ 1 7 14 20.. 2021. 4. 2. 이진 검색(Binary Search) 이진 검색(Binary Search) 정렬되어 있는 배열에 대하여 원소들의 가운데 있는 항목을 키 값과 비교하여 키 값이 더 크면 오른쪽을, 더 작으면 왼쪽을 검색한다. 왼쪽과 오른쪽으로 나누어서 검색하면서 이진 검색을 다시 반복하여 검색 범위를 반으로 줄여나가면서 검색한다. 절반 두 부분으로 나누어 검색하므로 이분 검색, 보간 검색(Interpolation Search)이라고도 하며 분할 정복 기법이라고도 한다. 삽입이나 삭제 작업을 수행한 후에 항상 배열을 정렬해야한다. 시간 복잡도는 O(log2n)이다. 예시 1) 50을 찾는 경우 {2, 6, 16, 27, 32, 41, 50} 1. 가운데 원소인 27을 기준으로 키 값과 비교한다. 키 값이 더 크기 때문에 검색 범위를 기준 값의 오른쪽으로.. 2021. 4. 2. 색인 순차 검색(Index Sequential Search) 색인 순차 검색(Index Sequential Search) 정렬이 되어 있는 자료 중 일정한 간격으로 떨어져 있는 원소를 가지고 있는 인덱스 테이블(Index Table)을 이용하는 순차 검색이다. 배열의 크기가 n이고 인덱스 테이블의 크기가 m일 때, n/m간격으로 떨어져있는 원소와 인덱스를 인덱스 테이블에 저장한다. 찾을 원소를 인덱스 테이블에서 먼저 검색하여 만족하는 범위를 알아낸 후 그 범위에 대해서만 순차 검색을 수행한다. 인덱스 테이블의 크기가 작으면 인덱스 테이블에 저장하는 간격이 커지므로 배열에서 검색할 범위도 커진다. 반대로 인덱스 테이블의 크기가 커지면 간격이 작아지므로 배열에서 검색할 범위도 작아진다. 하지만 인덱스 테이블을 검색하는 시간이 늘어난다. 시간 복잡도는 O(m+n/m.. 2021. 4. 2. 순차 검색(Sequential Search) 순차 검색(Sequential Search) = 선형 검색(Linear Search) 일렬로 되어 있는 자료를 처음부터 끝까지 순서대로 검색. 자료의 양에 따라 효율이 달라지기 때문에 많은 양의 자료를 대상으로는 비효율적. 알고리즘이 단순하여 구현이 쉽고 가장 간단한 방법이다. 정렬이 되어 있지 않은 순차 자료구조에서의 순차 검색 자료구조의 처음 원소부터 마지막 원소까지 키 값이 일치하는지 비교한다. 일치하는 원소를 찾으면 몇 번째 원소인지 반환하고 찾지 못하면 검색 실패가 된다. 찾고자 하는 원소의 위치에 따라 비교 횟수가 달라지므로 평균 비교 횟수는 (n+1)/2 이고 시간 복잡도는 O(n)이다. 예시 1) 50을 찾는 경우 {57, 16, 41, 2, 50, 6, 32, 27} ===> {5.. 2021. 4. 2. 이전 1 다음
