二分探索木（BST）完全ガイド：検索・挿入・削除の基本とAVL／赤黒木による平衡化、実装上の注意点

2025年11月19日 最終更新日時 : 2025年11月19日 エバープレイ編集部

二分探索木とは — 概要

二分探索木（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 系を選ぶことが一般的です。設計段階では、データの分布、必要な操作（挿入頻度か検索頻度か）、メモリ/ディスク要件、並行性の必要性を考慮して適切なバリアントを選択してください。

参考文献

カテゴリー
IT
前の記事
ジョニー・マティス入門：必聴アルバム6選と聴きどころ解説 — 初心者におすすめの代表盤ガイドNew!!
2025年11月19日
次の記事
Jack Jones（ジャック・ジョーンズ）入門：代表曲・名盤と“歌の魅力”を徹底解説New!!
2025年11月19日