clrs-algorithms

CLRS データ構造とアルゴリズムのリファレンス

「Introduction to Algorithms」（CLRS）に基づく、データ構造とアルゴリズムの包括的なリファレンスです。このスキルでは、あらゆるプログラミング言語に翻訳できる疑似コードの例とともに、言語に依存しないガイダンスを提供します。

このスキルが有効になるタイミング

次の場合に、このスキルが自動的に有効になります。

• データ構造について質問する、または実装する必要がある場合
• 問題に適したデータ構造を選ぶ必要がある場合
• 時間計算量と空間計算量のトレードオフについて話し合う場合
• アルゴリズムの実装が必要な場合（ソート、検索、グラフアルゴリズム）
• 特定のデータ構造に言及する場合：B-tree、ヒープ、ハッシュテーブル、グラフなど

データ構造のクイックリファレンス

線形構造

データ構造	アクセス	検索	挿入	削除	用途
配列	O(1)	O(n)	O(n)	O(n)	サイズが既知で、インデックスアクセスが必要な場合
動的配列	O(1)	O(n)	O(1)*	O(n)	サイズが不明で、末尾への追加が頻繁な場合
連結リスト	O(n)	O(n)	O(1)	O(1)	挿入・削除が頻繁な場合
スタック	O(1)	O(n)	O(1)	O(1)	LIFO が必要な場合
キュー	O(1)	O(n)	O(1)	O(1)	FIFO が必要な場合
両端キュー	O(1)	O(n)	O(1)	O(1)	両端からアクセスする場合

木構造

データ構造	検索	挿入	削除	用途
二分探索木	O(log n)*	O(log n)*	O(log n)*	順序付きデータを扱い、検索が頻繁な場合
AVL 木	O(log n)	O(log n)	O(log n)	バランスが保証される必要がある場合
赤黒木	O(log n)	O(log n)	O(log n)	挿入・削除が頻繁な場合
B 木	O(log n)	O(log n)	O(log n)	ディスクベースのストレージ
トライ木	O(m)	O(m)	O(m)	文字列・プレフィックス操作
ヒープ	O(1)/O(n)	O(log n)	O(log n)	優先度付きキューが必要な場合
スプレー木	O(log n)*	O(log n)*	O(log n)*	自己調整型で、時間的局所性がある場合
トレープ	O(log n)*	O(log n)*	O(log n)*	ランダム化されたバランスや、分割・併合が必要な場合
区間木	O(log n)	O(log n)	O(log n)	区間の重なりを問い合わせる場合
順序統計木	O(log n)	O(log n)	O(log n)	順位・選択の問い合わせ
K-D 木	O(log n)*	O(log n)*	O(log n)*	多次元の空間データ

ハッシュベース

データ構造	検索	挿入	削除	用途
ハッシュテーブル	O(1)*	O(1)*	O(1)*	キーと値を高速に検索する場合
ハッシュセット	O(1)*	O(1)*	O(1)*	要素が一意に含まれるかを判定する場合
ブルームフィルター	O(k)	O(k)	N/A	確率的な要素の存在判定

グラフ

データ構造	空間	辺の追加	辺の問い合わせ	用途
隣接リスト	O(V+E)	O(1)	O(degree)	疎グラフ
隣接行列	O(V²)	O(1)	O(1)	密グラフ

グラフアルゴリズム

アルゴリズム	時間計算量	用途
ネットワークフロー	O(VE²)	最大フロー、二部マッチング、最小カット
強連結成分	O(V+E)	強連結成分の検出、2-SAT、依存関係の分析

文字列

構造	構築	検索	使用する場面
接尾辞配列	O(n log n)	O(m log n)	メモリ効率の高い文字列照合
接尾辞木	O(n)	O(m)	高速なパターン照合、LCS
文字列アルゴリズム	O(m)	O(n)	KMP、Rabin-Karp、Boyer-Moore、Aho-Corasick

高度なデータ構造

構造	使用する場面
スキップリスト	確率的な平衡リスト
素集合データ構造	Union-Find 操作
セグメント木	更新を伴う区間クエリ
フェンウィック木	更新を伴う累積和
フィボナッチヒープ	O(1) の decrease-key を用いた Dijkstra、Prim
二項ヒープ	マージ可能な優先度付きキュー
van Emde Boas 木	O(log log u) で操作できる整数キー

アルゴリズム

アルゴリズム	使用する場面
ソートアルゴリズム	QuickSort、MergeSort、HeapSort、RadixSort など

* = 償却計算量または平均計算量

選択ガイド

• どのデータ構造を使うべきですか？ - 使用例に基づく選択ガイド
• 計算量早見表 - Big-O のクイックリファレンス

このリファレンスの使い方

1. 構造を選ぶ：選択ガイドから始めます
2. 構造を学ぶ：例を含む詳細なドキュメントを読みます
3. 素早く確認する：一覧性の高いリファレンスとして上の表を使います
4. 実装する：疑似コードに従い、使用する言語に合わせて調整します

言語への翻訳に関する注意

このリファレンスの疑似コードでは、次の規則を使用しています：

• 型定義には class
• メソッド／関数には function
• オブジェクトのメソッド呼び出しには ->
• コメントには //
• 型ヒントは name: Type の形式

使用する言語に合わせて翻訳してください：

• PHP：class、function、->、//、DocBlock または PHP 8+ の型ヒント
• JavaScript/TypeScript：class、function／アロー関数、.、//、TypeScript の型
• Python：class、def、.、#、型ヒント
• Java/C#：new とジェネリクスを用いて直接対応させます

---

「Introduction to Algorithms」（Cormen、Leiserson、Rivest、Stein 著、CLRS）、MIT Press の概念に基づいています。