다음 주 과제 기말고사 시험범위 : 6장 ~12장 필기시험 : 2015년 12월 18일(5교시) 필기장소 : E327

Presentation on theme: "다음 주 과제 기말고사 시험범위 : 6장 ~12장 필기시험 : 2015년 12월 18일(5교시) 필기장소 : E327"— Presentation transcript:

1 해시, 탐색 E304호, hwlee@inje.ac.kr

2 다음 주 과제 기말고사 시험범위 : 6장 ~12장 필기시험 : 2015년 12월 18일(5교시) 필기장소 : E327
실기시험 : 2015년 12월 18일(6,7교시) 실기장소 : E323, E531

3 CHAP 11 : 해싱 C로 쉽게 풀어쓴 자료구조 생능출판사

4 해싱이란? 대부분의 탐색 방법들은 키 값 비교로써 탐색하고자 하는 항목에 접근 해싱(hashing)
키 값에 대한 산술적 연산에 의해 테이블의 주소를 계산하여 항목에 접근 해시 테이블(hash table) 키 값의 연산에 의해 직접 접근이 가능한 구조 해싱은 물건을 정리하는 것과 같다

5 추상자료형 사전구조 사전구조(dictionary) 맵(map) 또는 테이블(table)로 불리움
탐색키와 탐색키와 관련된 값의 2가지 필드로 구성 영어 단어나 사람의 이름같은 탐색키(search key) 단어의 정의나 주소 또는 전화 번호같은 탐색키와 관련된 값(value) ∙객체: 일련의 (key,value) 쌍의 집합 ∙연산: ▪ add(key, value) ::= (key,value)를 사전에 추가한다. ▪ delete(key) ::= key에 해당되는 (key,value)를 찾아서 삭제한다. 관련된 value를 반환한다 만약 탐색이 실패하면 NULL를 반환한다. ▪ search(key) ::= key에 해당되는 value를 찾아서 반환한다. 만약 탐색이 실패하면 NULL를 반환한다.

6 해싱의 구조 해시 함수(hash function) 탐색키를 입력받아 해시 주소(hash address) 생성
이 해시 주소가 배열로 구현된 해시 테이블(hash table)의 인덱스

7 해시 테이블의 구조 해시테이블 ht 충돌(collision) 오버플로우(overflow)
M개의 버켓(bucket)으로 구성된 테이블 ht[0], ht[1], ...,ht[M-1]의 원소를 가짐 하나의 버켓에 s개의 슬롯(slot) 가능 충돌(collision) 서로 다른 두 개의 탐색키 k1과 k2에 대하여 h(k1) = h(k2)인 경우 오버플로우(overflow) 충돌이 버켓에 할당된 슬롯 수보다 많이 발생하는 것 오버플로우 해결 방법 반드시 필요

8 이상적인 해싱 학생 정보를 해싱으로 저장, 탐색해보자
5자리 학번 중에 앞 2자리가 학과 번호, 뒤 3자리가 각 학과의 학생 번호 같은 학과 학생들만 가정하면 뒤의 3자리만 사용해서 탐색 가능 학번이 00023이라면 이 학생의 인적사항은 해시테이블 ht[23]에 저장 만약 해시테이블이 1000개의 공간을 가지고 있다면 탐색 시간이 O(1)이 되므로 이상적임

9 실제의 해싱 실제로는 해시테이블의 크기가 제한되므로, 존재 가능한 모든 키에 대해 저장 공간을 할당할 수 없음
h(k)= k mod M 의 예에서 보듯이 필연적으로 충돌과 오버플로우 발생함

10 실제의 해싱(cont.) 알파벳 문자열 키의 해시함수가 키의 첫 번째 문자의 순서라고 하자 h("array")=1
h("binary")=2 입력데이터: array, binary, bubble, file, digit, direct, zero, bucket

11 해시함수 좋은 해시 함수의 조건 충돌이 적어야 한다 해시함수 값이 해시테이블의 주소 영역 내에서 고르게 분포되어야 한다
계산이 빨라야 한다

12 해시함수(cont.) 제산(나머지) 함수 폴딩 함수 h(k)=k mod M
해시 테이블의 크기 M은 소수(prime number) 선택 폴딩 함수 이동 폴딩(shift folding)과 경계 폴딩(boundary folding)

