탐색

탐색Search 알고리즘은 데이터를 찾는 방법을 뜻한다. 특정 탐색 알고리즘은 특정 자료구조(배열array, 링크드 리스트linked list, 이진 트리binary tree 등)에만 쓰일 수 있다.

순차 탐색Sequential Search

처음부터 끝으로 이동하면서 하나하나 찾아보는 방식이다. 간단한 형태의 탐색 알고리즘이지만, 최대 n개의 데이터를 다 살펴봐야 할 수도 있다. 따라서 효율을 높이고자 배열 요소의 순서를 바꿔주는 등의 보조적인 조치들이 취해지기도 한다.

전진 이동법Move to Front Method는 단순하게 방금 찾은 데이터를 맨 앞으로 끌어오는 방식이다. 전위법Transpose은 탐색된 항목을 맨 앞으로 옮기지 않고 바로 왼쪽의 데이터와 교환하여 한 칸을 전진시키는 방법이다. 계수법Frequency Count Method은 각 요소가 탐색된 횟수를 따로 저장해둔 뒤 그 횟수를 기반으로 정렬하는 알고리즘이다. 계수법이 가장 합리적으로 보이지만 저장 공간을 더 사용해야 한다는 점은 명백하다.

이진 탐색Binary Search

이진 탐색binary search은 이분 탐색이라고도 불리는 알고리즘이다. 정렬된 배열을 기준으로 중앙 요소를 선택한 뒤 찾으려는 값이 그 요소보다 크면 오른쪽 절반을 대상으로 같은 행위를 반복한다. 작은 경우에는 왼쪽 절반을 대상으로 움직이면 되며, 이분 탐색의 시간복잡도는 log n이 나온다. 탐색 요소가 많은 경우에 특히 큰 힘을 발휘한다.

void BinarySearch( int Set[], int length, int target )
{
    int left, right, middle;
    left = 0;
    right = length -1;
    
    while ( left <= right )
    {
        middle = (left + right) / 2;

        if ( target > Set[middle] )
            left = middle + 1;
        else if ( target < Set[middle] )
            right = middle - 1;
        else 
            return middle;
    }
}

C언어에는 이분 탐색이 내장 메서드로 구현되어 있으며 bsearch()가 바로 그것이다.

int cmp( const void* _elem1, const void* _elem2 )
{
    int* elem1 = (int*)_elem1;
    int* elem2 = (int*)_elem2;

    if ( *elem1 > *elem2 )
        return 1;
    else if ( *elem1 < *elem2 )
        return -1;
    else
        return 0;
}

int target = 100;
bsearch( &target, Arr, length, sizeof( int ), cmp );

첫 번째 파라미터는 기준값이 되는 값이 담긴 변수의 '주소'다. 두 번째는 우리가 찾으려는 배열의 주소, 세 번째는 탐색할 데이터 요수의 갯수, 네 번째는 데이터 요소의 크기를 담고 있다. qsort() 때와 마찬가지로 비교 함수(의 포인터)가 마지막에 담겨 있다.

이진 탐색 트리Binary Search Tree

이진 탐색 트리Binary search tree는 위에서 본 이진 탐색과 동일한 일을 한다. 그렇다면 왜 배열에 비해 복잡한 이진 트리를 활용해서 탐색을 해야 하는가? 맨 처음에 우리가 배열이 있음에도 링크드 리스트를 만들었던 것을 기억해보자. 링크드 리스트는 배열과 비교했을 때 여러 장단점이 있었지만, 동적으로 노드를 추가하고 제거하는 것이 훨씬 쉽다는 장점이 있었다.

이진 탐색 트리 역시 마찬가지다. bsearch()나 이진 탐색은 배열에만 사용이 가능한데(코드를 보면 사전에 길이를 담아두어야 하는 것을 알 수 있다), 이진 탐색 트리는 동적으로 노드 추가/제거가 가능한 형태의 자료구조에 이진 탐색을 하기 위해 만들어진 것이다. 따라서 삽입/제거가 잦은 경우에 이진 탐색에 비해 성능이 좋다. 이것이 이진 탐색 트리의 핵심이다.

이진 탐색 트리는 단 하나의 규칙을 따르는데, 그것은 왼쪽 자식 노드가 나보다 작고 오른쪽 자식 노드는 나보다 크다는 것이다. 정렬된 배열에서 이진 탐색을 활용했던 방식과 같다.

이진 탐색 때는 정렬된 배열의 중앙값을 활용했다. 그렇다면 이진 탐색 트리에서는 어떤 값이 중앙값 역할을 하는가? 방금 위에서 보았다. 그렇다. 부모 노드가 자식 노드의 중앙값 역할을 하게 된다. 예를 들어 뿌리 노드가 100이라고 하면 뿌리 노드의 왼쪽 하위 트리에는 100보다 작은 값을 가진 노드들만 존재한다. 반대로 오른쪽 하위 트리에는 100보다 큰 값을 가진 노드들만 존재할 것이다. 이 특징을 이용해서 찾으려는 값과 노드를 비교해 뿌리에서 잎 방향으로 탐색해나가는 것이 이진 탐색 트리다.

글을 읽어보면 알겠지만 생성 후 유지/보수가 어렵지 탐색 자체는 아주 심플하다. 그러므로 우리는 ADT에서 삽입/삭제는 구현이 어렵고(코드가 길고) 탐색은 비교적 간단할 것임을 예측할 수 있다.

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

typedef int ElemType;

