二分探索木（BST）完全ガイド：検索・挿入・削除の基本とAVL／赤黒木による平衡化、実装上の注意点
エバープレイ編集部二分探索木とは — 概要
二分探索木（Binary Search Tree, BST）は、各ノードが「キー」と任意の付随データを持ち、左の部分木のすべてのキーがノードのキーより小さく、右の部分木のすべてのキーがノードのキーより大きい（または等しい場合は実装ごとの扱い）という不変条件（BST性）を満たす二分木です。BSTは検索・挿入・削除などの動的集合操作を効率的に行うための基本データ構造で、順序を保った走査や範囲検索に向いています。
基本構造と性質
- ノード構成：キー、左子ポインタ、右子ポインタ、場合によっては親ポインタや高さ（バランス情報）を持ちます。
- BSTの不変条件：任意のノード N について、左部分木の全キー < N.key < 右部分木の全キー（重複の扱いは実装次第で、右に置く・左に置く・カウントを持つ等）。
- 巡回（トラバーサル）：中間順（in-order）走査を行うと、キーが昇順（ソート済み）で得られます。前順（pre-order）、後順（post-order）もよく使われます。
- 時間計算量：理想的（高さ h が O(log n)）なら検索・挿入・削除は O(h) = O(log n)。最悪（偏った木）では h = O(n) となり操作は O(n)。
基本操作
代表的な操作とアルゴリズム上のポイントを説明します。
検索（search）
根から始め、現在のノードのキーと検索キーを比較して左か右に進む（等しければ成功）。時間は木の高さに比例します。実装は再帰的でも反復的でもよい。
挿入（insert）
検索と同様に葉が置かれるべき位置を見つけ、そこに新ノードを割り当てます。バランス保持の仕組みがなければ、順序付きデータを単純に挿入し続けると偏った（鎖状の）木になりやすい点に注意。
削除（delete）
削除は三つの主要ケースがあります：
- 葉ノード：そのまま削除。
- 片方の子のみを持つノード：子を親に直接つなぎ替えて削除。
- 左右両方の子を持つノード：通常は「イネーブルメント」（in-order successor：右部分木の最小値）か「イネーブルメント predecessor（左部分木の最大値）」で値を置換し、置換元のノード（必ず子が高々一つ）を削除。
削除後に必要ならバランス調整（回転など）を行います（平衡BSTの場合）。
平衡性（バランス）の重要性
BSTの性能は木の高さに依存します。任意の順序で挿入を行うと最悪ケースとしてリンクリストのように偏るため、探索コストが線形になります。これを回避するために「平衡二分探索木（balanced BST）」が用いられます。代表的なもの：
- AVL木：各ノードの左右部分木の高さ差（バランス因子）が -1, 0, +1 の範囲に保たれる。回転操作で厳格にバランスを保つため検索は高速だが挿入・削除時の回転が多くなることがある。
- 赤黒木（Red-Black Tree）：色付けと緩やかな制約（各パスの黒ノード数が同じなど）で高さを O(log n) に保つ。実装がやや複雑だが挿入・削除の調整が比較的少なく産業用でよく使われる（例：JavaのTreeMap、C++のstd::mapの多くの実装）。
赤黒木は高さが最大で約 2 log2(n+1) に制限されるため、AVL よりも高さがやや大きくなる可能性はあるが、実装上の利便性から多くのライブラリで採用されています。
実装上の注意点
- 重複キーの扱い：許容する場合はカウントを保持したり、同じキーを右側に入れる方針をとることが多い。仕様を設計段階で明確にする。
- 再帰 vs 反復：再帰実装は簡潔だが深さが深いとスタックオーバーフローの恐れがある。大きなデータでは反復実装か明示的スタックを用いること。
- 親ポインタ：削除やイテレーションで便利だがメモリオーバーヘッドが増える。用途によって採用を検討する。
- メモリとローカリティ：BSTはノードがヒープ上に散らばるためキャッシュローカリティが悪く、ディスクベースの大規模インデックスには B-Tree 系の方が適している。
- イテレータ：in-order イテレータを作ることで順序走査や範囲クエリが容易にできる。スタックを使って非破壊的に実装するのが一般的。
回転（ローテーション）と高さ調整
AVLや赤黒木では局所的な回転（左回転、右回転）を用いて部分木の構造を変化させ、木全体の高さを抑えます。単回転と二重回転（左右の組合せ）があり、回転は O(1) の操作です。適切に行えば挿入・削除あたり平均的に O(1)〜O(log n) の回転で済みます。
用途と代替構造
- 用途：順序付きデータの管理、範囲検索、順序統計（k番目）や序数操作の拡張（部分木サイズを保持）など。メモリ上での動的集合に向く。
- 代替：ハッシュ表は平均 O(1) の検索だが順序性を保てない。ディスクや大規模データには B-Tree / B+Tree が適しており、ページ単位のアクセスを減らす設計になっている。
並行性・永続性（応用的話題）
高並列化が必要な場面では単純なロック（木全体ロック）はスケーラビリティを阻害するため、ノード単位でのロック分割や lock-free（非ブロッキング）実装、楽観的並行アルゴリズムが研究されています。永続データ構造（変更前のバージョンも保持する）としてはパスコピーを用いた永続BSTがあり、関数型言語でよく使われますが、メモリ効率や実装の複雑さが増します。
簡単な擬似コード（挿入と検索）
function search(root, key):
node = root
while node ≠ null:
if key == node.key: return node
if key < node.key: node = node.left
else: node = node.right
return null
function insert(root, key):
if root == null: return new Node(key)
parent = null
node = root
while node ≠ null:
parent = node
if key < node.key: node = node.left
else: node = node.right
if key < parent.key: parent.left = new Node(key)
else: parent.right = new Node(key)
return rootよくある落とし穴
- 無秩序な挿入で偏った木になる問題（ソート済み入力を順に挿入するとリンクリストになる）。
- 重複キーの非一貫な扱いによるバグ。
- 再帰深さとスタックオーバーフロー。
- ディスクやキャッシュを考慮しない設計（大規模データでは B-Tree が望ましい）。
まとめ
二分探索木は概念が単純で、動的集合の基本として非常に有用です。一方で「バランス」を考慮しないと性能が劣化するため、実運用では AVL、赤黒木、あるいは用途次第で B-Tree 系を選ぶことが一般的です。設計段階では、データの分布、必要な操作（挿入頻度か検索頻度か）、メモリ/ディスク要件、並行性の必要性を考慮して適切なバリアントを選択してください。
