応用情報 令和7年度 春期 問2アルゴリズムとプログラミングに関する問題

正解は「O(n)」です。

2分探索木は「左の子は親より小さい、右の子は親より大きい」というルールで作る木です。バランスが取れていれば探索は速い（O(log n)）のですが、たとえば 1→2→3→4→5 と順に追加すると、すべてが右側に偏った「ほぼ一直線の木」になります。この場合n個の要素を順に辿る必要があり、線形リストと変わらない O(n) になります。

これを避けるためにAVL木や赤黒木など「自動で平衡化する木」があります。最悪 O(log n) を保証します。

覚え方：「偏ったら遅い、平衡したら速い」。

正解は c「O(n)」です。

2分探索木（Binary Search Tree, BST）は左の子＜親＜右の子という大小関係を保つデータ構造で、平均的には木の高さが log n となるため探索は O(log n) です。しかし「最悪計算量」を問う本問では、木が極端に偏ったケースを想定する必要があります。

たとえば昇順データを順次挿入すると、すべての挿入が右の子として連鎖し、木は実質的に片方向の連結リストとなります。この状態で要素を探索すると最悪ケースで n 個の要素を辿る必要があり、計算量は O(n) です。

これを回避するために以下の平衡2分探索木が考案されています：

• AVL木：左右の部分木の高さ差を ±1 以内に保つ。挿入・削除後に回転で再平衡。
• 赤黒木：各ノードに赤/黒の色属性を付与し、特定ルールで高さを保証。STLの map/set 内部で採用。
• B木 / B+木：データベースインデックスで採用される多分木の平衡木。

これらは挿入・削除のたびに自動的に再平衡を行い、最悪でも O(log n) を保証します。

AP午前では「データ構造の計算量」は頻出で、平均/最悪/最良の区別を問われます。特に2分探索木は「平均 O(log n) / 最悪 O(n)」を明確に押さえましょう（シラバス「アルゴリズムとデータ構造」）。

正解は c「O(n)」です。

本問は「2分探索木の最悪計算量」という基礎的なテーマですが、上級レベルでは計算量解析の理論的背景、実装上のトレードオフ、現代システムでの選択肢を理解する必要があります。

1. 計算量の階層と理論的根拠

2分探索木の探索計算量は木の高さ h に等しく、Θ(h) と書けます。バランス木では h = ⌈log₂(n+1)⌉ なので Θ(log n)、退化した木では h = n なので Θ(n) です。平均的なランダム挿入では期待高さは Θ(log n) であり、平均計算量も Θ(log n) となります（Knuth『The Art of Computer Programming』 Vol.3で証明）。

2. なぜ最悪 O(n) なのか

ソート済みデータの挿入は最悪ケースの典型例ですが、削除順序の偏り、特定パターンのワークロード（時系列データ等）でも木は容易に偏ります。本質的な原因は「挿入順序に対して木の構造が不変的に依存する」点にあり、これがランダムアクセス保証のあるハッシュテーブル（O(1)期待）との根本的な違いです。

3. 平衡化アルゴリズムの選択肢と比較

| 構造 | 探索 | 挿入 | 削除 | 特徴 |

|---|---|---|---|---|

| AVL木 | O(log n) | O(log n) | O(log n) | 厳密に高さ差±1。読み多めなら有利。 |

| 赤黒木 | O(log n) | O(log n) | O(log n) | 平衡条件が緩く挿入/削除コスト低い。 |

| Treap | O(log n) 期待 | O(log n) 期待 | O(log n) 期待 | ランダム優先度でヒープ性質も併用。 |

| Splay木 | O(log n) 償却 | O(log n) 償却 | O(log n) 償却 | アクセスパターンに自己適応。 |

| Skip List | O(log n) 期待 | O(log n) 期待 | O(log n) 期待 | リンクリストベースで並列化に有利。 |

実装言語ライブラリでの採用例：

• C++ STL `std::map`/`std::set` ：赤黒木
• Java `TreeMap`/`TreeSet` ：赤黒木
• Linux カーネルの完全公平スケジューラ（CFS）：赤黒木

4. ハッシュテーブルとの使い分け

順序保持が不要なら ハッシュテーブル（HashMap）が平均 O(1) でより高速です。範囲検索や順序走査が必要なら平衡2分探索木が適します。

5. 現代のデータベースとB木

DBMSのインデックスは2分木ではなくB木/B+木を使います。理由は「ディスクI/Oが計算コストを支配する」ためで、1ノードに数十〜数百のキーを格納することで木の高さを3〜4段に抑え、I/O回数を最小化します。同じ Θ(log n) でも対数の底が大きいため実質的なアクセス回数が桁違いに少なくなります。

実務的示唆：探索性能が問題になる場面では、まずワークロード（挿入順序の偏り、範囲検索の有無、並列度）を把握し、データ構造を選定すべきです。「とりあえずBST」は本問の最悪ケースを引き当てる可能性があります。