基本的なデータ構造
基本的なデータ構造とは、データを格納しアクセスするための組織化された方法であり、配列、連結リスト、ハッシュテーブル、ツリー、ヒープなどが含まれます。これらは、その上に構築される操作の効率性を決定します。
Definition
データ構造とは、その抽象データ型によって定義される操作を効率的に実行できるように、データを整理し格納する方法です。基本的なデータ構造とは、他のほとんどのデータ構造が構築される汎用的な構造の小さなセットを指します。
Scope
この分野では、抽象データ型（リスト、辞書、優先度キュー、セット）と、それらを実装する具体的な構造、および最悪ケース分析と償却分析におけるそれらのコア操作（挿入、削除、検索、更新）のコストを扱います。構造の選択がアルゴリズムの性能をどのように形成するか、またこれらの構造に依存する設計パラダイムやグラフおよび文字列アルゴリズムとの関連性について論じます。他のサブフィールドで扱われるデータベースおよびファイルシステムストレージ構造は除外します。
Sub-topics
Core questions
- アプリケーションにはどの抽象データ型が必要で、どの具体的な構造がそれを最適に実装しますか？
- 特定の構造における各操作の最悪ケースおよび償却コストはどのくらいですか？
- 構造はメモリと時間のトレードオフ、または読み取り速度と更新速度のトレードオフをどのように行いますか？
- 不変条件（ソート済み、平衡、ヒーププロパティ）を維持することが操作コストをどのように制約しますか？
- 漸近的に高速だがより複雑な構造よりも、単純な構造が好ましいのはどのような場合ですか？
Key concepts
- 抽象データ型
- 配列と連結リスト
- スタックとキュー
- ハッシュテーブル
- 二分探索木
- 平衡木
- ヒープと優先度キュー
- 償却分析
- 時間空間トレードオフ
Key theories
- 抽象データ型と実装
- 抽象データ型は、表現に依存しない操作とそのセマンティクスを規定します。複数の具体的なデータ構造が、異なる性能プロファイルで同じADTを実装でき、設計者は正しさとコストについて個別に推論できます。
- 償却分析
- 一部の構造（動的配列、スプレー木）は、時折高価な操作を伴いますが、一連の操作全体では平均して安価な操作となります。償却分析（集計法、会計法、ポテンシャル法）は、この平均コストを厳密に制限します。
Clinical relevance
基本的なデータ構造は、実質的にすべてのソフトウェアの構成要素です。ハッシュテーブルは辞書やデータベースインデックスの基盤となり、平衡木やB-木はファイルシステムやデータベースを整理し、優先度キューはスケジューラやイベントシミュレーションを駆動します。適切な構造の選択は、しばしばシステムの拡張性を決定します。
History
基礎的なデータ構造は、1968年に始まったクヌースの『The Art of Computer Programming』で体系化されました。自己平衡木（AVL木、1962年；赤黒木、B-木、1970年代）や、フィボナッチヒープ、スプレー木（1980年代、主にタージャンとその共同研究者による）などの高度な構造がこの分野を拡張し、償却分析はそれらの性能を厳密に説明しました。
Key figures
- Donald Knuth
- Robert Sedgewick
- Robert Tarjan
- Rudolf Bayer
Related topics
Seminal works
- knuth1997vol1
- cormen2009
- sedgewick2011
Frequently asked questions
- ハッシュテーブルと平衡探索木のどちらを選択すればよいですか？
- ハッシュテーブルは期待されるO(1)のルックアップと挿入を提供しますが順序は保持しません。一方、平衡探索木はO(log n)の操作を提供し、キーをソートされた状態に保つため、範囲クエリや順序付きトラバーサルをサポートします。純粋なキーのルックアップにはハッシュを選択し、順序付けや範囲操作が重要な場合は木を選択します。
- データ構造における償却コストとは何を意味しますか？
- 償却コストとは、最悪ケースの一連の操作における、操作あたりの平均コストです。例えば、動的配列はサイズ変更のために時折O(n)のコストを支払いますが、サイズ変更が安価な追加操作に比べて稀であるため、追加操作あたりの平均コストはO(1)となります。