강의 #11 탐색(Search)

탐색이란? 탐색(search)은 탐색은 기본적으로 여러 개의 자료 중에서 원하는 자료를 찾는 작업 컴퓨터가 가장 많이 하는 작업 중의 하나 탐색을 효율적으로 수행하는 것은 매우 중요. 탐색키(search key): 항목과 항목을 구별해주는 키(key) 탐색을 위하여 사용되는 자료 구조 배열, 연결 리스트, 트리, 그래프 등 탐색키 데이터

순차 탐색 순차 탐색(sequential search)은 탐색 방법 중에서 가장 간단하고 직접적인 탐색 방법 순차 탐색은 정렬되지 않은 배열의 항목들을 처음부터 마지막까지 하나씩 검사하여 원하는 항목을 찾아가는 방법 int seq_search(int key, int low, int high) { int i; for(i=low; i<=high; i++) if(list[i]==key) return i; // 탐색 성공 return -1; // 탐색 실패 }

개선된 순차탐색 순차 탐색에서 비교 횟수를 줄이기 위해 리스트의 끝에 찾고자 하는 키 값을 저장하고 반복문의 탈출 조건을 키 값을 찾을 때까지로 설정 int seq_search2(int key, int low, int high) { int i; list[high+1] = key; for (i=low; list[i] != key; i++); // 키값을 찾으면 종료 if (i==(high+1)) return -1; // 탐색 실패 else return i; // 탐색 성공 }

이진탐색 (1) 정렬된 배열의 탐색에는 이진 탐색(binary search)이 적합 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 반으로 줄인다. (예) 10억 명중에서 이진 탐색을 이용하여 특정한 이름을 탐색 이진탐색은 단지 30번의 비교 순차 탐색에서는 평균 5억 번의 비교

ⅹ 이진탐색 (2) 영어사전 moveable move data 5을 탐색하는 경우 7과 비교 1 3 5 6 7 9 11 20 30 ⅹ 5< 7이므로 앞부분만을 다시 탐색 moveable 1 3 5 6 7 9 11 20 30 move 5를 3과 비교 1 3 5 6 7 9 11 20 30 5> 3이므로 뒷부분만을 다시 탐색 1 3 5 6 7 9 11 20 30 5==5이므로 탐색성공 data 1 3 5 6 7 9 11 20 30

이진탐색 알고리즘 search_binary(list, low, high) middle ← low에서 high사이의 중간 위치 if( 탐색값 ≠ list[middle] ) return TRUE; else if (탐색값 < list[middle] ) return list[0]부터 list[middle-1]에서의 탐색; else if (탐색값 > list[middle] ) return list[middle+1]부터 list[high]에서의 탐색;

색인순차탐색 색인 순차 탐색(indexed sequential search) 방법은 인덱스(index)라 불리는 테이블을 사용하여 탐색의 효율을 높이는 방법 인덱스 테이블은 주 자료 리스트에서 일정 간격으로 발췌한 자료를 가지고 있다. 주 자료 리스트와 인덱스 테이블은 모두 정렬되어 있어야 한다.

색인순차탐색 알고리즘 // 인덱스 테이블 구조체 typedef struct { int key; int index; } itable; itable index_list[INDEX_SIZE]; int search_index(int key) { int i, low, high; // 키값이 리스트 범위에 있는지를 검사 if (key<list[0] || key>list[n-1]) return -1; // 인덱스 테이블을 조사하여 해당키의 구간 결정 for (i=0; i<INDEX_SIZE; i++) if (index_list[i].key<=key && index_list[i+1].key>key) break; if (i==INDEX_SIZE) { low = index_list[i-1].index; high = n; } else { low = index_list[i].index; high = index_list[i+1].index; } // 예상되는 범위만 순차 탐색 return seq_search(key, low, high);

보간탐색 보간 탐색(interpolation search)은 사전이나 전화번호부를 탐색하는 방법과 같이 탐색키가 존재할 위치를 예측하여 탐색하는 방법 사전을 찾을 때 ‘ㅎ’으로 시작하는 단어는 사전의 뒷부분에서 찾고 ‘ㄱ'으로 시작하는 단어는 앞부분에서 찾는 것과 같은 원리이다. 보간 탐색은 이진 탐색과 유사하나 리스트를 반으로 분할하지 않고 불균등하게 분할하여 탐색한다.

보간탐색 알고리즘 int search_interpolation(int key, int n) { int j, low, high; high = n-1; while((list[high] >= key) && (key > list[low])) { j =((float)(key-list[low])/(list[high]-list[low]) * (high-low)) + low; if (key > list[j]) low = j+1; else if (key list[j]) high = j-1; else low = j; } if (list[low] == key) return (low); else return -1;

균형이진탐색트리 (1) 이진 탐색(binary search)과 이진 탐색 트리(binary search tree)와의 차이점 이진 탐색과 이진 탐색 트리는 근본적으로 같은 원리에 의한 탐색 구조 이진 탐색은 자료들이 배열에 저장되어 있으므로 삽입과 삭제가 상당히 힘들다. 즉 자료를 삽입하고 삭제할 때마다 앞뒤의 원소들을 이동시켜야 한다. 이진 탐색 트리는 비교적 빠른 시간 안에 삽입과 삭제를 끝마칠 수 있는 구조 삽입, 삭제가 빈번히 이루어진다면 반드시 이진 탐색 트리를 사용하여야 한다.

균형이진탐색트리 (2) 이진탐색트리에서의 시간복잡도 균형트리: O(logn) 불균형트리: O(n), 순차탐색과 동일  이진탐색트리에서의 균형 유지를 요구

AVL 트리 Adelson-Velskii와 Landis에 의해 1962년에 제안된 트리 각 노드에서 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 차이가 1 이하인 이진 탐색 트리 트리가 비균형 상태로 되면 스스로 노드들을 재배치하여 균형 상태로 만든다. AVL 트리는 균형 트리가 항상 보장되기 때문에 탐색이 O(logn)시간 안에 끝나게 된다. 균형 인수(balance factor)=(왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이) 모든 노드의 균형 인수가 ±1 이하이면 AVL 트리이다.

AVL 트리의 연산 탐색연산: 이진탐색트리와 동일 균형을 이룬 이진 탐색 트리에서 균형 상태가 깨지는 것은 삽입 연산과 삭제 연산시이다. 삽입 연산시에는 삽입되는 위치에서 루트까지의 경로에 있는 조상 노드들의 균형 인수에 영향을 줄 수 있다. 새로운 노드의 삽입 후에 불균형 상태로 변한 가장 가까운 조상 노드, 즉 균형 인수가 ±2가 된 가장 가까운 조상 노드의 서브 트리들에 대하여 다시 균형을 잡아야 한다.

AVL트리의 삽입연산 균형트리로 만드는 방법: 회전(rotation) AVL 트리에서 균형이 깨지는 경우에는 다음의 4가지의 경우가 있다. 새로 삽입된 노드 N로부터 가장 가까우면서 균형 인수가 ±2 된 조상 노드를 A라고 하자. LL 타입: N이 A의 왼쪽 서브 트리의 왼쪽 서브 트리에 삽입된다. LR 타입: N이 A의 왼쪽 서브 트리의 오른쪽 서브 트리에 삽입된다. RR 타입: N이 A의 오른쪽 서브 트리의 오른쪽 서브 트리에 삽입된다. RL 타입: N이 A의 오른쪽 서브 트리의 왼쪽 서브 트리에 삽입된다.

회전방법 (1) LL 회전: A부터 N까지의 경로상의 노드들을 오른쪽으로 회전시킨다. LR 회전: A부터 N까지의 경로상의 노드들을 왼쪽-오른쪽으로 회전시킨다. RR 회전: A부터 N까지의 경로상의 노드들을 왼쪽으로 회전시킨다. RL 회전: A부터 N까지의 경로상의 노드들을 오른쪽-왼쪽으로 회전시킨다.

회전방법 (2) rotate_LL(A) B <- A의 왼쪽 자식 B의 오른쪽 자식을 A의 왼쪽 자식으로 만든다 rotate_RR(A) B <- A의 오른쪽 자식 B의 왼쪽 자식을 A의 오른쪽 자식으로 만든다 A를 B의 왼쪽 자식 노드로 만든다

rotate_RL(A) B <- A의 오른쪽 자식 rotate_LL(B)가 반환하는 노드를 A의 오른쪽 자식으로 만든다 rotate_RR(A)

rotate_LR(A) B <- A의 왼쪽 자식 rotate_RR(B)가 반환하는 노드를 A의 왼쪽 자식으로 만든다 rotate_LL(A)

종합적인 예제 (1) 다음 데이터 리스트에 대한 AVL 트리 생성 과정: (7, 8, 9, 2, 1, 5, 3, 6, 4)

종합적인 예제 (2)