JavaScriptで二分探索木（BST）に特定の値が存在するかどうかを判定する方法

本記事では、BinarySearchTree（二分探索木）データ型のプロトタイプに、引数として渡された値がBST内に存在するかどうかを判定するJavaScript関数 contains を実装する方法を解説します。

二分探索木における探索の仕組み

二分探索木では、「左の子孫は親ノードより小さく、右の子孫は親ノードより大きい」という性質が成り立ちます。この性質を利用すると、1回の比較ごとに探索対象を左右どちらかに絞り込めるため、平均計算量 O(log n) で効率的に値を検索できます。

実装例

コードは以下の通りです。

// class for a single Node for BST
class Node {
    constructor(value) {
        this.value = value;
    }
}
// class for BST
// contains function to insert node and search for existing nodes
class BinarySearchTree {
    constructor() {
        this._root = null;
    };
    insert(value) {
        let node = this, side = '_root';
        while (node[side]) {
            node = node[side];
            if (value === node.value) {
                return;
            };
            side = value < node.value ? 'left' : 'right';
        };
        node[side] = new Node(value);
    };
    contains(value) {
        let current = this._root;
        while (current) {
            if (value === current.value) {
                return true;
            };
            current = value < current.value ? current.left : current.right;
        }
        return false;
    };
}
const tree = new BinarySearchTree();
for (let i = 0; i < 10; i++) {
    tree.insert(Math.floor(Math.random() * 1000));
};
tree.insert(34);
console.log(tree.contains(34));
console.log(tree.contains(334));

コードのポイント

• insert メソッド：値の大小関係に従って適切な位置に新しいノードを挿入します。重複した値は挿入されません。
• contains メソッド：根ノードから順に値を比較し、一致すれば true を返します。探索対象がなくなれば false を返します。

出力

コンソールには次のように出力されます。

true
false

34 は明示的に挿入しているため true となり、ランダム生成された10個の値に含まれる可能性が低い 334 は false となります。