[DataStruct 09.25] 4. 정리 다섯째날-검색!!ㅋㅋ

1. 정의
  기억공간에 저장되어 있는 자료 중에서 필요한 자료를 찾는 작업
  자료는 레코드의 형태로 되어 있고, 키를 사용해서 찾는다.
  Primary key : 데이터베이스에서 사용되는 내용이며 다른키와 중복되지 않는 고유한 값을 가지는 각가의 레코드를 식별할수
  있게하는 키이다. 

  Internal Search : 일반적으로 메모리에 올려져 있는 데이터를 검색하는 방법
  External Search : 보조기억장치에 저장된 리스트로 부터 자료를 검색하는 방법

검색방법에는 크게 두가지 검색 방법이 있으며 비교에 의한 검색(Comparison method)와 계산에 의한 검색(non Comparison Method)가 있으며 비교하는방법은 검색대상의 키와 레코드의 키를 비교해서 검색하는 방범이며  Sequential Sequential Search,  Controlled Search(Binary Search, Fibonacci Search, 보간검색), Tree Search방법이 있고 계산에 의한건 Hashing가 있다.

2. 검색 방법
2.1 선형(비정렬)
  첫번째 레코드로부터 차례로 키를 비교해 가면서 마지막 레코드까지 키값을 이치하는 자료를 찾는다. 이 방법을 사용할 경우
평균 검색시간은 O((n+1)/2)=O(n)의 시간이 걸린다.

int seqSearch(int data[], int size, int key) {        int i;        i=0;        while(i<=size && data[i]!=key)                   i++;        if(i>size)               return -1;        else               return (i); }

2.2 선형(정렬)
  첫번째 레코드로 부터 차례로 키를 비교해 가면서 마지막 레코드까지 키값에 일치하는 자료를 찾는다. 찾고자 하는 레코드의 키가 작아지면 중지한다.

int seqSearch(int data[], int size, int key) {        int i;        i=0;        while(i<=size && data[i]!=key)              if(data[i]>size)                   return -1;              else                   i++;       return (i); }

2.3 이진검색트리
  정렬이 되어 있는 경우에만 사용 가능하다는 전제하에 검색이 가능하다. 
  정렬된 리스트에서 중간에 위치한 원소의 값을 구한 후 키값과 비교한다. 
      - 중간값과 키값이 같으면 성공
      - 검색키가 중간값보다 작으면 이분된 리스트중에서 전반부에 찾으려는 원소가 있다. 이 전반부에 해당하는 리스트를
          대상으로 바이너리 서치를 계속 한다.
      - 검색키가 중간값보다 크다면 이분된 리스트중에서 후반부에 찾으려는 원소가 있다. 이 후반부에 해당하는 리스트를 
          대상으로 이진검색을 계속 한다.
  섬색시간은 O(log n)으로 된다.

장점으로는 검색이 효율적이고 파일 갱신이 용이하다. 레코드의 삽입과 삭제를 요구하는 파일의 대해서 빠른 검색에 적합하다.
단점 입력데이터 파일의 배열된 순서에 따라 BST가 구성되므로 균형을 맞추기 위해 트리를 재구성해야만 효율성을 유지할 수 있다.
최악의 경우 skewed tree 의 구조를 가지면 Binary 검색이 아니라 sequential 검색의 특징(사향 트리)을 갖게 된다.

2.4 해쉬(Hashing)
 해싱이란?
    레코드가 테이블에 저장되어 있을 때 레코드의 키 값을 주면 이 키값을 어떤 수학적 함수에 의하여 테이블의 주소를 변환시켜서  원하는 레코드를 검색하는 것
해싱함수는 레코드의 키 값을 테이블의 주소로 변환 시키는 수학적 함수
해싱 테이블  레코드들이 테이블 형태로 저장되어 해싱 함수에 접근, 호출될 때의 테이블

장점은 레코드의 검색시간이 테이블의 크기와 관계없이 상수시간으로 일정
단점은 서로 다른 키 값을 가지는 레코드들이 경우에 딸 해싱 테이블에서 같은 주소를 가지는 경우가 발생함

2.4.1 문제의 해결책
충돌(collision)
서로 다른 키 값을 갖는 두개 이상의 서로 다른 레코드들이 같은 주소 값으로 계산 되는 현상
K1과 K2 가 서로 다른 키 값일 때 h(K1)=h(K2)가 되는 경우
해결방법으로는 선형개방주소법(Linear Open Addressing), Chaining, 2차 탐사방법이 있다.

개방 주소법 충돌이 발생한 경우 그 다음의 빈 테이블 공간에 저장하는 방법 개념을 쉽지만 레코드들이 테이블에 골고루 분산되지 않고 집단화되어 한 곳에 몰려있는 clustering 현상이 발생

Chaining 충돌이 발생한 경우 Linked list 로 해결하는 방법 장점은 오버플로가 발생하지 않고 삭입 삭제가 용이 하며 단점은 malloc과 포인터 연산이 필요