【C++】二分探索木（BST）の最小値を求めるプログラムの解説

本記事では、二分探索木（Binary Search Tree：BST）に格納されたデータの中から最小値を求めるC++プログラムを紹介します。二分探索木には「左の子孫は親より小さい値を持つ」という性質があるため、木の左端にあるノードを順にたどっていくだけで、必ず最小値のノードに到達できます。

アルゴリズム

処理の手順は以下の擬似コードのとおりです。

開始
    構造体ndを宣言する。
    整数型の変数dを宣言する。
    構造体nd型へのポインタlt（左子）を宣言する。
    構造体nd型へのポインタrt（右子）を宣言する。

    関数new_nd()（戻り値：構造体nd型、引数：整数d）
        ポインタndを宣言し、
        nd = (struct nd*) malloc(sizeof(struct nd)) で初期化する。
        nd->d に d を代入する。
        nd->lt に NULL を代入する。
        nd->rt に NULL を代入する。
        nd を返す。

    関数add_node()（戻り値：構造体nd型、引数：ポインタnd・整数d）
        もし nd == NULL ならば
            new_nd(d) を返す。
        そうでなければ
            もし d <= nd->d ならば
                nd->lt = add_node(nd->lt, d)
            そうでなければ
                nd->rt = add_node(nd->rt, d)
            nd を返す。

    関数minimum_val()（戻り値：整数型、引数：ポインタnd）
        ポインタcurを宣言し、cur = nd で初期化する。
        cur->lt が NULL になるまで繰り返す
            cur = cur->lt
        cur->d を返す。

    ポインタrootを宣言し、NULL で初期化する。
    root = add_node(root, 54)
    add_node(root, 32)
    add_node(root, 25)
    add_node(root, 45)
    add_node(root, 65)
    add_node(root, 75)
    「与えられた二分探索木の最小値は次のとおりです」と出力する。
    二分探索木の最小値を出力する。
    getchar() を呼び出して入力待ちにする。
終了

サンプルコード（C++実装例）

#include <bits/stdc++.h>
using namespace std;

// ノードを表す構造体
struct nd {
    int d;              // ノードが保持するデータ
    struct nd* lt;      // 左の子ノードへのポインタ
    struct nd* rt;      // 右の子ノードへのポインタ
};

// 新しいノードを作成する関数
struct nd* new_nd(int d) {
    struct nd* nd = (struct nd*)
    malloc(sizeof(struct nd));
    nd->d = d;
    nd->lt = NULL;
    nd->rt = NULL;
    return(nd);
}

// 木にノードを挿入する関数
struct nd* add_node(struct nd* nd, int d) {
    if (nd == NULL)
        return(new_nd(d));
    else {
        if (d <= nd->d)                 // 現在の値以下なら左側へ
            nd->lt = add_node(nd->lt, d);
        else                            // 現在の値より大きければ右側へ
            nd->rt = add_node(nd->rt, d);
        return nd;
    }
}

// 最小値を求める関数
int minimum_val(struct nd* nd) {
    struct nd* cur = nd;
    while (cur->lt != NULL) {           // 左端のノードまで移動
        cur = cur->lt;
    }
    return(cur->d);
}

int main() {
    struct nd* root = NULL;
    root = add_node(root, 54);
    add_node(root, 32);
    add_node(root, 25);
    add_node(root, 45);
    add_node(root, 65);
    add_node(root, 75);
    cout << "The Minimum value of the given binary search tree is: " << minimum_val(root);
    getchar();
    return 0;
}

実行結果

The Minimum value of the given binary search tree is: 25

プログラムのポイント

このプログラムで重要なのはminimum_val()関数の動作です。二分探索木では、すべての小さい値が左側の部分木に配置されるため、ルートから出発して左の子ポインタがNULLになるまで移動を繰り返せば、その位置のノードが必ず最小値になります。

また、ノードの追加は再帰的に実装されたadd_node()関数が担当します。挿入する値が現在のノードの値以下であれば左の子に、大きければ右の子に再帰的に渡すことで、二分探索木の構造が自動的に保たれます。

計算量については、木のバランスが取れている場合は木の高さに比例したO(log n)、偏った木（線形に近い形状）の場合は最悪でO(n)となります。