검색

선형검색

선형 검색이란?

• 선형검색은 주어진 데이터에서 키 값에 의하여 데이터를 찾는 과정이다. 검색 방법 중 가장 단순하다.

선형검색 알고리즘

int sequential_search(int keys[], int find_key, int n)
{
int i=0;
while(i<=n)
	{i++
	if(keys[i]==find_key return i;}
return 0;

이진 검색

이진검색이란?

• 이진검색은 정렬된 데이터에서 사용하는 방법
• 이진 검색은 정렬된 데이터에서 찾으려는 값과 리스트의 가운데와 비교하여 찾는 방법이다. 비교해서 찾는 데이터가 아니더라도 정렬되어 있기 때문에 찾는 값이 가운데 값보다 크면 오른쪽, 작으면 왼쪽 반을 비교해 나가면 된다.
• 매번 비교할 때 마다 비교 대상 리스트를 1/2로 줄여 나갈 수 있다.

이진탐색 알고리즘-반복

int binsearch(int list[], int searchnum, int left, int right) 

int middle; 
while(left < — right){ 
	middle=(left+right)/2; 
	if( list[middle] < searchnum ) 
		left = middle +1 
	else if ( list[middle] > searchnum ) 
		right = middle - 1; 
	else if ( list[middle]==searchnum ) 
		return middle; }
return —1 ; 
}

이진탐색 알고리즘-순환

int binsearch(int list[], int searchnum, int left, int right) 
{int middle; 
if(left<=right){ 
middle=(left+right)/2; 
switch(COMPARE(list[middle], searchnum)) 
	case -1 :return 	binsearch(list, searchnum, middle+l, right); 
	O:return middle; 
	case 1:return binsearch(list, searchnum, left, middle—I); }}
	return -1 ; 
}

분석

• while 문을 반복하는 횟수가 이진 탐색의 시간이된다.
• O(log n)

Q 11.1

1. 이진탐색
   1. 다음 데이터를 이진 검색할 경우 최악의 경우 몇 번을 비교해야 하는가?4번
   2. 풀이: 마지막까지 비교한다면(데이터가 1개인 리스트까지 비교한다면) 비교 대상 데이터 수는 11개->5개->2개->1개 이므로 최악의 경우 4번 비교하게 된다.
   3. 11개의 데이터
   4. 데이터가 1000개인 정렬된 데이터에서 임의의 데이터 x를 이진 검색으로 찾을 때 최소 비교 회수와 최대 비교 회수는?
      1. 1번, 최대 비교 횟수: 10번

해시탐색

해싱이란?

• 해싱은 찾으려는 키 값을 조작하여 데이터를 바로 찾는 것을 말한다.
• 앞의 선형검색이 평균 n/2번 비교하고 이진검색이 log n 비교하는 것과 비교하면 비교도 없이 바로 찾을 수 있어서 검색중에서는 가장 빠르다.
• 데이터가 충돌 될 수 있다. 방법을 잘못 택하면 충돌이 심해진다는 것을 알 수 있다. 키 값이 23,123,233이면 모두 같은 위치에 저장된다는 것을 알 수 있다.

정의

해시 테이블 : 키 값을 저장하는 테이블

• b: 버킷 : 테이블의 크기, 해시 될 키 값의 법위
• s: 슬롯 : 한 개의 버킷에 저장될 키 값의 개수

• 전체 저장 할 수 있는 데이터의 개수는 s*b이다.

해시 테이블의 식별자 밀도 : n/T

• n: 테이블에 식별자 수
• T : 전체 가능한 식별자 수
• ex) 테이블에 저장된 식별자 수를 50개라 하고 전체 가능한 식별자 수를 100개라고 하면 식별자 밀도는 50/100=0.5이다.

적재 밀도

a=n/(s*b)

• ex) 저장될 데이터가 n=90개이고 해시테이블의 버킷이 100개 슬롯이 2개라면 적재 밀도는 90/(100*2)=0.45이다.
• 즉 데이터가 다 저장되면 기억장소 활용률은0.45이다.

동의어

• 두 식별자 i1과 i2가 해시 함수 f에 대하여 계산을 했을 때 같은 값을 갖는 경우 동의어라고 한다

오버플로우

• full인 상태의 bucket에 식별자 i가 해시되어 들어오는 경우 더 이상 데이터를 저장할 수 없는 상태를 말한다.

 

충돌

• 서로 다른 식별자가 같은 bucket에 해시되는 경우
• 충돌이 일어나면 한 버킷에 데이터를 저장할 슬롯이 충분하면 저장이 가능
• 충분하지 않으면 오버플로우가 발생
  • 오버플로우가 일어나면 데이터를 다른 곳에 저장 해야 함
  • 충돌과 오버플로우는 버킷 크기가 1일 경우 항상 같이 일어난다.