13 해시함수(cont.) 중간제곱 함수 비트추출 함수 숫자 분석 방법
탐색키를 제곱한 다음, 중간의 몇 비트를 취해서 해시 주소 생성 비트추출 함수 탐색키를 이진수로 간주하여 임의의 위치의 k개의 비트를 해시 주소로 사용 숫자 분석 방법 키 중에서 편중되지 않는 수들을 해시테이블의 크기에 적합하게 조합하여 사용

14 충돌해결책 충돌(collision) 충돌해결책 서로 다른 탐색 키를 갖는 항목들이 같은 해시 주소를 가지는 현상
충돌이 발생하면 해시 테이블에 항목 저장 불가능 충돌을 효과적으로 해결하는 방법 반드시 필요 충돌해결책 선형조사법: 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장 체이닝: 각 버켓에 삽입과 삭제가 용이한 연결 리스트 할당

15 선형조사법(linear probing)
충돌이 ht[k]에서 발생했다면, ht[k+1]이 비어 있는지 조사 만약 비어있지 않다면 ht[k+2] 조사 비어있는 공간이 나올 때까지 계속 조사 테이블의 끝에 도달하게 되면 다시 테이블의 처음부터 조사 조사를 시작했던 곳으로 다시 되돌아오게 되면 테이블이 가득 찬것임 조사되는 위치: h(k), h(k)+1, h(k)+2,… 군집화(clustering)과 결합(Coalescing) 문제 발생

16 선형조사법(linear probing)
(예) h(k)=k mod 7 1단계 2단계 3단계 4단계 5단계 [0] 13 [1] 8 [2] 1 [3] 9 [4] [5] [6] 6 1단계 (8) : h(8) = 8 mod 7 = 1(저장) 2단계 (1) : h(1) = 1 mod 7 = 1(충돌발생)             (h(1)+1) mod 7 = 2(저장) 3단계 (9) : h(9) = 9 mod 7 = 2(충돌발생)             (h(9)+1) mod 7 = 3(저장) 4단계 (6) : h(6) = 6 mod 7 = 6(저장) 5단계 (13) : h(13) = 13 mod 7 = 6(충돌 발생) (h(13)+1) mod 7 = 0(저장)

17 선형조사법(linear probing)
(예) “do”, “for”, “if”, “case”, “else”, “return”, “function’ M=13

18 선형조사법(linear probing)

19 이차 조사법(quadratic probing)
선형 조사법과 유사하지만, 다음 조사할 위치를 아래 식 사용 (h(k)+inc*inc) mod M 조사되는 위치는 다음과 같음 h(k), h(k)+1, h(k)+4,… 선형 조사법에서의 문제점인 군집과 결합 크게 완화 가능

20 이중해싱법(double hashing)
재해싱(rehashing)이라고도 함 오버플로우가 발생하면 원 해시함수와 다른 별개의 해시 함수 사용 step=C-(k mod C) h(k), h(k)+step, h(k)+2*step, … (예) 크기가 7인 해시테이블에서, 첫 번째 해시 함수가 k mod 7 오버플로우 발생시의 해시 함수는 step=5-(5 mod 5) 입력 (8, 1, 9, 6, 13 ) 적용

21 이중해싱법(double hashing)
1단계 (8) : h(8) = 8 mod 7 = 1(저장) 2단계 (1) : h(1) = 1 mod 7 = 1(충돌발생) (h(1)+h‘(1)) mod 7 = (1+5-(1 mod 5)) mod 7 = 5(저장) 3단계 (9) : h(9) = 9 mod 7 = 2(저장) 4단계 (6) : h(6) = 6 mod 7 = 6(저장) 5단계 (13) : h(13) = 13 mod 7 = 6(충돌 발생) (h(13)+h‘(13)) mod 7 = (6+5-(13 mod 5)) mod 7= 1(충돌발생) (h(13)+2*h‘(13)) mod 7 = (6+2*2) mod 7= 3(저장) 1단계 2단계 3단계 4단계 5단계 [0] [1] 8 [2] 9 [3] 13 [4] [5] 1 [6] 6

