データ構造：解説つき練習問題

1データ構造とは

データ構造は、特定の操作（項目を探す、追加する、削除する）が速くなるように、メモリ上のデータを整理する方法です。

すべてに速い構造はありません。構造を選ぶことは、どの操作を安くするかを選ぶことです。そのコストは、n を項目数としてビッグオーで書きます。

基本的な構成要素は、配列と連結リストの 2 つです。

配列は、項目を 1 つのメモリのかたまりに、順に並べて記憶します。コンピュータは i 番目の項目の位置を計算できるので、a[i] を読むのは O(1) です。先頭に挿入するには、すべての項目をずらす必要があります：O(n)。

連結リストは、各項目を、次のノードへのポインタをもつノードに記憶します。最後のポインタは null です。先頭（h）への挿入は、ポインタを 1 つ変えるだけです：O(1)。しかし、i 番目の項目に到達するには、i 個のポインタをたどる必要があります：O(n)。

双方向連結リストは、前のノードへのポインタももつので、両方向にたどれます。

2スタックとキュー

スタックは皿の山のようなものです：追加も削除も一番上でだけ行います。最後に入れた項目が最初に出ます：LIFO。

• push は項目を一番上に置き、pop は一番上の項目を取り除き、peek は取り除かずに一番上を読みます。いずれも O(1) です。
• 用途：エディタの元に戻す機能、プログラムのコールスタック、括弧の対応の確認、深さ優先探索。

キューはレジの行列のようなものです：後ろに並び、前から出ていきます。最初に入れた項目が最初に出ます：FIFO。

• enqueue は後ろに追加し、dequeue は前から取り除きます。どちらも O(1) です。
• 用途：印刷ジョブ、処理待ちのメッセージ、幅優先探索。

デック（両端キュー）は、両端での追加と削除を認めます。優先度つきキューは、常に最も優先度の高い項目を先に取り出します。通常はヒープとして作られます。

3木、ヒープ、ハッシュ表、グラフ

木には、一番上のノードである根が 1 つあります。他のすべてのノードには、親がちょうど 1 つあります。子をもたないノードは葉です。n 個のノードをもつ木には、n − 1 本の辺があります。

二分木では、すべてのノードが最大 2 つの子をもちます。二分探索木（BST）はさらに規則を加えます：左の部分木のキーはそのノードより小さく、右の部分木のキーはそのノードより大きい。

BST の探索は、1 本の経路を下っていくので、O(高さ) かかります。平衡木（AVL 木、赤黒木）は、高さを log₂ n に近く保ちます。整列した順にキーを挿入すると、高さ n の鎖状になります。

ヒープは、すべての親が子より小さい（最小ヒープ）、または大きい（最大ヒープ）二分木です。最小値または最大値は根にあり、挿入と削除は O(log n) です。

ハッシュ表は、キーと値の組を記憶します。ハッシュ関数がキーを添字に変換するので、挿入と検索は平均で O(1) です。同じ添字になる 2 つのキーは衝突であり、チェイン法（スロットごとのリスト）やオープンアドレス法（別のスロットを試す）で解決します。

グラフは、辺で結ばれた頂点をもち、辺には向きや重みがあることもあります。隣接行列（メモリ O(V²)）または隣接リスト（O(V + E)）で記憶します。

4ステップごとの方法

課題を述べて、どの構造が合うかを問う問題や、いくつかの操作の後で構造がどうなっているかを問う問題がよくあります。

1. 速くなければならない操作を見つけます：位置による参照、キーによる参照、最新の項目、最も古い項目、最小の項目、範囲のいずれか。
2. それを構造に対応させます：添字 → 配列、キー → ハッシュ表、最新 → スタック、最も古い → キュー、最小または最大 → ヒープ、整列順や範囲 → 平衡探索木。
3. 課題が必要とする他の操作のコストを、ビッグオーで確認します。
4. 追跡問題では、操作を 1 つずつ実行し、そのたびに状態を書き留めます。
5. 最終的な状態を、その構造の規則（LIFO、FIFO、BST の順序、ヒープの順序）に照らして確認します。

5例題

すべてのステップをたどりましょう。開く前に次のステップを予想してみましょう。

6よくある間違い

• LIFO と FIFO を混同する。スタックは最新の項目を、キューは最も古い項目を返します。
• 連結リストが添字による速いアクセスを与えると考える。先頭からたどらなければなりません。
• BST が常に O(log n) だと考える。そうなるのは平衡木だけで、整列順の挿入では O(n) になります。
• ハッシュ表の衝突を忘れる。O(1) は平均であり、最悪の場合ではありません。
• 走査の種類を混同する。前順：ノードが先。中順：ノードが中央。後順：ノードが最後。
• 大きな疎なグラフに隣接行列を使う。O(V²) のメモリを無駄にします。

7試験問題の例

• やさしい：用語と事実。LIFO と FIFO、ノード・根・葉とは何か、BST の規則、ハッシュ関数の働き。
• ふつう：概念の応用。課題に合う構造、push と pop や BST への挿入の結果、木の走査、線形探索法のハッシュ表、ビッグオーでのコスト。
• むずかしい：事例と分析。平衡木、配列によるヒープ、B 木、トライ、素集合データ構造（union-find）、ブルームフィルタ、LRU キャッシュのような設計。

添字 0 から始まる配列に格納されたヒープでは、添字 i の子は 2i + 1 と 2i + 2 にあり、その親は ⌊(i − 1) / 2⌋ にあります。