Java | 「二分探索木（BST）」をもっと深く理解する

Javaで学ぶ「二分探索木（BST）」をもっと深く理解する（前半）

二分探索木（Binary Search Tree, BST）は、「探索を速くするための木構造」です。 配列やリストでの線形探索に比べて、うまく使えば検索・挿入・削除をとても効率よく行えます。 前半では、BSTの基本ルール、Javaでの実装、探索・挿入の流れを丁寧にかみ砕きながら、 「なぜ速くなるのか」「どこが重要なのか」を直感レベルで掴んでいくことを目標にします。 後半では、削除処理、バランス、計算量、セキュリティ・パフォーマンスの観点まで踏み込みます。

二分探索木（BST）の基本ルールを言語化する

BSTの本質は、たった一つのルールに集約されます。

「あるノードを基準にしたとき、 左の子（左部分木）にはそのノードより小さい値だけが入る。 右の子（右部分木）にはそのノードより大きい値だけが入る。」

これがすべてです。

例えば、次のような木を考えます。

8 / \ 3 10 / \ \ 1 6 14

この木では、

左側には 3, 1, 6 があり、すべて 8 より小さい 右側には 10, 14 があり、すべて 8 より大きい

さらに、部分木ごとにも同じルールが適用されています。

3 を根とする部分木では、左に 1、右に 6 があり、 1 < 3 < 6 という関係が保たれています。

この「どのノードを見ても、左は小さい・右は大きい」という自己相似的なルールが、 BSTの強さの源です。

Javaで二分探索木を表現する基本クラス

まずは、最もシンプルな BST のノードクラスを定義します。

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) {
        this.value = value;
    }
}

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) {
        this.value = value;
    }
}

この TreeNode を使って、手動で木を作ることもできます。

TreeNode root = new TreeNode(8);
root.left = new TreeNode(3);
root.right = new TreeNode(10);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(6);
root.right.right = new TreeNode(14);

TreeNode root = new TreeNode(8);
root.left = new TreeNode(3);
root.right = new TreeNode(10);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(6);
root.right.right = new TreeNode(14);

この構造は、先ほどの図と同じ BST です。 ここから、「探索」「挿入」をアルゴリズムとして書いていきます。

BSTでの探索：なぜ速くなるのか

BSTの探索は、「比較しながら左右どちらかに絞り込んでいく」プロセスです。 これは二分探索と同じ発想で、「範囲を半分にしていく」ことで高速化します。

例えば、「値 6 を探したい」とします。

まず根の 8 と比較します。 6 は 8 より小さいので、「右側は絶対に違う」と分かり、左部分木だけを見ればよくなります。

次に 3 と比較します。 6 は 3 より大きいので、今度は右部分木だけを見ればよくなります。

最後に 6 と比較して、一致したので探索終了です。

このように、毎回「左右どちらか一方だけを見る」ことで、 探索範囲がどんどん半分に絞られていきます。

Javaで書く BST の探索メソッド

探索をコードにすると、次のようになります。

public static TreeNode search(TreeNode root, int target) {
    TreeNode current = root;
    while (current != null) {
        if (target == current.value) {
            return current;
        } else if (target < current.value) {
            current = current.left;
        } else {
            current = current.right;
        }
    }
    return null; // 見つからなかった場合
}

public static TreeNode search(TreeNode root, int target) {
    TreeNode current = root;
    while (current != null) {
        if (target == current.value) {
            return current;
        } else if (target < current.value) {
            current = current.left;
        } else {
            current = current.right;
        }
    }
    return null; // 見つからなかった場合
}

このメソッドは、次のような流れで動きます。

現在のノードの値とターゲットを比較する 小さければ左へ、大きければ右へ進む 一致したらそのノードを返す 葉まで行っても見つからなければ null を返す

ここで深掘りしたいポイントは、「毎回左右どちらか一方しか見ない」ということです。 配列の線形探索では、最悪の場合すべての要素を見ますが、 BSTでは「半分ずつ捨てていく」ため、増え方が非常にゆるやかになります。

BSTへの挿入：ルールを壊さずにノードを追加する

次に、「値を BST に挿入する」処理を考えます。 挿入でも、基本的な考え方は探索と同じです。

1. 根からスタートする
2. 挿入したい値と現在のノードを比較する
3. 小さければ左へ、大きければ右へ進む
4. 進んだ先が null なら、そこに新しいノードを置く

Javaコードは次のようになります。

