[자료구조 스터디] chap.13 탐색

13.1 탐색이란?

13.2 정렬되지 않은 배열에서의 탐색

13.3 정렬된 배열에서의 탐색

13.4 이진 탐색 트리 

13.5 AVL 트리 

13.6 2-3 트리

13.7 2-3-4 트리 

 

---

13.1 탐색이란?

탐색

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

- 탐색용 자료구조: 배열, 연결리스트, 트리, 그래프 

- 탐색키 (search key): 항목과 항목 구별해주는 키 

---

13.2 정렬되지 않은 배열에서의 탐색 

순차탐색 (sequential search)

- 가장 간단, 직접적 탐색 방법

- 정렬x sequence을 처음부터 마지막까지 하나씩 검사하는 방법

- 평균 비교 횟수 : 탐색 성공 => (1+2+...+n)/n = (n+1)/2번 비교  /  탐색 실패 => n번 비교 ==>> O(n)

- 시간 복잡도 

최선 : 찾는 것이 가장 앞 O(1)

최악 : 찾는 것이 가장 뒤 O(n)

평균 : (탐색 성공시 비교횟수 모두 더한것) / (n+1)  < O(n)

 

순차 탐색 프로그램 

int seq_search(int key, int low, int high) //record 개수 = (high-low+1) = n
{
  int i; 
  for (i=low; i<=high; i++)  //for 문 안의 비교를 제거 => 그래도 여전히 최악의 경우 n번 반복 O(n)
    if (list[i] == key)
       return i; // 탐색 성공하면 키 값의 인덱스 반환
  return -1; 
}


//개선된 순차탐색 
int seq_search2(int key, int low, int high) 
{
  int i; 
  list[high + 1] = key; //키 값을 찾으면 종료 
  for (i=low; list[i] != key; i++);
  if (i == (high+1)) return -1; 탐색 실패 
  else return i; // 탐색 성공
}

 

---

13.3 정렬된 배열에서의 탐색 

정렬된 배열을 이용한 이진탐색 (binary search)

- 정렬된 배열의 (그래서 고정된 dataset이 적절) 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색 범위를 반으로 줄인 탐색 진행 

 

이진탐색 알고리즘 

search_binary(list, low, high): 1. middle <- low에서 high사이의 중간 위치 2. if (탐색값 == list[middle]) 3.     return middle; //탐색성공은 여기서!! 4. else if (탐색값 < list[middle]) 5.        return list[low]부터 list[middle-1]에서 탐색;  6. else if (탐색값 > list[middle]) 7.       return list[middle+1]부터 list[high]에서 탐색;

 

순환 호출 버전 이진탐색 코드 

//순환을 이용한 이진탐색 프로그램 
int search_binary1(int key, int low, int high)
{
  int middle;
  if (low <= high) { //종료조건(실패 판단조건)
     middle = (low + high)/2;
     if (key==list[middle]) //탐색 성공
       return middle; //탐색성공은 여기서!!
     else if (key < list[middle]) //왼쪽 부분리스트 탐색 
       return search_binary1(key, low, middle-1);
     else                         //오른쪽 부분리스트 탐색 
       return search_binary1(key, middle+1, high);
  }                               //탐색 실패
  return -1; 
}

 

반복적인 버전 이진탐색 코드 

int search_binary2(int key, int low, int high)
{
   int middle; 
   
   while (low <= high) { //아직 숫자들이 남아 있으면 
      middle = (low + high) / 2; 
      if (key == list[middle])
         return middle;
      else if (key > list[middle]) 
         low = middle + 1; 
      else 
         high = middle - 1;
   }
   return -1; //발견되지 않음 
}

순환 이진탐색 프로그램 => 탐색범위가 n -> n/2 -> n/2^2 -> n/2^4 -> ... 1 로 줄어듬 => O(logn) 밑 2

반복 이진탐색 프로그램 => 탐색범위가 n -> n/2 -> n/2^2 -> n/2^4 -> ... 1 로 줄어듬 => O(logn) 밑 2

**이론적 시간복잡도는 둘이 동일하나, Call stack 을 이용한 context switching, push/pop이 없는 반복 호출 방법이 더 빠름

 