typedef struct _BSTNode
{
    struct _BSTNode* Left;
    struct _BSTNode* Right;

    ElemType Data;
} BSTNode;

BSTNode* CreateNode( ElemType data )
{
    BSTNode* NewNode = (BSTNode*)malloc( sizeof( BSTNode ) );

    NewNode->Data = data;
    NewNode->Left = NULL;
    NewNode->Right = NULL;

    return NewNode;
}
void DestroyNode( BSTNode* N )
{
    free( N );
}
void DestroyTree( BSTNode* Tree )
{
    if ( Tree->Right != NULL )
        DestroyTree( Tree->Right );
    if ( Tree->Left != NULL )
        DestroyTree( Tree->Left );
    
    Tree->Left = NULL;
    Tree->Right = NULL;

    DestroyNode( Tree );
}

BSTNode* SearchNode( BSTNode* Tree, ElemType target )
{
    if ( Tree == NULL ) return NULL;

    if ( Tree->Data == target )
        return Tree;
    else if ( Tree->Data > target )
        return SearchNode( Tree->Left, target );
    else
        return SearchNode( Tree->Right, target );
}

void InsertNode( BSTNode* Tree, BSTNode* NewNode )
{
    if ( Tree->Data < NewNode->Data )
    {
        if ( Tree->Right == NULL )
            Tree->Right = NewNode;
        else
            InsertNode( Tree->Right, NewNode );
    }
    if ( Tree->Data > NewNode->Data )
    {
        if ( Tree->Left == NULL )
            Tree->Left = NewNode;
        else
            InsertNode( Tree->Left, NewNode );
    }
}
BSTNode* SearchMinNode( BSTNode* Tree )
{
    if ( Tree == NULL )
        return NULL;
    
    if ( Tree->Left == NULL )
        return Tree;
    else
        return SearchMinNode( Tree->Left );
}
BSTNode* RemoveNode( BSTNode* Tree, BSTNode* Parent, ElemType target )
{
    BSTNode* Removed = NULL;

    if ( Tree == NULL ) return Removed;

    if ( Tree->Data > target )
        Removed = RemoveNode( Tree->Left, Tree, target );
    else if ( Tree->Data < target )
        Removed = RemoveNode( Tree->Right, Tree, target );
    else
    {
        Removed = Tree;

        if ( Tree->Left == NULL && Tree->Right == NULL )
        {
            if ( Parent->Left == Tree )
                Parent->Left = NULL;
            else
                Parent->Right = NULL;
        }
        else
        {
            if ( Tree->Left != NULL && Tree->Right != NULL )
            {
                BSTNode* MinNode = SearchMinNode( Tree->Right );
                MinNode = RemoveNode( Tree, NULL, MinNode->Data );
                Tree->Data = MinNode->Data;
            }
            else
            {
                BSTNode* Tmp = NULL;

                if ( Tree->Left != NULL )
                    Tmp = Tree->Left;
                else
                    Tmp = Tree->Right;
                
                if ( Parent->Left == Tree )
                    Parent->Left = Tmp;
                else
                    Parent->Right = Tmp;
            }
        }
    }

    return Removed;
}

삽입 연산의 경우 상대적으로 간단하다. 뿌리에서 시작해 새 데이터가 더 작으면 왼편으로, 크면 오른편으로 계속 간다. 가다가 빈자리를 발견하면 그곳에 자리를 잡는다.

제거 연산은 복잡하다. 제거된 후에도 노드들이 연결되어 있어야 하고 또한 이진 탐색 트리의 조건을 만족해야 하므로 사후처리가 필요하기 때문이다.

우선 자식이 없는 노드가 제거된 경우는 간단하다. 자신만 제거되면 된다. 왼쪽 혹은 오른쪽에 자식 하나를 가진 노드의 경우도 간단하다. 삭제되는 노드의 자리에 자식 노드가 그대로 위치하면 된다.

자식을 양쪽 다 가진 노드를 제거하는 경우가 복잡하다. 우선 삭제하기로 한 노드를 기준으로 오른쪽 하위 트리에서 가장 작은 값을 갖는 노드를 찾는다. 그 노드를 삭제 연산이 시행될 노드의 위치에 가져다 놓은 뒤 가장 작은 값을 갖는 노드가 이동해오면서 빈 자리에 또 똑같은 논리로 새로운 노드를 찾아서 가져다 두어야 한다. 이전 두 경우는 아래 딸려오는 노드들에 영향이 없었지만 이번에는 노드가 딸려오는 게 아니라 최소값만 삭제되는 노드의 위치로 이동하다보니 재귀 형태로 코드가 짜여진다.

다시 한 번 강조하지만 이진 탐색 트리는 "이진 탐색을 '동적인 자료구조'에서 할 수 있도록 '링크드 리스트Linked List'(이진 트리)를 기반으로 만든 자료구조"다. 삽입/삭제가 잦은 경우 이진 탐색보다 성능이 좋다. 다만, 데이터가 불균형하게 들어올 경우 최악의 상황에서는 순차 탐색과 동일한 성능을 보인다. (이번에도 역시나) 각 탐색법의 장단점을 염두에 두고 알고리즘을 선택하는 것이 바람직하다.

참고 서적:
박상현, 2022, 한빛미디어, 『이것이 자료구조+알고리즘이다』

참고 사이트:
노루의 씨분투 세상: C언어 bsearch() - 이진탐색 함수
stackoverflow: Why is Binary Search a divide and conquer algorithm?
Doromi: 이진 탐색 vs 이진 탐색 트리