探索木

めも。

図にすると、例えばこんな形に図示できるデータ構造(下記は、二分探索木)を作成。そのデータ構造を使ってデータの検索を平均してより高速に実行するのが目的。

参考サイト(2分探索木(アルゴリズムとデータ構造) – ++C++

2分探索木データ的には、『2,6,10,11,13,21』の6個となる。
仮に、総当たりで調べた場合は上記データがどのように格納されているかにもよるが、最大6回の比較が必要。二分探索木の場合、上記構造の場合は最大3回の比較が必要。(※最後に残った1個が目的の値かどうかまで調べた場合。)

2分探索木2

探索木を用いたアルゴリズムには、木構造をより最適な形にする為の派生アルゴリズムが多数存在する。
木構造 (データ構造)

そもそもプログラムは、アルゴリズムとデータ構造の2本柱で動いている。
探索アルゴリズムも、データ構造としての探索木を用いない探索アルゴリズムもありその方法論は多種多様。これが絶対という答えは存在しない。

なので、最適な方法を選択できるようにするには、まずいろいろなデータ探索方法について知る必要がある。

Tさんのブログに難しい書き込みを発見..

凸包を求める

概念の解説が判り易かったので、めも。

凸包を求める

 
『凸包』がなにかというと、漢字の凸の字が表わす通りの形のように『でっぱった部分を持つ形状』で囲まれた点の集合。
『凸包を求める』というのは、点の集合から『凸包』を割り出す計算のこと。

実際に凸の字の形に点の集合があったら、左右のくぼみが除かれた台形の形に集約されるので、凸という形は微妙に感じるんですが..w