JavaScriptで二分探索木（BinarySearchTree）を作成する方法

この記事では、JavaScriptで二分探索木（Binary Search Tree）を作成し、表現する方法を解説します。まずは BinarySearchTree クラスを作成し、そのクラスに Node プロパティを定義するところから始めましょう。

二分探索木とは

二分探索木（BST）は、各ノードが最大2つの子ノードを持つデータ構造です。「左の子ノードには親より小さい値、右の子ノードには親より大きい値を格納する」というルールに従うことで、高速な検索・挿入・削除を実現できます。

実装例

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

BinarySearchTree.prototype.Node = class {
    constructor(data, left = null, right = null) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
};

コードの解説

まず、BinarySearchTree クラスのコンストラクタ内で、ルート要素を null で初期化しています。これは「木がまだ空である」状態を表します。

次に、prototype を使って Node クラスを定義しています。各ノードは以下の3つのプロパティを持ちます。

• data：ノードが保持する値
• left：左の子ノードへの参照（デフォルトは null）
• right：右の子ノードへの参照（デフォルトは null）

ここまでで、BSTクラスの基本的な骨格が完成しました。今後は挿入や検索などの機能をこの構造に追加しながら、クラスを段階的に拡張していきます。