색인 순차탐색 (indexed sequential search)

 

 

 

- 인덱스 테이블 사용하여 탐색 효율 증대

-> 주자료 리스트에서 일정 간격으로 발췌한 자료 저장 

- 복잡도 : O((m+n)/m) => 인덱스 테이블의 크기 m, 주자료 리스트의 크기 n

 

 

 

색인 순차 탐색 코드

#define INDEX_SIZE 256 
typedef struct 
{
   int key; 
   int index;
} itable;
itable index_list[INDEX_SIZE];

//INDEX_SIZE는 인덱스 테이블의 크기, n은 전체 데이터의 수 
int search_index(int key, int n)
{
   int i, low, high;
   
   //키 값이 리스트 범위 내의 값이 아니면 탐색 종료 
   if (key<list[0] || key>list[n-1])
      return -1;
      
   //인덱스 테이블을 조사하여 해당키의 구간 결정 
   for ( i=0; i<INDEX_SIZE; i++)
      if (index_list[i].key <= key && index_list[i+1].key>key) 
         break;
   
   if (i==INDEX_SIZE) { //인덱스 테이블의 끝이면 
      low = index_list[i-1].index;
      high = n;
   }
   else {
      low = index_list[i].index;
      high = index_list[i+1].index;
   }
   //예상되는 범위만 순차 탐색
   return seq_search(key, low, high);
}

 

정렬된 배열을 이용한 보간탐색 (interpolation search)

- 사전이나 전화번호부 탐색하는 방법 

- 탐색키가 존재할 위치를 예측하여 탐색 => O(log(n))   (밑 2)

- 보간 탐색은 이진 탐색과 유사 but 리스트를 불균등 분할하여 탐색 (데이터 값이 비교적 균등하면 이진탐색보다 빠름)

ps. 이진 탐색에서 탐색 위치는 항상 (low + high)/2

보간탐색 위치 예측 수식

 

보간탐색 코드 

