JavaScriptで学ぶ二分探索木（BST）クラスの完全実装ガイド

二分探索木（Binary Search Tree：BST）は、各ノードが最大2つの子ノードを持つ木構造のデータ構造です。「左側の子孫は親より小さい値、右側の子孫は親より大きい値」という規則を保つことで、データの挿入・検索・削除を効率的に行えます。

この記事では、JavaScriptによる二分探索木クラスの完全な実装を紹介し、挿入・探索・削除などの主要な操作について詳しく解説します。すべての操作について、反復処理版と再帰処理版の両方を用意しています。

BinarySearchTreeクラスの完全な実装

以下が二分探索木クラスの完全な実装コードです。

class BinarySearchTree {
    constructor() {
        // ルート要素を null で初期化する
        this.root = null;
    }

    // 挿入（反復版）
    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;
                }
            }
        }
    }

    // 挿入（再帰版）
    insertRec(data) {
        let node = new this.Node(data);

        // 木が空かどうかチェック
        if (this.root === null) {
            // 最初の要素として挿入
            this.root = node;
        } else {
            insertRecHelper(this.root, node);
        }
    }

    // 探索（反復版）
    searchIter(data) {
        let currNode = this.root;

        while (currNode !== null) {
            if (currNode.data === data) {
                // 要素が見つかった！
                return true;
            } else if (data < currNode.data) {
                // 値が親より小さいので左へ進む
                currNode = currNode.left;
            } else {
                // 値が親より大きいので右へ進む
                currNode = currNode.right;
            }
        }
        return false;
    }

    // 探索（再帰版）
    searchRec(data) {
        return searchRecHelper(data, this.root);
    }

    // 最小値の取得
    getMinVal() {
        if (this.root === null) {
            throw "木が空です！";
        }
        let currNode = this.root;

        while (currNode.left !== null) {
            currNode = currNode.left;
        }
        return currNode.data;
    }

    // 最大値の取得
    getMaxVal() {
        if (this.root === null) {
            throw "木が空です！";
        }
        let currNode = this.root;

        while (currNode.right !== null) {
            currNode = currNode.right;
        }
        return currNode.data;
    }

    // ノードの削除
    deleteNode(key) {
        return !(deleteNodeHelper(this.root, key) === false);
    }

    // 通りがけ順走査
    inOrder() {
        inOrderHelper(this.root);
    }

    // 行きがけ順走査
    preOrder() {
        preOrderHelper(this.root);
    }

    // 帰りがけ順走査
    postOrder() {
        postOrderHelper(this.root);
    }
}

// ノードクラスの定義
BinarySearchTree.prototype.Node = class {
    constructor(data, left = null, right = null) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
};

// ===== ヘルパーメソッド =====

// 行きがけ順走査（自分 → 左 → 右）
function preOrderHelper(root) {
    if (root !== null) {
        console.log(root.data);
        preOrderHelper(root.left);
        preOrderHelper(root.right);
    }
}

// 通りがけ順走査（左 → 自分 → 右）
function inOrderHelper(root) {
    if (root !== null) {
        inOrderHelper(root.left);
        console.log(root.data);
        inOrderHelper(root.right);
    }
}

// 帰りがけ順走査（左 → 右 → 自分）
function postOrderHelper(root) {
    if (root !== null) {
        postOrderHelper(root.left);
        postOrderHelper(root.right);
        console.log(root.data);
    }
}

// 挿入のヘルパー関数
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);
        }
    }
}

// 探索のヘルパー関数
function searchRecHelper(data, root) {
    if (root === null) {
        // 葉まで到達したが見つからなかった
        return false;
    }
    if (data < root.data) {
        return searchRecHelper(data, root.left);
    } else if (data > root.data) {
        return searchRecHelper(data, root.right);
    }
    // 要素が見つかった
    return true;
}

