탐색 선형 탐색, 이진 탐색, 이진 탐색 트리.

Presentation on theme: "탐색 선형 탐색, 이진 탐색, 이진 탐색 트리."— Presentation transcript:

1 탐색 선형 탐색, 이진 탐색, 이진 탐색 트리

2 탐색 01. 탐색의 정의 02. 탐색의 종류 03. 선형탐색 (순차 탐색) 04. 이진 탐색 05. 이진 탐색 트리
06. 이진 탐색과 이진 탐색 트리의 차이점

3 탐색

4 탐색

5 탐색 여러 개의 자료 중에서 원하는 자료를 찾는 작업

6 탐색 탐색의 단위 : 항목 ( 탐색키 + 데이터 ) * 탐색키 : 항목과 항목을 구별시켜 주는 키

7 탐색 탐색 키와 데이터로 이루어진 항목 중에서 원하는 탐색 키를 가지고 있는 항목을 찾는 것

8 탐색의 종류 탐색 정렬되지 않은 배열에서의 탐색 정렬된 배열에서의 탐색
순차 탐색 (Sequential Search) = 선형 탐색 이진 탐색(Binary Search) 색인 순차 탐색 보간 탐색

9 순차 탐색(선형 탐색) 9,5,8,3,7 중에 숫자 하나를 생각 해 주세요.

10 순차 탐색(선형 탐색) 9 입니까 ? NO YES

11 순차 탐색(선형 탐색) 5 입니까 ? NO YES

12 순차 탐색(선형 탐색) 8 입니까 ? NO YES

13 순차 탐색(선형 탐색) 3 입니까 ? NO YES

14 순차 탐색(선형 탐색) 7 입니까 ? NO YES

15 순차 탐색(선형 탐색) STOP YES 생각한 숫자는 ( ) 에요.

16 순차 탐색(선형 탐색) 정렬되지 않은 배열의 항목들을 처음부터 마지막까지 검사하여 원하는 항목을 찾아가는 방법

17 순차 탐색(선형 탐색) 7을 찾을 경우

