アルゴリズムクイックリファレンス 第2版

102

■

5

章 探索

メモリ制限（Restrictedmemory）

集まりが変化しない配列で、メモリを保全したいなら

二分探索

を使う。

動的メンバーシップ（Dynamicmembership）

集まりの要素が頻繁に変更されるなら、データ構造保守に伴うコストを

分散できるので、ハッシュに基いた探索と二分探索木を考える。

整列アクセス（Sortedaccess）

動的メンバーシップと集まりの要素を整列順に処理する能力とが必要な

ら二分探索木を使う。

前もって探索クエリを扱うためアルゴリズムがデータを構造化するのに必要とな

る、前処理を考慮しておくのを忘れないように。個別の質問の性能を向上させるこ

とだけでなく、動的なアクセスや複数の質問に対しても集まりの構造を保守するた

めの全体コストが最小になるような、適切な構造を選ぶ。

探索対象値を含む全体集合

U

が存在することを仮定する。集まり

C

の要素は、

U

から選ばれ、探索する目標要素

t

も、

U

の要素である。

t

がキー値と考えられる場合

には、

U

を取り得るキー値の集合、すなわち

k

∈

U

と考え、集まり

C

に含まれる要

素はより複雑なものと考える。

C

には、重複値の存在が許されており、（重複を許さ

ない）集合としては扱えない、とする。

集まりの任意の要素に添字でアクセスできるなら、集まりを配列

A

と呼び、

i

番目

の要素を表すのに表記法

A[i ]

を使う。慣例で、集まり

U

に存在しない要素を表すの

に、値

null

＊

1

を使う。この値は、探索で返すべき要素が、集まりの中になかった場

合に役立つ。 ...