예

• 변수 이름을 해시 테이블에 저장하는 예
• 해시 테이블 이름 ht 버킷의 수 b=26, 슬롯 s=3, 해시 함수 f=(식별자의 영문 첫 글자) 식별자 = {acos, atan, char, ceil, exp, float, define,,…..}
  • 앞 단어가 같으면 같은 곳에 들어감

해시함수

1. 해시함수는 식별자 x를 변환하여 해시 테이블의 버킷 주소로 바꾼다.
2. 좋은 해시함수의 조건
   • 계산이 편해야 한다.
   • 충돌을 최소화하여야 한다.
3. uniform hash function : 충돌을 최소화하는 함수의 성질
   • 확률함수 f(x)=i; 1/b를 갖는 함수이다.
   • 즉 random 값 x가 버킷의 어느 위치에 들어갈 확률이 같은 경우이다.

해시함수의 기법

1. mid-square
   • 식별자의 제곱 값의 가운데 값을 취한다
   1. 식별자의 제곱을 계산한다.
   2. 계산된 값의 가운데 숫자(비트)를 이용하여 버킷을 계산한다
      • 예를 들면 3으로 끝나는 수의 곱은 9가 되기 때문에 동의어가 될 가능성이 높다. 따라서 제곱값의 뒷부분을 이용하면 좋지 않은 방법이다.
   3. 가운데 값을 이용하는 것이 uniform 분포를 가질 가능성이 많다
2. division
   • 나머지 연산자를 이용한다.
   • fp(x) = x%M, M: 테이블 사이즈
     • bucket 주소의 범위 0~M-1
     • M값 선택이 중요하다. M을 소수로 정한다.
3. digit analysis
   • 키 값의 자리 수를 분석하여 분포가 고른 자리 수를 해시 값으로 사용한다
     • 접지법이라고 하며 키 값을 접어서 조작을 하는 방법이다.
     • 접지하는 방법이 여러가지이다
     • 식별자 x =12320324000220 folding

오버플로우 문재해결

• 해싱에서는 오버플로우는 반드시 일어난다. 오버플로우를 해결하는 방법은 다양하고 성능에 영향을 미친다.

1. 개방주소법 : 해시 영역 내에서 빈 공간을 찾아서 해결하는 방법이다.
   • 선형조사법과 2차 조사법이 있다.
   1. 선형조사법
      • 해시 테이블을 1차원 배열로 보고 충돌이 일어나고 해당 버킷에 저장이 어려우면 다음 버킷에 저장하는 방법이다.

      //해시 함수 문자 변수 포인터른 key 값을 증가시키면서 
      //number 변수에 문자값을 계속 더한다.
      //문자열의 끝에서 덧셈을 종료한다.
      int transform(char *key){
      	int number=0;
      	while(*key){number=number+*key++;}
      	return number;}
      
      //버킷 주소 행성 함수
      int hash(char *key){
      	return(transform(key) % TABLE_SIZE};}
      
      

      • 앞의 해시함수를 이용하여 아래의 식별자를 해싱하여 해시 값을 구한 다음 해시테이블에 저장한다.
        • 식별자 : for, do, while, if, else, function
        • 해시테이블 : b=13,s=1
        선형조사법의 단점
        • 충돌이 한 버킷에 집중하는 경향이 있다.
        • 검색 시간을 증가시킨다
        • 예 : C언어의 내장함수 이름을 26 버킷과 1개의 슬롯을 가진 해시테이블에 다음과 같이 삽입한다.
          • acos, atoi, char, define, exp, cos, float,…,
          → 단점 : atol 같은 키워드는 원래 저장될 위치보다 훨씬 아래쪽에 위치한다.
      • 선형조사법에 의한 오버플로우 조작
      
   2. 2차 조사법
      • 해시 테이블의 버킷을 조사하여 1의 제곱, 2의 제곱, 3의 제곱 순으로 새로운 위치를 찾는다. 평균 조사 시간을 중릴 수 있다.
      
2. 재해싱
   • 오버플로우 상태에서 다른 해시 함수를 사용하는 것을 말한다.
   • 새로운 해시 함수 f1,f2,…fb를 계속해서 적용한다
   • 버킷 fi(x) i=1,2,…,b를 조사한다
3. chaining
   • 선형조사법의 단점을 극복한다.
   • 식별자 저장 버킷의 기억장소 공간을 늘려서 해결한다.
   • 버킷에 연결리스트를 만든다.
     • 연결리스는 무한정 증가 시킬 수 있기 때문에 오버플로우를 쉽게 해결
   • 각 연결리스트는 동의어를 저장한다

이진탐색트리(BST)

• 동적 데이터의 관리

이진탐색 트리의 정의

