자료구조론 12장 검색(search)

이 장에서 다룰 내용 검색 순차 검색 이진 검색 이진 트리 검색 해싱

검색 검색(search, 탐색) 컴퓨터에 저장한 자료 중에서 원하는 항목을 찾는 작업 즉, 원하는 검색 키를 지닌 항목을 찾는 것 검색 키(search key) - 자료를 구별하여 인식할 수 있는 키 검색 성공 – 원하는 항목을 찾은 경우 검색 실패 – 원하는 항목을 찾지 못한 경우 삽입/삭제 작업에서의 검색 원소를 삽입하거나 삭제할 위치를 찾기 위해서 검색 연산 수행

검색 방법 수행 위치에 따른 분류 검색 방식에 따른 분류 검색 방법의 선택 내부 검색 - 메모리 내의 자료에 대해서 검색 수행 외부 검색 - 보조 기억 장치에 있는 자료에 대해서 검색 수행 검색 방식에 따른 분류 비교 검색 검색 대상의 키를 저장된 자료의 키와 비교하여 검색하는 방법 순차 검색, 이진 검색, 트리 검색 계산 검색 계수적인 성질을 이용한 계산으로 검색하는 방법 해싱 검색 방법의 선택 자료 구조의 형태와 자료의 저장 상태(정렬 유무 등)에 따라 최적의 검색이 달라진다.

순차 검색 순차 검색(sequential search) 세가지 순차 검색을 학습한다. 선형 검색(linear search) 일렬로 된 자료를 처음부터 마지막까지 순서대로 검색하는 방법 배열이나 연결 리스트로 구현된 순차 자료 구조에서 원하는 항목을 찾는 방법 장점: 알고리즘이 단순하여 구현이 용이함 단점: 검색 대상 자료가 많은 경우에 비효율적 세가지 순차 검색을 학습한다. 정렬되지 않은 배열의 순차 검색 정렬된 배열의 순차 검색 색인(index) 순차 검색

순차 검색 정렬되지 않은 배열의 순차 검색 검색 방법 첫 번째 원소부터 시작하여 마지막 원소까지 순서대로 키 값이 일치하는 원소를 검색 키 값이 일치하는 원소를 찾으면 그 원소의 인덱스를 반환 마지막 원소까지 비교하여 키 값이 일치하는 원소가 없으면 찾은 원소가 없는 것이므로 검색 실패 예) (a) 검색 성공 (b) 검색 실패

순차 검색 정렬되지 않은 배열의 순차검색 알고리즘 비교 횟수 찾는 원소가 첫 번째 원소라면 비교횟수는 1번, 두 번째 원소 라면 2번, 세 번째 원소라면 3번, … , 마지막 원소라면 n번 정렬되지 않은 원소에서의 순차 검색의 평균 비교 횟수 = (1+2+3+ … + n)/n = (n+1)/2    평균 시간 복잡도 : O(n) sequentialSearch1(a[], n, key) // a[0…n-1] 에서 key를 검색 i←0; while (i<n and a[i]≠key) do { i←i+1; } if (i<n) then return i; // 검색 성공 else return -1; // 검색 실패 end sequentialSearch1() [알고리즘 12-1]

순차 검색 정렬된 배열의 순차 검색 검색 방법 첫번 째 원소부터 순서대로 검색하되, 원소의 키 값이 찾는 키 값 보다 크면 찾는 원소가 없는 것이므로 더 이상 검색을 수행하지 않고 검색종료 예)

순차 검색 정렬된 배열의 순차검색 알고리즘 비교횟수 검색 성공의 경우는 정렬되지 않은 배열의 순차 검색과 동일 검색 실패의 경우에 평균 비교 횟수가 반으로 줄어든다.  평균 시간 복잡도 : O(n) sequentialSearch2(a[], n, key) // a[0…n-1] 에서 key를 검색 i←0; while (i<n and a[i]<key) do { i←i+1; } if (i<n and a[i]=key) then return i; // 검색 성공 else return -1; // 검색 실패 end sequentialSearch2() [알고리즘 12-2]

