二分探索を使って特定の数値の出現回数を求めるC++プログラム

本記事では、二分探索(バイナリサーチ)の考え方を応用し、指定した数値がデータ集合の中に何回出現するかを効率的に求めるC++プログラムを紹介します。

このプログラムのポイントは、二分探索木(BST)の各ノードに「出現回数」を記録するカウンタを持たせている点です。同じ値が挿入されるたびに新規ノードを作成するのではなく、既存ノードのカウントを増やすことで、重複データをコンパクトに管理できます。そのため、検索時には木をたどるだけで、目的の数値の出現回数を高速に取得できます。

アルゴリズム

挿入処理(Insert関数)

1. 引数で渡されたデータを持つ新しいノードを作成します。
2. 木が完全に空の場合は、新しいノードを根(root)として挿入します。
3. d = tmp->data の場合、そのノードのカウントを1増やします。
4. d < tmp->data の場合、tmpポインタを左の子へ移動します。
5. d > tmp->data の場合、tmpポインタを右の子へ移動します。

検索処理(SearchNode関数)

1. tmpがNULLを指すか、目的のデータが見つかるまでループを繰り返します。
2. d < tmp->data の場合、tmpポインタを左の子へ移動します。
3. d > tmp->data の場合、tmpポインタを右の子へ移動します。
4. d = tmp->data の場合、見つかった項目とその出現回数を出力し、main関数へ戻ります。
5. 最後まで見つからない場合は「データが見つかりません(Data not found)」と出力します。

サンプルコード

#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 = new 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 = new nod;
    tmp = root;
    while(tmp != NULL) {
        if(tmp->data == d) {
            cout<<"\nData item "<<d<<" is present "<<tmp->cnt<<" number of times.";
            return;
        } else if(tmp->data > d)
            tmp = tmp->l;
        else
            tmp = tmp->r;
    }
    cout<<"\n Data not found";
    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 = new nod;
    root = NULL;
    for(i = 0; i < 20; i++)
        root = Insert(root, a[i]);
    up:
    cout<<"\nEnter the Element to be searched: ";
    cin>>n;
    SearchNode(root, n);
    cout<<"\n\nWant to search more...enter choice(y/n)?";
    cin>>c;
    if(c == 'Y' || c == 'y')
        goto up;
    return 0;
}

実行結果

Enter the Element to be searched: 7
Data item 7 is present 2 number of times.
Want to search more...enter choice(y/n)?y
Enter the Element to be searched: 6
Data item 6 is present 2 number of times.
Want to search more...enter choice(y/n)?y
Enter the Element to be searched: 4
Data item 4 is present 2 number of times.
Want to search more...enter choice(y/n)?y
Enter the Element to be searched: 15
Data not found
Want to search more...enter choice(y/n)?n

プログラムの解説

このプログラムは、20個の整数を含む配列の要素を順番に二分探索木へ挿入します。挿入の際、すでに同じ値が木の中に存在していれば、新しいノードを作らずにそのノードのカウンタ(cnt)をインクリメントします。これにより、各ノードが「値」と「その出現回数」のペアを保持することになります。

検索を行うSearchNode関数では、通常の二分探索と同じ要領で木をたどります。目的の値を持つノードに到達したら、そのノードのcntフィールドを出力することで、出現回数を即座に知ることができます。値が存在しない場合はNULLに到達するため、「Data not found」と表示されます。

なお、サンプルコードでは繰り返し検索を実現するためにgoto文を使用していますが、実務のコードではwhileループなどの構造化された制御構文を使うことが推奨されます。また、木のバランスが偏ると検索性能が最悪O(n)まで低下するため、実用場面では平衡二分探索木(std::mapなど)の利用も検討するとよいでしょう。