アルゴリズム - 13. 二分探索木 (BST)
algorithmsdata-structurestreesearching
By sko•10/9/2025•13 min read
二分探索木をいつ使うか
効率的な操作で動的に変化するソート済みコレクションを維持する必要がある場合は、二分探索木を使用します。ソート済みデータの検索に最もよく使われますが、BSTは以下の用途にも適応できます：
- データベースのインデックス（古典的な使用例）- B木とB+木はBSTの変種
- 頻繁な更新を伴う優先度キュー（ヒープ操作では不十分な場合）
- 値の範囲内のすべての要素を見つける - 例：80〜90の間のすべてのスコア。BSTは範囲内の実際の要素を返します（「$50〜$100の価格帯のすべての製品を表示」など）、セグメント木は範囲集約クエリ（「インデックス3から7までの要素の合計」など）に優れています
- 順序統計量 - k番目に小さい/大きい要素を見つける
- 区間木 - 重複する区間を管理するBSTベースの構造（午後2〜4時、午後3〜5時のカレンダーイベントなど）。「午後3:30と重複するイベントは？」や「午後2〜3時のスロットと競合するすべての会議を見つける」などを効率的に答えます
- ファイルシステム - ディレクトリ構造とファイル整理
- 頻繁な挿入/削除でソート順を維持する必要がある問題
例題
音楽プレイリストマネージャー：曲のタイトルでソートされたプレイリストを維持する音楽プレーヤーを構築しています。["Bohemian Rhapsody", "Imagine", "Hey Jude", "Let It Be", "Yesterday", "Come Together"]のような曲を追加する操作で、効率的に：
- アルファベット順を維持しながら新しい曲を追加
- 特定の曲を検索して再生
- プレイリストから曲を削除
- 特定の文字またはプレフィックスで始まるすべての曲を見つける
すべての操作を処理した後：
- BSTは曲をアルファベット順に維持
- 「Hey Jude」の検索は平均O(log n)時間
- 中間順走査でソート済み順序ですべての曲を取得可能（左部分木 → 現在のノード → 右部分木を訪問し、アルファベット順を得る）
- 「Hで始まるすべての曲」などの範囲クエリは効率的（アルファベット順で「H」と「I」の間のすべての値を見つけること）
答え：BSTは自動的にソート順を維持するため、これらすべての操作を手動ソートなしで効率的にします。
二分探索木が実際に何をするか
二分探索木は、単純なルールによって要素をソート済み順序で維持する階層データ構造です。3つのコア操作を提供します：
- SEARCH：要素が木に存在するか見つける
- INSERT：BSTプロパティを維持しながら新しい要素を追加
- DELETE：要素を削除して木を再編成
（注：UPDATEは別の操作ではありません。値の変更にはDELETE + INSERTが必要です - 新しい値は木の別の位置に属する可能性があるためです）
音楽プレイリストをアルファベット順に整理することと考えてください：
- SEARCH：「この曲は私のプレイリストにある？」
- INSERT：「この新しい曲を正しいアルファベット位置に追加」
- DELETE：「この曲を削除してプレイリストをソート済みに保つ」
操作の仕組み
SEARCH操作 - 「この値は木にある？」
search(root, 42)を呼び出すと：
- ルートノードから開始
- 42を現在のノードの値と比較
- 42が小さければ左へ、大きければ右へ
- 見つかればtrueを返し、nullに到達すればfalse
- 重要な効率性：各ステップで残りの木の半分を除外
INSERT操作 - 「順序を維持しながらこの値を追加」
insert(root, 35)を呼び出すと：
- 検索と同じ比較パス（小さければ左、大きければ右）をたどる
- 空のスポット（null）に必ず到達する - 理由：値がすでに存在する（挿入をスキップ）か、葉ノードの空の子に到達するまで下降を続ける
- その空のスポットに値35で新しいノードを作成
- BSTプロパティ維持：左部分木のすべての値 < ノード < 右部分木のすべての値
例 - 35の挿入：
現在の木: 35を挿入するパス: 挿入後:
50 1. 50で: 35<50, 左へ 50
/ \ 2. 30で: 35>30, 右へ / \
30 70 3. 40で: 35<40, 左へ 30 70
/ \ 4. NULL（空）に到達！ / \
20 40 5. ここにノード作成 20 40
/
35DELETE操作 - 「この値を削除して再編成」
delete(root, 50)を呼び出すと、3つのケースを処理します：
-
葉ノード：単純に削除（他のノードに影響なし）
-
1つの子：ノードをその子で置き換える（子とそのすべての子孫は相対的な順序を維持）
-
2つの子：中間順後継（右部分木の最小）を見つけ、値を置き換え、後継を削除
なぜ「中間順後継」=「右部分木の最小」：この用語はソート順から来ています。すべての値をソート順にリストすると、「後継」は削除する値の次の値です。2つの子を持つノードの場合、この次の値は常に右部分木の最小値です。例：[30, 40, 50, 60, 70]で、50を削除するには60（次の値）が必要で、これは右に一度行き（70の部分木へ）、その後可能な限り左に行く（60を見つける）ことで見つかります。
なぜ「可能な限り左に行く」ことが最小値を見つけるのか：BSTでは、小さい値は常に左にあります。任意のノードから開始して、できなくなるまで左に進み続けると、その部分木の最小値に到達します。これがまさに中間順走査が次の要素を見つける方法です - ノードを訪問した後、右部分木に行き、すぐに可能な限り左に行きます。
したがって、中間順後継は右部分木の最も左のノードです。
これらがBST順序を維持する理由：
1つの子のケース - 30を削除（右の子40のみ）：
削除前: 削除後: なぜ機能するか:
50 50 40の部分木のすべてのノード（40, 35, 45）
/ \ / \ は30より大きく50より小さかった
30 70 40 70 30の位置より大きく50より小さいまま！
\ / \ 順序が保たれる！
40 35 45
/ \
35 452つの子のケース - 50を削除：
削除前: 削除後: なぜ機能するか:
50 60 60は右部分木で最小だった
/ \ / \ つまり：60 > 左のすべて（30,40）
30 70 30 70 そして：60 < 右の残り（70,80）
/ \ \ 完璧な置き換え！
60 80 80これらの操作がいつ発生するか
これらの操作は明示的に呼び出したときにのみ発生します：
const bst = new BinarySearchTree();
// INSERT: 明示的に要素を追加
bst.insert(50); // ルートを作成
bst.insert(30); // 50の左へ
bst.insert(70); // 50の右へ
bst.insert(40); // 30の右へ
// SEARCH: 要素が存在するか確認
let found = bst.search(40); // trueを返す
let notFound = bst.search(25); // falseを返す
// DELETE: 要素を削除
bst.delete(30); // 30を削除、木を再編成BSTの美しさは、ソート順を自動的に維持することです - データを手動でソートしたり再編成したりする必要はありません！
最も重要な洞察
すべてのノードでのBSTプロパティ（左 < 親 < 右）は検索のための決定木を作成します - そして「小さければ左、大きければ右」に一貫して従うことで、各ステップで検索空間の半分を除外し、平衡木でO(log n)検索を実現します。
メンタルノート：アルゴリズムの天才性は、ソート順を木構造自体にエンコードすることにあります。各ノードで、比較に基づいて左または右に行くという1つの決定をするだけです。各レベルでのこの単純なバイナリ決定は、自動的にソートされたデータを維持し、配列なしでバイナリサーチを可能にします。
決定フレームワーク
BST操作には以下の重要な決定が含まれます：
検索中：
- 現在のノードはnull？見つからないを返す
- ターゲットは現在の値と等しい？見つかったを返す
- ターゲットは現在より小さい？左へ行く
- ターゲットは現在より大きい？右へ行く
挿入中：
- 新しい値を現在のノードと比較（検索と同じ）
- 新しい値が小さければ左へ、大きければ右へ
- 空のスポット（null）を見つけるまで下降を続ける
- その空の位置に新しいノードを作成
削除中（最も複雑）：
- 子なし（葉）？単純に削除
- 1つの子？その子で置き換え
- 2つの子？中間順後継を見つけ、値を交換、後継を削除
なぜBSTプロパティが重要か
BSTプロパティはすべての操作が部分木全体を無視できることを保証します：
BSTプロパティなし（ソートされていない木）：
値35を見つけるには:
50
/ \
70 30
/ \ / \
20 40 60 10
すべての7ノードをチェック必須 - O(n)時間！BSTプロパティあり：
値35を見つけるには:
50
/ \
30 70 ← 右部分木全体を無視！
/ \
20 40 ← 30の左のみチェック、20は無視！
パス: 50 → 30 → 40 → 見つからない（3回のチェックのみ）BSTプロパティは以下を保証します：
- 左部分木のすべての値 < ノード値
- 右部分木のすべての値 > ノード値
- これはすべての部分木に再帰的に適用される
- 結果：各ステップで残りのノードの約50%を除外できる
これが平衡BSTがO(log n)操作を実現する理由です - 高さが必要な最大比較数を決定します！
コード
// 木のノード構造
class TreeNode {
constructor(value) {
this.value = value;
this.left = null; // 左の子（小さい値）
this.right = null; // 右の子（大きい値）
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
// SEARCH: 値が木に存在するか見つける
search(targetValue) {
return this.searchFromNode(this.root, targetValue);
}
searchFromNode(currentNode, targetValue) {
// ベースケース：パスの終わりに到達
const reachedEndOfPath = currentNode === null;
if (reachedEndOfPath) {
return false; // 値が見つからない
}
// 比較のために現在のノードの値を抽出
const currentValue = currentNode.value;
// 決定フレームワーク：3方向比較
const foundTarget = targetValue === currentValue;
const shouldSearchLeft = targetValue < currentValue;
const shouldSearchRight = targetValue > currentValue;
if (foundTarget) {
return true; // ターゲットの発見に成功！
}
if (shouldSearchLeft) {
// ターゲットが小さい - 左部分木のみ検索
const leftSubtree = currentNode.left;
return this.searchFromNode(leftSubtree, targetValue);
}
if (shouldSearchRight) {
// ターゲットが大きい - 右部分木のみ検索
const rightSubtree = currentNode.right;
return this.searchFromNode(rightSubtree, targetValue);
}
}
// INSERT: BSTプロパティを維持しながら新しい値を追加
insert(newValue) {
// ルートから挿入を開始、必要に応じてルートを更新
this.root = this.insertIntoSubtree(this.root, newValue);
}
insertIntoSubtree(currentNode, newValue) {
// ベースケース：新しいノードの空のスポットを見つけた
const foundEmptySpot = currentNode === null;
if (foundEmptySpot) {
const newNode = new TreeNode(newValue);
return newNode;
}
// 比較のために現在の値を抽出
const currentValue = currentNode.value;
// ベースケース：重複が見つかった - 挿入不要
const isDuplicate = newValue === currentValue;
if (isDuplicate) {
return currentNode; // 変更されていないノードを返す
}
// 決定フレームワーク：挿入方向を決定
const insertToLeft = newValue < currentValue;
if (insertToLeft) {
// 新しい値が小さい - 左部分木に挿入
const updatedLeftSubtree = this.insertIntoSubtree(
currentNode.left,
newValue
);
currentNode.left = updatedLeftSubtree;
} else {
// 新しい値が大きい - 右部分木に挿入
const updatedRightSubtree = this.insertIntoSubtree(
currentNode.right,
newValue
);
currentNode.right = updatedRightSubtree;
}
return currentNode;
}
// DELETE: 値を削除してBSTプロパティを維持
delete(valueToDelete) {
// ルートから削除を開始、必要に応じてルートを更新
this.root = this.deleteFromSubtree(this.root, valueToDelete);
}
deleteFromSubtree(currentNode, valueToDelete) {
// ベースケース：値が木に見つからない
const nodeNotFound = currentNode === null;
if (nodeNotFound) {
return null;
}
// 比較のために現在の値を抽出
const currentValue = currentNode.value;
// 決定フレームワーク：削除するノードを見つける
const searchLeft = valueToDelete < currentValue;
const searchRight = valueToDelete > currentValue;
const foundNodeToDelete = valueToDelete === currentValue;
if (searchLeft) {
// 削除する値は左部分木にある
const updatedLeftSubtree = this.deleteFromSubtree(
currentNode.left,
valueToDelete
);
currentNode.left = updatedLeftSubtree;
return currentNode;
}
if (searchRight) {
// 削除する値は右部分木にある
const updatedRightSubtree = this.deleteFromSubtree(
currentNode.right,
valueToDelete
);
currentNode.right = updatedRightSubtree;
return currentNode;
}
if (foundNodeToDelete) {
// 削除するノードを見つけた - 3つのケースを処理
// 決定フレームワーク：子の数に基づく削除ケース
const hasNoChildren =
currentNode.left === null && currentNode.right === null;
const hasOnlyRightChild =
currentNode.left === null && currentNode.right !== null;
const hasOnlyLeftChild =
currentNode.right === null && currentNode.left !== null;
const hasBothChildren =
currentNode.left !== null && currentNode.right !== null;
if (hasNoChildren) {
// ケース1：葉ノード - 単純に削除
return null;
}
if (hasOnlyRightChild) {
// ケース2a：右の子のみ存在 - それで置き換え
const rightChild = currentNode.right;
return rightChild;
}
if (hasOnlyLeftChild) {
// ケース2b：左の子のみ存在 - それで置き換え
const leftChild = currentNode.left;
return leftChild;
}
if (hasBothChildren) {
// ケース3：両方の子が存在 - 後継戦略を使用
// 中間順後継を見つける（右部分木の最小値）
const rightSubtree = currentNode.right;
const successorNode = this.findMinimumNode(rightSubtree);
const successorValue = successorNode.value;
// 現在のノードの値を後継の値で置き換える
currentNode.value = successorValue;
// 右部分木から後継を削除（最大1つの子を持つ）
const updatedRightSubtree = this.deleteFromSubtree(
rightSubtree,
successorValue
);
currentNode.right = updatedRightSubtree;
return currentNode;
}
}
}
// ヘルパー：部分木の最小値を持つノードを見つける
findMinimumNode(startNode) {
// 最小値は常に最も左のノード
let currentNode = startNode;
// さらに進めなくなるまで左に進み続ける
while (currentNode.left !== null) {
currentNode = currentNode.left;
}
// これが最も左（最小）のノード
return currentNode;
}
// ボーナス：中間順走査（ソート済み配列を返す）
getSortedValues() {
const sortedArray = [];
this.collectInOrder(this.root, sortedArray);
return sortedArray;
}
collectInOrder(currentNode, resultArray) {
// ベースケース：nullノードは何も貢献しない
const isNullNode = currentNode === null;
if (isNullNode) {
return;
}
// 中間順走査：左 → 現在 → 右
const leftSubtree = currentNode.left;
const currentValue = currentNode.value;
const rightSubtree = currentNode.right;
// ステップ1：左部分木のすべての値を処理（小さい値）
this.collectInOrder(leftSubtree, resultArray);
// ステップ2：現在のノードの値を処理
resultArray.push(currentValue);
// ステップ3：右部分木のすべての値を処理（大きい値）
this.collectInOrder(rightSubtree, resultArray);
}
}
// === 使用例：音楽プレイリストマネージャー ===
function demonstrateMusicPlaylist() {
const playlist = new BinarySearchTree();
// プレイリストに追加する曲
const songsToAdd = [
"Bohemian Rhapsody",
"Imagine",
"Hey Jude",
"Let It Be",
"Yesterday",
"Come Together",
];
// 各曲をプレイリストに追加
console.log("=== プレイリストに曲を追加 ===");
for (const songTitle of songsToAdd) {
playlist.insert(songTitle);
console.log(`✓ 追加: "${songTitle}"`);
}
// 検索機能をテスト
console.log("\n=== 曲検索のテスト ===");
const songToFind = "Hey Jude";
const songExists = playlist.search(songToFind);
console.log(`"${songToFind}"は存在する？ ${songExists}`); // true
const missingSong = "Stairway to Heaven";
const notInPlaylist = playlist.search(missingSong);
console.log(`"${missingSong}"は存在する？ ${notInPlaylist}`); // false
// ソート済み順序ですべての曲を表示
console.log("\n=== すべての曲（アルファベット順） ===");
const allSongsInOrder = playlist.getSortedValues();
console.log(allSongsInOrder);
// 出力: ["Bohemian Rhapsody", "Come Together", "Hey Jude", "Imagine", "Let It Be", "Yesterday"]
// プレイリストから曲を削除
console.log("\n=== 曲の削除 ===");
const songToRemove = "Hey Jude";
console.log(`"${songToRemove}"をプレイリストから削除中...`);
playlist.delete(songToRemove);
// 更新されたプレイリストを表示
const updatedPlaylist = playlist.getSortedValues();
console.log("更新されたプレイリスト:", updatedPlaylist);
// 出力: ["Bohemian Rhapsody", "Come Together", "Imagine", "Let It Be", "Yesterday"]
// 最終的な木構造を視覚化
console.log("\n=== 最終的な木構造 ===");
console.log(`
"Imagine"
/ \\
"Come Together" "Let It Be"
/ \\
"Bohemian Rhapsody" "Yesterday"
`);
}
// デモンストレーションを実行
demonstrateMusicPlaylist();疑問バスター
よくある疑問：「2つの子を持つノードを削除するとき、なぜ特に中間順後継（右部分木の最小）を選ぶのか？なぜ中間順前任（左部分木の最大）や他のノードではないのか？」
これは恣意的に見えます - アルゴリズムは前任でも動作するように見えるので、なぜすべての教科書が後継を主張するのでしょうか？この選択がなぜ重要なのか探ってみましょう。
なぜこれが恣意的に見えるのか
2つの子を持つノード50の削除を考えてみましょう：
50 (これを削除)
/ \
30 70
/ \ / \
20 40 60 80
オプション:
1. 前任（40）で置き換える - 左部分木の最大
2. 後継（60）で置き換える - 右部分木の最小
3. 70で置き換える？30は？なぜダメ？前任と後継の両方が機能するように見えます - 両方ともBSTプロパティを維持します！
重要な洞察：BSTプロパティの維持
ここが重要な要件です：置換値は以下でなければなりません：
- 左部分木のすべての値より大きい
- 右部分木のすべての値より小さい
- 現在の位置から削除しやすい
各オプションをチェックしてみましょう：
オプション1：中間順前任（40）
削除前: 50を40で置き換えた後:
50 40
/ \ / \
30 70 30 70
/ \ / \ / \ / \
20 40 60 80 20 - 60 80
✓ 40 > 左部分木のすべて（20, 30）
✓ 40 < 右部分木のすべて（60, 70, 80）
✓ 左部分木から40を削除するのは簡単（葉または1つの子を持つ）オプション2：中間順後継（60）
削除前: 50を60で置き換えた後:
50 60
/ \ / \
30 70 30 70
/ \ / \ / \ / \
20 40 60 80 20 40 - 80
✓ 60 > 左部分木のすべて（20, 30, 40）
✓ 60 < 右部分木のすべて（70, 80）
✓ 右部分木から60を削除するのは簡単（葉または1つの子を持つ）オプション3：70のようなランダムノード
50を70で置き換えた後:
70
/ \
30 70 (重複？！)
/ \ / \
20 40 60 80
✗ 70は右部分木のすべてより小さいわけではない（70と等しく、60より大きい）
✗ 重複を作成するかBSTプロパティに違反するなぜ特に後継（または前任）なのか？
数学的保証：中間順後継と前任は、すべての要件を満たす唯一の2つの値です：
-
中間順後継 = 削除されたノードより大きい最小値
- 左部分木のすべてより大きいことが保証
- 右部分木のすべて（自身を除く）より小さいことが保証
- 常に最大1つの子を持つ（定義上左の子なし）
-
中間順前任 = 削除されたノードより小さい最大値
- 右部分木のすべてより小さいことが保証
- 左部分木のすべて（自身を除く）より大きいことが保証
- 常に最大1つの子を持つ（定義上右の子なし）
-
他の値 = 少なくとも1つの部分木でBSTプロパティに違反
なぜ後継がわずかに好まれるのか
両方とも正しく動作しますが、後継は一貫性のためによく選ばれます：
- 標準慣習：ほとんどの教科書は均一性のために後継を使用
- バランスの考慮：ランダムな削除では、交互にするとよりバランスが取れる可能性
- 実装の簡潔性：最小（最も左）を見つけることは、最大を見つけるよりもクリーンなことが多い
- 歴史的前例：初期のBST論文は後継を使用
美しいプロパティ：なぜ後継/前任は最大1つの子しか持たないのか
これが削除を効率的にするエレガントな部分です：
中間順後継（右部分木の最小）：
ノード
\
右部分木
/
後継 (左の子なし！)
\
右の子があるかも- 後継が左の子を持っていたら、その子の方が小さいはず
- しかし、そうならその子が後継になるはず
- 矛盾！したがって、後継は右の子しか持てない
中間順前任（左部分木の最大）：
ノード
/
左部分木
\
前任 (右の子なし！)
/
左の子があるかも- 前任が右の子を持っていたら、その子の方が大きいはず
- しかし、そうならその子が前任になるはず
- 矛盾！したがって、前任は左の子しか持てない
このプロパティは、後継/前任をその位置から削除するとき、ケース1（葉）またはケース2（1つの子）しか直面しないことを保証します - 複雑なケース3に再び直面することはありません！
具体例：なぜアルゴリズムが最適なのか
削除をトレースして、このアプローチがなぜエレガントなのか見てみましょう：
// この木から50を削除:
// 50
// / \
// 30 70
// / \ / \
// 20 40 60 80
// \
// 65
//
deleteNode(root, 50):
// ノード50を見つけた - 2つの子を持つ
// 後継を見つける：右に1回行き、その後nullまで左に行く
successor = findMin(70の部分木) = 60
// 50の値を60で置き換える
node.value = 60
// 今度は右部分木から60を削除
// 60は1つの子（65）を持つので、これはケース2 - 簡単！
// 最終的な木:
// 60
// / \
// 30 70
// / \ / \
// 20 40 65 80アルゴリズムはエレガントに複雑な2つの子のケースをより単純な1つの子のケースに削減します！
結論：中間順後継（または前任）を使用することは恣意的ではありません - それらは削除されたノードを置き換えるときにBSTプロパティを維持する唯一の値です。それらの間の選択は小さな実装の詳細ですが、それらの1つを使用するための数学的要件は絶対的です。