検索データ構造

コンピュータサイエンスにおいて、検索データ構造^{[要出典]とは、}データベースからの特定のレコードなど、一連の項目から特定の項目を効率的に取得できるデータ構造のことです。

最も単純で、最も一般的で、最も効率の悪い検索構造は、すべての項目を順序付けせずに並べたリストに過ぎません。線形検索方式でこのようなリスト内の目的の項目を見つけるには、最悪の場合でも平均的な場合でも、項目の数nに比例する操作の数が必要になります。便利な検索データ構造を使用すると、検索が高速になりますが、特定の種類のクエリに限定されます。さらに、このような構造を構築するコストは少なくともnに比例するため、複数のクエリを同じデータベース (またはクエリ間でほとんど変更されないデータベース) で実行する場合にのみ効果があります。

静的検索構造は、固定されたデータベース上の多数のクエリに応答するように設計されています。動的構造では、連続するクエリ間でアイテムの挿入、削除、または変更も可能になります。動的ケースでは、データベースの変更を考慮して検索構造を固定するコストも考慮する必要があります。

分類

最も単純な種類のクエリは、特定のフィールド (キー) が指定された値vに等しいレコードを見つけることです。その他の一般的な種類のクエリには、「最小 (または最大) のキー値を持つ項目を検索する」、「v を超えない最大のキー値を持つ項目を検索する」、「指定された境界v _minとv _{max の}間のキー値を持つすべての項目を検索する」などがあります。

特定のデータベースでは、キー値は多次元空間内の点である場合があります。たとえば、キーは地球上の地理的位置 (緯度と経度)である場合があります。その場合、一般的な種類のクエリは、「指定された点vに最も近いキーを持つレコードを検索する」、「キーがvから指定された距離にあるすべての項目を検索する」、または「空間の指定された領域R内のすべての項目を検索する」などです。

後者の一般的な特殊なケースは、「給与が 50,000 から 100,000 の間で、1995 年から 2007 年に雇用されたすべての従業員レコードを検索する」など、2 つ以上の単純なキーに対する同時範囲クエリです。

単一の順序付きキー

キー値が適度にコンパクトな間隔にまたがる場合は配列。
優先順位順に並べたリスト。線形検索を参照
キーソート配列。二分探索を参照
自己バランス二分探索木
ハッシュテーブル

最小の要素を見つける

ヒープ

漸近的最悪ケース分析

この表では、漸近表記O ( f ( n )) は「最悪の場合でも f ( n )の一定の倍数を超えない」ことを意味します。

注: 未ソート配列への挿入は、挿入する要素は配列の特定の位置に挿入する必要があるという想定から、 O ( n ) であると引用されることがあります。挿入するには、後続の要素をすべて 1 つずつシフトする必要があります。ただし、従来の配列では、配列は任意の未ソート要素を格納するために使用されるため、特定の要素の正確な位置は重要ではなく、挿入は配列サイズを 1 増やして要素を配列の末尾に格納することによって実行されます。これはO (1) 操作です。^[3]^[4]同様に、削除操作は、後続の要素をシフトする必要があるという想定から、 O ( n ) であると引用されることがあります。ただし、従来の未ソート配列では、順序は重要ではありません (要素は挿入時に暗黙的に順序付けされます)。そのため、削除する要素を配列の最後の要素と交換し、配列サイズを 1 減らすことで削除を実行できます。これはO (1) 操作です。^[5]

この表は、おおよその概要にすぎません。各データ構造には、異なるコストにつながる特殊な状況やバリエーションがあります。また、2 つ以上のデータ構造を組み合わせてコストを削減することもできます。

脚注

^ ab Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest (1990)。アルゴリズム入門。ペンシルベニア州立大学情報科学技術学部。ISBN 978-0-262-53091-0LIST-DELETEはO (1)時間で実行されますが、指定されたキーを持つ要素を削除する場合は、最初にLIST-SEARCHを呼び出す必要があるため、最悪の場合Θ(n)時間が必要になります。
^ ab Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest (1990)。アルゴリズム入門。ペンシルベニア州立大学情報科学技術学部。ISBN 978-0-262-53091-0バイナリヒープには、最大ヒープと最小ヒープの2種類があります。どちらの種類でも、ノード内の値はヒーププロパティを満たしています...最大ヒープ内の最大要素はルートに格納されます...最小ヒープ内の最小要素はルートにあります...操作HEAP-MAXIMUMは、ヒープ内の値A [1 ]を返すだけで、Θ(1)時間で最大ヒープ要素を返します。
^ Allen Sherrod (2007)。ゲーム開発者のためのデータ構造とアルゴリズム。Cengage Learning。ISBN 978-1-58450-663-8順序なし配列への項目の挿入は、新しい項目をリストの末尾に配置すること以外には何も依存しません。これにより、順序なし配列への挿入はO (1) になります。
^ Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest (1990)。アルゴリズム入門。ペンシルベニア州立大学情報科学技術学部。ISBN 978-0-262-53091-0。
^ 「アルゴリズム - ソートされていない配列の削除にかかる時間の複雑さ」。指定された値を持つ要素の検索は線形です。配列はソートされていないため、削除自体は定数時間で実行できます。まず、削除する要素を配列の末尾にスワップし、次に配列のサイズを 1 要素分減らします。

参照

[listdelete-1] Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest (1990)。アルゴリズム入門。ペンシルベニア州立大学情報科学技術学部。ISBN 978-0-262-53091-0LIST-DELETEはO (1)時間で実行されますが、指定されたキーを持つ要素を削除する場合は、最初にLIST-SEARCHを呼び出す必要があるため、最悪の場合Θ(n)時間が必要になります。

[heap-2] Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest (1990)。アルゴリズム入門。ペンシルベニア州立大学情報科学技術学部。ISBN 978-0-262-53091-0バイナリヒープには、最大ヒープと最小ヒープの2種類があります。どちらの種類でも、ノード内の値はヒーププロパティを満たしています...最大ヒープ内の最大要素はルートに格納されます...最小ヒープ内の最小要素はルートにあります...操作HEAP-MAXIMUMは、ヒープ内の値A [1 ]を返すだけで、Θ(1)時間で最大ヒープ要素を返します。

[games-3] Allen Sherrod (2007)。ゲーム開発者のためのデータ構造とアルゴリズム。Cengage Learning。ISBN 978-1-58450-663-8順序なし配列への項目の挿入は、新しい項目をリストの末尾に配置すること以外には何も依存しません。これにより、順序なし配列への挿入はO (1) になります。

[4] Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest (1990)。アルゴリズム入門。ペンシルベニア州立大学情報科学技術学部。ISBN 978-0-262-53091-0。

[5] 「アルゴリズム - ソートされていない配列の削除にかかる時間の複雑さ」。指定された値を持つ要素の検索は線形です。配列はソートされていないため、削除自体は定数時間で実行できます。まず、削除する要素を配列の末尾にスワップし、次に配列のサイズを 1 要素分減らします。