자료구조 11강 탐색의 이해와 보간 탐색 정리

탐색의 이해

탐색은 알고리즘보다 자료구조에 더 가까운 주제

효율적인 탐색을 위해서는 어떻게 찾을까 만을 고민하기보다는 효율적인 탐색을 위한 저장방법이 무엇일까가 더 우선적인 고민이기 때문.

효율적인 탐색이 가능한 대표적인 저장방법은 트리이고 때문에 탐색에 관한 이야기는 대부분 트리의 연장선상.

보간 탐색

이진 탐색의 비효율성을 개선시킨 탐색법.

중앙에서 탐색을 시작하지 않고 탐색대상이 앞쪽에 위치해 있으면 앞쪽에서 탐색을 시작.

탐색에서 사용할 탐색 키(Search Key)와 탐색 데이터(Seach Data).

"사원이 7인 직원의 정보를 찾는다"라는 예시를 들면 사번이 탐색 키, 직원의 정보가 탐색 데이터.

탐색 키는 값이 고유해야함.

2강에서 구현했던 이진 탐색 코드

#include <stdio.h>

int BSearchRecur(int ar[], int first, int last, int target)
{
    int mid;
    if(first > last)
        return -1;          // -1의 반환은 탐색 실패 의미
    mid = (first+last) / 2;  // 탐색대상의 중앙을 찾는다.
  
    if(ar[mid] == target)
        return mid; // 탐색된 타겟의 인덱스 값 반환
    else if(target < ar[mid])
        return BSearchRecur(ar, first, mid-1, target);
    else
        return BSearchRecur(ar, mid+1, last, target);
}

int main(void) {
    int arr[]={1, 3, 5, 7, 9};
    int idx;
    idx = BSearchRecur(arr, 0, sizeof(arr)/sizeof(int)-1, 7);
    if(idx == -1)
        printf("탐색 실패\n");
    else
        printf("타겟 저장 인덱스: %d\n", idx);

    idx = BSearchRecur(arr, 0, sizeof(arr)/sizeof(int)-1, 4);
    if(idx == -1)
        printf("탐색 실패\n");
    else
        printf("타겟 저장 인덱스: %d\n", idx);
  
    return 0;
}



#include <stdio.h>

int ISearch(int ar[], int first, int last, int target)
{
    int mid;

    if(first > last)
        return -1; // 탐색 실패

    // 이진 탐색과의 차이점이 반영
    mid = ((double)(target - ar[first]) / (ar[last] - ar[first]) * (last - first)) + first;

    if(ar[mid] == target)
        return mid;
    else if(target < ar[mid])
        return ISearch(ar, first, mid-1, target);
    else
        return ISearch(ar, mid+1, last, target);
}

int main(void)
{
    int arr[] = {1, 3, 5, 7, 9};
    int idx;

    idx = ISearch(arr, 0, sizeof(arr) / sizeof(int) - 1, 7);
    if(idx == -1)
        printf("탐색 실패\n");
    else
        printf("타겟 저장 인덱스: %d\n", idx);

    idx = ISearch(arr, 0, sizeof(arr) / sizeof(int) - 1, 10);
    if (idx == -1)
        printf("탐색 실패\n");
    else
        printf("타겟 저장 인덱스: %d\n", idx);

    return 0;
}

하지만 위 코드는

idx = ISearch(arr, 0, sizeof(arr) / sizeof(int) - 1, 2);

를 실행할 경우 제대로 동작하지 못함

이진 트리의 구조를 보면 이진 트리에 저장된 데이터의 수가 10억 개 수준에 이른다 해도 높이는 30을 넘지 않기 때문에 탐색에 효율적.

단, 이진 트리는 단말 노드에 이르는 길의 갈래가 매우 많아서 찾는 데이터가 존재하는 제대로 된 길을 선택할 수 있어야 한다.

이진 탐색 티르가 되기 위한 조건

1. 이진 탐색 트리의 노드에 저장된 키는 유일

2. 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다.

3. 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다.

4. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리

보간 탐색 구현 코드

// BinarySearchTree.h

#ifndef __BINARY_SEARCH_TREE_H_

#define __BINARY_SEARCH_TREE_H_

#include "BinaryTree2.h"

typedef BTData BSTData;