22 체이닝(chaining) 오버플로우 문제를 연결 리스트로 해결 (예) 크기가 7인 해시테이블에서
각 버켓에 고정된 슬롯이 할당되어 있지 않음 각 버켓에, 삽입과 삭제가 용이한 연결 리스트 할당 버켓 내에서는 연결 리스트 순차 탐색 (예) 크기가 7인 해시테이블에서 h(k)=k mod 7의 해시 함수 사용 입력 (8, 1, 9, 6, 13) 적용

23 체이닝(chaining) 1단계 (8) : h(8) = 8 mod 7 = 1(저장)

24 해싱의 성능분석 적재 밀도(loading density) 또는 적재 비율(loading factor)
저장되는 항목의 개수 n과 해시 테이블의 크기 M의 비율 선형 조사법에서의 비교 연산 체이닝에서의 비교 연산

25 해싱의 성능분석(cont.) 선형조사법에서의 비교 연산 횟수

26 해싱의 성능분석(cont.) 체인닝에서의 비교 연산 횟수

27 V.Lum, P.Yuen, M.Dodd, CACM, 1971, Vol.14, No.4 참조
해싱의 성능분석(cont.) 각 알고리즘에 따른 평균 버켓 접근 수 V.Lum, P.Yuen, M.Dodd, CACM, 1971, Vol.14, No.4 참조

28 해싱과 다른 탐색 방법의 비교

29 CHAP 12 : 탐색 C로 쉽게 풀어쓴 자료구조 생능출판사

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

31 순차 탐색(sequential search)
탐색 방법 중에서 가장 간단하고 직접적인 탐색 방법 정렬되지 않은 배열을 처음부터 마지막까지 하나씩 검사하는 방법 평균 비교 횟수 탐색 성공: (n + 1)/2번 비교 탐색 실패: n번 비교 시간 복잡도: O(n) 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; // 탐색 실패 }

32 개선된 순차탐색 반복문의 리스트 끝 테스트 배제 리스트 끝에 탐색 키 저장 키 값을 찾을 때 반복문 탈출 8 8 8
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; // 탐색 성공 } 8 8 8

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

34 이진탐색

