11강 제 6장 탐색 알고리즘(탐색, 순차 탐색, 이진 탐색)

학습 목표

1. 탐색의 개념을 이해할 수 있다.

2. 순차 탐색 알고리즘의 개념, 동작, 그리고 특징을 이해할 수 있다.

3. 이진 탐색 알고리즘의 개념, 동작, 그리고 특징을 이해할 수 있다.

4. 이진 탐색 트리와 흑적 트리, B-트리의 개념, 동작, 그리고 특징을 이해할 수 있다. 

5. 해싱의 개념과 해시 함수 및 충돌 해결 방법의 종류와 특징을 이해할 수 있다.

 

주요용여

#탐색 #순차탐색 #이진탐색 #이진탐색트리 #흑적트리 #B트리 #노드분할 #해싱 #해시함수 #제산잔여법 #비닝

#중간제곡법 #충돌 #충돌해결방법 #개방해싱 #폐쇄 해싱 # 버킷해싱 #선형 탐사 # 1차 클러스터링 #이차담사

# 2차 클러스터링 #이중 해싱

 

 

6.1 탐색 ( search ) 의 개념

> 여러 원소로 구성된 데이터에서 원하는 값을 가진 원소를 찾는 것

  - 데이터의 형태 → 리스트,트리,그래프 등

  - 내부 탐색 vs외부 탐색 

  - 탐색 연산 +초기화(정렬),삽입,삭제 등의 연산도 함께 고려해야 함

  - 순차 탐색

  - 이진 탐색

  - 탐색 트리 -> 이진탐색트리, 흑적트리, B - 트리

  - 해싱 >> 해시함수, 충돌 해결 방법

 

 

6.2 순차 탐색

 

6.2.1 개념과 원리 

> 리스트 형태로 주어진 원소들을 처음부터 하나씩 차례로(“순차”) 비교하면서 원하는 값을 가진 원소를 찾는 방법

 

6.2.2 알고리즘

 

순차 탐색 알고리즘

 

SequentialSearch ( A[] , n , x )  // 순차 탐색

입력 : A[0..n-1]: 입력 배열 

      n:입력 크기 (탐색 대상 원소의 개수) 

      x:탐색키 

출력:배열 A에서 x의 위치(인덱스)

{

   for( i = 0; i < n; i++)

     {

         if( A [i] == x ) returni;

      }

   return-1; //탐색키 x가 존재하지 않는 경우

} 

 

 

순차 탐색의 삽입 알고리즘

 

SequentialSearch_Insert ( A[], n, x)

입력 : A[0..n-1] : 탐색 대상 배열

      n : 탐색 대상 원소의 개수 (배열의 개수) 

      x : 삽입할 원소  

출력 :  A[ 0.. n-1], n + 1; 원소가 삽입된 탐색 대상 배열

{

   A[n] = x;              // 원소 삽입

   return A , n +1;     //배열의 크기가 1증가
}

 

 

순차 탐색에서의 삭제 연산

 

SequentialSearch_Delete (A[0..n-1],n,x)

입력 : A[0..n-1] : 탐색 대상 배열

      n : 탐색 대상 원소의 개수 (배열의 개수) 

      x : 삭제 할 원소  

출력 :  A[ 0.. n-1], n + 1; 원소가 삭제된 탐색 대상 배열

{

   Index = SequentialSearch( A , n , x );   // 순차 탐색 알고리즘

   if( Index == -1 ) returnA, n ;              // 삭제할 원소가 존재하지 않음

   A[ Index ] =A [n-1];                        // 마지막 원소를 삭제할 위치로 이동 (원소 삭제 )

   returnA,n-1;   //배열의 크기가 1감소

}

 

 

6.2.3 성능 분석

> 성능 분석 ( 모든 경우 O(n) )

  - 탐색 실패의 경우 → 항상 n번 비교

  - 탐색 성공의 경우 → 최소 1번,평균 (n+1)/2번,최대 n번 비교   

  - 삽입 → O(1), 삭제 → O(n)

 

 

6.2.4 특징 

> 모든 리스트에 적용 가능 

• 원소가 무순서로 연속해서 저장된 비정렬 데이터 탐색에 적합

>  데이터가 큰 경우에는 부적합 

• 탐색과 삭제에 O(n)시간을 요구

 

 

 

 

6.3 이진 (binary search ) 탐색

6.3.1 개념과 원리

> 정렬된 리스트 형태로 주어진 원소들을 절반씩 줄여가면서 원하는 값을 가진 원소를 찾는 방법

  - 분할 정복 방법

> 탐색 방법 

  - 배열의 가운데 원소와 탐색키 x를 비교

    1)탐색키 = 가운데 원소 ⇒ 탐색 성공

    2)탐색키 < 가운데 원소 ⇒ ‘이진 탐색 ( 크기 ½의 왼쪽 부분배열 )  순환 호출

    3)탐색키 > 가운데 원소 ⇒ ‘이진 탐색 ( 크기 ½의 오른쪽 부분배열 ) 순환 호출 

>>> 탐색을 반복할 때마다 대상 원소의 개수가 ½씩 감소

 

 

6.3.2 알고리즘

탐색 알고리즘

 

BinarySearch ( A[] , Left , Right , x)

입력 : A[0..n-1] : 탐색 대상 배열

          n : 탐색 대상 원소의 개수 ( 배열의 크기 )

출력 : A[0..n-1] : 오름차순으로 정렬된 탐색 대상 배열