// BST 생성 및 초기화

void BSTMakeAndInit(BTreeNode ** pRoot);

// 노드에 저장된 데이터 반환

BSTData BSTGetNodeData(BTreeNode * bst);

// BST를 대상으로 데이터 저장(노드의 생성과정 포함)

void BSTInsert(BTreeNode ** pRoot, BSTData data);

// BST를 대상으로 데이터 탐색

BTreeNode * BSTSearch(BTreeNode * bst, BSTData target);

#endif

// BinarySearchTree.c

#include <stdio.h>
#include "BinaryTree2.h"
#include "BinarySearchTree.h"

void BSTMakeAndInit(BTreeNode ** pRoot)
{
    *pRoot = NULL;
}

// 노드에 저장된 데이터 반환
BSTData BSTGetNodeData(BTreeNode *bst)
{
    return GetData(bst);
}

// BST를 대상으로 데이터 저장(노드의 생성과정 포함)
void BSTInsert(BTreeNode **pRoot, BSTData data)
{
    BTreeNode * pNode = NULL;       // parent node
    BTreeNode * cNode = *pRoot;     // current node
    BTreeNode * nNode = NULL;       // new node

    // 새로운 노드가(새 데이터가 담긴 노드가) 추가될 위치 찾기
    while(cNode != NULL)
    {
        if(data == GetData(cNode))
            return;     // 데이터의(키의) 중복을 허용하지 않음

        pNode = cNode;

        if(GetData(cNode) > data)
            cNode = GetLeftSubTree(cNode);
        else
            cNode = GetRightSubTree(cNode);
    }

    // pNode의 자식 노드로 추가할 새 노드의 생성
    nNode = MakeBTreeNode();
    SetData(nNode, data);

    // pNode의 자식 노드로 새 노드를 추가
    if(pNode != NULL) // 새 노드가 루트가 아니라면
    {   
        if(data < GetData(pNode))
            MakeLeftSubTree(pNode, nNode);
        else
            MakeRightSubTree(pNode, nNode);
    }
    else
    {
        *pRoot = nNode;
    }
}

// BST를 대상으로 데이터 탐색
BTreeNode *BSTSearch(BTreeNode *bst, BSTData target)
{
    BTreeNode * cNode = bst;
    BSTData cd;

    while(cNode != NULL)
    {
        cd = GetData(cNode);

        if(target == cd)
            return cNode;
        else if(target < cd)
            cNode = GetLeftSubTree(cNode);
        else
            cNode = GetRightSubTree(cNode);
    }

    return NULL; // 탐색대상이 저장되어 있지 않음.
}

// BinarySearchTreeMain.c

#include <stdio.h>
#include "BinarySearchTree.h"

int main(void)
{
    BTreeNode * bstRoot;
    BTreeNode * sNode;

    BSTMakeAndInit(&bstRoot);

    BSTInsert(&bstRoot, 9);
    BSTInsert(&bstRoot, 1);
    BSTInsert(&bstRoot, 6);
    BSTInsert(&bstRoot, 2);
    BSTInsert(&bstRoot, 8);
    BSTInsert(&bstRoot, 3);
    BSTInsert(&bstRoot, 5);

    sNode = BSTSearch(bstRoot, 1);
    if(sNode == NULL)
        printf("탐색 실패 \n");
    else
        printf("탐색에 성공한 키의 값: %d\n", BSTGetNodeData(sNode));

    sNode = BSTSearch(bstRoot, 4);
    if (sNode == NULL)
        printf("탐색 실패 \n");
    else
        printf("탐색에 성공한 키의 값: %d\n", BSTGetNodeData(sNode));

    sNode = BSTSearch(bstRoot, 6);
    if (sNode == NULL)
        printf("탐색 실패 \n");
    else
        printf("탐색에 성공한 키의 값: %d\n", BSTGetNodeData(sNode));

    sNode = BSTSearch(bstRoot, 7);
    if (sNode == NULL)
        printf("탐색 실패 \n");
    else
        printf("탐색에 성공한 키의 값: %d\n", BSTGetNodeData(sNode));

    return 0;
}

출력 결과

탐색에 성공한 키의 값: 1
탐색 실패 
탐색에 성공한 키의 값: 6
탐색 실패