Cohe
검색 본문
728x90
선형검색
선형 검색이란?
- 선형검색은 주어진 데이터에서 키 값에 의하여 데이터를 찾는 과정이다. 검색 방법 중 가장 단순하다.
선형검색 알고리즘
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
- 이진탐색
- 다음 데이터를 이진 검색할 경우 최악의 경우 몇 번을 비교해야 하는가?4번
- 풀이: 마지막까지 비교한다면(데이터가 1개인 리스트까지 비교한다면) 비교 대상 데이터 수는 11개->5개->2개->1개 이므로 최악의 경우 4번 비교하게 된다.
- 11개의 데이터
- 데이터가 1000개인 정렬된 데이터에서 임의의 데이터 x를 이진 검색으로 찾을 때 최소 비교 회수와 최대 비교 회수는?
- 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,,…..}
- 앞 단어가 같으면 같은 곳에 들어감
해시함수
- 해시함수는 식별자 x를 변환하여 해시 테이블의 버킷 주소로 바꾼다.
- 좋은 해시함수의 조건
- 계산이 편해야 한다.
- 충돌을 최소화하여야 한다.
- uniform hash function : 충돌을 최소화하는 함수의 성질
- 확률함수 f(x)=i; 1/b를 갖는 함수이다.
- 즉 random 값 x가 버킷의 어느 위치에 들어갈 확률이 같은 경우이다.
해시함수의 기법
- mid-square
- 식별자의 제곱 값의 가운데 값을 취한다
- 식별자의 제곱을 계산한다.
- 계산된 값의 가운데 숫자(비트)를 이용하여 버킷을 계산한다
- 예를 들면 3으로 끝나는 수의 곱은 9가 되기 때문에 동의어가 될 가능성이 높다. 따라서 제곱값의 뒷부분을 이용하면 좋지 않은 방법이다.
- 가운데 값을 이용하는 것이 uniform 분포를 가질 가능성이 많다
- division
- 나머지 연산자를 이용한다.
- fp(x) = x%M, M: 테이블 사이즈
- bucket 주소의 범위 0~M-1
- M값 선택이 중요하다. M을 소수로 정한다.
- digit analysis
- 키 값의 자리 수를 분석하여 분포가 고른 자리 수를 해시 값으로 사용한다
- 접지법이라고 하며 키 값을 접어서 조작을 하는 방법이다.
- 접지하는 방법이 여러가지이다
- 식별자 x =12320324000220 folding
- 키 값의 자리 수를 분석하여 분포가 고른 자리 수를 해시 값으로 사용한다
오버플로우 문재해결
- 해싱에서는 오버플로우는 반드시 일어난다. 오버플로우를 해결하는 방법은 다양하고 성능에 영향을 미친다.
- 개방주소법 : 해시 영역 내에서 빈 공간을 찾아서 해결하는 방법이다.
- 선형조사법과 2차 조사법이 있다.
- 선형조사법
- 해시 테이블을 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,…,
- 선형조사법에 의한 오버플로우 조작
- 2차 조사법
- 해시 테이블의 버킷을 조사하여 1의 제곱, 2의 제곱, 3의 제곱 순으로 새로운 위치를 찾는다. 평균 조사 시간을 중릴 수 있다.
- 재해싱
- 오버플로우 상태에서 다른 해시 함수를 사용하는 것을 말한다.
- 새로운 해시 함수 f1,f2,…fb를 계속해서 적용한다
- 버킷 fi(x) i=1,2,…,b를 조사한다
- chaining
- 선형조사법의 단점을 극복한다.
- 식별자 저장 버킷의 기억장소 공간을 늘려서 해결한다.
- 버킷에 연결리스트를 만든다.
- 연결리스는 무한정 증가 시킬 수 있기 때문에 오버플로우를 쉽게 해결
- 각 연결리스트는 동의어를 저장한다
이진탐색트리(BST)
- 동적 데이터의 관리
이진탐색 트리의 정의
- 이진 탐색 트리는 이진 트리이며 empty이거나 다음을 만족하는 트리
- 모든 노드는 키 값을 갖고 있으며 같은 키 값을 갖는 경우는 없다.
- 왼쪽 부속 트리의 모든 노드의 키 값은 루트의 키 값보다 작다
- 오른쪽 부속 트리의 모든 노드의 키 값은 루트의 키 값보다 크다
- 왼쪽과 오른쪽 부속 트리도 마찬가지로 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가 높이균형 트리라고 하며 다음을 만족한다.
- Tl과 Tr이 높이 균형 트리이고
- |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 탐색트리로 다음을 만족한다.
- 트리에 있는 각 노드는 최대 m개, 최소 m/2개의 종속 트리를 갖는다.
- 뿌리노드는 최소한 두 개의 종속 트리를 갖는다.
- 모든 잎 노드는 같은 서열에 있어야 한다.
- 노드에 있는 키 값 개수는 종속 트리의 개수보다 하나 적으며 최소 (m/2)-1개 최대 m-1개이다.
B트리에서 키 값의 삽입
- B 트리에서 연산을 수행한 수에도 b-트리의 성질을 보존해야 함
- B- 트리는 거의 균형된 트리이므로 AVL 트리에서의 경우와 같이 연산이 끝난 후에 트리가 균형되어 있어야 한다.
- 새로운 키 값은 항상 잎에 삽입된다.
- 해당 노드가 가득 차 있찌 않은 경우는 키 값을 오름차순으로 채운다.
- 해당 노드가 가득 찬 경우 해당 노드를 두 개의 노드로 분열한다.
노드의 분열 방법
- 해당 노드의 키 값들과 새로운 키 값 중에서 중간 키 값을 부모 노드로 올려 보내고 나머지 키 값들을 전반으로 나누어 각 절반씩 분열된 두 개의 노드에 옮기며 이 두 노드들을 부모 노드로 올라간 키 값의 왼쪽과 오른쪽 종속 트리가 되도록 한다.
B트리에서 삽입의 예
- 그림 2의 B-트리에 다음의 키 값을 차례로 추가 삽입
- 왼쪽은 원래 노드 모양이고 오른쪽은 합입 후 변경된 모양이다.