18 순차 탐색(선형 탐색) Function seq_search(key,low,high) {
For(i=low;i<=high;i++) if(list[i]==key) return i; // 탐색 성공 return -1; // 탐색 실패 }

19 이진 탐색 1 ~ 50번까지 있는 소주 병뚜껑 숫자 맞추기 게임 !

20 이진 탐색 ’9’ 일 경우 UP 25 !

21 이진 탐색 ’9’ 일 경우 DOWN 14 !

22 이진 탐색 ’9’ 일 경우 UP 7 !

23 이진 탐색 ’9’ 일 경우 UP 8 !

24 이진 탐색 ’9’ 일 경우 정답 9 !

25 이진 탐색 여기서 부르는 숫자의 공통점은 ?

26 이진 탐색 부르는 범위의 가운데 위치 숫자

27 이진 탐색 25 : 1 ~ 50 까지의 숫자 중 가운데 위치 숫자 14 : 1 ~ 25 까지의 숫자 중 가운데 위치 숫자 7 : 1 ~ 14 까지의 숫자 중 가운데 위치 숫자 8 : 7 ~ 9까지의 숫자 중 가운데 위치 숫자

28 이진 탐색 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 리스트에 있는지 알아내어 탐색의 범위를 반으로 줄여 찾는 방법

29 이진 탐색 찾고자 하는 항목이 속해 있지 않은 부분은 전혀 고려할 필요가 없기 때문에 비교가 이루어질 때 마다 탐색 범위가 반으로 줄어듬. 데이터 삽입, 삭제가 빈번할 때는 적합하지 않고, 고정된 데이터에 대한 탐색에 적합함.

30 이진 탐색

31 이진 탐색 Function search_binary(key,low,high) { while(low<=high) {
middle=(low + high) / 2; if(key==low[middle]) return middle; } else if ( key > list[middle]) { low = middle + 1; } else { high=middle + 1; } return -1;

32 이진 탐색 트리 파일 용량 계산

33 이진 탐색 트리 이진 탐색 트리의 성질을 만족하는 트리 모든 노드의 키는 유일하다.
왼쪽 서브트리의 키들은 루트의 키보다 작다. 오른쪽 서브트리의 키들은 루트의 키보다 크다. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

34 이진 탐색 트리 search(x, k) if x=NULL then return NULL; // 탐색 실패
if k=x->key then return x; // 탐색 성공 else if k<x->key then return search(x->left, k); // 계속 탐색 else return search(x->right, k); // 계속 탐색

35 이진 탐색 트리(삽입) - 이진 탐색 트리에 원소를 삽입하기 위해 먼저 탐색을 수행하는 것이 필요 탐색에 실패한 위치가 바로
- 이진 탐색 트리에 원소를 삽입하기 위해 먼저 탐색을 수행하는 것이 필요 탐색에 실패한 위치가 바로 새로운 노드를 삽입하는 위치

36 이진 탐색 트리(삽입) // key를 이진 탐색 트리 root에 삽입한다.
void insert_node(TreeNode **root, int key) { TreeNode *p, *t; // p는 부모노드, t는 현재노드 TreeNode *n; // n은 새로운 노드 t = *root; p = NULL; // 탐색을 먼저 수행 while (t != NULL) { if ( key == t->key ) return; p = t; if ( key < t->key ) t = t->left; else t = t->right; }

37 이진 탐색 트리(삽입) // key가 트리 안에 없으므로 삽입 가능
n = (TreeNode *) malloc(sizeof(TreeNode)); if ( n == NULL ) return; // 데이터 복사 n->key = key; n->left = n->right = NULL; // 부모 노드와 링크 연결 if ( p != NULL ) if ( key < p->key ) p->left = n; else p->right = n; else *root = n; }

38 이진 탐색 트리(삭제) 3가지의 경우 1. 삭제하려는 노드가 단말 노드일 경우
2. 삭제하려는 노드가 하나의 왼쪽이나 오른쪽 서브 트리중 하나만 가지고 있는 경우 3. 삭제하려는 노드가 두개의 서브 트리 모두 가지고 있는 경우

39 이진 탐색 트리(삭제) 1. 삭제하려는 노드가 단말 노드일 경우
- 단말의 부모노드를 찾아서 부모 노드 안의 해당 필드를 NULL로 만들어 연결을 끊음.

40 이진 탐색 트리(삭제) 2. 삭제하려는 노드가 하나의 서브트리만 갖고 있는 경우
- 자기 노드 삭제하고, 그 서브 트리를 자기 노드의 부모 노드가 가리키게 한다.

41 이진 탐색 트리(삭제) 3. 삭제하려는 노드가 두개의 서브트리를 갖고 있는 경우
삭제 되는 노드와 가장 값이 비슷한 노드를 후계자로 !

42 이진 탐색 트리(삭제) 3. 삭제하려는 노드가 두개의 서브트리를 갖고 있는 경우

43 이진 탐색 트리(삭제) // 삭제 함수 void delete_node(TreeNode **root, int key) {
TreeNode *p, *child, *succ, *succ_p, *t; // key를 갖는 노드 t를 탐색, p는 t의 부모노드 p = NULL; t = *root; // key를 갖는 노드 t를 탐색한다. while ( t != NULL && t->key != key ) { p = t; t = ( key < t->key ) ? t->left : t->right; } // 탐색이 종료된 시점에 t가 NULL이면 트리안에 key가 없음 if ( t == NULL ) { // 탐색트리에 없는 키 printf("key is not in the tree"); return;

44 이진 탐색 트리(삭제) // 첫번째 경우: 단말노드인 경우
if ( (t->left==NULL) && (t->right==NULL) ) { if ( p != NULL ) { // 부모노드의 자식필드를 NULL로 만든다. if ( p->left == t ) p->left = NULL; else p->right = NULL; } else // 만약 부모노드가 NULL이면 삭제되는 노드가 루트 *root = NULL;

45 이진 탐색 트리(삭제) // 두번째 경우: 하나의 자식만 가지는 경우
else if ((t->left==NULL)||(t->right==NULL)) { child = (t->left != NULL) ? t->left : t->right; if ( p != NULL ) { if ( p->left == t ) // 부모를 자식과 연결 p->left = child; else p->right = child; } else // 만약 부모노드가 NULL이면 삭제되는 노드가 루트 *root = child;

46 이진 탐색 트리(삭제) // 세번째 경우: 두개의 자식을 가지는 경우 else{ // 오른쪽 서브트리에서 후계자를 찾는다.
succ_p = t; succ = t->right; // 후계자를 찾아서 계속 왼쪽으로 이동한다. while(succ->left != NULL){ succ_p = succ; succ = succ->left; }

47 이진 탐색 트리(삭제) // 후속자의 부모와 자식을 연결 if( succ_p->left == succ )
succ_p->left = succ->right; // succ 노드의 우측 서브트리를 연결 else succ_p->right = succ->right; // succ 노드의 왼쪽 서브트리가 없는 경우 // 후속자가 가진 키값을 현재 노드에 복사 t->key = succ->key; // 원래의 후속자 삭제 t = succ; } free(t);

48 이진 탐색과 이진 탐색 트리의 차이점 삽입, 삭제가 용이하냐, 안하냐

49 이진 탐색과 이진 탐색 트리의 차이점 이진 탐색 : 자료들이 배열에 저장되어 있으므로 삽입, 삭제 할 때마다 앞뒤의 원소들을 이동 시켜야 함.

50 이진 탐색과 이진 탐색 트리의 차이점 이진 탐색 트리 : 비교적 빠른 시간 안에 삽입과 삭제를 끝마칠 수 있는 구조로 되어 있음.

51 이진 탐색과 이진 탐색 트리의 차이점 5 { 5, 2, 8, 3,1, 3, 7, 9} 순서로 삽입 했을 때 2 8
최대 비교 횟수 3번 이진 탐색 트리 – 균형 트리

52 이진 탐색과 이진 탐색 트리의 차이점 { 1, 2, 3, 5, 7, 8, 9} 순서로 삽입 했을 때 1 2
{ 1, 2, 3, 5, 7, 8, 9} 순서로 삽입 했을 때 이진 탐색 트리 – 불균형 트리 1 2 3 5 7 8 9 최대 비교 횟수 7번

53 이진 탐색과 이진 탐색 트리의 차이점 이진 탐색 트리에서는 균형을 유지하는 것이 중요함!

54 감사합니다