• 이진 탐색 트리는 이진 트리이며 empty이거나 다음을 만족하는 트리
  1. 모든 노드는 키 값을 갖고 있으며 같은 키 값을 갖는 경우는 없다.
  2. 왼쪽 부속 트리의 모든 노드의 키 값은 루트의 키 값보다 작다
  3. 오른쪽 부속 트리의 모든 노드의 키 값은 루트의 키 값보다 크다
  4. 왼쪽과 오른쪽 부속 트리도 마찬가지로 BST이다.

성질

• 탐색, 삽입, 삭제 시간은 트리의 높이만큼 시간이 걸린다. O(h), h: BST의 깊이
• 키 값에 의한 탐색은 루트 노드로부터 시작을 한다. 비교하여 키 값이 더 크면 오른쪽 트리로 이동하며 작으면 왼쪽 트리로 이동한다. 이 같은 방법으로 원하는 데이터를 찾아 내려간다.
• 트리를 중위 탐색하면 정렬된 리스트가 출력된다.

/*이진탐색트리에서의 키 값 찾는 알고리즘 - 반복 알고리즘 */
tree_ptr iter_search(tree_ptr tree, int key)
{while(tree) { //tree가 not null일때
	if(key tree—>data) return tree; /*찾음*/
	if(key < tree—>data) tree = tree—>left_child; /*왼쪽트리에서검색*/
	else tree = tree-> right)child; /*오른쪽 트리에서 검색*/
	return NULL; /*찾지 못함*/
}

/*이진탐색트리에서의 키 값 찾는 알고리즘-순환 알고리즘*/
tree_ptr search(tree_ptr root, int key){
	if(!root) return NULL ;
		if(key root—>data) return root;
		if(key<root->data)	return search (root—>left_child, key);
	return search(root->right_child, key);
}

알고리즘

생성 알고리즘

treetraversal.c 
#include <stdio.h> 
#include <malloc.h> 
struct tnode { 
	int data; 
	struct tnode * left_child; 
	struct tnode * right_child; };

typedef struct tnode node; 
typedef node *tree_ptr; 

tree_ptr insert(tree_ptr head, int number) {...}

int main() {
	int i, number[10] = {23, 24, 42, 13, 28, 56, 32, 14, 31, 17}; 
	tree_ptr head = NULL; 
	/* 데이터 10개로 트리를 미리 구성, */ 
	for(i-0;i<10;i++){
	**head = insert(head,number[i]);** };
}

삽입 알고리즘

tree_ptr insert(tree_ptr head, int number) {
	tree_ptr temp=NULL; 
	tree_prt insertpoint=	NULL; 
/*	head 값이 NULL이면 빈트리이므로 노드를 만들고head 값을 반환*/
	if(! head) 
	{ temp = (tree_ptr)malloc(sizeof(node)); 
	temp—>data = number; 
	temp—>left_child = temp—>right_child = NULL; 
	return temp; }

/* head a.k01 NULL */

insertpoint = head;

for( ; ;){
	//printf("%d insertpoint—>data);
	if ((insertpoint—>data >number) && (insertpoint—>left_child!=NULL))
		insertpoint — insertpoint—>left_child;
	else if (insertpoint—>data==number) return head;
	else if ((insertpoint—>data < number) && (insertpoint—>right_child !=NULL))
		insertpoint = insertpoint—>right_child;
	else break;
}

	**temp = (tree_ptr)malloc(sizeof(node));
	temp—>data = number;
	temp—>left_child = temp —>right_child = NULL;
	if (insertpoint—>data < number) insertpoint-> right_child= temp;
	else insertpoint—>left_child=temp;**
return head;}

단점

• 시간 복잡도가 다음과 같다. 최악의 경우가 문제가 된다. BST에서 삽입 순서에 따라 최악의 경우 skewed 트리가 된다.
  • 평균 (average case) : O(log2n)
  • 최악(worst case): O(n)
• 이진 탐색 트리를 완전 이진 트리로 바꿀 수 있다면 최악의 경우 없앨 수 있다.
  • 새로운 원소를 삽일 할 때 삽입시간을 줄인다
  • 평균과 최악의 시간이 같다 O(log2 n)

AVL tree

정의

• 균형 이진 트리이다. 이진 트리에서 모든 노드의 왼쪽과 오른쪽 트리의 높이차를 1이하로 만든 트리이다.
• 평균과 최악의 경우 O(log2 n)

높이균형 이진트리

• 빈 트리이거나 아닐경우
• T가 이진트리이고 Tl과 Tr을 왼쪽과 오른쪽 부속 트리라고 하면 T가 높이균형 트리라고 하며 다음을 만족한다.
  1. Tl과 Tr이 높이 균형 트리이고
  2. |hl=hr|≤1, hl과 hr이 Tr과 Tr의 높이

균형인자