{

   if (Left>Right) return-1;

   Mid = ë (Left+Right)/2 û;

   if ( x == A[ Mid ] ) returnMid;

   else if ( x < A [Mid]) BinarySearch( A , Left , Mid-1 , x)

        else BinarySearch( A , Mid+1 , Right , x);

}

>> T(n)=T(n/2)+O(1) (n>1),T(1)=1   >> T(n)=O(logn)

 

초기화 알고리즘

 

BinarySearch_Initialize ( A[] , n )

{

   for( i = 0; i < n - 1; i++ )

   if( A[i] > A[i+1])

      {

         A = Sort ( A , n ); // 오름차순으로 정렬

         break;

      }

   returnA;

}    >>> O (lnogn)

 

 

삽입 알고리즘

 

BinarySearch_Insert (A[],n,x) 

{ 

   Left = 0; Right = n-1;

   while( Left <= Right )

     {

         Mid = ë(Left+Right)/2û;

         if( x == A[Mid ] ) returnA , n;             // 삽입할 원소가 이미 존재

         else if( x < A [Mid] ) Right = Mid - 1;  // 왼쪽 부분 배열 탐색

              else Left = Mid+1;                     // 오른쪽 부분 배열 탐색

      } // 삽입할 위치(Left)부터 오른쪽 모든 원소를 오른쪽으로 한칸씩 이동

   for( i = n; i > Left; i-- )

      A[i] = A[i-1];

   A[Left] = x;                                       // 원소 삽입

   return A , n+1;

}    >>> O (n) 

 

 

 

 

 

// 반복 형태의 이진 탐색 알고리즘

// 삭제할 원소가 존재하지 않음

// 삭제할 위치의 오른쪽 모든 원소를 왼쪽으로 한칸씩 이동 (원소 삭제 )

 

 

 

 

 

 

 

 

6.3.3 성능 분석

> 성능 분석 

   - 탐색 → O(logn)

   - 초기화 → O(nlogn) 

   - 삽입,삭제 → O(n)

 

> 특징

  - 정렬된 리스트에 대해서만 적용 가능

  - 삽입과 삭제가 빈번한 경우에는 부적합

     - 삽입 / 삭제 후 입력 리스트의 정렬 상태를 유지하기 위해서 O(n) 의 자료 이동이 필요

 

 

6.4 탐색 트리

 

6.4.1 이진 탐색 트리

 

이진 탐색 트리 BinarySearchTree

 

- 이진 트리

 

- 각 노드의 왼쪽 서브트리에 있는 모든 키값은 그 노드의 키 값보다 작다.

 

- 각 노드의 오른쪽 서브트리에 있는 모든 키값은 그 노드의 키값보다 크다.

 

 

(2) 알고리즘

 

BST_Search ( T , x )   // 이진 탐색 트리의 탐색 알고리즘

{

   CNode = T의 루트 노드;

   while ( CNode != Null )                   

      if ( x == CNode.key ) returnCNode ; 

      else if ( x < CNode.key ) CNode =CNode.Left;   // 왼쪽 서브트리 탐색

            else CNode = CNode.Right;                     // 오른쪽 서브트리 탐색

   returnNull;                                                    // 탐색키가 존재하지 않는 경우

}

 

 

 

BST_Insert (T,x)   // 이진 탐색 트리의 삽입 알고리즘 

{ 

   PNode = CNode =T의 루트 노드;

   while ( CNode != Null )

      if ( x == CNode.key) returnT;                       // 삽입할 원소가 이미 존재

      else

      {

           PNode = CNode;

           if ( x < CNode.key ) CNode = CNode.Left;  // 왼쪽 서브 트리 탐색

           else CNode = CNode.Right;                     // 오른쪽 서브 트리 탐색

       }

   NewNode.key = x;                                         // 새 노드 생성, Left와 Right는 Null

   if ( x < PNode.key ) PNode.Left = NewNode;       // 왼쪽 자식으로 새 노드 추가

   else PNode.Right = NewNode;                         // 오른쪽 자식으로 새 노드 추가

   returnT;

}

 

 

 삭제 연산 

> 후속자(successor,계승자) 노드  

  - 어떤 노드의 바로 다음 키값을 갖는 노드 

> 삭제되는 노드의 자식 노드의 개수에 따라 3가지 경우로 구분

1. 자식 노드가 없는 경우(리프 노드의 경우) 

  - 남은 노드의 위치 조절이 불필요

2. 자식 노드가 하나인 경우

  - 자식 노드를 삭제되는 노드의 위치로 올리면서 서브트리 전체도 따라 올린다

3. 자식 노드가 두 개인 경우 

  - 삭제되는 노드의 후속자 노드를 삭제되는 노드의 위치로 올리고,

  - 후속자 노드가 삭제되는 노드가 되어,자식 노드의 개수(0,1)에 따라 처리

 

 

(3) 성능 분석

> 탐색,삽입,삭제의 시간 복잡도

 - 키값을 비교하는 횟수에 비례 → 이진 트리의 높이가 h라면 O(h) 

 

 

 

(4) 특징

 

> 삽입/삭제 연산 시 기존 노드의 이동이 거의 발생하지 않음

 

> 원소의 삽입,삭제에 따라 경사 트리 형태가 될 수 있음 

 - 최악의 수행 시간 O(n)을 가짐

   - 경사 트리가 되지 않도록 균형을 유지해서 O(logn)을 보장 

       → 균형 탐색 트리(흑적 트리,B-트리)

 

 

 

 

 

 

 

 

2020/05/07 - [방송통신대학/알고리즘] - 11강 제 6장 탐색 알고리즘

불러오는 중입니다...