C++で二分探索木（BST）を使って配列の最大要素を検索する方法

本記事では、二分探索木（Binary Search Tree：BST）を利用して、配列の中から最大要素を検索するC++プログラムを紹介します。二分探索木の構造的な性質を活かすことで、最大値の探索は右側のノードを辿るだけで完了し、このプログラムの計算量は O(log n) に抑えられます。

アルゴリズム

開始
   与えられたデータ要素をもとに二分探索木を構築する。
   ルートポインタを、存在する限り最も右側の子ノードへ辿り続ける。
   そのノードのデータ部分を、データ集合の最大要素として出力する。
   最大データの深さ（ルートからの距離）を出力する。
終了

仕組みのポイント

二分探索木では、「左の子ノードは親より小さく、右の子ノードは親より大きい」という性質が常に成り立ちます。したがって、データ集合全体の最大値は必ず木の最も右端に存在します。ルートから右の子ポインタを順に辿り、右の子がNULLになった時点のノードの値こそが最大値となるのです。

サンプルコード

#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 maximum element of the given data set is\n ";
    i = 0;
    while(root->right != NULL) {
       i++;
       root = root->right;
    }
    cout<<root->d<<"\n"<<"data found at "<<i<<" depth from the root.";
    return 0;
}

実行結果

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

結果の解説

この例では、{86, 63, 95, 6, 7, 67, 52, 26, 45, 98} という10個の整数を順番に二分探索木へ挿入しています。挿入が完了した後、ルートから右の子ノードを辿ると、最大値である 98 が見つかりました。出力によれば、この最大値はルートから深さ2の位置に存在します。

なお、二分探索木への挿入順序によって木の形状は変化します。データが昇順・降順に近い形で挿入されると木が片寄り（偏った木）になり、最悪の場合は計算量がO(n)まで悪化する点には注意が必要です。バランスの取れた木を維持したい場合は、AVL木などの平衡二分探索木の採用も検討するとよいでしょう。