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

■

101

5

章

 

探索

複数の要素からなる集まり

C

に対して、

2

つの基本的な問いがある。

存在

C

の中に探している要素

t

があるか。集まり

C

に対して、その集まりの中

に、要素

t

が含まれているかを調べたいとする。このような質問の答えが

true

になるのは、探索している

t

に合致する要素が集まりの中にあるとき

で、答えが

false

になるのは、合致する要素がないときである。

関連照合

目標のキー値

k

の関連情報を集まり

C

の中から返す。通常、キーには、

「値」と呼ばれる複合構造が関連している。照合とは、その値を取り出し

たり置き換えたりすることだ。

本章のアルゴリズムでは、このような探索クエリをより効率的に処理するために、

データを構造化する方式について述べる。例えば、

4

章で述べた整列アルゴリズム

を用いて、集まり

C

を整列する。後で述べるように、整列で質問効率は改善される

のだが、集まりを整列した状態に保守することは、特に頻繁に要素の追加削除が

あ

る場合には、手間がかかる。

結局のところ、性能は、アルゴリズムがクエリ処理にどれだけの要素を検査する

かで決まる。次のようなガイドラインを用いて、最良のアルゴリズムを選ぶべきだ。

少数の集まり（Smallcollections）

逐次探索

は最も単純な実装で、多くのプログラミング言語で基本要素と

して実装される。集まりがイテレータを介して逐次アクセスしかできな

いときには、

逐次探索

を使う。