Ch11. 탐색(Search) 1

castlehi·2021년 8월 30일
자료구조
0

DataStructure

목록 보기
11/14
post-thumbnail

11-1. 탐색의 이해와 보간 탐색

탐색의 이해

‘데이터를 찾는 방법’

효율적인 탐색을 위해서는 ’어떻게 찾을까’ 뿐만 아니라 ’효율적인 탐색을 위한 저장방법’이 무엇일까를 고려해야 한다

  • 정렬되지 않은 대상을 기반으로 하는 탐색 : 순차 탐색
  • 정렬된 대상을 기반으로 하는 탐색 : 이진 탐색

이진 탐색은 찾는 대상의 위치에 따라서 탐색의 효율에 차이가 발생한다

이진 탐색처럼 무조건 중앙에서 탐색을 시작하는 것이 아닌, 탐색 대상이 앞쪽에 있으면 앞쪽에서 탐색을 시작한다

Ex) 12를 찾을 때 이진탐색 vs 보간탐색

  • low : 탐색 대상의 시작
  • high : 탐색 대상의 끝
    A : Q = (high - low) : (s - low)
    이 때, s는 찾는 데이터의 위치이므로

    찾는 데이터의 값 arr[s]를 x라 한다면

다만, s를 구하기 위해 나눗셈 연산을 하는데 오차율을 최소화하기 위해서 정수형 나눗셈이 아닌 실수형 나눗셈을 한다는 것이 보간 탐색의 단점이다

탐색 키(Search key)와 탐색 데이터(Search Data)

탐색 키는 그 값이 고유해야 한다

보간 탐색의 구현

int ISearch(int ar[], int first, int last, int target)
{
    int mid;
    
    if(first > last)
        return -1;  // -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);
}

탐색 대상이 존재하지 않는 경우, ISearch 함수가 재귀적으로 호출됨에 따라 target에 저장된 값은 first와 last가 가리키는 값의 범위를 넘어서게 되므로 탈출 조건을 변경해야 한다.

if(ar[first]>target || ar[last] < target)
    return -1;

탈출 조건을 만족하지 않는 이유

탐색 대상이 존재하지 않을 경우, 탐색대상의 값은 탐색범위의 값을 넘어선다

11-2. 이진 탐색 트리

이진 탐색 트리의 이해

  • 이진 탐색 트리의 노드에 저장된 키(key)는 유일하다
  • 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다
  • 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다
  • 왼쪽과 오른쪽의 서브 트리도 모두 이진 탐색 트리이다

왼쪽 자식 노드의 키 < 부모 노드의 키 < 오른쪽 자식 노드의 키

Ex) 숫자 10을 저장할 때

  • 1단계 : 10 < 12이므로 왼쪽 자식 노드로 이동!
  • 2단계 : 10 > 8이므로오른쪽 자식 노드로 이동!
  • 3단계 : 10 > 9이므로 오른쪽 자식 노드로 이동!
  • 4단계 : 오른쪽에 아무것도 없으니 그 자리에 저장!

이진 탐색 트리의 헤더파일

#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

이진 탐색 트리의 구현 : 삽입과 탐색


비교대상이 없을 때까지 내려간다. 그 위치가 새 데이터가 저장될 위치이다

삽입 함수

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;
    }
}

탐색 함수

BTreeNode *BSTSearch(BTreeNode *bst, BSTData target)
{
    BTreeNode *cNode = bst; //current node
    BSTData cd; //current data
    
    while(cNode != NULL)
    {
        cd = GetData(cNode);
        
        if(target == cd)
            return cNode;
        else if(target < cd)
            cNode = GetLeftSubTree(cNode);
        else
            cNode = GetRightSubTree(cNode);
    }
    
    return NULL;    //탐색사대상이 저장되어 있지 않음
}

이진 탐색 트리의 삭제구현 : 삭제에 대한 이론적 설명과 구현 일부

삭제 후에도 이진 탐색 트리가 유지되도록 빈 자리를 채워야 한다

  • 상황1 삭제할 노드가 단말 노드인 경우