public static TreeNode insert(TreeNode root, int value) {
    if (root == null) {
        return new TreeNode(value);
    }

    TreeNode current = root;
    while (true) {
        if (value < current.value) {
            if (current.left == null) {
                current.left = new TreeNode(value);
                break;
            } else {
                current = current.left;
            }
        } else if (value > current.value) {
            if (current.right == null) {
                current.right = new TreeNode(value);
                break;
            } else {
                current = current.right;
            }
        } else {
            break;
        }
    }
    return root;
}

public static TreeNode insert(TreeNode root, int value) {
    if (root == null) {
        return new TreeNode(value);
    }

    TreeNode current = root;
    while (true) {
        if (value < current.value) {
            if (current.left == null) {
                current.left = new TreeNode(value);
                break;
            } else {
                current = current.left;
            }
        } else if (value > current.value) {
            if (current.right == null) {
                current.right = new TreeNode(value);
                break;
            } else {
                current = current.right;
            }
        } else {
            break;
        }
    }
    return root;
}

この挿入処理は、「探索しながら空き場所を見つける」というイメージです。 重要なのは、「左は小さい・右は大きい」という BST のルールを一切壊していないことです。

深掘り：挿入の流れを具体例で追う

例えば、空の木に順番に値を挿入してみます。

最初に 8 を挿入すると、根が 8 になります。 次に 3 を挿入すると、3 は 8 より小さいので、左に入ります。 次に 10 を挿入すると、10 は 8 より大きいので、右に入ります。 次に 6 を挿入すると、6 は 8 より小さいので左へ、 さらに 3 より大きいので、3 の右に入ります。

このように、挿入は「探索の延長」として理解できます。 探索で「ここにあるはずだ」と思った場所が空いていれば、そこに置く。 それだけです。

中順（in-order）走査で「ソート済みの順番」が得られる

BSTの非常に重要な性質が、「中順走査をすると値が昇順に並ぶ」という点です。

中順走査とは、「左 → 自分 → 右」の順番でノードを訪れる DFS です。

Javaコードは次のようになります。

public static void inOrder(TreeNode node) {
    if (node == null) return;
    inOrder(node.left);
    System.out.println(node.value);
    inOrder(node.right);
}

public static void inOrder(TreeNode node) {
    if (node == null) return;
    inOrder(node.left);
    System.out.println(node.value);
    inOrder(node.right);
}

この inOrder(root) を実行すると、 BST に格納されている値が「小さい順」に表示されます。

これは、BSTのルール「左は小さい・右は大きい」が そのまま「ソート済みの順番」に対応しているからです。

この性質は、検索だけでなく「順序付きデータ構造」として BST を使うときに非常に重要です。

BSTの計算量の直感（前半の触り）

計算量の話は後半で詳しく扱いますが、 ここで直感だけ先に共有しておきます。

BSTが「ほどよくバランスしている」場合、 探索・挿入・削除の時間計算量は O(log n) になります。

これは、「毎回左右どちらか一方だけを見る」ことで、 探索範囲が半分ずつ減っていくからです。

一方で、値を「昇順にだけ」挿入していくと、 BSTは「ほぼ一本の鎖」のような形になり、 計算量が O(n) まで悪化します。

この「バランス」の問題は、後半で 平衡二分探索木（AVL木やRed-Black Tree）との関係も含めて扱います。

セキュリティ・パフォーマンスの観点（前半の導入）

セキュリティスペシャリストの視点から見ると、 BSTには次のようなポイントがあります。

入力によって木の形が変わる 攻撃者が「わざと偏ったデータ」を送ることで、 BST を「鎖状」にして性能を落とすことが理論上可能です。

探索・挿入の計算量が形に依存する バランスが崩れた BST は、最悪 O(n) になり、 大量データを扱う場面では DoS攻撃の入り口になり得ます。

そのため、実務では「自前の素朴な BST」ではなく、 Java標準の TreeMap や TreeSet のような 平衡二分探索木ベースのデータ構造を使うことが多いです。

このあたりも後半で詳しく掘り下げます。

前半のまとめと後半への橋渡し

前半では、二分探索木（BST）の基本を

左は小さい・右は大きいというルール Javaでの基本クラスと構造 探索と挿入の流れ 中順走査によるソート済み順の取得 計算量とバランスの直感

という軸で整理しました。

後半では、さらに一歩進んで

削除アルゴリズム（3パターン） バランスが崩れたときの問題点 平衡二分探索木との関係（TreeMap / TreeSet の裏側イメージ） 計算量・セキュリティ・パフォーマンスの観点から見た BST の使い方

を、Javaコードとともに詳しく解説していきます。