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;
}
}
この 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);
この構造は、先ほどの図と同じ 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; // 見つからなかった場合
}
このメソッドは、次のような流れで動きます。
現在のノードの値とターゲットを比較する 小さければ左へ、大きければ右へ進む 一致したらそのノードを返す 葉まで行っても見つからなければ null を返す
ここで深掘りしたいポイントは、「毎回左右どちらか一方しか見ない」ということです。 配列の線形探索では、最悪の場合すべての要素を見ますが、 BSTでは「半分ずつ捨てていく」ため、増え方が非常にゆるやかになります。
BSTへの挿入：ルールを壊さずにノードを追加する
次に、「値を BST に挿入する」処理を考えます。 挿入でも、基本的な考え方は探索と同じです。
- 根からスタートする
- 挿入したい値と現在のノードを比較する
- 小さければ左へ、大きければ右へ進む
- 進んだ先が 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;
}
この挿入処理は、「探索しながら空き場所を見つける」というイメージです。 重要なのは、「左は小さい・右は大きい」という 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);
}
この 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コードとともに詳しく解説していきます。