1.3データ構造

FEでも学ぶ基本的なデータ構造ですが、APレベルでは「なぜその計算量になるのか」を構造から説明できることが求められます。木がなぜ平衡を保つ必要があるのか、ハッシュ衝突がなぜ性能を悪化させるのか——構造と計算量の因果関係を理解することが、次節のアルゴリズム設計の土台になります。

1.3.1配列・リスト・スタック・キュー

• 配列＝連続メモリに要素を並べ、添字でO(1)アクセスできる一方、途中挿入・削除は要素をずらすためO(n)。リスト（連結リスト）は途中挿入・削除が参照の付け替えだけでO(1)だが、n番目要素へのアクセスは先頭からたどりO(n)。
• スタック（LIFO）・キュー（FIFO）はいずれも push/pop・enqueue/dequeueがO(1)の特殊化されたリスト。用途で選ぶ＝コールスタックや括弧対応チェックはスタック、幅優先探索やジョブの順番待ちはキュー。

1.3.2木構造（2分探索木・平衡木・ヒープ）

• 2分探索木（BST）＝各ノードについて「左部分木の全要素 < 自身 < 右部分木の全要素」を満たす2分木。検索・挿入・削除は木の高さに比例し、平均O(log n)だが、挿入順が偏ると一直線の木（偏った木）になり最悪O(n)まで悪化する。
• 平衡木（AVL木・赤黒木等）＝挿入・削除のたびに木の高さの偏りを自動的に是正し、常にO(log n)を保証する2分探索木の改良版。最悪ケースでも性能が悪化しないことが実務での採用理由。
• ヒープ＝親が子より必ず大きい（または小さい）というヒープ条件を満たす完全2分木。最大値（または最小値）の取得が常にO(1)（根を見るだけ）で、挿入・削除は木の高さに比例しO(log n)。優先度付きキューの実装に使われる。

1.3.3ハッシュとグラフ

• ハッシュ＝キーをハッシュ関数で固定長の値（ハッシュ値）に変換し、それを配列の添字として使うことで平均O(1)での検索・挿入を実現する構造。異なるキーが同じハッシュ値になる衝突が発生すると、チェイン法（同じ位置に連結リストで複数格納）等で対処するが、衝突が多発すると性能はO(n)に近づく。
• グラフ＝頂点（ノード）と辺（エッジ）で要素間の関係を表す構造。SNSの友人関係、道路網、依存関係の管理など多対多の関係を表現するのに適し、木構造は「閉路がなく親が1つ」というグラフの特殊な形。

あるECサイトの商品検索機能で、100万件の商品を商品コード（キー）から即座に取得したいという要件があるとします。2分探索木を使う場合、平均でも log2(1,000,000) ≒ 20 回の比較が必要ですが、ハッシュテーブルを使えば衝突が少ない限り平均1回のアクセスで目的の商品にたどり着けます。ただしハッシュ関数の設計が悪く、多くの商品コードが同じハッシュ値に集中してしまうと、その場所に長い連結リストができてO(n)に近い性能まで悪化するため、ハッシュ関数の分散性が重要になります。一方、この商品の「関連商品」「同カテゴリの商品」といった多対多の関係を管理したい場合はグラフが適しています——商品を頂点、関連性を辺として表現すれば、「ある商品から2ステップ以内でたどれる関連商品」のような問い合わせを幅優先探索（キューを使う）で効率的に解けます。さらに、在庫が残りわずかな人気商品を常に最優先で処理したい（在庫確認バッチの優先度付け等）という要件にはヒープが適しており、根に最優先の商品が常に来るため、優先度付きキューとしてO(log n)で挿入しつつO(1)で最優先品を取得できます。このように、同じ「複数のデータを扱う」課題でも、アクセスパターン（キーからの直接検索か、関係性のたどりか、優先度順の取り出しか）によって最適なデータ構造は大きく異なります。

1.3.4この節のまとめ

• 配列＝アクセス速いが挿入遅い、リスト＝挿入速いがアクセス遅いというトレードオフを理解する
• BSTは平均O(log n)だが偏ると最悪O(n)、平衡木は常にO(log n)を保証、ヒープは最大/最小取得がO(1)
• ハッシュは平均O(1)だが衝突が増えると劣化、グラフは多対多の関係を表現する