C++ 이진 탐색으로 특정 숫자의 등장 횟수 구하기

이 글에서는 이진 탐색 트리(Binary Search Tree)를 활용하여 주어진 숫자가 데이터 집합에 몇 번 나타나는지 효율적으로 찾아내는 C++ 프로그램을 소개합니다.

일반적인 선형 탐색은 모든 요소를 하나씩 확인해야 하므로 O(n)의 시간이 걸리지만, 이진 탐색 트리를 사용하면 평균적으로 O(log n)의 시간 복잡도로 원하는 값을 빠르게 찾을 수 있습니다. 이 프로그램의 핵심 아이디어는 각 노드에 등장 횟수(cnt)를 함께 저장하고, 동일한 값이 다시 삽입될 때마다 해당 노드의 카운트만 증가시키는 것입니다.

알고리즘

1. 노드 삽입 함수 (Insert)

Begin
    function Insert() : 트리에 노드를 삽입한다.
    인자:
        root(루트 노드), d(삽입할 데이터)
    함수 본문:
        인자로 받은 데이터로 새 노드를 생성한다.
        트리가 완전히 비어 있다면, 새 노드를 루트로 지정한다.
        d = tmp->data 이면, 해당 노드의 카운트(cnt)를 1 증가시킨다.
        d < tmp->data 이면, tmp 포인터를 왼쪽 자식으로 이동한다.
        d > tmp->data 이면, tmp 포인터를 오른쪽 자식으로 이동한다.
End

2. 노드 탐색 함수 (SearchNode)

Begin
    function SearchNode() : 트리에서 항목을 검색한다.
    인자:
        root(루트 노드), d(찾을 데이터)
    함수 본문:
        tmp가 NULL을 가리키거나 데이터를 찾을 때까지 반복문을 수행한다.
            d < tmp->data 이면, tmp 포인터를 왼쪽 자식으로 이동한다.
            d > tmp->data 이면, tmp 포인터를 오른쪽 자식으로 이동한다.
            d = tmp->data 이면, 항목을 찾았다는 메시지와 함께
            저장된 등장 횟수를 출력하고 main으로 돌아간다.
        그렇지 않으면:
            "데이터를 찾을 수 없습니다"라는 메시지를 출력한다.
End

예제 코드

아래는 위 알고리즘을 실제로 구현한 전체 C++ 코드입니다.

#include<iostream>
using namespace std;

struct nod // 노드 선언
{
    int data;   // 저장할 데이터
    int cnt;    // 등장 횟수
    nod *l;     // 왼쪽 자식 포인터
    nod *r;     // 오른쪽 자식 포인터
};

nod* CreateNod(int d) // 새 노드 생성
{
    nod *newnod = new nod;
    newnod->data = d;
    newnod->cnt = 1;
    newnod->l = NULL;
    newnod->r = NULL;
    return newnod;
}

nod* Insert(nod* root, int d) // 노드 삽입 수행
{
    nod *tmp = CreateNod(d);
    nod *t = root;

    if(root == NULL)
        root = tmp;
    else {
        while(t != NULL) {
            if(t->data == d) {      // 같은 값이 이미 존재하면
                t->cnt++;           // 카운트만 증가
                break;
            } else if(t->data < d) {   // 값이 더 크면 오른쪽으로
                if(t->r == NULL) {
                    t->r = tmp;
                    break;
                }
                t = t->r;
            } else if(t->data > d) {   // 값이 더 작으면 왼쪽으로
                if(t->l == NULL) {
                    t->l = tmp;
                    break;
                }
                t = t->l;
            }
        }
    }
    return root;
}

void SearchNode(nod *root, int d) // 노드 탐색 수행
{
    nod *tmp = root;

    while(tmp != NULL) {
        if(tmp->data == d) {
            cout<<"\n데이터 "; cout<<d<<" 은(는) ";
            cout<<tmp->cnt<<"번 나타납니다.";
            return;
        } else if(tmp->data > d)
            tmp = tmp->l;
        else
            tmp = tmp->r;
    }
    cout<<"\n데이터를 찾을 수 없습니다.";
    return;
}

int main() {
    char c;
    int n, i, a[20] = {8,1,3,6,4,7,10,14,13,7,6,1,26,4,26,20,21,12,10,1}; // 배열 요소
    nod *root = NULL;

    for(i = 0; i < 20; i++)
        root = Insert(root, a[i]);

    up:
        cout<<"\n탐색할 요소를 입력하세요: ";
        cin>>n;
        SearchNode(root, n);
        cout<<"\n\n계속 탐색하시겠습니까? (y/n): ";
        cin>>c;
        if(c == 'Y' || c == 'y')
            goto up;
    return 0;
}

실행 결과

위 코드를 컴파일하여 실행하면 다음과 같은 결과를 얻을 수 있습니다.

탐색할 요소를 입력하세요: 7
데이터 7 은(는) 2번 나타납니다.

계속 탐색하시겠습니까? (y/n): y

탐색할 요소를 입력하세요: 6
데이터 6 은(는) 2번 나타납니다.

계속 탐색하시겠습니까? (y/n): y

탐색할 요소를 입력하세요: 4
데이터 4 은(는) 2번 나타납니다.

계속 탐색하시겠습니까? (y/n): y

탐색할 요소를 입력하세요: 15
데이터를 찾을 수 없습니다.

계속 탐색하시겠습니까? (y/n): n

동작 원리 정리

프로그램의 흐름을 단계별로 살펴보면 다음과 같습니다.

먼저 배열에 담긴 20개의 숫자를 순서대로 트리에 삽입합니다. 이때 중복된 값(예: 7, 6, 4, 1, 26, 10)이 들어오면 새 노드를 만들지 않고 기존 노드의 cnt 필드를 1씩 증가시킵니다. 그런 다음 사용자가 탐색할 값을 입력하면, 루트부터 시작해 값의 크기를 비교하며 왼쪽 또는 오른쪽 자식으로 내려가는 이진 탐색 방식으로 해당 노드를 찾습니다.

노드를 찾으면 저장된 등장 횟수를 출력하고, 끝까지 내려갔는데도 값을 찾지 못하면 "데이터를 찾을 수 없습니다"라는 메시지를 출력합니다. 사용자가 'y'를 입력하는 동안에는 계속해서 새로운 값을 탐색할 수 있습니다.

이처럼 이진 탐색 트리와 카운트 필드를 조합하면, 중복 데이터가 많은 대용량 데이터셋에서도 특정 값의 출현 빈도를 매우 효율적으로 조회할 수 있습니다.