//dNode와 pNode는 각각 삭제할 노드와 이의 부모 노드를 가리키는 포인터 변수
if(삭제할 노드가 단말 노드이다!)
{
    if(GetLeftSubTree(pNode) == dNode)  //삭제할 노드가 왼쪽 자식 노드라면,
        RemoveLeftSubTree(pNode);   //왼쪽 자식 노드 트리에서 제거
    else
        RemoveRightSubTree(pNode);  //오른쪽 자식 노드 트리에서 제거
}
  • 상황2 삭제할 노드가 하나의 자식 노드를(하나의 서브트리를) 갖는 경우
//dNode와 pNode는 각각 삭제할 노드와 이의 부모 노드를 가리키는 포인터 변수
if(삭제할 노드가 하나의 자식 노드를 지닌다!)
{
    BTreeNode *dcNode;  //삭제 대상의 자식 노드를 가리키는 포인터 변수
    
    //삭제 대상의 자식 노드를 찾는다
    if(GetLeftSubTree(dNode) != NULL)   //자식 노드가 왼쪽에 있다면,
        dcNOde = GetLeftSubTree(dNode);
    else    //자식 노드가 오른쪽에 있다면,
        dcNOde = GetRightSubTree(dNode);
        
    //삭제 대상의 부모 노드와 자식 노드를 연결한다
    if(GetLeftSubTree(pNode) == dNode)  //삭제 대상이 왼쪽 자식 노드이면,
        ChangeLeftSubTree(pNode, dcNode);   //왼쪽으로 연결한다
    else
        ChangeRightSubTree(pNode, dcNode);  //오른쪽으로 연결한다
}
  • 상황3 삭제할 노드가 두 개의 자식 노드를(두 개의 서브트리를) 갖는 경우

    8을 대체할 후보
    - 8이 저장된 노드의 왼쪽 서브 트리에서 가장 큰 값인 7을 저장한 노드
    - 8이 저장된 노드의 오르쪽 서브 트리에서 가장 작은 값인 9를 저장한 노드

삭제할 노드의 왼쪽 서브 트리에서 가장 큰 값이나, 삭제할 노드의 오른쪽 서브 트리에서 가장 작은 값을 저장한 노드로 대체하면 된다

이 예시에서는 오른쪽 서브 트리에서 가장 작은 값을 저장한 노드로 대체한다

단말 노드가 아니라면 단순 대입으로 노드의 대체를 대신할 수 없다

  • 단계1 삭제할 노드를 대체한 노드를 찾는다
  • 단계2 대체할 노드에 저장된 값을 삭제할 노드에 대입한다
  • 단계3 대체할 노드의 부모 노드와 자식 노드를 연결한다
//dNode와 pNode는 각각 삭제할 노드와 이의 부모 노드를 가리키는 포인터 변수
if(삭제할 노드가 두 개의 자식 노드를 지닌다)
{
    BTreeNode *mNode = GetRightSubTree(dNode);  //mNode는 대체 노드를 가리킴
    BTreeNode *mpNode = dNode;  //mpNode는 대체 노드의 부모 노드 가리킴
    
    //단계1. 삭제 대상의 대체 노드를 찾는다
    while(GetLeftSubTree(mNode) != NULL)
    {
        mpNode = mNode;
        mNode = GetLeftSubTree(mNode);
    }
    
    // 단계2. 대체할 노드에 저장된 값을 삭제할 노드에 대입한다.
    SetData(dNode, GetData(mNode));
    
    //단계3. 대체할 노드의 부모 노드와 자식 노드를 연결한다.
    if(GetLeftSubTree(mpNOde) == mNode) //대체할 노드가 왼쪽라자식 노드라면
    {
        //대체할 노드의 자식 노드를 부모 노드의 왼쪽에 연결한다
        ChangeLeftSubTree(mpNode, GetRightSubTree(mNode));
    }
    else    //대체할 노드가 오른쪽 자식 노드라면
    {
        //대체할 노드의 자식 노드를 부모 노드의 오른쪽에 연결한다
        ChangeRightSubTree(mpNode, GetRightSubTree(mNode));
    }
}