35 이진탐색 알고리즘 이진탐색 프로그램(재귀) int search_binary2(int key, int low, int high)
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]에서의 탐색; 이진탐색 프로그램(재귀) int search_binary2(int key, int low, int high) {int middle; while( low <= high ){ // 아직 숫자들이 남아 있으면 middle = (low+high)/2; if( key == list[middle] ) return middle; // 탐색 성공 else if( key > list[middle] ) low = middle+1; // 왼쪽 부분리스트 탐색 else high = middle-1; // 오른쪽 부분리스트 탐색 } return -1; // 탐색 실패

36 이진탐색

37 색인 순차탐색 (indexed sequential search)
주 자료 리스트에서 일정 간격으로 발췌한 자료 저장 주 자료 리스트와 인덱스 테이블은 모두 정렬되어 있어야 함 복잡도: O(m+n/m) 인덱스 테이블의 크기=m, 주자료 리스트의 크기=n

38 보간탐색(interpolation search)
사전이나 전화번호부를 탐색하는 방법 ‘ㅎ’으로 시작하는 단어는 사전의 뒷부분에서 찾음 ‘ㄱ'으로 시작하는 단어는 앞부분에서 찾음 탐색키가 존재할 위치를 예측하여 탐색하는 방법: O(log(n)) 보간 탐색은 이진 탐색과 유사하나 리스트를 불균등 분할하여 탐색

39 보간탐색(interpolation search)

40 균형 이진탐색트리 이진 탐색(binary search)과 이진 탐색 트리(binary search tree)의 차이점
이진 탐색과 이진 탐색 트리는 근본적으로 같은 원리에 의한 탐색 구조 이진 탐색은 자료들이 배열에 저장되어 있으므로 삽입/삭제가 매우 비효율 자료의 삽입/삭제 시 원소들을 모두 이동시켜야 함 이진 탐색 트리는 매우 빠르게 삽입/삭제 수행 삽입, 삭제가 빈번히 이루어진다면 이진탐색트리가 유리함 이진탐색트리에서의 시간복잡도 균형트리: O(log(n)) 불균형트리: O(n), 순차탐색과 동일

41 AVL 트리 Adelson-Velskii와 Landis에 의해 1962년에 제안된 트리
모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차가 1이하인 이진탐색트리 트리가 비균형 상태로 되면 스스로 노드들을 재배치하여 균형 상태 유지 평균, 최선, 최악 시간적복잡도: O(log(n)) 균형 인수(balance factor) =(왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이) 모든 노드의 균형 인수가 ±1 이하이면 AVL 트리

42 AVL 트리의 연산 탐색연산: 이진탐색트리와 동일 삽입 연산과 삭제 연산 시 균형 상태가 깨질 수 있음 삽입 연산
삽입 위치에서 루트까지의 경로에 있는 조상 노드들의 균형 인수 영향 삽입 후에 불균형 상태로 변한 가장 가까운 조상 노드(균형 인수가 ±2가 된 가장 가까운 조상 노드)의 서브 트리들에 대하여 다시 재균형 삽입 노드부터 균형 인수가 ±2가 된 가장 가까운 조상 노드까지 회전

43 AVL 트리의 삽입연산

44 AVL트리의 삽입연산 AVL 트리의 균형이 깨지는 4가지 경우(삽입된 노드 N으로부터 가장 가까우면서 균형 인수가 ±2가 된 조상 노드가 A라면) LL 타입: N이 A의 왼쪽 서브 트리의 왼쪽 서브 트리에 삽입 LR 타입: N이 A의 왼쪽 서브 트리의 오른쪽 서브 트리에 삽입 RR 타입: N이 A의 오른쪽 서브 트리의 오른쪽 서브 트리에 삽입 RL 타입: N이 A의 오른쪽 서브 트리의 왼쪽 서브 트리에 삽입 각 타입별 재균형 방법 LL 회전: A부터 N까지의 경로상 노드의 오른쪽 회전 LR 회전: A부터 N까지의 경로상 노드의 왼쪽-오른쪽 회전 RR 회전: A부터 N까지의 경로상 노드의 왼쪽 회전 RL 회전: A부터 N까지의 경로상 노드의 오른쪽-왼쪽 회전

45 LL 회전 방법

46 RR 회전 방법

47 RL 회전 방법

48 LR 회전 방법

49 AVL 트리 단순회전 알고리즘 AVL 트리 이중회전 알고리즘 rotate_LL(A)
B의 오른쪽 자식을 A의 왼쪽 자식으로 만든다 A를 B의 오른쪽 자식 노드로 만든다. rotate_RR(A) B의 왼쪽 자식을 A의 오른쪽 자식으로 만든다 A를 B의 왼쪽 자식 노드로 만든다. AVL 트리 이중회전 알고리즘 rotate_RL(A) rotate_LL(B)가 반환하는 노드를 A의 오른쪽 자식으로 만든다 rotate_RR(A) rotate_LR(A) rotate_RR(B)가 반환하는 노드를 A의 왼쪽 자식으로 만든다 rotate_LL(A)

50 AVL 트리의 삽입

51 AVL 트리의 삽입

52 AVL 트리의 삽입

53 2-3 트리 차수가 2 또는 3인 노드를 가지는 트리 2-노드 3-노드
이진탐색트리 처럼 하나의 데이터 k1와 두 개의 자식 노드를 가진다 3-노드 2개의 데이터 k1, k2와 3개의 자식노드를 가진다 왼쪽 서브 트리에 있는 데이터들은 모두 k1보다 작은 값이다 중간 서브 트리에 있는 값들은 모두 k1보다 크고 k2보다 작다 오른쪽에 있는 데이터들은 모두 k2보다 크다

54 2-3 트리

55 2-3 트리 삽입의 예

56 2-3 트리 탐색 프로그램 tree23_search(Tree23Node *root, int key) {
if( root == NULL ) // 트리가 비어 있으면 return FALSE; else if( key == root->key1 ) // 루트의 키==탐색 키 return TRUE; else if( root->type == TWO_NODE ) { // 2-노드 if( key < root->key1 ) return tree23_search(root->left, key) else return tree23_search(root->right, key) } else { // 3-노드 else if( key > root->key2 ) return tree23_search(root->middle, key)

57 2-3 트리 단말노드 분리

58 2-3 트리 비단말노드 분리

59 2-3 트리 루트노드 분리