二分探索木を使って配列の最小要素を求めるC++プログラム

本記事では、二分探索木（Binary Search Tree）を活用して、ソートされていない配列の中から最小要素を効率的に見つけるC++プログラムを紹介します。このアプローチの時間計算量は O(log(n)) であり、全要素を順に調べる線形探索の O(n) と比べて、大規模なデータセットで大きな高速化効果が期待できます。

アルゴリズムの考え方

二分探索木には「左の子ノード ＜ 親ノード ＜ 右の子ノード」という重要な性質があります。そのため、根（ルート）から出発してひたすら左側の子ノードをたどり続ければ、必ず最小値を持つノードに到達できます。

処理の手順

Begin
   与えられた未ソートのデータ配列から二分探索木を構築する。
   最小要素を求めるため、ポインタを最も左の子ノードまで移動する。
   そのノードの値を、データ集合全体の最小値として出力する。
End

サンプルコード

#include<iostream>
using namespace std;
struct node {
    int d;
    node *left;
    node *right;
};
// 新しいノードを生成する関数
node* CreateNode(int d) {
    node *newnode = new node;
    newnode->d = d;
    newnode->left = NULL;
    newnode->right = NULL;
    return newnode;
}
// 二分探索木へ値を挿入する関数
node* InsertIntoTree(node* root, int d) {
    node *temp = CreateNode(d);
    node *t = new node;
    t = root;
    if(root == NULL)
        root = temp;
    else{
        while(t != NULL) {
            if(t->d < d) {
                if(t->right == NULL) {
                    // 挿入位置が決まったのでノードを接続する
                    t->right = temp;
                    break;
                }
                // ポインタを右の子ノードへ移動
                t = t->right;
            }
            else if(t->d > d) {
                if(t->left == NULL) {
                    t->left = temp;
                    break;
                }
                // ポインタを左の子ノードへ移動
                t = t->left;
            }
        }
    }
    return root;
}
int main() {
    int n, i, a[10]={86, 63, 95, 6, 7, 67, 52, 26, 45, 98};
    node *root = new node;
    root = NULL;
    cout<<"\nData set:\n";
    for(i = 0; i < 10; i++) {
        cout<<a[i]<<" ";
        root = InsertIntoTree(root, a[i]);
    }
    cout<<"\n\nThe minimum element of the given data set is ";
    i = 0;
    // 左端のノードまでたどることで最小値を取得
    while(root->left != NULL) {
        i++;
        root = root->left;
    }
    cout<<root->d<<" which found at "<<i<<" depth from the root.";
    return 0;
}

実行結果

Data set:
86 63 95 6 7 67 52 26 45 98
The minimum element of the given data set is 6 which found at 2 depth from the root.

コードのポイント

• CreateNode関数：新しいノードを動的に確保し、左右の子ポインタをNULLで初期化します。
• InsertIntoTree関数：挿入する値と現在のノードの値を比較しながら木をたどります。値が大きければ右へ、小さければ左へ進み、空き位置にノードを接続します。
• 最小値の探索：main関数内のwhileループで、左の子が存在する限り左へ移動します。カウンタ変数iは根からの深さを記録しており、実行例では最小値「6」が深さ2の位置に見つかっています。