순차 검색 순차 검색 프로그램 public class Search { public static int sequentialSearch1(int[] a, int size, int key) { int i=0; while(i<size && (a[i]!=key)) i++; if(i<size) return i; else return -1; } public static int sequentialSearch2(int[] a, int size, int key) { while(i<size && a[i] < key) i++; if(i<size && a[i] == key)

순차 검색 public class Main { public static void main(String [] args) { int[] a1 = {8, 30, 1, 19, 11, 9, 2}; int size = a1.length; System.out.println("정렬되지 않은 배열의 순차검색 – 결과 인덱스"); System.out.println("19 검색 : " + Search.sequentialSearch1(a1, size, 19)); System.out.println("39 검색 : " + Search.sequentialSearch1(a1, size, 39)); int[] a2 = {1, 2, 8, 9, 11, 19, 29}; size = a2.length; System.out.println("정렬된 배열의 순차검색 – 결과 인덱스"); System.out.println("19 검색 : " + Search.sequentialSearch2(a2, size, 19)); System.out.println("39 검색 : " + Search.sequentialSearch2(a2, size, 39)); }

순차 검색 색인 순차 검색(index sequential search) 정렬된 배열을 검색하는 데 인덱스 테이블(index table)을 추가로 사 용하여 검색 효율을 높이는 방법 인덱스 테이블 정렬된 배열에서 일정한 간격으로 떨어져있는 원소들의 인덱스 와 키 값을 저장한 테이블 일정한 간격이란 : 자료가 저장된 배열의 크기가 n이고 인덱스 테이블의 크기가 m일 때, n/m 간격 검색 방법 indexTable[i].key ≤ key < indexTable[i+1].key를 만족하는 i 를 찾아서 배열의 어느 범위에 있는지를 먼저 알아낸 후에 해당 범위에 대해서만 순차 검색 수행 indexTable[i].index 부터 indexTable[i+1].index-1까지만 검색하면 됨

순차 검색 색인 순차 검색 예 검색 대상 자료 : {1, 2, 8, 9, 11, 19, 29} 크기가 3인 인덱스 테이블 작성 인덱스 테이블에서 먼저 검색 키를 검색하여 검색 범위를 확인하 고, 해당 범위에 대해서만 순차 검색 실행

순차 검색 색인 순차 검색의 성능 인덱스 테이블의 크기를 줄이면 배열의 인덱스를 저장하는 간격이 커지므로 배열에서 검색해야 하는 범위도 커진다. 인덱스 테이블의 크기를 늘리면 배열의 인덱스를 저장하는 간격이 작아지므로 배열에서 검색 해야 하는 범위는 작아지겠지만 인덱스 테이블을 검색하는 시간이 늘어난다.  시간 복잡도 : O(m + n/m) 배열의 크기 : n, 인덱스 테이블의 크기 : m

이진 검색 이진 검색(binary search) 정렬된 전체 원소들 중에서 어떤 키 값을 찾기 위해 일단 가운데 저 장된 원소와 비교하여 다음 검색 대상을 결정하는 방법 검색 키 = 가운데 원소의 키 : 검색 성공 검색 키 > 가운데 원소의 키 : 오른쪽 부분을 검색 검색 키 < 가운데 원소의 키 : 왼쪽 부분을 검색 키를 찾을 때까지 이진 검색을 순환적으로 수행한다. 즉, 검색 범위를 반으로 줄여가면서 검색한다. divide-and-conquer 기법 검색 범위를 반으로 분할하는 작업과 검색 작업을 반복 수행 정렬되어있는 자료에 대해서 수행하는 검색 방법

이진 검색 예

이진 검색 예

이진 검색 이진 검색 알고리즘 시간 복잡도 : O(log2n) 삽입이나 삭제시 항상 배열의 상태를 정렬 상태로 유지하는 추가적 인 작업 필요 binarySearch(a[], low, high, key) // a[low...high] 에서 key를 검색 if (low > high) return -1; else { middle ← (low+high)/2; if (key = a[middle]) then return i; else if (key < a[middle]) then binarySearch(a, low, middle-1, key); else then binarySearch(a, middle+1, high, key); } end binarySearch()

이진 트리 검색 이진 트리 검색 8장에서 설명한 이진 탐색 트리(binary search tree)를 사용한 검색 방법 원소의 삽입이나 삭제 연산에 대해서 항상 이진 탐색 트리를 재구성 하는 작업 필요

해싱 해싱(hashing) 원소가 저장된 위치를 산술적인 연산을 통해 계산하여 바로 찾아가 는 방법 검색 방법 검색 키 값을 해시 함수에 대입하여 주소를 구하고, 구한 주소에 해당하는 해시 테이블로 바로 이동 해당 주소에 찾는 항목이 있으면 검색 성공, 없으면 검색 실패 해시 함수(hash function) 키 값을 원소의 위치로 변환하는 함수 해시 테이블(hash table) 해시 함수에 의해서 계산한 위치에 따라 원소를 저장한 테이블

해싱 해싱 수행 방법 슬롯1 슬롯2 슬롯3

해싱 해싱의 예 : 도서 검색

해싱 해싱 용어 충돌(collision) 서로 다른 키 값에 대해서 해시 함수로 구한 주소(버킷 번호)가 같은 경우 서로 다른 키 값에 대해서 해시 함수로 구한 주소(버킷 번호)가 같은 경우 충돌이 발생한 경우에 해당 버킷에 비어있는 슬롯이 있는 경우 synonym 관계로 저장 동거자(synonym) 서로 다른 키 값을 가지지만 해시 함수에 의해서 같은 버킷에 저장된 키 값들 오버플로우(overflow) 충돌이 발생한 버킷이 비어있는 슬롯이 없는 포화 상태이어서 더 이상 키 값을 저장할 수 없는 상태

해싱 키 값 밀도 사용 가능한 전체 키 값들 중에서 현재 해시 테이블에 저장되어 서 실제 사용되고 있는 키 값의 개수 비율 적재 밀도 해시 테이블에 저장 가능한 키 값의 개수 중에서 현재 해시 테이 블에 저장되어서 실제 사용되고 있는 키 값의 개수

해싱 – 해시 함수 해시 함수의 조건 해시 테이블에 고르게 분포할 수 있도록 주소를 만들어야 한다. 즉, 가능한 충돌을 적게 발생시키는 함수이어야 한다. 충돌이 많이 발생한다는 것은 같은 버킷을 할당받는 키 값이 많 다는 것  비어있는 버킷이 많은데도 어떤 버킷은 오버플로우 가 발생할 수 있는 상태가 되므로 좋은 해시 함수가 될 수 없다. 계산이 쉬워야 한다. 비교 검색 방법을 사용하여 키 값의 비교연산을 수행하는 시간 보다 해시 함수를 사용하여 계산하는 시간이 빨라야 해싱을 사 용하는 의미가 있다.

해싱 – 해시 함수 해시 함수의 종류 bit extraction(비트 추출) 방법 해시 테이블 크기가 2b일 때 키 값으로부터 b개의 비트를 추출 하여 주소로 사용하는 방법 키 값의 특정 부분만 고려하므로 충돌이 많이 발생할 수 있음 mid-square(중간-제곱) 방법 키 값을 제곱한 결과 값에서 b개의 비트를 주소로 사용하는 방 법 제곱한 값의 중간 비트들은 대개 그 키의 전체 부분과 관련이 있 기 때문에 서로 다른 키 값은 서로 다른 중간-제곱 값을 가질 가 능성이 높다. 예) 키 값 00110101 10100111의 해시 주소 계산                        00110101 10100111          X             00110101 10100111          00001011001111101001001011110001 해시 주소

해싱 – 해시 함수 division(나누기) 방법 나머지 연산을 사용하는 방법 키 값 k를 해시 테이블의 크기 m으로 나눈 나머지를 해시 주소 로 사용 h(k) = k mod m m으로 나눈 나머지 값은 0~(m-1)이므로 해시 테이블의 인덱 스로 사용할 수 있다. 해시 주소는 충돌이 발생하지 않고 고르게 분포하도록 생성되어 야 하므로 m은 적당한 크기의 소수(prime number) multiplication(곱하기) 방법 곱하기 연산을 사용하는 방법 키 값 k와 정해진 실수 α를 곱한 결과에서 소수점 이하 부분만 을 테이블의 크기 m과 곱하여 그 정수 값을 해시 주소로 사용

해싱 – 해시 함수 folding(접지) 방법 키의 비트 수가 해시 테이블 인덱스의 비트 수보다 큰 경우에 주 로 사용 키 값을 분할하여 각 분할 부분을 이동시켜서 오른쪽 끝자리가 일치하게 맞추고 더하는 방법 예) 해시 테이블 인덱스가 3자리, 키 값이 12341234123인 경우

해싱 – 충돌 처리 충돌 처리 방법 = 오버플로우 처리 방법 (버킷 당 슬롯이 하나라고 가정하면) 선형 개방 주소법(linear open addressing) 선형 조사법(linear probing) 저장 : 충돌이 일어나면 다음 버킷을 조사한다. 다음 버킷이 비어있으면 키 값을 저장 버킷이 차있으면 다시 다음 버킷을 조사 이런 과정을 되풀이 하여 비어있는 버킷을 찾아 저장함 검색 : 버킷에 저장된 값이 검색 키 값과 다르면 바로 다음 버킷 을 조사한다. 다음 버킷이 비어있으면 검색 실패

해싱 – 충돌 처리 저장할 키 값 : 45, 9, 10, 96, 25

해싱 – 충돌 처리 체이닝(chaining) 각 버킷을 연결 리스트로 구현하여, synonym들을 하나의 연결 리스트에 저장한다. 각 버킷에 대해 헤드노드를 두고 헤드노드들을 1차원 배열 로 만든다. 각 버킷에 대한 헤드노드는 슬롯들을 연결 리스트로 가지고 있어서 슬롯의 삽입이나 삭제 연산을 쉽게 수행할 수 있다. 버킷 내에서 원하는 슬롯을 검색하기 위해서는 버킷의 연결 리스트를 선형 검색한다.

해싱 – 충돌 처리 저장할 키 값 : 45, 9, 10, 96, 25