/**
 * ルートとキーを受け取り、キーを再帰的に探索して削除する。
 * キーが見つかった場合、次の3つのケースがあり得る：
 *
 * 1. 葉ノードの場合 → 親からの接続を切断するだけでよい
 *
 * 2. 子が1つある場合 → 子ノードを親の位置にそのまま置き換える
 *
 * 3. 子が2つある場合 → 後継者（successor）または前任者（predecessor）を
 *    見つけてノードを置き換える。後継者とは右部分木における最小要素。
 *    簡単な実装方法は、削除対象ノードの値を後継者の値に置き換え、
 *    その後継者を右部分木から削除すること。
 */
function deleteNodeHelper(root, key) {
    if (root === null) {
        // 空の木
        return false;
    }

    if (key < root.data) {
        root.left = deleteNodeHelper(root.left, key);
        return root;
    } else if (key > root.data) {
        root.right = deleteNodeHelper(root.right, key);
        return root;
    } else {
        // ケース1：子がない（葉ノード）
        if (root.left === null && root.right === null) {
            root = null;
            return root;
        }

        // ケース2：子が1つのみ
        if (root.left === null) return root.right;
        if (root.right === null) return root.left;

        // ケース3：子が2つあるため、後継者を見つける必要がある
        let currNode = root.right;

        while (currNode.left !== null) {
            currNode = currNode.left;
        }
        root.data = currNode.data;

        // 右部分木から後継者の値を削除
        root.right = deleteNodeHelper(root.right, currNode.data);
        return root;
    }
}

各メソッドの解説

1. ノードの挿入（insertIter / insertRec）

insertIter() は while ループを使った反復的な挿入、insertRec() は再帰呼び出しを使った挿入を行います。どちらも木が空の場合は新しいノードをルートに設定し、空でない場合は値の大小を比較しながら適切な位置（葉ノード）まで降りていきます。

2. 要素の探索（searchIter / searchRec）

探索も挿入と同じ要領で行います。現在のノードの値と一致すれば true を返し、探している値が小さければ左へ、大きければ右へ移動します。葉ノードまで到達して見つからなければ false を返します。BSTの性質上、毎回片側の部分木だけを調べればよいため、平均計算量は O(log n) と効率的です。

3. 最小値・最大値の取得（getMinVal / getMaxVal）

BSTでは、最小値は常に最も左のノード、最大値は常に最も右のノードに存在します。そのため、left をたどり続ければ最小値が、right をたどり続ければ最大値が得られます。木が空の場合は例外をスローします。

4. ノードの削除（deleteNode）

削除はBSTの操作の中で最も複雑です。削除対象のノードの状態によって、次の3つのケースに分けられます。

ケース1：葉ノード（子なし）の場合
例えば F を削除する場合、親ノードからの接続を切るだけで完了します。

ケース2：子が1つある場合
例えば B を削除する場合、その子ノードを親の位置にそのまま置き換えます。

ケース3：子が2つある場合（要注意）
例えば C を削除する場合、削除対象ノードの後継者（successor）または前任者（predecessor）を見つけて置き換える必要があります。後継者とは、右部分木における最小の要素、すなわち削除対象より大きい値の中で最も小さいものです。実装上は、削除対象ノードのデータを後継者の値で置き換えたうえで、右部分木から後継者を削除する方法が最もシンプルです。

5. 木の走査（inOrder / preOrder / postOrder）

深さ優先走査には3種類あり、それぞれ出力される順序が異なります。

• 行きがけ順（preOrder）：「自分 → 左 → 右」の順に訪問
• 通りがけ順（inOrder）：「左 → 自分 → 右」の順に訪問。BSTを通りがけ順で走査すると、昇順にソートされた結果が得られるのが特徴です。
• 帰りがけ順（postOrder）：「左 → 右 → 自分」の順に訪問

まとめ

この記事で紹介した BinarySearchTree クラスを使えば、挿入・検索・削除・最小値／最大値の取得・3種類の走査といった、二分探索木に必要な基本操作をすべて網羅できます。アルゴリズムの学習やコーディング面接の対策にも役立つ内容なので、ぜひ実際にコードを動かしながら挙動を確かめてみてください。