int interpol_search(int key, int n)
{
  int low, high, j;
  low = 0;
  high = n-1; while(low <= high) {
  while ((list[high] >= key) && (key > list[low])) {
    j = ((float)(key-list[low]) / (list[high]-list[low])*(high-low))+low; //O(log(n)) while문 한번 실행 후 list[]의 크기가 /x (<=2)로 줄어듬.
    if (key>list[j]) low=j+1;
    else if (key<list[j]) high=j-1;
    else return j; //탐색성공
  }
  return -1; //탐색실패
}

주의 : 만약 나눗셈 계산할 때 float로 형변환 안해주면 정수로 계산돼서 항상 0이 됨 

---

13.4 이진 탐색 트리 

이진탐색트리 (BST: Binary Search Tree) 

- 이진탐색과 이진탐색트리는 근복적으로 같은 원리에 의한 탐색 구조 

- 이진탐색은 자료들이 배열에 저장되어 있어 삽입/삭제 매우 비효율 but 이진탐색 트리는 빠르게 삽입/삭제 수행

따라서 이진 탐색 트리에서는 최악을 피하기 위해 균형을 유지하는 것이 무엇보다 중요! 

 

균형 이진탐색트리 (Balanced BST)

- 이진탐색트리에서의 시간복잡도  ***이진탐색트리를 이용한 모든 연산의 time complexity는 O(h) (h=트리 높이 logn or n)

   ㄴ 균형트리 : O(log(n))

   ㄴ 불균형트리 : O(n), 순차탐색과 동일 

***탐색 작업 효율적으로 하기 위해 중위순회하면 오름차순으로 정렬된 값 얻음

==>> key(왼쪽서브트리) < key(루트노드) <  key(오른쪽서브트리) 

---

13.5 AVL 트리 

AVL 트리 

- 모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차가 1이하인 이진탐색트리 

- 트리가 비균형 상태로 되면 스스로 노드들을 재배치하여 균형 상태 유지 

- 시간복잡도 

  ㄴ 평균, 최선 최악 모두 : O(log(n))

- 균형 인수 (balace factor) = 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이 

- 모든 노드의 균형인수가 ±1 이하면 AVL 트리 

 

AVL 트리의 연산 

- 탐색 연산 : 이진탐색트리와 동일 O(logn) (밑2)

- 삽입 위치에서 루트까지의 경로에 있는 조상 노드들의 균형 인수 영향

- 삽입 후에 불균형 상태로 변한 가장 가까운 조상 노드(균형 인 수가 ±2가 된 가장 가까운 조상 노드)의 서브 트리들에 대하 여 다시 재균형 

- 삽입 노드부터 균형 인수가 ±2가 된 가장 가까운 조상 노드까지 회전 

***AVT 트리 마지막 완성된 트리 그리시오 문제 냈다. => 고치는것까지 할 수 있어야. 

AVL트리 삽입시 균형 깨지는 4가지 경우

 

 

- in-order로 읽으면 됨 

그림보고 => 어디다 붙일지 알아야함 

 

J: 새로 삽입된 노드 

X: 노드 J와 가장 가까우면서 균형 인수가 ±2가 된 조상 노드

 

 

 

 

 

 

 

 

AVL 트리 구축 예시

 

AVL 트리 구현 코드 

#include <stdio.h>
#include <stdlib.h>

//AVL 트리 노드 정의 
typedef struct AVLNode
{
   int key;
   struct AVLNode *left; 
   struct AVLNode *right;
} AVLNode;


//노드 동적 생성 함수 
AVL_Node* create_node(int key)
{
   AVLNode* node = (AVLNode*)malloc(sizeof(AVLNode));
   node->key = key;
   node->left = NULL;
   node->right = NULL;
   return(node)
}


//오른쪽으로 회전시키는 함수 
AVLNode *rotate_right(AVLNode *parent)
{
   AVLNode* child = parent->left;
   parent->left = chile->right;
   chile->right = parent;
   
   //새로운 루트를 반환
   return child;
}


//왼쪽으로 회전시키는 함수 
AVLNode *rotate_left(AVLNode *parent)
{
   AVLNode* child = parent->left;
   parent->right = chile->left;
   chile->left = parent;
   
   //새로운 루트를 반환
   return child;
}


//트리의 높이를 반환 
int get_height(AVLNode *node)
{
   int height = 0;
   
   if (node != NULL)
      height = 1 + max(get_height(node->left), 
         get_height(node->right));
         
   return height;
}

//노드의 균형인수 반환
int get_balance(AVLNode* node)
{
   if (node == NULL) return 0;
    
   return get_height(node->left) - get_height(node->right);
}

 

실행결과 : 

전위 순회 결과

[30] [20] [10] [29] [40] [50]

 

---

13.6 2-3 트리 

2-3 트리 

- 차수(자식노드 개수)가 2 또는 3인 노드를 가지는 트리 (중복키 허용X)

•  2-노드 

- 이진탐색트리와 유사 

- 나의 데이터 k1와 두개의 자식 노드 가짐

- 왼쪽 서브 티리에 있는 데이터들은 모두 k1보다 작은 값

- 중간 서브 트리에 있는 값들은 모두 k1 보다 크고 k2보다 작다 ?오타인가 ??

• 3-노드 

- 2개의 데이터 (k1,k2)와 3개의 자식노드 가짐

- 왼쪽 서브 트리에 있는 데이터들은 모두 k1보다 작은 값

- 중간 서브 트리에 있는 값들은 모두 k1보다 크고 k2보다 작다 

- 오른쪽에 있는 데이터들은 모두 k2보다 크다 

단말노드 분리의 경우

비단말 노드 분리의 경우

루트 노드 분리의 경우

 

2-3 트리 탐색 프로그램 

tree23_search(Tree23Node *root, int key) 
{
  if (root == NULL) // 트리가 비어 있으면
    return FALSE;
  else if (key == root->key1) // 루트의 키==탐색 키
    return TRUE;
  else if (root->type == TWO_NODE) { // 2-노드
    if (key < root->key1)
      return tree23_search(root->left, key)
    else
      return tree23_search(root->right, key)
  } else {                            // 3-노드
    if (key < root->key1)
      return tree23_search(root->left, key)
    else if (key > root->key2)
      return tree23_search(root->right, key)
    else
      return tree23_search(root->middle, key)
 }
}