JavaScriptで二分探索木にキーを挿入する方法【反復・再帰の両方を解説】

二分木への挿入の基本

新しく作成した二分木への最初の挿入では、ノードがルートとして配置されます。2回目以降の挿入では、二分探索木（BST）の特性に従ってノードが配置されます。つまり、左の子は親より小さい値、右の子は親より大きい値を持つというルールです。

ここでは、このアルゴリズムをコードで実装する方法を、反復（イテレーティブ）と再帰の2つのアプローチで解説します。

反復版の挿入メソッド

insertIter(data) {
    let node = new this.Node(data);

    // ツリーが空かどうかを確認
    if (this.root === null) {
        // 最初の要素として挿入
        this.root = node; return;
    }

    let currNode = this.root;
    while (true) {
        if (data < currNode.data) {
            // 葉ノードに到達したので、ここに値をセット
            if (currNode.left === null) {
                currNode.left = node;
                break;
            } else {
                currNode = currNode.left;
            }
        } else {
            // 葉ノードに到達したので、ここに値をセット
            if (currNode.right === null) {
                currNode.right = node;
                break;
            } else {
                currNode = currNode.right;
            }
        }
    }
}

処理の流れ

この関数の動作を順に見ていきましょう。

まず、ルートがnullかどうかを確認します。nullであればツリーが空であることを意味するため、新しいノードをルートとして代入すれば完了です。

空でない場合は、currNode変数を作成してルートを指させます。その後、挿入するデータがcurrNodeの値より小さいかどうかを判定します。小さい場合は左の子がnullかどうかを確認し、nullであればそこにデータを配置して終了します。nullでなければ、さらに左の子へ移動して処理を繰り返します。

これを葉ノードに到達するまで繰り返し、最終的にその位置にデータを配置します。

反復版の実行例

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

再帰版の挿入メソッド

同じ処理は再帰を使っても実装できます。ツリーは本質的に再帰的な構造であるため、この特性を活かすのは非常に自然なアプローチです。以下が再帰版のinsertメソッドです。

insertRec(data) {
    let node = new this.Node(data);

    // ツリーが空かどうかを確認
    if (this.root === null) {
        // 最初の要素として挿入
        this.root = node;
    } else {
        insertRecHelper(this.root, node);
    }
}

ヘルパー関数について

再帰処理を行うためのヘルパー関数が必要ですが、この関数をクラスのプロパティとして公開したくないため、クラス定義の外に配置します。

function insertRecHelper(root, node) {
    if (node.data < root.data) {
        // 葉ノードに到達したので、ここに値をセット
        if (root.left === null) {
            root.left = node;
        } else {
            // 左部分木を引数にして再帰的に呼び出し
            insertRecHelper(root.left, node);
        }
    } else {
        // 葉ノードに到達したので、ここに値をセット
        if (root.right === null) {
            root.right = node;
        } else {
            // 右部分木を引数にして再帰的に呼び出し
            insertRecHelper(root.right, node);
        }
    }
}

再帰版の実行例

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);

まとめ

二分探索木へのキー挿入は、反復でも再帰でも実装できます。反復版はwhileループで葉ノードまで辿るためスタックオーバーフローの心配がなく、再帰版はコードが簡潔でツリーの構造と相性が良いという特徴があります。用途やツリーの深さに応じて使い分けるとよいでしょう。