가장 작은 값을 지니는 노드를 찾으려면 NULL을 만날 때까지 왼쪽 자식 노드로 계속해서 이동해야 하므로 자식 노드가 있다면 그것은 오른쪽 자식 노드일 것이다

이진 탐색 트리의 삭제구현: 삭제의 구현을 위한 이진 트리의 확장

//왼쪽 자식 노드를 트리에서 제거, 제거된 노드의 주소 값이 반환된다.
BTreeNode * RemoveLeftSubTree(BTreeNode * bt);
//오른쪽 자식 노드를 트리에서 제거, 제거된 노드의 주소 값이 반환된다.
BTreeNode * RemoveRightSubTree(BTreeNode * bt);
//메모리 소멸을 수반하지 않고 main의 왼쪽 자식 노드를 변경한다
void ChangeLeftSubTree(BTreeNode * main, BTreeNode * sub);
//메모리 소멸을 수반하지 않고 main의 오른쪽 자식 노드를 변경한다
void ChangeRightSubTree(BTreeNode * main, BTreeNode * sub);

삭제 함수에서 왼쪽 자식 노드와 오르쪽 자식 노드를 트리에서 제거하는 코드만 있을 뿐, 메모리의 해제까지 이루어지지 않는다. 메모리 해제는 호출한 영역으로 책임을 전가한다

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

BTreeNode * MakeBTreeNode(void)
{
    BTreeNode * nd = (BTreeNode*)malloc(sizeof(BTreeNode));
    nd->left = NULL;
    nd->right = NULL;
    return nd;
}

BTData GetData(BTreeNode *bt) {return bt->data;}

void SetData(BTreeNode *bt, BTData data) {bt->data = data;}

BTreeNode * GetLeftSubTree(BTreeNode * bt) {return bt->left;}

BTreeNode * GetRightSubTree(BTreeNode * bt) {return bt->right;}

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub)
{
    if(main->left != NULL)
        free(main->left);
    main->left = sub;
}

void MakeRightSubTree(BTreeNode * main, BTreeNode * sub)
{
    if(main->right != NULL)
        free(main->right);
    main->right = sub;
}

void PreorderTraverse(BTreeNode * bt, VisitFuncPtr action)
{
    if(bt == NULL)
        return;
    action(bt->data);
    PreorderTraverse(bt->left, action);
    PreorderTraverse(bt->right, action);
}

void InorderTraverse(BTreeNode * bt, VisitFuncPtr action)
{
    if(bt == NULL)
        return;
    InorderTraverse(bt->left, action);
    action(bt->data);
    InorderTraverse(bt->right, action);
}

void PostorderTraverse(BTreeNode * bt, VisitFuncPtr action)
{
    if(bt == NULL)
        return;
    PostorderTraverse(bt->left, action);
    PostorderTraverse(bt->right, action);
    action(bt->data);
}

BTreeNode * RemoveLeftSubTree(BTreeNode *bt)
{
    BTreeNode * delNode;
    
    if(bt != NULL)
    {
        delNode = bt->left;
        bt->left = NULL;
    }
    return delNode;
}

BTreeNode * RemoveRightSubTree(BTreeNode * bt)
{
    BTreeNode * delNode;
    
    if(bt != NULL)
    {
        delNode = bt->right;
        bt->right = NULL;
    }
    return delNode;
}

void ChangeLeftSubTree(BTreeNode * main, BTreeNode * sub)
{
    main->left = sub;
}

void ChangeRightSubTree(BTreeNOde * main, BTreeNode * sub)
{
    main->right = sub;
}

이진 탐색 트리의 삭제구현 : 완전한 구현

