JavaScriptの二分探索木（BST）で最小値と最大値を検索する方法

二分探索木（Binary Search Tree：BST）には「左の子は必ず親より小さい」という重要な性質があります。この性質に注目すると、左の子が存在しなくなるまで左へ辿り続ければ、BST内の最小値のノードにたどり着くことが分かります。

同様に、「右の子は必ず親より大きい」という性質から、右端まで辿れば最大値が見つかることも理解できます。

それでは、実際にコードでこの機能を実装してみましょう。ここからは関数を反復処理版または再帰版のどちらか一方のみ実装していきます。今回は反復処理を使った関数を作成します。

getMinVal() の実装例

getMinVal() {
    if (this.root === null) {
        throw "Empty tree!";
    }

    let currNode = this.root;

    // 左の子がなくなるまで左へ移動
    while (currNode.left !== null) {
        currNode = currNode.left;
    }

    return currNode.data;
}

まず、ルートが空の場合は例外をスローしてエラーを通知します。その後、ルートから開始し、left プロパティが null になるまで左の子ノードへ移動を繰り返します。最終的に到達したノードのデータが最小値です。

動作確認

以下のコードでテストできます。

let BST = new BinarySearchTree();
BST.insertRec(10);
BST.insertRec(15);
BST.insertRec(5);
BST.insertRec(50);
BST.insertRec(3);
BST.insertRec(7);
BST.insertRec(12);

console.log(BST.getMinVal());

出力結果

3

木の中で最も小さい値である 3 が正しく取得できています。

getMaxVal() の実装

同じ考え方で、最大値を返す getMaxVal() 関数も作成できます。こちらは右端の子ノードまで反復処理することで値を取得します。以下に検証用のコードを示します。

getMaxVal() {
    if (this.root === null) {
        throw "Empty tree!";
    }

    let currNode = this.root;

    // 右の子がなくなるまで右へ移動
    while (currNode.right !== null) {
        currNode = currNode.right;
    }

    return currNode.data;
}

計算量について

これらの操作の時間計算量は O(h)（h は木の高さ）です。木がバランスしている場合、O(log n) で高速に動作しますが、偏った木（連結リストのような形）では O(n) になる点に注意しましょう。BSTを扱う上で、挿入時にバランスを保つこと（AVL木や赤黒木などの自己平衡木）が重要な理由の一つです。