• hl=hr, hl와 hr는 트리의 왼쪽과 오른쪽 트리의 높이
• AVL 트리의 모든 노드에 대하여 BF(T)=-1,0,1이다.

높이 균형 이진트리 만들기

• 비어있는 트리로부터 혹은 이미 구성된 AVL 트리로부터 노드를 삽입하거나 삭제할 경우 트리의 높이 균형이 깨지면서 BF 값이 +2혹은 -2가 될 수 있다.
• 균형이 깨진 트리의 모양에 따라 다음과 같이 구분하여 균형을 다시 맞춘다. 균형을 맞추려면 다음과 같이 회전을 하여야한다.
  • 4가지 회전

LL

• 삽입 후 +2가 되는 노드를 기준으로 왼쪽 자신을 루트로 만든다.

LR

• 삽입 후 +2가 되는 노드를 기준으로 왼쪽 자식의 오른쪽 자식을 루트로 만든다.

 

RR

• 삽입 후 +2가 되는 노드를 기준으로 오른쪽 자식을 루트로 만든

RL

• 삽입 후 -2가 되는 노드를 기준으로 오른쪽 자식의 왼쪽 자식을 루트로 만든다.

분석

• 이진 탐색 트리의 단점을 극복하여 트리의 높이를 균형을 맞춘 것
• 트리의 높이가 log n 이기 때문에 검색시간의 복잡도는 O(log n)
• 데이터를 삽입하고 삭제할 때 트리의 균형인자가 깨지는 경우가 있기 때문에 균형인자가 +2 혹은 -2가 되는 노드를 대상으로 트리를 회전하여 균형을 다시 맞춰야 한다.
• 검색, 삽입, 삭제의 평균과 최악의 경우 : O(log2 n)

 

B-tree

m-way 탐색트리

• m-way 탐색 트리는 이진 트리와 달리 각 노드에서 나가는 자식노드가 최대 m인 탐색 트리를 말한다.
• m-way 탐색 트리의 성질
  • 트리에 있는 각 노드는 아래와 같은 구조를 갖는다 n은 노드에 있는 키 값 개수, p(i)는 자식 노드 링크, k(i)는 키 값
  • 한 노드 안에 키 값은 오름차순으로 정렬
  • p(i)가 가리키는 자식 노드 트리에 있는 노드의 모든 키 값은 k(i) 값보다 크고 k(i+1)보다 작다
  • p(i)가 가리키는 자식노드도 역시 m-way 탐색 트리이다.

ex)

• 2진 탐색 트리와 3-way(3원 탐색트리) 탐색 트리의 비교

• 3-way 트리는 2진 트리에 비해 높이가 낮다.
• 2진 탐색트리에서의 탐색과정은 한 단계 한 단계 진행할 때 노드 개수가 반으로 줄어 들지만 3-way 트리에서는 1/3으로 줄어든다.

차수 m 의 B-트리

• m-원 탐색 트리의 성능 향상을 위해서는 m을 크게하고 트리가 균형이 되도록 해야 한다. m-원 탐색 트리에 트리의 높이에 제한을 두어 탐색을 효율적으로 진행되도록 한 것이 B-트리이다.

정의

• b-트리는 m-way 탐색트리로 다음을 만족한다.
  1. 트리에 있는 각 노드는 최대 m개, 최소 m/2개의 종속 트리를 갖는다.
  2. 뿌리노드는 최소한 두 개의 종속 트리를 갖는다.
  3. 모든 잎 노드는 같은 서열에 있어야 한다.
  4. 노드에 있는 키 값 개수는 종속 트리의 개수보다 하나 적으며 최소 (m/2)-1개 최대 m-1개이다.

B트리에서 키 값의 삽입

1. B 트리에서 연산을 수행한 수에도 b-트리의 성질을 보존해야 함
2. B- 트리는 거의 균형된 트리이므로 AVL 트리에서의 경우와 같이 연산이 끝난 후에 트리가 균형되어 있어야 한다.
3. 새로운 키 값은 항상 잎에 삽입된다.
4. 해당 노드가 가득 차 있찌 않은 경우는 키 값을 오름차순으로 채운다.
5. 해당 노드가 가득 찬 경우 해당 노드를 두 개의 노드로 분열한다.

노드의 분열 방법

• 해당 노드의 키 값들과 새로운 키 값 중에서 중간 키 값을 부모 노드로 올려 보내고 나머지 키 값들을 전반으로 나누어 각 절반씩 분열된 두 개의 노드에 옮기며 이 두 노드들을 부모 노드로 올라간 키 값의 왼쪽과 오른쪽 종속 트리가 되도록 한다.

B트리에서 삽입의 예

• 그림 2의 B-트리에 다음의 키 값을 차례로 추가 삽입
• 왼쪽은 원래 노드 모양이고 오른쪽은 합입 후 변경된 모양이다.