BTreeNode * BSTRemove(BTreeNode ** pRoot, BSTData target)
{
    //삭제 대상이 루트이노드인 경우를 별도로 고려해야 한다
    BTreeNode * pVRoot = MakeBTreeNode();   //가상 루트 노드
    BTreeNode * pNode = pVRoot; //parent node 
    BTreeNode * cNode = *pRoot; //current node
    BTreeNode * dNode;  //delete node
    
    //루트 노드를 pVRoot가 가리키는 노드의 오른쪽 자식 노드가 되게 한다
    ChangeRightSubTree(pVRoot, *pRoot);
    
    //삭제 대상인 노드를 탐색
    while(cNode != NULL && GetData(cNode) != target)
    {
        pNode = cNode;
        if(target < GetData(cNode))
            cNode = GetLeftSubTree(cNode);
        else
            cNode = GetRightSubTree(cNode);
    }
    
    if(cNode == NULL)   //삭제 대상이 존재하지 않는다면
        return NULL;
        
    dNode = cNode;  //삭제 대상을 dNode가 가리키게 한다
    
    // 첫 번재 경우 : 삭제 대상이 단말 노드인 경우
    if(GetLeftSubTree(dNode) == NULL && GetRightSubTree(dNode) == NULL)
    {
        if(GetLeftSubTree(pNode) == dNode)
            RemoveLeftSubTree(pNode);
        else
            RemoveRightSubTree(pNode);
    }
    
    // 두 번째 경우 : 삭제 대상이 하나의 자식 노드를 갖는 경우
    else if(GetLeftSubTree(dNode) == NULL || GetRightSubTree(dNode) == NULL)
    {
        BTreeNOde * dcNode; //삭제 대상의 자식 노드 가리킴
        
        if(GetLeftSubTree(dNode) != NULL)
            dcNode = GetLeftSubTree(dNode);
        else
            dcNode = GetRightSubTree(dNode);
            
        if(GetLeftSubTree(pNode) == dNode)
            ChangeLeftSubTree(pNode, dcNode);
        else
            ChangeRightSubTree(pNode, dcNode);
    }
    
    // 세 번째 경우 : 두 개의 자식 노드를 모두 갖는 경우
    else{
        BTreeNode * mNode = GetRightSubTree(dNode); //대체 노드 가리킴
        BTreeNode * mpNode = dNode; //대체 노드의 부모 노드 가리킴
        int delData;
        
        //삭제 대상의 대체 노드를 찾는다.
        while(GetLeftSubTree(mNode) != NULL)
        {
            mpNode = mNode;
            mNode = GetLeftSubTree(mNode);
        }
        
        //대체 노드에 저장된 값을 삭제한 노드에 대입한다
        delData = GetData(dNode);   //대입 전 데이터 백업
        SetData(dNode, GetData(mNode)); //대입!
        
        //대체 노드의 부모 노드와 자식 노드를 연결한다
        if(GetLeftSubTree(mpNode) == mNode)
            ChangeLeftSubTree(mpNode, GetRightSubTree(mNode));
        else
            ChangeRightSubTree(mpNode, GetRightSubTree(mNode));
            
        dNode = mNode;
        SetData(dNode, delData);    //백업 데이터 복원
    }
    
    //삭제된 노드가 루트 노드인 경우에 대한 추가적인 처리
    if(GetRightSubTree(pVRoot) != * pRoot)
        *pRoot = GetRightSubTree(pVRoot);   //루트 노드의 변경을 반영
        
    free(pVRoot);   //가상 루트 노드의 소멸
    return dNode;   //삭제 대상의 반환
}

pNode는 cNode의 부모 노드를 가리킨다
삭제의 과정에서 cNode의 부모와 자식을 연결하는 과정이 있기 때문에, 항상 pNode는 cNode의 부모 노드를 가리키고 있어야 한다

중위 순회를 할 경우, 정렬된 순서로 데이터 참조 및 출력이 가능하다

profile
castlehi
Back-end Developer
이전 포스트

Ch10. 정렬(Sorting)

다음 포스트

Ch12. 탐색(Search) 2

0개의 댓글

관련 채용 정보