JavaScriptで学ぶ二分探索木（BST）の実装方法をわかりやすく解説

本記事では、JavaScriptを使って二分探索木（Binary Search Tree、BST）を実装する手順を、初心者にもわかるように段階的に解説します。まずは基本となる「ツリー構造」の概念から確認していきましょう。

ツリー構造とは

ツリー（木構造）は、ノードと呼ばれる要素がエッジ（辺）によって接続されたデータ構造です。一般的に、各ノードは何らかのデータと、その子ノードへの参照を保持します。

二分探索木（BST）とは

二分探索木とは、各ノードが最大2つの子を持つ「二分木」の一種で、次のルールに従ってノードを配置するデータ構造です。

• 親ノードより小さい値は左側の子ノードに配置する
• 親ノードより大きい値は右側の子ノードに配置する

例えば、有効な二分探索木は次のように視覚化できます。

     25
   /   \
  20    36
 / \   / \
10  22 30  40

それでは、このルールに基づいた二分探索木をJavaScriptで実際に実装していきましょう。

ステップ1：Nodeクラスを作成する

まず、BST内の各ノードを表すNodeクラスを定義します。二分探索木は、前述のルールに従って配置されたノードの集合体にすぎません。そのため、各ノードは「保持するデータ」と「左右の子ノードへの参照」を持つことになります。

class Node {
  constructor(data) {
    this.data = data;   // ノードが保持する値
    this.left = null;   // 左の子ノードへの参照
    this.right = null;  // 右の子ノードへの参照
  }
}

新しいノードを作成したい場合は、次のようにデータを渡してクラスを呼び出します。

const newNode = new Node(23);

これにより、dataが23に設定され、leftとrightがどちらもnullである新しいNodeインスタンスが生成されます。

ステップ2：BinarySearchTreeクラスを作成する

次に、ツリー本体となるBinarySearchTreeクラスを定義します。最初はroot（根ノード）が存在しないため、nullで初期化しておきます。

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
}

このクラスはnewキーワードで呼び出すことで、新しいツリーインスタンスを生成できます。

const BST = new BinarySearchTree();

基本的な土台はこれで完成です。続いて、新しいノードをBSTのルールに従った正しい位置に挿入する処理を実装しましょう。

ステップ3：BSTにノードを挿入する

挿入処理は、insertメソッドとinsertNodeメソッドの2つに分けて実装します。insertメソッドは新しいノードの生成とルート判定を担当し、insertNodeメソッドは再帰処理によって適切な挿入位置を探します。

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(data) {
    const newNode = new Node(data);
    if (this.root === null) {
      // ツリーが空の場合、新ノードをルートにする
      this.root = newNode;
    } else {
      // そうでなければ、適切な位置を探して挿入する
      this.insertNode(this.root, newNode);
    }
  }

  insertNode(node, newNode) {
    if (newNode.data < node.data) {
      // 新しい値の方が小さい場合 → 左側へ
      if (node.left === null) {
        node.left = newNode;
      } else {
        this.insertNode(node.left, newNode);
      }
    } else {
      // 新しい値の方が大きい場合 → 右側へ
      if (node.right === null) {
        node.right = newNode;
      } else {
        this.insertNode(node.right, newNode);
      }
    }
  }
}

挿入の流れ：

• ツリーが空（rootがnull）なら、新しいノードがそのままルートになります。
• 既存のノードがある場合は、新しい値を現在のノードの値と比較し、小さければ左、大きければ右へ進みます。
• 進んだ先に空きスロット（null）があればそこにノードを置き、なければさらに再帰的に比較を繰り返します。

動作例：完全な二分探索木のコード

ここまでの内容をすべて統合した完全なコードがこちらです。最後にいくつかの値を挿入して、実際にツリーを構築してみましょう。

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

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(data) {
    const newNode = new Node(data);
    if (this.root === null) {
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode);
    }
  }

  insertNode(node, newNode) {
    if (newNode.data < node.data) {
      if (node.left === null) {
        node.left = newNode;
      } else {
        this.insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        this.insertNode(node.right, newNode);
      }
    }
  }
}

// インスタンスを生成してノードを挿入
const BST = new BinarySearchTree();
BST.insert(1);
BST.insert(3);
BST.insert(2);

このコードを実行すると、以下のような二分探索木が構築されます。

    1
     \
      3
     /
    2

このように、値の大小比較を繰り返しながら再帰的に位置を決めることで、BSTのルールに従ったツリーが自動的に形成されます。二分探索木は検索・挿入・削除の操作を平均O(log n)の計算量で実現できるため、大量のデータを効率的に扱いたい場面で非常に有用なデータ構造です。次のステップとして、特定の値を探す「searchメソッド」や、ツリー内の全ノードを順番に走査する「トラバーサル（巡回）処理」の実装にもぜひ挑戦してみてください。