C++で二分探索木の要素を検索するプログラム

本記事では、C++を使って二分探索木（Binary Search Tree、BST）の中に特定の要素が存在するかどうかを検索するプログラムを紹介します。二分探索木は「左の子 ＜ 親 ＜ 右の子」という大小関係を保つデータ構造で、この性質を利用することで効率的な探索が可能です。探索の最悪ケースの計算量はO(n)ですが、平均ケースではO(log n)となり、バランスの取れた木であれば非常に高速に動作します。

アルゴリズム

探索処理の手順は以下の通りです。

Begin
    未ソートのデータ配列から、データを1つずつ木に挿入して二分探索木を構築する
    探索対象のデータを入力として受け取る
    根ノードから開始し、ノードの値と探索データを比較する
    data < temp->d の場合、tempポインタを左の子へ移動する
    data > temp->d の場合、tempポインタを右の子へ移動する
    data == temp->d の場合、見つかった位置の深さを出力してmainに戻る
    ノードがNULLに到達した場合は「要素が見つからない」ことを出力する
End

サンプルコード

以下が実際のC++コードです。あらかじめ用意した配列のデータをすべてBSTに挿入した後、ユーザーが入力した値を根ノードから順に比較しながら探索します。要素が見つかった場合は、その深さ（根を1とした階層数）を表示します。

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

// BSTにデータを挿入する関数
node* InsertIntoTree(node* root, int d) {
    node *temp = CreateNode(d);
    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;
}

// BST内を探索する関数
void Search(node *root, int d) {
    int depth = 0;
    node *temp = root;
    while(temp != NULL) {
        depth++;
        if(temp->d == d) {
            cout<<\"\n要素が見つかりました。深さ: \"<<depth;
            return;
        } else if(temp->d > d)
            temp = temp->left;
        else
            temp = temp->right;
    }
    cout<<\"\n要素は見つかりませんでした\";
    return;
}

int main() {
    char ch;
    int n, i, a[10] = {93, 53, 45, 2, 7, 67, 32, 26, 71, 76};
    node *root = NULL;
    for (i = 0; i < 10; i++)
        root = InsertIntoTree(root, a[i]);
up:
    cout<<\"\n検索する要素を入力してください: \";
    cin>>n;
    Search(root, n);
    cout<<\"\n\n\t続けて検索しますか？(y/n): \";
    cin>>ch;
    if(ch == 'y' || ch == 'Y')
        goto up;
    return 0;
}

実行結果

検索する要素を入力してください: 26
要素が見つかりました。深さ: 7

        続けて検索しますか？(y/n): y

検索する要素を入力してください: 1
要素は見つかりませんでした

        続けて検索しますか？(y/n): n

計算量のポイント

二分探索木の探索では、1回の比較ごとに候補となる部分木が半分に絞られていくため、平均的にはO(log n)の時間で探索が完了します。ただし、ソート済みのデータを順番に挿入すると木が片側に偏って連結リストと同じ形状になり、最悪ケースではO(n)まで性能が低下します。実務ではAVL木や赤黒木といった平衡二分探索木を採用することで、常にO(log n)の性能を保証できます。